Files
krahets 81e6fc70d7 deploy
2026-11-04 05:26:02 +08:00

2579 lines
214 KiB
HTML
Raw Permalink Blame History

This file contains invisible Unicode characters
This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!DOCTYPE html>
<html class="no-js" lang="ru">
<head>
<meta charset="utf-8"/>
<meta content="width=device-width,initial-scale=1" name="viewport"/>
<meta content="Учебник по структурам данных и алгоритмам с анимированными иллюстрациями и готовым к запуску кодом" name="description"/>
<meta content="krahets" name="author"/>
<link href="https://www.hello-algo.com/ru/chapter_divide_and_conquer/hanota_problem/" rel="canonical"/>
<link href="../build_binary_tree_problem/" rel="prev"/>
<link href="../summary/" rel="next"/>
<link href="/chapter_divide_and_conquer/hanota_problem/" hreflang="zh" rel="alternate"/>
<link href="/zh-hant/chapter_divide_and_conquer/hanota_problem/" hreflang="zh-Hant" rel="alternate"/>
<link href="/en/chapter_divide_and_conquer/hanota_problem/" hreflang="en" rel="alternate"/>
<link href="/ja/chapter_divide_and_conquer/hanota_problem/" hreflang="ja" rel="alternate"/>
<link href="/ru/chapter_divide_and_conquer/hanota_problem/" hreflang="ru" rel="alternate"/>
<link href="/ko/chapter_divide_and_conquer/hanota_problem/" hreflang="ko" rel="alternate"/>
<link href="../../assets/images/favicon.png" rel="icon"/>
<meta content="zensical-0.0.51" name="generator"/>
<title>12.4 Задача о Ханойской башне - Hello Algo</title>
<link href="../../assets/stylesheets/modern/main.62c9b9cc.min.css" rel="stylesheet"/>
<link href="../../assets/stylesheets/modern/palette.dfe2e883.min.css" rel="stylesheet"/>
<style>:root{--md-text-font:"PT Sans";--md-code-font:"JetBrains Mono"}</style>
<link href="../../stylesheets/extra.css" rel="stylesheet"/>
<link href="../../stylesheets/animation_player.css" rel="stylesheet"/>
<script>__md_scope=new URL("../..",location),__md_scope.pathname.endsWith("/")||(__md_scope=new URL(__md_scope.pathname+"/",location)),__md_hash=e=>[...e].reduce(((e,t)=>(e<<5)-e+t.charCodeAt(0)),0),__md_get=(e,t=localStorage,_=__md_scope)=>JSON.parse(t.getItem(_.pathname+"."+e)),__md_set=(e,t,_=localStorage,a=__md_scope)=>{try{_.setItem(a.pathname+"."+e,JSON.stringify(t))}catch(e){}},document.documentElement.setAttribute("data-platform",navigator.platform)</script>
<script data-ha-shared-palette="1">
/* Share only the palette across language roots; other preferences stay scoped. */
(() => {
const get = __md_get;
const set = __md_set;
const shared = new URL("/", location);
__md_get = (key, storage = localStorage, scope = __md_scope) => {
if (key !== "__palette") return get(key, storage, scope);
let value = get(key, storage, shared);
// Adopt the current language's old preference only if none is shared yet.
if (value === null && scope.pathname !== shared.pathname) {
value = get(key, storage, scope);
if (value !== null) set(key, value, storage, shared);
}
return value;
};
__md_set = (key, value, storage = localStorage, scope = __md_scope) =>
set(key, value, storage, key === "__palette" ? shared : scope);
})();
</script>
<link href="/assets/figure-svg/css/5632068fdac847e7b03f598e.css" rel="stylesheet"/><link href="/assets/figure-svg/css/c053e5d2507ba0f764c3d1cf.css" rel="stylesheet"/></head>
<body data-md-color-accent="teal" data-md-color-primary="white" data-md-color-scheme="default" dir="ltr">
<input autocomplete="off" class="md-toggle" data-md-toggle="drawer" id="__drawer" type="checkbox"/>
<input autocomplete="off" class="md-toggle" data-md-toggle="search" id="__search" type="checkbox"/>
<label aria-label="Навигация" class="md-overlay" for="__drawer"></label>
<div data-md-component="skip">
<a class="md-skip" href="#124">
Перейти к содержанию
</a>
</div>
<div data-md-component="announce">
<aside class="md-banner">
<div class="md-banner__inner md-grid md-typeset">
<div class="banner-svg">
<svg viewbox="0 0 512 512" xmlns="http://www.w3.org/2000/svg"><!--!Font Awesome Free 6.5.1 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free Copyright 2024 Fonticons, Inc.-->
<path d="M480 32c0-12.9-7.8-24.6-19.8-29.6s-25.7-2.2-34.9 6.9L381.7 53c-48 48-113.1 75-181 75H192 160 64c-35.3 0-64 28.7-64 64v96c0 35.3 28.7 64 64 64l0 128c0 17.7 14.3 32 32 32h64c17.7 0 32-14.3 32-32V352l8.7 0c67.9 0 133 27 181 75l43.6 43.6c9.2 9.2 22.9 11.9 34.9 6.9s19.8-16.6 19.8-29.6V300.4c18.6-8.8 32-32.5 32-60.4s-13.4-51.6-32-60.4V32zm-64 76.7V240 371.3C357.2 317.8 280.5 288 200.7 288H192V192h8.7c79.8 0 156.5-29.8 215.3-83.3z"></path>
</svg>
<span>Приглашаем вас участвовать в развитии русской версии! Подробнее <a href="/ru/chapter_appendix/contribution/">здесь</a>.</span>
</div>
</div>
</aside>
</div>
<header class="md-header md-header--shadow" data-md-component="header">
<nav aria-label="Верхний колонтитул" class="md-header__inner md-grid">
<a aria-label="Hello Algo" class="md-header__button md-logo" data-md-component="logo" href="../.." title="Hello Algo">
<img alt="Hello Algo" src="../../assets/images/logo.svg"/>
</a>
<label aria-label="Навигация" class="md-header__button md-icon" for="__drawer">
<svg class="lucide lucide-menu" fill="none" stroke="currentColor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M4 5h16M4 12h16M4 19h16"></path></svg>
</label>
<div class="md-header__title" data-md-component="header-title">
<div class="md-header__ellipsis">
<div class="md-header__topic">
<span class="md-ellipsis">
Hello Algo
</span>
</div>
<div class="md-header__topic" data-md-component="header-topic">
<span class="md-ellipsis">
12.4   Задача о Ханойской башне
</span>
</div>
</div>
</div>
<form class="md-header__option" data-md-component="palette">
<input aria-label="Темная тема" class="md-option" data-md-color-accent="teal" data-md-color-media="none" data-md-color-primary="white" data-md-color-scheme="default" id="__palette_0" name="__palette" type="radio"/>
<label class="md-header__button md-icon" for="__palette_1" hidden="" title="Темная тема">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M7.5 2c-1.79 1.15-3 3.18-3 5.5s1.21 4.35 3.03 5.5C4.46 13 2 10.54 2 7.5A5.5 5.5 0 0 1 7.5 2m11.57 1.5 1.43 1.43L4.93 20.5 3.5 19.07zm-6.18 2.43L11.41 5 9.97 6l.42-1.7L9 3.24l1.75-.12.58-1.65L12 3.1l1.73.03-1.35 1.13zm-3.3 3.61-1.16-.73-1.12.78.34-1.32-1.09-.83 1.36-.09.45-1.29.51 1.27 1.36.03-1.05.87zM19 13.5a5.5 5.5 0 0 1-5.5 5.5c-1.22 0-2.35-.4-3.26-1.07l7.69-7.69c.67.91 1.07 2.04 1.07 3.26m-4.4 6.58 2.77-1.15-.24 3.35zm4.33-2.7 1.15-2.77 2.2 2.54zm1.15-4.96-1.14-2.78 3.34.24zM9.63 18.93l2.77 1.15-2.53 2.19z"></path></svg>
</label>
<input aria-label="Светлая тема" class="md-option" data-md-color-accent="teal" data-md-color-media="none" data-md-color-primary="black" data-md-color-scheme="slate" id="__palette_1" name="__palette" type="radio"/>
<label class="md-header__button md-icon" for="__palette_0" hidden="" title="Светлая тема">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M7.5 2c-1.79 1.15-3 3.18-3 5.5s1.21 4.35 3.03 5.5C4.46 13 2 10.54 2 7.5A5.5 5.5 0 0 1 7.5 2m11.57 1.5 1.43 1.43L4.93 20.5 3.5 19.07zm-6.18 2.43L11.41 5 9.97 6l.42-1.7L9 3.24l1.75-.12.58-1.65L12 3.1l1.73.03-1.35 1.13zm-3.3 3.61-1.16-.73-1.12.78.34-1.32-1.09-.83 1.36-.09.45-1.29.51 1.27 1.36.03-1.05.87zM19 13.5a5.5 5.5 0 0 1-5.5 5.5c-1.22 0-2.35-.4-3.26-1.07l7.69-7.69c.67.91 1.07 2.04 1.07 3.26m-4.4 6.58 2.77-1.15-.24 3.35zm4.33-2.7 1.15-2.77 2.2 2.54zm1.15-4.96-1.14-2.78 3.34.24zM9.63 18.93l2.77 1.15-2.53 2.19z"></path></svg>
</label>
</form>
<script>var palette=__md_get("__palette");if(palette&&palette.color){if("(prefers-color-scheme)"===palette.color.media){var media=matchMedia("(prefers-color-scheme: light)"),input=document.querySelector(media.matches?"[data-md-color-media='(prefers-color-scheme: light)']":"[data-md-color-media='(prefers-color-scheme: dark)']");palette.color.media=input.getAttribute("data-md-color-media"),palette.color.scheme=input.getAttribute("data-md-color-scheme"),palette.color.primary=input.getAttribute("data-md-color-primary"),palette.color.accent=input.getAttribute("data-md-color-accent")}for(var[key,value]of Object.entries(palette.color))document.body.setAttribute("data-md-color-"+key,value)}</script>
<div class="md-header__option">
<div class="md-select">
<button aria-label="Выберите язык" class="md-header__button md-icon">
<svg class="lucide lucide-languages" fill="none" stroke="currentColor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m5 8 6 6M4 14l6-6 2-3M2 5h12M7 2h1M22 22l-5-10-5 10M14 18h6"></path></svg>
</button>
<div class="md-select__inner">
<ul class="md-select__list">
<li class="md-select__item">
<a class="md-select__link" href="/chapter_divide_and_conquer/hanota_problem/" hreflang="zh">
简体中文
</a>
</li>
<li class="md-select__item">
<a class="md-select__link" href="/zh-hant/chapter_divide_and_conquer/hanota_problem/" hreflang="zh-Hant">
繁體中文
</a>
</li>
<li class="md-select__item">
<a class="md-select__link" href="/en/chapter_divide_and_conquer/hanota_problem/" hreflang="en">
English
</a>
</li>
<li class="md-select__item">
<a class="md-select__link" href="/ja/chapter_divide_and_conquer/hanota_problem/" hreflang="ja">
日本語
</a>
</li>
<li class="md-select__item">
<a class="md-select__link" href="/ru/chapter_divide_and_conquer/hanota_problem/" hreflang="ru">
Русский
</a>
</li>
<li class="md-select__item">
<a class="md-select__link" href="/ko/chapter_divide_and_conquer/hanota_problem/" hreflang="ko">
한국어
</a>
</li>
</ul>
</div>
</div>
</div>
<label aria-label="Поиск" class="md-header__button md-icon" for="__search">
<svg class="lucide lucide-search" fill="none" stroke="currentColor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m21 21-4.34-4.34"></path><circle cx="11" cy="11" r="8"></circle></svg>
</label>
<div aria-label="Поиск" class="md-search" data-md-component="search" role="dialog">
<button class="md-search__button" type="button">
Поиск
</button>
</div>
<div class="md-header__source">
<a class="md-source" data-md-component="source" href="https://github.com/krahets/hello-algo" title="Перейти к репозиторию">
<div class="md-source__icon md-icon">
<svg viewbox="0 0 512 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M173.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6m-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3m44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9M252.8 8C114.1 8 8 113.3 8 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C436.2 457.8 504 362.9 504 252 504 113.3 391.5 8 252.8 8M105.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1m-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7m32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1m-11.4-14.7c-1.6 1-1.6 3.6 0 5.9s4.3 3.3 5.6 2.3c1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2" fill="currentColor"></path></svg>
</div>
<div class="md-source__repository">
krahets/hello-algo
</div>
</a>
</div>
</nav>
</header>
<div class="md-container" data-md-component="container">
<main class="md-main" data-md-component="main">
<div class="md-main__inner md-grid">
<div class="md-sidebar md-sidebar--primary" data-md-component="sidebar" data-md-type="navigation">
<div class="md-sidebar__scrollwrap">
<div class="md-sidebar__inner">
<nav aria-label="Навигация" class="md-nav md-nav--primary" data-md-level="0">
<label class="md-nav__title" for="__drawer">
<a aria-label="Hello Algo" class="md-nav__button md-logo" data-md-component="logo" href="../.." title="Hello Algo">
<img alt="Hello Algo" src="../../assets/images/logo.svg"/>
</a>
Hello Algo
</label>
<div class="md-nav__source">
<a class="md-source" data-md-component="source" href="https://github.com/krahets/hello-algo" title="Перейти к репозиторию">
<div class="md-source__icon md-icon">
<svg viewbox="0 0 512 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M173.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6m-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3m44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9M252.8 8C114.1 8 8 113.3 8 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C436.2 457.8 504 362.9 504 252 504 113.3 391.5 8 252.8 8M105.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1m-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7m32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1m-11.4-14.7c-1.6 1-1.6 3.6 0 5.9s4.3 3.3 5.6 2.3c1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2" fill="currentColor"></path></svg>
</div>
<div class="md-source__repository">
krahets/hello-algo
</div>
</a>
</div>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_1" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_hello_algo/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m13.13 22.19-1.63-3.83c1.57-.58 3.04-1.36 4.4-2.27zM5.64 12.5l-3.83-1.63 6.1-2.77C7 9.46 6.22 10.93 5.64 12.5M19.22 4c.28 0 .53 0 .74.05.17 1.39-.02 4.25-3.3 7.53-1.7 1.71-3.73 3.02-6.01 3.89l-2.15-2.1c.92-2.31 2.23-4.34 3.92-6.03C15.18 4.58 17.64 4 19.22 4m0-2c-1.98 0-4.98.69-8.22 3.93-2.19 2.19-3.5 4.6-4.35 6.71-.28.75-.09 1.57.46 2.13l2.13 2.12c.38.38.89.61 1.42.61.23 0 .47-.06.7-.15A19.1 19.1 0 0 0 18.07 13c5.66-5.66 3.54-10.61 3.54-10.61S20.7 2 19.22 2m-4.68 7.46c-.78-.78-.78-2.05 0-2.83s2.05-.78 2.83 0c.77.78.78 2.05 0 2.83s-2.05.78-2.83 0m-5.66 7.07-1.41-1.41zM6.24 22l3.64-3.64c-.34-.09-.67-.24-.97-.45L4.83 22zM2 22h1.41l4.77-4.76-1.42-1.41L2 20.59zm0-2.83 4.09-4.08c-.21-.3-.36-.62-.45-.97L2 17.76z"></path></svg>
<span class="md-ellipsis">
Перед началом
</span>
</a>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_1_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_1">
<span class="md-nav__icon md-icon"></span>
Перед началом
</label>
<ul class="md-nav__list" data-md-scrollfix="">
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_2" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_preface/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M21 4H3a2 2 0 0 0-2 2v13a2 2 0 0 0 2 2h18a2 2 0 0 0 2-2V6a2 2 0 0 0-2-2M3 19V6h8v13zm18 0h-8V6h8zm-7-9.5h6V11h-6zm0 2.5h6v1.5h-6zm0 2.5h6V16h-6z"></path></svg>
<span class="md-ellipsis">
Глава 0. Предисловие
</span>
</a>
<label class="md-nav__link" for="__nav_2" id="__nav_2_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_2_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_2">
<span class="md-nav__icon md-icon"></span>
Глава 0. Предисловие
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_preface/about_the_book/">
<span class="md-ellipsis">
0.1 Об этой книге
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_preface/suggestions/">
<span class="md-ellipsis">
0.2 Как пользоваться этой книгой
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_preface/summary/">
<span class="md-ellipsis">
0.3 Резюме
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_3" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_introduction/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M19 3H5c-1.1 0-2 .9-2 2v14c0 1.1.9 2 2 2h14c1.1 0 2-.9 2-2V5c0-1.1-.9-2-2-2m0 16H5V5h14zM6.2 7.7h5v1.5h-5zm6.8 8.1h5v1.5h-5zm0-2.6h5v1.5h-5zM8 18h1.5v-2h2v-1.5h-2v-2H8v2H6V16h2zm6.1-7.1 1.4-1.4 1.4 1.4 1.1-1-1.4-1.4L18 7.1 16.9 6l-1.4 1.4L14.1 6 13 7.1l1.4 1.4L13 9.9z"></path></svg>
<span class="md-ellipsis">
Глава 1. Введение в алгоритмы
</span>
</a>
<label class="md-nav__link" for="__nav_3" id="__nav_3_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_3_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_3">
<span class="md-nav__icon md-icon"></span>
Глава 1. Введение в алгоритмы
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_introduction/algorithms_are_everywhere/">
<span class="md-ellipsis">
1.1 Алгоритмы повсюду
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_introduction/what_is_dsa/">
<span class="md-ellipsis">
1.2 Что такое алгоритм
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_introduction/summary/">
<span class="md-ellipsis">
1.3 Резюме
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_4" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_computational_complexity/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M6 2h12v6l-4 4 4 4v6H6v-6l4-4-4-4zm10 14.5-4-4-4 4V20h8zm-4-5 4-4V4H8v3.5zM10 6h4v.75l-2 2-2-2z"></path></svg>
<span class="md-ellipsis">
Глава 2. Анализ сложности
</span>
</a>
<label class="md-nav__link" for="__nav_4" id="__nav_4_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_4_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_4">
<span class="md-nav__icon md-icon"></span>
Глава 2. Анализ сложности
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_computational_complexity/performance_evaluation/">
<span class="md-ellipsis">
2.1 Оценка эффективности алгоритмов
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_computational_complexity/iteration_and_recursion/">
<span class="md-ellipsis">
2.2 Итерация и рекурсия
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_computational_complexity/time_complexity/">
<span class="md-ellipsis">
2.3 Временная сложность
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_computational_complexity/space_complexity/">
<span class="md-ellipsis">
2.4 Пространственная сложность
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_computational_complexity/summary/">
<span class="md-ellipsis">
2.5 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_computational_complexity/exercises/">
<span class="md-ellipsis">
2.6 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_5" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_data_structure/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M11 13.5v8H3v-8zm-2 2H5v4h4zM12 2l5.5 9h-11zm0 3.86L10.08 9h3.84zM17.5 13c2.5 0 4.5 2 4.5 4.5S20 22 17.5 22 13 20 13 17.5s2-4.5 4.5-4.5m0 2a2.5 2.5 0 0 0-2.5 2.5 2.5 2.5 0 0 0 2.5 2.5 2.5 2.5 0 0 0 2.5-2.5 2.5 2.5 0 0 0-2.5-2.5"></path></svg>
<span class="md-ellipsis">
Глава 3. Структуры данных
</span>
</a>
<label class="md-nav__link" for="__nav_5" id="__nav_5_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_5_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_5">
<span class="md-nav__icon md-icon"></span>
Глава 3. Структуры данных
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_data_structure/classification_of_data_structure/">
<span class="md-ellipsis">
3.1 Классификация структур данных
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_data_structure/basic_data_types/">
<span class="md-ellipsis">
3.2 Базовые типы данных
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_data_structure/number_encoding/">
<span class="md-ellipsis">
3.3 Кодирование чисел *
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_data_structure/character_encoding/">
<span class="md-ellipsis">
3.4 Кодирование символов *
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_data_structure/summary/">
<span class="md-ellipsis">
3.5 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_data_structure/exercises/">
<span class="md-ellipsis">
3.6 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_6" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M3 5v14h17V5zm4 2v2H5V7zm-2 6v-2h2v2zm0 2h2v2H5zm13 2H9v-2h9zm0-4H9v-2h9zm0-4H9V7h9z"></path></svg>
<span class="md-ellipsis">
Глава 4. Массивы и списки
</span>
</a>
<label class="md-nav__link" for="__nav_6" id="__nav_6_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_6_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_6">
<span class="md-nav__icon md-icon"></span>
Глава 4. Массивы и списки
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/array/">
<span class="md-ellipsis">
4.1 Массив
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/linked_list/">
<span class="md-ellipsis">
4.2 Связный список
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/list/">
<span class="md-ellipsis">
4.3 Список
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/ram_and_cache/">
<span class="md-ellipsis">
4.4 Оперативная память и кэш *
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/summary/">
<span class="md-ellipsis">
4.5 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/exercises/">
<span class="md-ellipsis">
4.6 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_7" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_stack_and_queue/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M17.36 20.2v-5.38h1.79V22H3v-7.18h1.8v5.38zM6.77 14.32l.37-1.76 8.79 1.85-.37 1.76zm1.16-4.21.76-1.61 8.14 3.78-.76 1.62zm2.26-3.99 1.15-1.38 6.9 5.76-1.15 1.37zm4.45-4.25L20 9.08l-1.44 1.07-5.36-7.21zM6.59 18.41v-1.8h8.98v1.8z"></path></svg>
<span class="md-ellipsis">
Глава 5. Стек и очередь
</span>
</a>
<label class="md-nav__link" for="__nav_7" id="__nav_7_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_7_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_7">
<span class="md-nav__icon md-icon"></span>
Глава 5. Стек и очередь
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_stack_and_queue/stack/">
<span class="md-ellipsis">
5.1 Стек
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_stack_and_queue/queue/">
<span class="md-ellipsis">
5.2 Очередь
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_stack_and_queue/deque/">
<span class="md-ellipsis">
5.3 Двусторонняя очередь
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_stack_and_queue/summary/">
<span class="md-ellipsis">
5.4 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_stack_and_queue/exercises/">
<span class="md-ellipsis">
5.5 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_8" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_hashing/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M19.3 17.89c1.32-2.1.7-4.89-1.41-6.21a4.52 4.52 0 0 0-6.21 1.41C10.36 15.2 11 18 13.09 19.3c1.47.92 3.33.92 4.8 0L21 22.39 22.39 21zm-2-.62c-.98.98-2.56.97-3.54 0-.97-.98-.97-2.56.01-3.54.97-.97 2.55-.97 3.53 0 .96.99.95 2.57-.03 3.54zM19 4H5a2 2 0 0 0-2 2v12a2 2 0 0 0 2 2h5.81a6.3 6.3 0 0 1-1.31-2H5v-4h4.18c.16-.71.43-1.39.82-2H5V8h6v2.81a6.3 6.3 0 0 1 2-1.31V8h6v2a6.499 6.499 0 0 1 2 2V6a2 2 0 0 0-2-2"></path></svg>
<span class="md-ellipsis">
Глава 6. Хеш-таблицы
</span>
</a>
<label class="md-nav__link" for="__nav_8" id="__nav_8_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_8_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_8">
<span class="md-nav__icon md-icon"></span>
Глава 6. Хеш-таблицы
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_hashing/hash_map/">
<span class="md-ellipsis">
6.1 Хеш-таблица
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_hashing/hash_collision/">
<span class="md-ellipsis">
6.2 Хеш-коллизии
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_hashing/hash_algorithm/">
<span class="md-ellipsis">
6.3 Алгоритмы хеширования
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_hashing/summary/">
<span class="md-ellipsis">
6.4 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_hashing/exercises/">
<span class="md-ellipsis">
6.5 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_9" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_tree/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M19.5 17c-.14 0-.26 0-.39.04L17.5 13.8c.45-.45.75-1.09.75-1.8a2.5 2.5 0 0 0-2.5-2.5c-.14 0-.25 0-.4.04L13.74 6.3c.47-.46.76-1.09.76-1.8a2.5 2.5 0 0 0-5 0c0 .7.29 1.34.76 1.79L8.65 9.54c-.15-.04-.26-.04-.4-.04a2.5 2.5 0 0 0-2.5 2.5c0 .71.29 1.34.75 1.79l-1.61 3.25C4.76 17 4.64 17 4.5 17a2.5 2.5 0 0 0 0 5A2.5 2.5 0 0 0 7 19.5c0-.7-.29-1.34-.76-1.79l1.62-3.25c.14.04.26.04.39.04s.25 0 .38-.04l1.63 3.25c-.47.45-.76 1.09-.76 1.79a2.5 2.5 0 0 0 5 0A2.5 2.5 0 0 0 12 17c-.13 0-.26 0-.39.04L10 13.8c.45-.45.75-1.09.75-1.8 0-.7-.29-1.33-.75-1.79l1.61-3.25c.13.04.26.04.39.04s.26 0 .39-.04L14 10.21a2.5 2.5 0 0 0 1.75 4.29c.13 0 .25 0 .38-.04l1.63 3.25c-.47.45-.76 1.09-.76 1.79a2.5 2.5 0 0 0 5 0 2.5 2.5 0 0 0-2.5-2.5m-15 3.5c-.55 0-1-.45-1-1s.45-1 1-1 1 .45 1 1-.45 1-1 1m8.5-1c0 .55-.45 1-1 1s-1-.45-1-1 .45-1 1-1 1 .45 1 1M7.25 12c0-.55.45-1 1-1s1 .45 1 1-.45 1-1 1-1-.45-1-1M11 4.5c0-.55.45-1 1-1s1 .45 1 1-.45 1-1 1-1-.45-1-1m3.75 7.5c0-.55.45-1 1-1s1 .45 1 1-.45 1-1 1-1-.45-1-1m4.75 8.5c-.55 0-1-.45-1-1s.45-1 1-1 1 .45 1 1-.45 1-1 1"></path></svg>
<span class="md-ellipsis">
Глава 7. Деревья
</span>
</a>
<label class="md-nav__link" for="__nav_9" id="__nav_9_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_9_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_9">
<span class="md-nav__icon md-icon"></span>
Глава 7. Деревья
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_tree/binary_tree/">
<span class="md-ellipsis">
7.1 Двоичное дерево
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_tree/binary_tree_traversal/">
<span class="md-ellipsis">
7.2 Обход двоичного дерева
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_tree/array_representation_of_tree/">
<span class="md-ellipsis">
7.3 Представление двоичного дерева массивом
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_tree/binary_search_tree/">
<span class="md-ellipsis">
7.4 Двоичное дерево поиска
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_tree/avl_tree/">
<span class="md-ellipsis">
7.5 AVL-дерево *
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_tree/summary/">
<span class="md-ellipsis">
7.6 Краткие итоги
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_tree/exercises/">
<span class="md-ellipsis">
7.7 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_10" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_heap/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M12 1a2.5 2.5 0 0 0-2.5 2.5A2.5 2.5 0 0 0 11 5.79V7H7a2 2 0 0 0-2 2v.71A2.5 2.5 0 0 0 3.5 12 2.5 2.5 0 0 0 5 14.29V15H4a2 2 0 0 0-2 2v1.21A2.5 2.5 0 0 0 .5 20.5 2.5 2.5 0 0 0 3 23a2.5 2.5 0 0 0 2.5-2.5A2.5 2.5 0 0 0 4 18.21V17h4v1.21a2.5 2.5 0 0 0-1.5 2.29A2.5 2.5 0 0 0 9 23a2.5 2.5 0 0 0 2.5-2.5 2.5 2.5 0 0 0-1.5-2.29V17a2 2 0 0 0-2-2H7v-.71A2.5 2.5 0 0 0 8.5 12 2.5 2.5 0 0 0 7 9.71V9h10v.71A2.5 2.5 0 0 0 15.5 12a2.5 2.5 0 0 0 1.5 2.29V15h-1a2 2 0 0 0-2 2v1.21a2.5 2.5 0 0 0-1.5 2.29A2.5 2.5 0 0 0 15 23a2.5 2.5 0 0 0 2.5-2.5 2.5 2.5 0 0 0-1.5-2.29V17h4v1.21a2.5 2.5 0 0 0-1.5 2.29A2.5 2.5 0 0 0 21 23a2.5 2.5 0 0 0 2.5-2.5 2.5 2.5 0 0 0-1.5-2.29V17a2 2 0 0 0-2-2h-1v-.71A2.5 2.5 0 0 0 20.5 12 2.5 2.5 0 0 0 19 9.71V9a2 2 0 0 0-2-2h-4V5.79a2.5 2.5 0 0 0 1.5-2.29A2.5 2.5 0 0 0 12 1m0 1.5a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1M6 11a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1m12 0a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1M3 19.5a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1m6 0a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1m6 0a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1m6 0a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1"></path></svg>
<span class="md-ellipsis">
Глава 8. Куча
</span>
</a>
<label class="md-nav__link" for="__nav_10" id="__nav_10_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_10_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_10">
<span class="md-nav__icon md-icon"></span>
Глава 8. Куча
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_heap/heap/">
<span class="md-ellipsis">
8.1 Куча
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_heap/build_heap/">
<span class="md-ellipsis">
8.2 Построение кучи
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_heap/top_k/">
<span class="md-ellipsis">
8.3 Задача Top-k
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_heap/summary/">
<span class="md-ellipsis">
8.4 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_heap/exercises/">
<span class="md-ellipsis">
8.5 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_11" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_graph/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m12 5.37-.44-.06L6 14.9c.24.21.4.48.47.78h11.06c.07-.3.23-.57.47-.78l-5.56-9.59zM6.6 16.53l4.28 2.53c.29-.27.69-.43 1.12-.43s.83.16 1.12.43l4.28-2.53zM12 22a1.68 1.68 0 0 1-1.68-1.68l.09-.56-4.3-2.55c-.31.36-.76.58-1.27.58a1.68 1.68 0 0 1-1.68-1.68c0-.79.53-1.45 1.26-1.64V9.36c-.83-.11-1.47-.82-1.47-1.68A1.68 1.68 0 0 1 4.63 6c.55 0 1.03.26 1.34.66l4.41-2.53-.06-.45c0-.93.75-1.68 1.68-1.68s1.68.75 1.68 1.68l-.06.45 4.41 2.53c.31-.4.79-.66 1.34-.66a1.68 1.68 0 0 1 1.68 1.68c0 .86-.64 1.57-1.47 1.68v5.11c.73.19 1.26.85 1.26 1.64a1.68 1.68 0 0 1-1.68 1.68c-.51 0-.96-.22-1.27-.58l-4.3 2.55.09.56A1.68 1.68 0 0 1 12 22M10.8 4.86 6.3 7.44l.02.24c0 .71-.44 1.32-1.06 1.57l.03 5.25zm2.4 0 5.51 9.64.03-5.25c-.62-.25-1.06-.86-1.06-1.57l.02-.24z"></path></svg>
<span class="md-ellipsis">
Глава 9. Графы
</span>
</a>
<label class="md-nav__link" for="__nav_11" id="__nav_11_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_11_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_11">
<span class="md-nav__icon md-icon"></span>
Глава 9. Графы
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_graph/graph/">
<span class="md-ellipsis">
9.1 Граф
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_graph/graph_operations/">
<span class="md-ellipsis">
9.2 Базовые операции графа
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_graph/graph_traversal/">
<span class="md-ellipsis">
9.3 Обход графа
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_graph/summary/">
<span class="md-ellipsis">
9.4 Краткие итоги
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_graph/exercises/">
<span class="md-ellipsis">
9.5 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_12" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_searching/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m19.31 18.9 3.08 3.1L21 23.39l-3.12-3.07c-.69.43-1.51.68-2.38.68-2.5 0-4.5-2-4.5-4.5s2-4.5 4.5-4.5 4.5 2 4.5 4.5c0 .88-.25 1.71-.69 2.4m-3.81.1a2.5 2.5 0 0 0 0-5 2.5 2.5 0 0 0 0 5M21 4v2H3V4zM3 16v-2h6v2zm0-5V9h18v2h-2.03c-1.01-.63-2.2-1-3.47-1s-2.46.37-3.47 1z"></path></svg>
<span class="md-ellipsis">
Глава 10. Поиск
</span>
</a>
<label class="md-nav__link" for="__nav_12" id="__nav_12_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_12_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_12">
<span class="md-nav__icon md-icon"></span>
Глава 10. Поиск
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_searching/binary_search/">
<span class="md-ellipsis">
10.1 Двоичный поиск
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_searching/binary_search_insertion/">
<span class="md-ellipsis">
10.2 Двоичный поиск точки вставки
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_searching/binary_search_edge/">
<span class="md-ellipsis">
10.3 Двоичный поиск границ
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_searching/replace_linear_by_hashing/">
<span class="md-ellipsis">
10.4 Стратегии оптимизации с помощью хеширования
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_searching/searching_algorithm_revisited/">
<span class="md-ellipsis">
10.5 Переосмысление алгоритмов поиска
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_searching/summary/">
<span class="md-ellipsis">
10.6 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_searching/exercises/">
<span class="md-ellipsis">
10.7 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_13" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_sorting/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M19 17h3l-4 4-4-4h3V3h2M2 17h10v2H2M6 5v2H2V5m0 6h7v2H2z"></path></svg>
<span class="md-ellipsis">
Глава 11. Сортировка
</span>
</a>
<label class="md-nav__link" for="__nav_13" id="__nav_13_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_13_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_13">
<span class="md-nav__icon md-icon"></span>
Глава 11. Сортировка
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/sorting_algorithm/">
<span class="md-ellipsis">
11.1 Алгоритмы сортировки
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/selection_sort/">
<span class="md-ellipsis">
11.2 Сортировка выбором
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/bubble_sort/">
<span class="md-ellipsis">
11.3 Сортировка пузырьком
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/insertion_sort/">
<span class="md-ellipsis">
11.4 Сортировка вставками
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/quick_sort/">
<span class="md-ellipsis">
11.5 Быстрая сортировка
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/merge_sort/">
<span class="md-ellipsis">
11.6 Сортировка слиянием
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/heap_sort/">
<span class="md-ellipsis">
11.7 Пирамидальная сортировка
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/bucket_sort/">
<span class="md-ellipsis">
11.8 Блочная сортировка
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/counting_sort/">
<span class="md-ellipsis">
11.9 Сортировка подсчетом
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/radix_sort/">
<span class="md-ellipsis">
11.10 Поразрядная сортировка
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/summary/">
<span class="md-ellipsis">
11.11 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_sorting/exercises/">
<span class="md-ellipsis">
11.12 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--active md-nav__item--nested">
<input checked="" class="md-nav__toggle md-toggle" id="__nav_14" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M17 7v2h5V7zM2 9v6h5V9zm10 0v2H9v2h3v2l3-3zm5 2v2h5v-2zm0 4v2h5v-2z"></path></svg>
<span class="md-ellipsis">
Глава 12. Разделяй и властвуй
</span>
</a>
<label class="md-nav__link" for="__nav_14" id="__nav_14_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="true" aria-labelledby="__nav_14_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_14">
<span class="md-nav__icon md-icon"></span>
Глава 12. Разделяй и властвуй
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../divide_and_conquer/">
<span class="md-ellipsis">
12.1 Стратегия разделяй и властвуй
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../binary_search_recur/">
<span class="md-ellipsis">
12.2 Поисковая стратегия разделяй и властвуй
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../build_binary_tree_problem/">
<span class="md-ellipsis">
12.3 Задача построения двоичного дерева
</span>
</a>
</li>
<li class="md-nav__item md-nav__item--active">
<label class="md-nav__link md-nav__link--active" for="__toc">
<span class="md-ellipsis">
12.4 Задача о Ханойской башне
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<a class="md-nav__link md-nav__link--active" href="././">
<span class="md-ellipsis">
12.4 Задача о Ханойской башне
</span>
</a>
<nav aria-label="Содержание" class="md-nav md-nav--secondary">
<label class="md-nav__title" for="__toc">
<span class="md-nav__icon md-icon"></span>
Содержание
</label>
<ul class="md-nav__list" data-md-component="toc" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="#1">
<span class="md-ellipsis">
<span class="md-typeset">
1.   Рассмотрим базовые случаи
</span>
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#2">
<span class="md-ellipsis">
<span class="md-typeset">
2.   Разбиение на подзадачи
</span>
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#3">
<span class="md-ellipsis">
<span class="md-typeset">
3.   Реализация кода
</span>
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../summary/">
<span class="md-ellipsis">
12.5 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../exercises/">
<span class="md-ellipsis">
12.6 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_15" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_backtracking/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M18 15a3 3 0 0 1 3 3 3 3 0 0 1-3 3 2.99 2.99 0 0 1-2.83-2H14v-2h1.17c.41-1.17 1.52-2 2.83-2m0 2a1 1 0 0 0-1 1 1 1 0 0 0 1 1 1 1 0 0 0 1-1 1 1 0 0 0-1-1m0-9a1.43 1.43 0 0 0 1.43-1.43 1.43 1.43 0 1 0-2.86 0A1.43 1.43 0 0 0 18 8m0-5.43a4 4 0 0 1 4 4C22 9.56 18 14 18 14s-4-4.44-4-7.43a4 4 0 0 1 4-4M8.83 17H10v2H8.83A2.99 2.99 0 0 1 6 21a3 3 0 0 1-3-3c0-1.31.83-2.42 2-2.83V14h2v1.17c.85.3 1.53.98 1.83 1.83M6 17a1 1 0 0 0-1 1 1 1 0 0 0 1 1 1 1 0 0 0 1-1 1 1 0 0 0-1-1M6 3a3 3 0 0 1 3 3c0 1.31-.83 2.42-2 2.83V10H5V8.83A2.99 2.99 0 0 1 3 6a3 3 0 0 1 3-3m0 2a1 1 0 0 0-1 1 1 1 0 0 0 1 1 1 1 0 0 0 1-1 1 1 0 0 0-1-1m5 14v-2h2v2zm-4-6H5v-2h2z"></path></svg>
<span class="md-ellipsis">
Глава 13. Поиск с возвратом
</span>
</a>
<label class="md-nav__link" for="__nav_15" id="__nav_15_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_15_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_15">
<span class="md-nav__icon md-icon"></span>
Глава 13. Поиск с возвратом
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_backtracking/backtracking_algorithm/">
<span class="md-ellipsis">
13.1 Алгоритм поиска с возвратом
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_backtracking/permutations_problem/">
<span class="md-ellipsis">
13.2 Задача о перестановках
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_backtracking/subset_sum_problem/">
<span class="md-ellipsis">
13.3 Задача о сумме подмножеств
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_backtracking/n_queens_problem/">
<span class="md-ellipsis">
13.4 Задача о n ферзях
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_backtracking/summary/">
<span class="md-ellipsis">
13.5 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_backtracking/exercises/">
<span class="md-ellipsis">
13.6 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_16" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_dynamic_programming/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M22 15h-2v3c0 1.11-.89 2-2 2h-3v2l-3-3 3-3v2h3v-3h-2l3-3zm0-11v4c0 1.1-.9 2-2 2H10v10c0 1.1-.9 2-2 2H4c-1.1 0-2-.9-2-2V4c0-1.1.9-2 2-2h16c1.1 0 2 .9 2 2M4 8h4V4H4zm0 2v4h4v-4zm4 10v-4H4v4zm6-12V4h-4v4zm6-4h-4v4h4z"></path></svg>
<span class="md-ellipsis">
Глава 14. Динамическое программирование
</span>
</a>
<label class="md-nav__link" for="__nav_16" id="__nav_16_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_16_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_16">
<span class="md-nav__icon md-icon"></span>
Глава 14. Динамическое программирование
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_dynamic_programming/intro_to_dynamic_programming/">
<span class="md-ellipsis">
14.1 Первое знакомство с динамическим программированием
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_dynamic_programming/dp_problem_features/">
<span class="md-ellipsis">
14.2 Свойства задач динамического программирования
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_dynamic_programming/dp_solution_pipeline/">
<span class="md-ellipsis">
14.3 Подход к решению задач динамического программирования
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_dynamic_programming/knapsack_problem/">
<span class="md-ellipsis">
14.4 Задача о рюкзаке 0-1
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_dynamic_programming/unbounded_knapsack_problem/">
<span class="md-ellipsis">
14.5 Задача о полном рюкзаке
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_dynamic_programming/edit_distance_problem/">
<span class="md-ellipsis">
14.6 Задача о расстоянии редактирования
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_dynamic_programming/summary/">
<span class="md-ellipsis">
14.7 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_dynamic_programming/exercises/">
<span class="md-ellipsis">
14.8 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_17" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_greedy/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M13 3c3.88 0 7 3.14 7 7 0 2.8-1.63 5.19-4 6.31V21H9v-3H8c-1.11 0-2-.89-2-2v-3H4.5c-.42 0-.66-.5-.42-.81L6 9.66A7.003 7.003 0 0 1 13 3m0-2C8.41 1 4.61 4.42 4.06 8.9L2.5 11h-.03l-.02.03c-.55.76-.62 1.76-.19 2.59.36.69 1 1.17 1.74 1.32V16c0 1.85 1.28 3.42 3 3.87V23h11v-5.5c2.5-1.67 4-4.44 4-7.5 0-4.97-4.04-9-9-9m4 7.83c0 1.54-1.36 2.77-3.42 4.64L13 14l-.58-.53C10.36 11.6 9 10.37 9 8.83c0-1.2.96-2.19 2.16-2.2h.04c.69 0 1.35.31 1.8.83.45-.52 1.11-.83 1.8-.83 1.2-.01 2.2.96 2.2 2.16z"></path></svg>
<span class="md-ellipsis">
Глава 15. Жадность
</span>
</a>
<label class="md-nav__link" for="__nav_17" id="__nav_17_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_17_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_17">
<span class="md-nav__icon md-icon"></span>
Глава 15. Жадность
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_greedy/greedy_algorithm/">
<span class="md-ellipsis">
15.1 Жадный алгоритм
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_greedy/fractional_knapsack_problem/">
<span class="md-ellipsis">
15.2 Задача о дробном рюкзаке
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_greedy/max_capacity_problem/">
<span class="md-ellipsis">
15.3 Задача о максимальной вместимости
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_greedy/max_product_cutting_problem/">
<span class="md-ellipsis">
15.4 Задача о максимальном произведении разбиения
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_greedy/summary/">
<span class="md-ellipsis">
15.5 Резюме
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_greedy/exercises/">
<span class="md-ellipsis">
15.6 Упражнения
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_18" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_appendix/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M11 18h2v-2h-2zm1-16A10 10 0 0 0 2 12a10 10 0 0 0 10 10 10 10 0 0 0 10-10A10 10 0 0 0 12 2m0 18c-4.41 0-8-3.59-8-8s3.59-8 8-8 8 3.59 8 8-3.59 8-8 8m0-14a4 4 0 0 0-4 4h2a2 2 0 0 1 2-2 2 2 0 0 1 2 2c0 2-3 1.75-3 5h2c0-2.25 3-2.5 3-5a4 4 0 0 0-4-4"></path></svg>
<span class="md-ellipsis">
Глава 16. Приложение
</span>
</a>
<label class="md-nav__link" for="__nav_18" id="__nav_18_label" tabindex="0">
<span class="md-nav__icon md-icon"></span>
</label>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_18_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_18">
<span class="md-nav__icon md-icon"></span>
Глава 16. Приложение
</label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_appendix/installation/">
<span class="md-ellipsis">
16.1 Установка среды программирования
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_appendix/contribution/">
<span class="md-ellipsis">
16.2 Присоединяйтесь к созданию книги
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../../chapter_appendix/terminology/">
<span class="md-ellipsis">
16.3 Глоссарий
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle" id="__nav_19" type="checkbox"/>
<div class="md-nav__link md-nav__container">
<a class="md-nav__link" href="../../chapter_reference/">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M9 3v15h3V3zm3 2 4 13 3-1-4-13zM5 5v13h3V5zM3 19v2h18v-2z"></path></svg>
<span class="md-ellipsis">
Список литературы
</span>
</a>
</div>
<nav aria-expanded="false" aria-labelledby="__nav_19_label" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_19">
<span class="md-nav__icon md-icon"></span>
Список литературы
</label>
<ul class="md-nav__list" data-md-scrollfix="">
</ul>
</nav>
</li>
</ul>
</nav>
</div>
</div>
</div>
<div class="md-sidebar md-sidebar--secondary" data-md-component="sidebar" data-md-type="toc">
<div class="md-sidebar__scrollwrap">
<input class="md-nav__toggle md-toggle" id="__toc" type="checkbox"/>
<div class="md-sidebar-button__wrapper">
<label class="md-sidebar-button" for="__toc"></label>
</div>
<div class="md-sidebar__inner">
<nav aria-label="Содержание" class="md-nav md-nav--secondary">
<label class="md-nav__title" for="__toc">
<span class="md-nav__icon md-icon"></span>
Содержание
</label>
<ul class="md-nav__list" data-md-component="toc" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="#1">
<span class="md-ellipsis">
<span class="md-typeset">
1.   Рассмотрим базовые случаи
</span>
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#2">
<span class="md-ellipsis">
<span class="md-typeset">
2.   Разбиение на подзадачи
</span>
</span>
</a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#3">
<span class="md-ellipsis">
<span class="md-typeset">
3.   Реализация кода
</span>
</span>
</a>
</li>
</ul>
</nav>
</div>
</div>
</div>
<div class="md-content" data-md-component="content">
<article class="md-content__inner md-typeset">
<!-- Tags -->
<!-- Actions -->
<!-- Actions -->
<!-- Edit button -->
<a class="md-content__button md-icon" href="https://github.com/krahets/hello-algo/tree/main/ru/docs/chapter_divide_and_conquer/hanota_problem.md" title="Редактировать страницу">
<svg viewbox="0 0 512 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M441 58.9 453.1 71c9.4 9.4 9.4 24.6 0 33.9L424 134.1 377.9 88 407 58.9c9.4-9.4 24.6-9.4 33.9 0zM209.8 256.2 344 121.9l46.1 46.1-134.3 134.2c-2.9 2.9-6.5 5-10.4 6.1L186.9 325l16.7-58.5c1.1-3.9 3.2-7.5 6.1-10.4zM373.1 25 175.8 222.2c-8.7 8.7-15 19.4-18.3 31.1l-28.6 100c-2.4 8.4-.1 17.4 6.1 23.6s15.2 8.5 23.6 6.1l100-28.6c11.8-3.4 22.5-9.7 31.1-18.3L487 138.9c28.1-28.1 28.1-73.7 0-101.8L474.9 25c-28.1-28.1-73.7-28.1-101.8 0M88 64c-48.6 0-88 39.4-88 88v272c0 48.6 39.4 88 88 88h272c48.6 0 88-39.4 88-88V312c0-13.3-10.7-24-24-24s-24 10.7-24 24v112c0 22.1-17.9 40-40 40H88c-22.1 0-40-17.9-40-40V152c0-22.1 17.9-40 40-40h112c13.3 0 24-10.7 24-24s-10.7-24-24-24z" fill="currentColor"></path></svg>
</a>
<!-- View button -->
<!-- Page content -->
<h1 id="124">12.4   Задача о Ханойской башне<a class="headerlink" href="#124" title="Permanent link"></a></h1>
<p>В задачах сортировки слиянием и построения двоичного дерева мы делили исходную задачу на две подзадачи, каждая из которых имела размер, равный примерно половине исходной задачи. Однако для задачи о Ханойской башне используется другая стратегия разбиения.</p>
<div class="admonition question">
<p class="admonition-title">Question</p>
<p>Даны три стержня, обозначенные как <code>A</code> , <code>B</code> и <code>C</code> . В начальном состоянии на стержне <code>A</code> находятся <span class="arithmatex">\(n\)</span> дисков, расположенных сверху вниз в порядке от меньшего к большему. Нужно переместить эти <span class="arithmatex">\(n\)</span> дисков на стержень <code>C</code> , сохранив их исходный порядок (как показано на рисунке 12-10). Во время перемещения дисков необходимо соблюдать следующие правила.</p>
<ol>
<li>Диск можно снять только с вершины одного стержня и положить только на вершину другого стержня.</li>
<li>За один раз можно перемещать только один диск.</li>
<li>Меньший диск всегда должен лежать на большем.</li>
</ol>
</div>
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_example.png" data-dark-src="/assets/figure-svg/figures/ec9b2244a0563952851ed112.json" data-src="/assets/figure-svg/figures/769ef24db0a80a6318cd0e8e.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_example.svg" data-theme="light" tabindex="-1" type="image/svg+xml">Пример задачи о Ханойской башне</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_example.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">Пример задачи о Ханойской башне</object></ha-svg-figure></p>
<p align="center"> Рисунок 12-10   Пример задачи о Ханойской башне </p>
<p><strong>Обозначим задачу о Ханойской башне размера <span class="arithmatex">\(i\)</span> как <span class="arithmatex">\(f(i)\)</span></strong> . Например, <span class="arithmatex">\(f(3)\)</span> означает задачу перемещения 3 дисков со стержня <code>A</code> на стержень <code>C</code> .</p>
<h3 id="1">1.   Рассмотрим базовые случаи<a class="headerlink" href="#1" title="Permanent link"></a></h3>
<p>Как показано на рисунке 12-11, для задачи <span class="arithmatex">\(f(1)\)</span> , то есть когда имеется только один диск, достаточно просто переместить его напрямую со стержня <code>A</code> на стержень <code>C</code> .</p>
<div class="tabbed-set tabbed-alternate" data-figure-sequence="" data-tabs="1:2"><input checked="checked" id="__tabbed_1_1" name="__tabbed_1" type="radio"/><input id="__tabbed_1_2" name="__tabbed_1" type="radio"/><div class="tabbed-labels"><label for="__tabbed_1_1">&lt;1&gt;</label><label for="__tabbed_1_2">&lt;2&gt;</label></div>
<div class="tabbed-content">
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step1.png" data-dark-src="/assets/figure-svg/figures/253cc7b1a67bb9f459eeb98b.json" data-src="/assets/figure-svg/figures/3824fad8f3e25f668dc31a05.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step1.svg" data-theme="light" tabindex="-1" type="image/svg+xml">Решение задачи размера 1</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step1.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">Решение задачи размера 1</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step2.png" data-dark-src="/assets/figure-svg/figures/524e038f6466e77929e8f6d3.json" data-src="/assets/figure-svg/figures/1f6f14585ea7d6db8261c30b.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step2.svg" data-theme="light" tabindex="-1" type="image/svg+xml">hanota_f1_step2</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step2.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">hanota_f1_step2</object></ha-svg-figure></p>
</div>
</div>
</div>
<p align="center"> Рисунок 12-11   Решение задачи размера 1 </p>
<p>Как показано на рисунке 12-12, для задачи <span class="arithmatex">\(f(2)\)</span> , то есть когда есть два диска, <strong>поскольку меньший диск все время должен лежать на большем, приходится использовать <code>B</code> как вспомогательный стержень</strong>.</p>
<ol>
<li>Сначала переместить верхний маленький диск с <code>A</code> на <code>B</code> .</li>
<li>Затем переместить большой диск с <code>A</code> на <code>C</code> .</li>
<li>Наконец, переместить маленький диск с <code>B</code> на <code>C</code> .</li>
</ol>
<div class="tabbed-set tabbed-alternate" data-figure-sequence="" data-tabs="2:4"><input checked="checked" id="__tabbed_2_1" name="__tabbed_2" type="radio"/><input id="__tabbed_2_2" name="__tabbed_2" type="radio"/><input id="__tabbed_2_3" name="__tabbed_2" type="radio"/><input id="__tabbed_2_4" name="__tabbed_2" type="radio"/><div class="tabbed-labels"><label for="__tabbed_2_1">&lt;1&gt;</label><label for="__tabbed_2_2">&lt;2&gt;</label><label for="__tabbed_2_3">&lt;3&gt;</label><label for="__tabbed_2_4">&lt;4&gt;</label></div>
<div class="tabbed-content">
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step1.png" data-dark-src="/assets/figure-svg/figures/57a3076f8b98eaaa87122c76.json" data-src="/assets/figure-svg/figures/e8b5aa41b0fdf42244f8527d.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step1.svg" data-theme="light" tabindex="-1" type="image/svg+xml">Решение задачи размера 2</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step1.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">Решение задачи размера 2</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step2.png" data-dark-src="/assets/figure-svg/figures/0059130b1a2bdc62b9dd164c.json" data-src="/assets/figure-svg/figures/a7205f040c4449b64c9cbcee.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step2.svg" data-theme="light" tabindex="-1" type="image/svg+xml">hanota_f2_step2</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step2.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">hanota_f2_step2</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step3.png" data-dark-src="/assets/figure-svg/figures/39e23856b05923ef0694b25c.json" data-src="/assets/figure-svg/figures/a13146a738e2a304aeaee1fe.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step3.svg" data-theme="light" tabindex="-1" type="image/svg+xml">hanota_f2_step3</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step3.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">hanota_f2_step3</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step4.png" data-dark-src="/assets/figure-svg/figures/def6e4e147d341ab9fe1381e.json" data-src="/assets/figure-svg/figures/05b4f77087e6282cb88e959a.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step4.svg" data-theme="light" tabindex="-1" type="image/svg+xml">hanota_f2_step4</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step4.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">hanota_f2_step4</object></ha-svg-figure></p>
</div>
</div>
</div>
<p align="center"> Рисунок 12-12   Решение задачи размера 2 </p>
<p>Процесс решения задачи <span class="arithmatex">\(f(2)\)</span> можно кратко описать так: <strong>переместить два диска с <code>A</code> на <code>C</code> с помощью <code>B</code></strong> . Здесь <code>C</code> называется целевым стержнем, а <code>B</code> - буферным стержнем.</p>
<h3 id="2">2.   Разбиение на подзадачи<a class="headerlink" href="#2" title="Permanent link"></a></h3>
<p>Для задачи <span class="arithmatex">\(f(3)\)</span> , то есть когда имеется три диска, ситуация становится сложнее.</p>
<p>Поскольку решения <span class="arithmatex">\(f(1)\)</span> и <span class="arithmatex">\(f(2)\)</span> уже известны, можно подойти к задаче с точки зрения стратегии «разделяй и властвуй» и <strong>рассматривать два верхних диска на <code>A</code> как единое целое</strong>, выполняя шаги, показанные на рисунке 12-13. Так три диска успешно перемещаются с <code>A</code> на <code>C</code> .</p>
<ol>
<li>Сделать <code>B</code> целевым стержнем, а <code>C</code> буферным, и переместить два диска с <code>A</code> на <code>B</code> .</li>
<li>Переместить оставшийся один диск с <code>A</code> напрямую на <code>C</code> .</li>
<li>Сделать <code>C</code> целевым стержнем, а <code>A</code> буферным, и переместить два диска с <code>B</code> на <code>C</code> .</li>
</ol>
<div class="tabbed-set tabbed-alternate" data-figure-sequence="" data-tabs="3:4"><input checked="checked" id="__tabbed_3_1" name="__tabbed_3" type="radio"/><input id="__tabbed_3_2" name="__tabbed_3" type="radio"/><input id="__tabbed_3_3" name="__tabbed_3" type="radio"/><input id="__tabbed_3_4" name="__tabbed_3" type="radio"/><div class="tabbed-labels"><label for="__tabbed_3_1">&lt;1&gt;</label><label for="__tabbed_3_2">&lt;2&gt;</label><label for="__tabbed_3_3">&lt;3&gt;</label><label for="__tabbed_3_4">&lt;4&gt;</label></div>
<div class="tabbed-content">
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step1.png" data-dark-src="/assets/figure-svg/figures/cc0aea42551bb97b50066cae.json" data-src="/assets/figure-svg/figures/d9b83326765bb50cbe8bef27.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step1.svg" data-theme="light" tabindex="-1" type="image/svg+xml">Решение задачи размера 3</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step1.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">Решение задачи размера 3</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step2.png" data-dark-src="/assets/figure-svg/figures/1b66619f300ca39b162f8316.json" data-src="/assets/figure-svg/figures/ad5cbd12ea13d94779b58eb9.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step2.svg" data-theme="light" tabindex="-1" type="image/svg+xml">hanota_f3_step2</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step2.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">hanota_f3_step2</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step3.png" data-dark-src="/assets/figure-svg/figures/46025f75426890e453071d15.json" data-src="/assets/figure-svg/figures/db2371cffa4a071c96d01741.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step3.svg" data-theme="light" tabindex="-1" type="image/svg+xml">hanota_f3_step3</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step3.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">hanota_f3_step3</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step4.png" data-dark-src="/assets/figure-svg/figures/ed5d9561d0dc4da9d678e6b7.json" data-src="/assets/figure-svg/figures/77cc63d2d5328953217418e9.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step4.svg" data-theme="light" tabindex="-1" type="image/svg+xml">hanota_f3_step4</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step4.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">hanota_f3_step4</object></ha-svg-figure></p>
</div>
</div>
</div>
<p align="center"> Рисунок 12-13   Решение задачи размера 3 </p>
<p>Иначе говоря, <strong>мы разбиваем задачу <span class="arithmatex">\(f(3)\)</span> на две подзадачи <span class="arithmatex">\(f(2)\)</span> и одну подзадачу <span class="arithmatex">\(f(1)\)</span></strong> . Если последовательно решить эти три подзадачи, исходная задача тоже будет решена. Это показывает, что подзадачи независимы и что их решения можно объединить.</p>
<p>Таким образом, можно сформулировать показанную на рисунке 12-14 стратегию «разделяй и властвуй» для задачи о Ханойской башне: исходная задача <span class="arithmatex">\(f(n)\)</span> разбивается на две подзадачи <span class="arithmatex">\(f(n-1)\)</span> и одну подзадачу <span class="arithmatex">\(f(1)\)</span> , которые затем решаются в следующем порядке.</p>
<ol>
<li>Переместить <span class="arithmatex">\(n-1\)</span> дисков с <code>A</code> на <code>B</code> с помощью <code>C</code> .</li>
<li>Переместить оставшийся <span class="arithmatex">\(1\)</span> диск напрямую с <code>A</code> на <code>C</code> .</li>
<li>Переместить <span class="arithmatex">\(n-1\)</span> дисков с <code>B</code> на <code>C</code> с помощью <code>A</code> .</li>
</ol>
<p>Для двух подзадач <span class="arithmatex">\(f(n-1)\)</span> <strong>можно применять тот же способ рекурсивного разбиения</strong>, пока не будет достигнута наименьшая подзадача <span class="arithmatex">\(f(1)\)</span> . А решение для <span class="arithmatex">\(f(1)\)</span> уже известно и требует всего одного перемещения.</p>
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_divide_and_conquer.png" data-dark-src="/assets/figure-svg/figures/9de0fa5cc47f15da46e1d8cc.json" data-src="/assets/figure-svg/figures/58425fd5e7f2ddc320511c3c.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_divide_and_conquer.svg" data-theme="light" tabindex="-1" type="image/svg+xml">Стратегия разделяй и властвуй для решения задачи о Ханойской башне</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_divide_and_conquer.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">Стратегия разделяй и властвуй для решения задачи о Ханойской башне</object></ha-svg-figure></p>
<p align="center"> Рисунок 12-14   Стратегия разделяй и властвуй для решения задачи о Ханойской башне </p>
<h3 id="3">3.   Реализация кода<a class="headerlink" href="#3" title="Permanent link"></a></h3>
<p>В коде мы объявляем рекурсивную функцию <code>dfs(i, src, buf, tar)</code> , которая перемещает <span class="arithmatex">\(i\)</span> верхних дисков со стержня <code>src</code> на целевой стержень <code>tar</code> с помощью буферного стержня <code>buf</code> :</p>
<div class="tabbed-set tabbed-alternate" data-tabs="4:13"><input checked="checked" id="__tabbed_4_1" name="__tabbed_4" type="radio"/><input id="__tabbed_4_2" name="__tabbed_4" type="radio"/><input id="__tabbed_4_3" name="__tabbed_4" type="radio"/><input id="__tabbed_4_4" name="__tabbed_4" type="radio"/><input id="__tabbed_4_5" name="__tabbed_4" type="radio"/><input id="__tabbed_4_6" name="__tabbed_4" type="radio"/><input id="__tabbed_4_7" name="__tabbed_4" type="radio"/><input id="__tabbed_4_8" name="__tabbed_4" type="radio"/><input id="__tabbed_4_9" name="__tabbed_4" type="radio"/><input id="__tabbed_4_10" name="__tabbed_4" type="radio"/><input id="__tabbed_4_11" name="__tabbed_4" type="radio"/><input id="__tabbed_4_12" name="__tabbed_4" type="radio"/><input id="__tabbed_4_13" name="__tabbed_4" type="radio"/><div class="tabbed-labels"><label for="__tabbed_4_1">Python</label><label for="__tabbed_4_2">C++</label><label for="__tabbed_4_3">Java</label><label for="__tabbed_4_4">C#</label><label for="__tabbed_4_5">Go</label><label for="__tabbed_4_6">Swift</label><label for="__tabbed_4_7">JS</label><label for="__tabbed_4_8">TS</label><label for="__tabbed_4_9">Dart</label><label for="__tabbed_4_10">Rust</label><label for="__tabbed_4_11">C</label><label for="__tabbed_4_12">Kotlin</label><label for="__tabbed_4_13">Ruby</label></div>
<div class="tabbed-content">
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.py</span><pre><span></span><code><a href="#__codelineno-0-1" id="__codelineno-0-1" name="__codelineno-0-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">move</span><span class="p">(</span><span class="n">src</span><span class="p">:</span> <span class="nb">list</span><span class="p">[</span><span class="nb">int</span><span class="p">],</span> <span class="n">tar</span><span class="p">:</span> <span class="nb">list</span><span class="p">[</span><span class="nb">int</span><span class="p">]):</span>
<a href="#__codelineno-0-2" id="__codelineno-0-2" name="__codelineno-0-2"></a><span class="w"> </span><span class="sd">"""Переместить один диск"""</span>
<a href="#__codelineno-0-3" id="__codelineno-0-3" name="__codelineno-0-3"></a> <span class="c1"># Снять диск с вершины src</span>
<a href="#__codelineno-0-4" id="__codelineno-0-4" name="__codelineno-0-4"></a> <span class="n">pan</span> <span class="o">=</span> <span class="n">src</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
<a href="#__codelineno-0-5" id="__codelineno-0-5" name="__codelineno-0-5"></a> <span class="c1"># Положить диск на вершину tar</span>
<a href="#__codelineno-0-6" id="__codelineno-0-6" name="__codelineno-0-6"></a> <span class="n">tar</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">pan</span><span class="p">)</span>
<a href="#__codelineno-0-7" id="__codelineno-0-7" name="__codelineno-0-7"></a>
<a href="#__codelineno-0-8" id="__codelineno-0-8" name="__codelineno-0-8"></a><span class="k">def</span><span class="w"> </span><span class="nf">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">:</span> <span class="nb">int</span><span class="p">,</span> <span class="n">src</span><span class="p">:</span> <span class="nb">list</span><span class="p">[</span><span class="nb">int</span><span class="p">],</span> <span class="n">buf</span><span class="p">:</span> <span class="nb">list</span><span class="p">[</span><span class="nb">int</span><span class="p">],</span> <span class="n">tar</span><span class="p">:</span> <span class="nb">list</span><span class="p">[</span><span class="nb">int</span><span class="p">]):</span>
<a href="#__codelineno-0-9" id="__codelineno-0-9" name="__codelineno-0-9"></a><span class="w"> </span><span class="sd">"""Решить задачу Ханойской башни f(i)"""</span>
<a href="#__codelineno-0-10" id="__codelineno-0-10" name="__codelineno-0-10"></a> <span class="c1"># Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-0-11" id="__codelineno-0-11" name="__codelineno-0-11"></a> <span class="k">if</span> <span class="n">i</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
<a href="#__codelineno-0-12" id="__codelineno-0-12" name="__codelineno-0-12"></a> <span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span> <span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-0-13" id="__codelineno-0-13" name="__codelineno-0-13"></a> <span class="k">return</span>
<a href="#__codelineno-0-14" id="__codelineno-0-14" name="__codelineno-0-14"></a> <span class="c1"># Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-0-15" id="__codelineno-0-15" name="__codelineno-0-15"></a> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">src</span><span class="p">,</span> <span class="n">tar</span><span class="p">,</span> <span class="n">buf</span><span class="p">)</span>
<a href="#__codelineno-0-16" id="__codelineno-0-16" name="__codelineno-0-16"></a> <span class="c1"># Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-0-17" id="__codelineno-0-17" name="__codelineno-0-17"></a> <span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span> <span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-0-18" id="__codelineno-0-18" name="__codelineno-0-18"></a> <span class="c1"># Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-0-19" id="__codelineno-0-19" name="__codelineno-0-19"></a> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">buf</span><span class="p">,</span> <span class="n">src</span><span class="p">,</span> <span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-0-20" id="__codelineno-0-20" name="__codelineno-0-20"></a>
<a href="#__codelineno-0-21" id="__codelineno-0-21" name="__codelineno-0-21"></a><span class="k">def</span><span class="w"> </span><span class="nf">solve_hanota</span><span class="p">(</span><span class="n">A</span><span class="p">:</span> <span class="nb">list</span><span class="p">[</span><span class="nb">int</span><span class="p">],</span> <span class="n">B</span><span class="p">:</span> <span class="nb">list</span><span class="p">[</span><span class="nb">int</span><span class="p">],</span> <span class="n">C</span><span class="p">:</span> <span class="nb">list</span><span class="p">[</span><span class="nb">int</span><span class="p">]):</span>
<a href="#__codelineno-0-22" id="__codelineno-0-22" name="__codelineno-0-22"></a><span class="w"> </span><span class="sd">"""Решить задачу Ханойской башни"""</span>
<a href="#__codelineno-0-23" id="__codelineno-0-23" name="__codelineno-0-23"></a> <span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">A</span><span class="p">)</span>
<a href="#__codelineno-0-24" id="__codelineno-0-24" name="__codelineno-0-24"></a> <span class="c1"># Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-0-25" id="__codelineno-0-25" name="__codelineno-0-25"></a> <span class="n">dfs</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">B</span><span class="p">,</span> <span class="n">C</span><span class="p">)</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.cpp</span><pre><span></span><code><a href="#__codelineno-1-1" id="__codelineno-1-1" name="__codelineno-1-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-1-2" id="__codelineno-1-2" name="__codelineno-1-2"></a><span class="kt">void</span><span class="w"> </span><span class="nf">move</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&amp;</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&amp;</span><span class="n">tar</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-1-3" id="__codelineno-1-3" name="__codelineno-1-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-1-4" id="__codelineno-1-4" name="__codelineno-1-4"></a><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">pan</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">src</span><span class="p">.</span><span class="n">back</span><span class="p">();</span>
<a href="#__codelineno-1-5" id="__codelineno-1-5" name="__codelineno-1-5"></a><span class="w"> </span><span class="n">src</span><span class="p">.</span><span class="n">pop_back</span><span class="p">();</span>
<a href="#__codelineno-1-6" id="__codelineno-1-6" name="__codelineno-1-6"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-1-7" id="__codelineno-1-7" name="__codelineno-1-7"></a><span class="w"> </span><span class="n">tar</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">pan</span><span class="p">);</span>
<a href="#__codelineno-1-8" id="__codelineno-1-8" name="__codelineno-1-8"></a><span class="p">}</span>
<a href="#__codelineno-1-9" id="__codelineno-1-9" name="__codelineno-1-9"></a>
<a href="#__codelineno-1-10" id="__codelineno-1-10" name="__codelineno-1-10"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-1-11" id="__codelineno-1-11" name="__codelineno-1-11"></a><span class="kt">void</span><span class="w"> </span><span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&amp;</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&amp;</span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&amp;</span><span class="n">tar</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-1-12" id="__codelineno-1-12" name="__codelineno-1-12"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-1-13" id="__codelineno-1-13" name="__codelineno-1-13"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-1-14" id="__codelineno-1-14" name="__codelineno-1-14"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-1-15" id="__codelineno-1-15" name="__codelineno-1-15"></a><span class="w"> </span><span class="k">return</span><span class="p">;</span>
<a href="#__codelineno-1-16" id="__codelineno-1-16" name="__codelineno-1-16"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-1-17" id="__codelineno-1-17" name="__codelineno-1-17"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-1-18" id="__codelineno-1-18" name="__codelineno-1-18"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">);</span>
<a href="#__codelineno-1-19" id="__codelineno-1-19" name="__codelineno-1-19"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-1-20" id="__codelineno-1-20" name="__codelineno-1-20"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-1-21" id="__codelineno-1-21" name="__codelineno-1-21"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-1-22" id="__codelineno-1-22" name="__codelineno-1-22"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-1-23" id="__codelineno-1-23" name="__codelineno-1-23"></a><span class="p">}</span>
<a href="#__codelineno-1-24" id="__codelineno-1-24" name="__codelineno-1-24"></a>
<a href="#__codelineno-1-25" id="__codelineno-1-25" name="__codelineno-1-25"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-1-26" id="__codelineno-1-26" name="__codelineno-1-26"></a><span class="kt">void</span><span class="w"> </span><span class="nf">solveHanota</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&amp;</span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&amp;</span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&amp;</span><span class="n">C</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-1-27" id="__codelineno-1-27" name="__codelineno-1-27"></a><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">A</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
<a href="#__codelineno-1-28" id="__codelineno-1-28" name="__codelineno-1-28"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-1-29" id="__codelineno-1-29" name="__codelineno-1-29"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">C</span><span class="p">);</span>
<a href="#__codelineno-1-30" id="__codelineno-1-30" name="__codelineno-1-30"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.java</span><pre><span></span><code><a href="#__codelineno-2-1" id="__codelineno-2-1" name="__codelineno-2-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-2-2" id="__codelineno-2-2" name="__codelineno-2-2"></a><span class="kt">void</span><span class="w"> </span><span class="nf">move</span><span class="p">(</span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-2-3" id="__codelineno-2-3" name="__codelineno-2-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-2-4" id="__codelineno-2-4" name="__codelineno-2-4"></a><span class="w"> </span><span class="n">Integer</span><span class="w"> </span><span class="n">pan</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">src</span><span class="p">.</span><span class="na">remove</span><span class="p">(</span><span class="n">src</span><span class="p">.</span><span class="na">size</span><span class="p">()</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">);</span>
<a href="#__codelineno-2-5" id="__codelineno-2-5" name="__codelineno-2-5"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-2-6" id="__codelineno-2-6" name="__codelineno-2-6"></a><span class="w"> </span><span class="n">tar</span><span class="p">.</span><span class="na">add</span><span class="p">(</span><span class="n">pan</span><span class="p">);</span>
<a href="#__codelineno-2-7" id="__codelineno-2-7" name="__codelineno-2-7"></a><span class="p">}</span>
<a href="#__codelineno-2-8" id="__codelineno-2-8" name="__codelineno-2-8"></a>
<a href="#__codelineno-2-9" id="__codelineno-2-9" name="__codelineno-2-9"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-2-10" id="__codelineno-2-10" name="__codelineno-2-10"></a><span class="kt">void</span><span class="w"> </span><span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-2-11" id="__codelineno-2-11" name="__codelineno-2-11"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-2-12" id="__codelineno-2-12" name="__codelineno-2-12"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-2-13" id="__codelineno-2-13" name="__codelineno-2-13"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-2-14" id="__codelineno-2-14" name="__codelineno-2-14"></a><span class="w"> </span><span class="k">return</span><span class="p">;</span>
<a href="#__codelineno-2-15" id="__codelineno-2-15" name="__codelineno-2-15"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-2-16" id="__codelineno-2-16" name="__codelineno-2-16"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-2-17" id="__codelineno-2-17" name="__codelineno-2-17"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">);</span>
<a href="#__codelineno-2-18" id="__codelineno-2-18" name="__codelineno-2-18"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-2-19" id="__codelineno-2-19" name="__codelineno-2-19"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-2-20" id="__codelineno-2-20" name="__codelineno-2-20"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-2-21" id="__codelineno-2-21" name="__codelineno-2-21"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-2-22" id="__codelineno-2-22" name="__codelineno-2-22"></a><span class="p">}</span>
<a href="#__codelineno-2-23" id="__codelineno-2-23" name="__codelineno-2-23"></a>
<a href="#__codelineno-2-24" id="__codelineno-2-24" name="__codelineno-2-24"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-2-25" id="__codelineno-2-25" name="__codelineno-2-25"></a><span class="kt">void</span><span class="w"> </span><span class="nf">solveHanota</span><span class="p">(</span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span><span class="w"> </span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span><span class="w"> </span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span><span class="w"> </span><span class="n">C</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-2-26" id="__codelineno-2-26" name="__codelineno-2-26"></a><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">A</span><span class="p">.</span><span class="na">size</span><span class="p">();</span>
<a href="#__codelineno-2-27" id="__codelineno-2-27" name="__codelineno-2-27"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-2-28" id="__codelineno-2-28" name="__codelineno-2-28"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">C</span><span class="p">);</span>
<a href="#__codelineno-2-29" id="__codelineno-2-29" name="__codelineno-2-29"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.cs</span><pre><span></span><code><a href="#__codelineno-3-1" id="__codelineno-3-1" name="__codelineno-3-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-3-2" id="__codelineno-3-2" name="__codelineno-3-2"></a><span class="k">void</span><span class="w"> </span><span class="nf">Move</span><span class="p">(</span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-3-3" id="__codelineno-3-3" name="__codelineno-3-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-3-4" id="__codelineno-3-4" name="__codelineno-3-4"></a><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">pan</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">src</span><span class="p">[</span><span class="o">^</span><span class="mi">1</span><span class="p">];</span>
<a href="#__codelineno-3-5" id="__codelineno-3-5" name="__codelineno-3-5"></a><span class="w"> </span><span class="n">src</span><span class="p">.</span><span class="n">RemoveAt</span><span class="p">(</span><span class="n">src</span><span class="p">.</span><span class="n">Count</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">);</span>
<a href="#__codelineno-3-6" id="__codelineno-3-6" name="__codelineno-3-6"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-3-7" id="__codelineno-3-7" name="__codelineno-3-7"></a><span class="w"> </span><span class="n">tar</span><span class="p">.</span><span class="n">Add</span><span class="p">(</span><span class="n">pan</span><span class="p">);</span>
<a href="#__codelineno-3-8" id="__codelineno-3-8" name="__codelineno-3-8"></a><span class="p">}</span>
<a href="#__codelineno-3-9" id="__codelineno-3-9" name="__codelineno-3-9"></a>
<a href="#__codelineno-3-10" id="__codelineno-3-10" name="__codelineno-3-10"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-3-11" id="__codelineno-3-11" name="__codelineno-3-11"></a><span class="k">void</span><span class="w"> </span><span class="nf">DFS</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-3-12" id="__codelineno-3-12" name="__codelineno-3-12"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-3-13" id="__codelineno-3-13" name="__codelineno-3-13"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-3-14" id="__codelineno-3-14" name="__codelineno-3-14"></a><span class="w"> </span><span class="n">Move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-3-15" id="__codelineno-3-15" name="__codelineno-3-15"></a><span class="w"> </span><span class="k">return</span><span class="p">;</span>
<a href="#__codelineno-3-16" id="__codelineno-3-16" name="__codelineno-3-16"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-3-17" id="__codelineno-3-17" name="__codelineno-3-17"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-3-18" id="__codelineno-3-18" name="__codelineno-3-18"></a><span class="w"> </span><span class="n">DFS</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">);</span>
<a href="#__codelineno-3-19" id="__codelineno-3-19" name="__codelineno-3-19"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-3-20" id="__codelineno-3-20" name="__codelineno-3-20"></a><span class="w"> </span><span class="n">Move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-3-21" id="__codelineno-3-21" name="__codelineno-3-21"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-3-22" id="__codelineno-3-22" name="__codelineno-3-22"></a><span class="w"> </span><span class="n">DFS</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-3-23" id="__codelineno-3-23" name="__codelineno-3-23"></a><span class="p">}</span>
<a href="#__codelineno-3-24" id="__codelineno-3-24" name="__codelineno-3-24"></a>
<a href="#__codelineno-3-25" id="__codelineno-3-25" name="__codelineno-3-25"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-3-26" id="__codelineno-3-26" name="__codelineno-3-26"></a><span class="k">void</span><span class="w"> </span><span class="nf">SolveHanota</span><span class="p">(</span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">C</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-3-27" id="__codelineno-3-27" name="__codelineno-3-27"></a><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">A</span><span class="p">.</span><span class="n">Count</span><span class="p">;</span>
<a href="#__codelineno-3-28" id="__codelineno-3-28" name="__codelineno-3-28"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-3-29" id="__codelineno-3-29" name="__codelineno-3-29"></a><span class="w"> </span><span class="n">DFS</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">C</span><span class="p">);</span>
<a href="#__codelineno-3-30" id="__codelineno-3-30" name="__codelineno-3-30"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.go</span><pre><span></span><code><a href="#__codelineno-4-1" id="__codelineno-4-1" name="__codelineno-4-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-4-2" id="__codelineno-4-2" name="__codelineno-4-2"></a><span class="kd">func</span><span class="w"> </span><span class="nx">move</span><span class="p">(</span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="w"> </span><span class="o">*</span><span class="nx">list</span><span class="p">.</span><span class="nx">List</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-4-3" id="__codelineno-4-3" name="__codelineno-4-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-4-4" id="__codelineno-4-4" name="__codelineno-4-4"></a><span class="w"> </span><span class="nx">pan</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">src</span><span class="p">.</span><span class="nx">Back</span><span class="p">()</span>
<a href="#__codelineno-4-5" id="__codelineno-4-5" name="__codelineno-4-5"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-4-6" id="__codelineno-4-6" name="__codelineno-4-6"></a><span class="w"> </span><span class="nx">tar</span><span class="p">.</span><span class="nx">PushBack</span><span class="p">(</span><span class="nx">pan</span><span class="p">.</span><span class="nx">Value</span><span class="p">)</span>
<a href="#__codelineno-4-7" id="__codelineno-4-7" name="__codelineno-4-7"></a><span class="w"> </span><span class="c1">// Убрать верхний диск из src</span>
<a href="#__codelineno-4-8" id="__codelineno-4-8" name="__codelineno-4-8"></a><span class="w"> </span><span class="nx">src</span><span class="p">.</span><span class="nx">Remove</span><span class="p">(</span><span class="nx">pan</span><span class="p">)</span>
<a href="#__codelineno-4-9" id="__codelineno-4-9" name="__codelineno-4-9"></a><span class="p">}</span>
<a href="#__codelineno-4-10" id="__codelineno-4-10" name="__codelineno-4-10"></a>
<a href="#__codelineno-4-11" id="__codelineno-4-11" name="__codelineno-4-11"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-4-12" id="__codelineno-4-12" name="__codelineno-4-12"></a><span class="kd">func</span><span class="w"> </span><span class="nx">dfsHanota</span><span class="p">(</span><span class="nx">i</span><span class="w"> </span><span class="kt">int</span><span class="p">,</span><span class="w"> </span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">buf</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="w"> </span><span class="o">*</span><span class="nx">list</span><span class="p">.</span><span class="nx">List</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-4-13" id="__codelineno-4-13" name="__codelineno-4-13"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-4-14" id="__codelineno-4-14" name="__codelineno-4-14"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-4-15" id="__codelineno-4-15" name="__codelineno-4-15"></a><span class="w"> </span><span class="nx">move</span><span class="p">(</span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">)</span>
<a href="#__codelineno-4-16" id="__codelineno-4-16" name="__codelineno-4-16"></a><span class="w"> </span><span class="k">return</span>
<a href="#__codelineno-4-17" id="__codelineno-4-17" name="__codelineno-4-17"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-4-18" id="__codelineno-4-18" name="__codelineno-4-18"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-4-19" id="__codelineno-4-19" name="__codelineno-4-19"></a><span class="w"> </span><span class="nx">dfsHanota</span><span class="p">(</span><span class="nx">i</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">,</span><span class="w"> </span><span class="nx">buf</span><span class="p">)</span>
<a href="#__codelineno-4-20" id="__codelineno-4-20" name="__codelineno-4-20"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-4-21" id="__codelineno-4-21" name="__codelineno-4-21"></a><span class="w"> </span><span class="nx">move</span><span class="p">(</span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">)</span>
<a href="#__codelineno-4-22" id="__codelineno-4-22" name="__codelineno-4-22"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-4-23" id="__codelineno-4-23" name="__codelineno-4-23"></a><span class="w"> </span><span class="nx">dfsHanota</span><span class="p">(</span><span class="nx">i</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="nx">buf</span><span class="p">,</span><span class="w"> </span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">)</span>
<a href="#__codelineno-4-24" id="__codelineno-4-24" name="__codelineno-4-24"></a><span class="p">}</span>
<a href="#__codelineno-4-25" id="__codelineno-4-25" name="__codelineno-4-25"></a>
<a href="#__codelineno-4-26" id="__codelineno-4-26" name="__codelineno-4-26"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-4-27" id="__codelineno-4-27" name="__codelineno-4-27"></a><span class="kd">func</span><span class="w"> </span><span class="nx">solveHanota</span><span class="p">(</span><span class="nx">A</span><span class="p">,</span><span class="w"> </span><span class="nx">B</span><span class="p">,</span><span class="w"> </span><span class="nx">C</span><span class="w"> </span><span class="o">*</span><span class="nx">list</span><span class="p">.</span><span class="nx">List</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-4-28" id="__codelineno-4-28" name="__codelineno-4-28"></a><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">A</span><span class="p">.</span><span class="nx">Len</span><span class="p">()</span>
<a href="#__codelineno-4-29" id="__codelineno-4-29" name="__codelineno-4-29"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-4-30" id="__codelineno-4-30" name="__codelineno-4-30"></a><span class="w"> </span><span class="nx">dfsHanota</span><span class="p">(</span><span class="nx">n</span><span class="p">,</span><span class="w"> </span><span class="nx">A</span><span class="p">,</span><span class="w"> </span><span class="nx">B</span><span class="p">,</span><span class="w"> </span><span class="nx">C</span><span class="p">)</span>
<a href="#__codelineno-4-31" id="__codelineno-4-31" name="__codelineno-4-31"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.swift</span><pre><span></span><code><a href="#__codelineno-5-1" id="__codelineno-5-1" name="__codelineno-5-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-5-2" id="__codelineno-5-2" name="__codelineno-5-2"></a><span class="kd">func</span><span class="w"> </span><span class="nf">move</span><span class="p">(</span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="kr">inout</span><span class="w"> </span><span class="p">[</span><span class="nb">Int</span><span class="p">],</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="kr">inout</span><span class="w"> </span><span class="p">[</span><span class="nb">Int</span><span class="p">])</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-5-3" id="__codelineno-5-3" name="__codelineno-5-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-5-4" id="__codelineno-5-4" name="__codelineno-5-4"></a><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="nv">pan</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">src</span><span class="p">.</span><span class="n">popLast</span><span class="p">()</span><span class="o">!</span>
<a href="#__codelineno-5-5" id="__codelineno-5-5" name="__codelineno-5-5"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-5-6" id="__codelineno-5-6" name="__codelineno-5-6"></a><span class="w"> </span><span class="n">tar</span><span class="p">.</span><span class="n">append</span><span class="p">(</span><span class="n">pan</span><span class="p">)</span>
<a href="#__codelineno-5-7" id="__codelineno-5-7" name="__codelineno-5-7"></a><span class="p">}</span>
<a href="#__codelineno-5-8" id="__codelineno-5-8" name="__codelineno-5-8"></a>
<a href="#__codelineno-5-9" id="__codelineno-5-9" name="__codelineno-5-9"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-5-10" id="__codelineno-5-10" name="__codelineno-5-10"></a><span class="kd">func</span><span class="w"> </span><span class="nf">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">:</span><span class="w"> </span><span class="nb">Int</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="kr">inout</span><span class="w"> </span><span class="p">[</span><span class="nb">Int</span><span class="p">],</span><span class="w"> </span><span class="n">buf</span><span class="p">:</span><span class="w"> </span><span class="kr">inout</span><span class="w"> </span><span class="p">[</span><span class="nb">Int</span><span class="p">],</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="kr">inout</span><span class="w"> </span><span class="p">[</span><span class="nb">Int</span><span class="p">])</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-5-11" id="__codelineno-5-11" name="__codelineno-5-11"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-5-12" id="__codelineno-5-12" name="__codelineno-5-12"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="p">==</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-5-13" id="__codelineno-5-13" name="__codelineno-5-13"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-5-14" id="__codelineno-5-14" name="__codelineno-5-14"></a><span class="w"> </span><span class="k">return</span>
<a href="#__codelineno-5-15" id="__codelineno-5-15" name="__codelineno-5-15"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-5-16" id="__codelineno-5-16" name="__codelineno-5-16"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-5-17" id="__codelineno-5-17" name="__codelineno-5-17"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">:</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">buf</span><span class="p">)</span>
<a href="#__codelineno-5-18" id="__codelineno-5-18" name="__codelineno-5-18"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-5-19" id="__codelineno-5-19" name="__codelineno-5-19"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-5-20" id="__codelineno-5-20" name="__codelineno-5-20"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-5-21" id="__codelineno-5-21" name="__codelineno-5-21"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">:</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-5-22" id="__codelineno-5-22" name="__codelineno-5-22"></a><span class="p">}</span>
<a href="#__codelineno-5-23" id="__codelineno-5-23" name="__codelineno-5-23"></a>
<a href="#__codelineno-5-24" id="__codelineno-5-24" name="__codelineno-5-24"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-5-25" id="__codelineno-5-25" name="__codelineno-5-25"></a><span class="kd">func</span><span class="w"> </span><span class="nf">solveHanota</span><span class="p">(</span><span class="n">A</span><span class="p">:</span><span class="w"> </span><span class="kr">inout</span><span class="w"> </span><span class="p">[</span><span class="nb">Int</span><span class="p">],</span><span class="w"> </span><span class="n">B</span><span class="p">:</span><span class="w"> </span><span class="kr">inout</span><span class="w"> </span><span class="p">[</span><span class="nb">Int</span><span class="p">],</span><span class="w"> </span><span class="n">C</span><span class="p">:</span><span class="w"> </span><span class="kr">inout</span><span class="w"> </span><span class="p">[</span><span class="nb">Int</span><span class="p">])</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-5-26" id="__codelineno-5-26" name="__codelineno-5-26"></a><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="nv">n</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="p">.</span><span class="bp">count</span>
<a href="#__codelineno-5-27" id="__codelineno-5-27" name="__codelineno-5-27"></a><span class="w"> </span><span class="c1">// Хвост списка соответствует вершине столбца</span>
<a href="#__codelineno-5-28" id="__codelineno-5-28" name="__codelineno-5-28"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из src в C с помощью B</span>
<a href="#__codelineno-5-29" id="__codelineno-5-29" name="__codelineno-5-29"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">:</span><span class="w"> </span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="p">&amp;</span><span class="n">C</span><span class="p">)</span>
<a href="#__codelineno-5-30" id="__codelineno-5-30" name="__codelineno-5-30"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.js</span><pre><span></span><code><a href="#__codelineno-6-1" id="__codelineno-6-1" name="__codelineno-6-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-6-2" id="__codelineno-6-2" name="__codelineno-6-2"></a><span class="kd">function</span><span class="w"> </span><span class="nx">move</span><span class="p">(</span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-6-3" id="__codelineno-6-3" name="__codelineno-6-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-6-4" id="__codelineno-6-4" name="__codelineno-6-4"></a><span class="w"> </span><span class="kd">const</span><span class="w"> </span><span class="nx">pan</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nx">src</span><span class="p">.</span><span class="nx">pop</span><span class="p">();</span>
<a href="#__codelineno-6-5" id="__codelineno-6-5" name="__codelineno-6-5"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-6-6" id="__codelineno-6-6" name="__codelineno-6-6"></a><span class="w"> </span><span class="nx">tar</span><span class="p">.</span><span class="nx">push</span><span class="p">(</span><span class="nx">pan</span><span class="p">);</span>
<a href="#__codelineno-6-7" id="__codelineno-6-7" name="__codelineno-6-7"></a><span class="p">}</span>
<a href="#__codelineno-6-8" id="__codelineno-6-8" name="__codelineno-6-8"></a>
<a href="#__codelineno-6-9" id="__codelineno-6-9" name="__codelineno-6-9"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-6-10" id="__codelineno-6-10" name="__codelineno-6-10"></a><span class="kd">function</span><span class="w"> </span><span class="nx">dfs</span><span class="p">(</span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">buf</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-6-11" id="__codelineno-6-11" name="__codelineno-6-11"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-6-12" id="__codelineno-6-12" name="__codelineno-6-12"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="nx">i</span><span class="w"> </span><span class="o">===</span><span class="w"> </span><span class="mf">1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-6-13" id="__codelineno-6-13" name="__codelineno-6-13"></a><span class="w"> </span><span class="nx">move</span><span class="p">(</span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">);</span>
<a href="#__codelineno-6-14" id="__codelineno-6-14" name="__codelineno-6-14"></a><span class="w"> </span><span class="k">return</span><span class="p">;</span>
<a href="#__codelineno-6-15" id="__codelineno-6-15" name="__codelineno-6-15"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-6-16" id="__codelineno-6-16" name="__codelineno-6-16"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-6-17" id="__codelineno-6-17" name="__codelineno-6-17"></a><span class="w"> </span><span class="nx">dfs</span><span class="p">(</span><span class="nx">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mf">1</span><span class="p">,</span><span class="w"> </span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">,</span><span class="w"> </span><span class="nx">buf</span><span class="p">);</span>
<a href="#__codelineno-6-18" id="__codelineno-6-18" name="__codelineno-6-18"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-6-19" id="__codelineno-6-19" name="__codelineno-6-19"></a><span class="w"> </span><span class="nx">move</span><span class="p">(</span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">);</span>
<a href="#__codelineno-6-20" id="__codelineno-6-20" name="__codelineno-6-20"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-6-21" id="__codelineno-6-21" name="__codelineno-6-21"></a><span class="w"> </span><span class="nx">dfs</span><span class="p">(</span><span class="nx">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mf">1</span><span class="p">,</span><span class="w"> </span><span class="nx">buf</span><span class="p">,</span><span class="w"> </span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">);</span>
<a href="#__codelineno-6-22" id="__codelineno-6-22" name="__codelineno-6-22"></a><span class="p">}</span>
<a href="#__codelineno-6-23" id="__codelineno-6-23" name="__codelineno-6-23"></a>
<a href="#__codelineno-6-24" id="__codelineno-6-24" name="__codelineno-6-24"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-6-25" id="__codelineno-6-25" name="__codelineno-6-25"></a><span class="kd">function</span><span class="w"> </span><span class="nx">solveHanota</span><span class="p">(</span><span class="nx">A</span><span class="p">,</span><span class="w"> </span><span class="nx">B</span><span class="p">,</span><span class="w"> </span><span class="nx">C</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-6-26" id="__codelineno-6-26" name="__codelineno-6-26"></a><span class="w"> </span><span class="kd">const</span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nx">A</span><span class="p">.</span><span class="nx">length</span><span class="p">;</span>
<a href="#__codelineno-6-27" id="__codelineno-6-27" name="__codelineno-6-27"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-6-28" id="__codelineno-6-28" name="__codelineno-6-28"></a><span class="w"> </span><span class="nx">dfs</span><span class="p">(</span><span class="nx">n</span><span class="p">,</span><span class="w"> </span><span class="nx">A</span><span class="p">,</span><span class="w"> </span><span class="nx">B</span><span class="p">,</span><span class="w"> </span><span class="nx">C</span><span class="p">);</span>
<a href="#__codelineno-6-29" id="__codelineno-6-29" name="__codelineno-6-29"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.ts</span><pre><span></span><code><a href="#__codelineno-7-1" id="__codelineno-7-1" name="__codelineno-7-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-7-2" id="__codelineno-7-2" name="__codelineno-7-2"></a><span class="kd">function</span><span class="w"> </span><span class="nx">move</span><span class="p">(</span><span class="nx">src</span><span class="o">:</span><span class="w"> </span><span class="kt">number</span><span class="p">[],</span><span class="w"> </span><span class="nx">tar</span><span class="o">:</span><span class="w"> </span><span class="kt">number</span><span class="p">[])</span><span class="o">:</span><span class="w"> </span><span class="ow">void</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-7-3" id="__codelineno-7-3" name="__codelineno-7-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-7-4" id="__codelineno-7-4" name="__codelineno-7-4"></a><span class="w"> </span><span class="kd">const</span><span class="w"> </span><span class="nx">pan</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nx">src</span><span class="p">.</span><span class="nx">pop</span><span class="p">();</span>
<a href="#__codelineno-7-5" id="__codelineno-7-5" name="__codelineno-7-5"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-7-6" id="__codelineno-7-6" name="__codelineno-7-6"></a><span class="w"> </span><span class="nx">tar</span><span class="p">.</span><span class="nx">push</span><span class="p">(</span><span class="nx">pan</span><span class="p">);</span>
<a href="#__codelineno-7-7" id="__codelineno-7-7" name="__codelineno-7-7"></a><span class="p">}</span>
<a href="#__codelineno-7-8" id="__codelineno-7-8" name="__codelineno-7-8"></a>
<a href="#__codelineno-7-9" id="__codelineno-7-9" name="__codelineno-7-9"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-7-10" id="__codelineno-7-10" name="__codelineno-7-10"></a><span class="kd">function</span><span class="w"> </span><span class="nx">dfs</span><span class="p">(</span><span class="nx">i</span><span class="o">:</span><span class="w"> </span><span class="kt">number</span><span class="p">,</span><span class="w"> </span><span class="nx">src</span><span class="o">:</span><span class="w"> </span><span class="kt">number</span><span class="p">[],</span><span class="w"> </span><span class="nx">buf</span><span class="o">:</span><span class="w"> </span><span class="kt">number</span><span class="p">[],</span><span class="w"> </span><span class="nx">tar</span><span class="o">:</span><span class="w"> </span><span class="kt">number</span><span class="p">[])</span><span class="o">:</span><span class="w"> </span><span class="ow">void</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-7-11" id="__codelineno-7-11" name="__codelineno-7-11"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-7-12" id="__codelineno-7-12" name="__codelineno-7-12"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="nx">i</span><span class="w"> </span><span class="o">===</span><span class="w"> </span><span class="mf">1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-7-13" id="__codelineno-7-13" name="__codelineno-7-13"></a><span class="w"> </span><span class="nx">move</span><span class="p">(</span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">);</span>
<a href="#__codelineno-7-14" id="__codelineno-7-14" name="__codelineno-7-14"></a><span class="w"> </span><span class="k">return</span><span class="p">;</span>
<a href="#__codelineno-7-15" id="__codelineno-7-15" name="__codelineno-7-15"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-7-16" id="__codelineno-7-16" name="__codelineno-7-16"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-7-17" id="__codelineno-7-17" name="__codelineno-7-17"></a><span class="w"> </span><span class="nx">dfs</span><span class="p">(</span><span class="nx">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mf">1</span><span class="p">,</span><span class="w"> </span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">,</span><span class="w"> </span><span class="nx">buf</span><span class="p">);</span>
<a href="#__codelineno-7-18" id="__codelineno-7-18" name="__codelineno-7-18"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-7-19" id="__codelineno-7-19" name="__codelineno-7-19"></a><span class="w"> </span><span class="nx">move</span><span class="p">(</span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">);</span>
<a href="#__codelineno-7-20" id="__codelineno-7-20" name="__codelineno-7-20"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-7-21" id="__codelineno-7-21" name="__codelineno-7-21"></a><span class="w"> </span><span class="nx">dfs</span><span class="p">(</span><span class="nx">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mf">1</span><span class="p">,</span><span class="w"> </span><span class="nx">buf</span><span class="p">,</span><span class="w"> </span><span class="nx">src</span><span class="p">,</span><span class="w"> </span><span class="nx">tar</span><span class="p">);</span>
<a href="#__codelineno-7-22" id="__codelineno-7-22" name="__codelineno-7-22"></a><span class="p">}</span>
<a href="#__codelineno-7-23" id="__codelineno-7-23" name="__codelineno-7-23"></a>
<a href="#__codelineno-7-24" id="__codelineno-7-24" name="__codelineno-7-24"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-7-25" id="__codelineno-7-25" name="__codelineno-7-25"></a><span class="kd">function</span><span class="w"> </span><span class="nx">solveHanota</span><span class="p">(</span><span class="nx">A</span><span class="o">:</span><span class="w"> </span><span class="kt">number</span><span class="p">[],</span><span class="w"> </span><span class="nx">B</span><span class="o">:</span><span class="w"> </span><span class="kt">number</span><span class="p">[],</span><span class="w"> </span><span class="nx">C</span><span class="o">:</span><span class="w"> </span><span class="kt">number</span><span class="p">[])</span><span class="o">:</span><span class="w"> </span><span class="ow">void</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-7-26" id="__codelineno-7-26" name="__codelineno-7-26"></a><span class="w"> </span><span class="kd">const</span><span class="w"> </span><span class="nx">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nx">A</span><span class="p">.</span><span class="nx">length</span><span class="p">;</span>
<a href="#__codelineno-7-27" id="__codelineno-7-27" name="__codelineno-7-27"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-7-28" id="__codelineno-7-28" name="__codelineno-7-28"></a><span class="w"> </span><span class="nx">dfs</span><span class="p">(</span><span class="nx">n</span><span class="p">,</span><span class="w"> </span><span class="nx">A</span><span class="p">,</span><span class="w"> </span><span class="nx">B</span><span class="p">,</span><span class="w"> </span><span class="nx">C</span><span class="p">);</span>
<a href="#__codelineno-7-29" id="__codelineno-7-29" name="__codelineno-7-29"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.dart</span><pre><span></span><code><a href="#__codelineno-8-1" id="__codelineno-8-1" name="__codelineno-8-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-8-2" id="__codelineno-8-2" name="__codelineno-8-2"></a><span class="kt">void</span><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-8-3" id="__codelineno-8-3" name="__codelineno-8-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-8-4" id="__codelineno-8-4" name="__codelineno-8-4"></a><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">pan</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">src</span><span class="p">.</span><span class="n">removeLast</span><span class="p">();</span>
<a href="#__codelineno-8-5" id="__codelineno-8-5" name="__codelineno-8-5"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-8-6" id="__codelineno-8-6" name="__codelineno-8-6"></a><span class="w"> </span><span class="n">tar</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">pan</span><span class="p">);</span>
<a href="#__codelineno-8-7" id="__codelineno-8-7" name="__codelineno-8-7"></a><span class="p">}</span>
<a href="#__codelineno-8-8" id="__codelineno-8-8" name="__codelineno-8-8"></a>
<a href="#__codelineno-8-9" id="__codelineno-8-9" name="__codelineno-8-9"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-8-10" id="__codelineno-8-10" name="__codelineno-8-10"></a><span class="kt">void</span><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-8-11" id="__codelineno-8-11" name="__codelineno-8-11"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-8-12" id="__codelineno-8-12" name="__codelineno-8-12"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-8-13" id="__codelineno-8-13" name="__codelineno-8-13"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-8-14" id="__codelineno-8-14" name="__codelineno-8-14"></a><span class="w"> </span><span class="k">return</span><span class="p">;</span>
<a href="#__codelineno-8-15" id="__codelineno-8-15" name="__codelineno-8-15"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-8-16" id="__codelineno-8-16" name="__codelineno-8-16"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-8-17" id="__codelineno-8-17" name="__codelineno-8-17"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">);</span>
<a href="#__codelineno-8-18" id="__codelineno-8-18" name="__codelineno-8-18"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-8-19" id="__codelineno-8-19" name="__codelineno-8-19"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-8-20" id="__codelineno-8-20" name="__codelineno-8-20"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-8-21" id="__codelineno-8-21" name="__codelineno-8-21"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-8-22" id="__codelineno-8-22" name="__codelineno-8-22"></a><span class="p">}</span>
<a href="#__codelineno-8-23" id="__codelineno-8-23" name="__codelineno-8-23"></a>
<a href="#__codelineno-8-24" id="__codelineno-8-24" name="__codelineno-8-24"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-8-25" id="__codelineno-8-25" name="__codelineno-8-25"></a><span class="kt">void</span><span class="w"> </span><span class="n">solveHanota</span><span class="p">(</span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">List</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">C</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-8-26" id="__codelineno-8-26" name="__codelineno-8-26"></a><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">A</span><span class="p">.</span><span class="n">length</span><span class="p">;</span>
<a href="#__codelineno-8-27" id="__codelineno-8-27" name="__codelineno-8-27"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-8-28" id="__codelineno-8-28" name="__codelineno-8-28"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">C</span><span class="p">);</span>
<a href="#__codelineno-8-29" id="__codelineno-8-29" name="__codelineno-8-29"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.rs</span><pre><span></span><code><a href="#__codelineno-9-1" id="__codelineno-9-1" name="__codelineno-9-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-9-2" id="__codelineno-9-2" name="__codelineno-9-2"></a><span class="k">fn</span><span class="w"> </span><span class="nf">move_pan</span><span class="p">(</span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="kp">&amp;</span><span class="nc">mut</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="kt">i32</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="kp">&amp;</span><span class="nc">mut</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="kt">i32</span><span class="o">&gt;</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-9-3" id="__codelineno-9-3" name="__codelineno-9-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-9-4" id="__codelineno-9-4" name="__codelineno-9-4"></a><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="n">pan</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">src</span><span class="p">.</span><span class="n">pop</span><span class="p">().</span><span class="n">unwrap</span><span class="p">();</span>
<a href="#__codelineno-9-5" id="__codelineno-9-5" name="__codelineno-9-5"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-9-6" id="__codelineno-9-6" name="__codelineno-9-6"></a><span class="w"> </span><span class="n">tar</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">pan</span><span class="p">);</span>
<a href="#__codelineno-9-7" id="__codelineno-9-7" name="__codelineno-9-7"></a><span class="p">}</span>
<a href="#__codelineno-9-8" id="__codelineno-9-8" name="__codelineno-9-8"></a>
<a href="#__codelineno-9-9" id="__codelineno-9-9" name="__codelineno-9-9"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-9-10" id="__codelineno-9-10" name="__codelineno-9-10"></a><span class="k">fn</span><span class="w"> </span><span class="nf">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">:</span><span class="w"> </span><span class="kt">i32</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="kp">&amp;</span><span class="nc">mut</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="kt">i32</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">:</span><span class="w"> </span><span class="kp">&amp;</span><span class="nc">mut</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="kt">i32</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="kp">&amp;</span><span class="nc">mut</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="kt">i32</span><span class="o">&gt;</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-9-11" id="__codelineno-9-11" name="__codelineno-9-11"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-9-12" id="__codelineno-9-12" name="__codelineno-9-12"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-9-13" id="__codelineno-9-13" name="__codelineno-9-13"></a><span class="w"> </span><span class="n">move_pan</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-9-14" id="__codelineno-9-14" name="__codelineno-9-14"></a><span class="w"> </span><span class="k">return</span><span class="p">;</span>
<a href="#__codelineno-9-15" id="__codelineno-9-15" name="__codelineno-9-15"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-9-16" id="__codelineno-9-16" name="__codelineno-9-16"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-9-17" id="__codelineno-9-17" name="__codelineno-9-17"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">);</span>
<a href="#__codelineno-9-18" id="__codelineno-9-18" name="__codelineno-9-18"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-9-19" id="__codelineno-9-19" name="__codelineno-9-19"></a><span class="w"> </span><span class="n">move_pan</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-9-20" id="__codelineno-9-20" name="__codelineno-9-20"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-9-21" id="__codelineno-9-21" name="__codelineno-9-21"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">);</span>
<a href="#__codelineno-9-22" id="__codelineno-9-22" name="__codelineno-9-22"></a><span class="p">}</span>
<a href="#__codelineno-9-23" id="__codelineno-9-23" name="__codelineno-9-23"></a>
<a href="#__codelineno-9-24" id="__codelineno-9-24" name="__codelineno-9-24"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-9-25" id="__codelineno-9-25" name="__codelineno-9-25"></a><span class="k">fn</span><span class="w"> </span><span class="nf">solve_hanota</span><span class="p">(</span><span class="n">A</span><span class="p">:</span><span class="w"> </span><span class="kp">&amp;</span><span class="nc">mut</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="kt">i32</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">B</span><span class="p">:</span><span class="w"> </span><span class="kp">&amp;</span><span class="nc">mut</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="kt">i32</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">C</span><span class="p">:</span><span class="w"> </span><span class="kp">&amp;</span><span class="nc">mut</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="kt">i32</span><span class="o">&gt;</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-9-26" id="__codelineno-9-26" name="__codelineno-9-26"></a><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">A</span><span class="p">.</span><span class="n">len</span><span class="p">()</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="kt">i32</span><span class="p">;</span>
<a href="#__codelineno-9-27" id="__codelineno-9-27" name="__codelineno-9-27"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-9-28" id="__codelineno-9-28" name="__codelineno-9-28"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">C</span><span class="p">);</span>
<a href="#__codelineno-9-29" id="__codelineno-9-29" name="__codelineno-9-29"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.c</span><pre><span></span><code><a href="#__codelineno-10-1" id="__codelineno-10-1" name="__codelineno-10-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-10-2" id="__codelineno-10-2" name="__codelineno-10-2"></a><span class="kt">void</span><span class="w"> </span><span class="nf">move</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">srcSize</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">tarSize</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-10-3" id="__codelineno-10-3" name="__codelineno-10-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-10-4" id="__codelineno-10-4" name="__codelineno-10-4"></a><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">pan</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">src</span><span class="p">[</span><span class="o">*</span><span class="n">srcSize</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">];</span>
<a href="#__codelineno-10-5" id="__codelineno-10-5" name="__codelineno-10-5"></a><span class="w"> </span><span class="n">src</span><span class="p">[</span><span class="o">*</span><span class="n">srcSize</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span>
<a href="#__codelineno-10-6" id="__codelineno-10-6" name="__codelineno-10-6"></a><span class="w"> </span><span class="p">(</span><span class="o">*</span><span class="n">srcSize</span><span class="p">)</span><span class="o">--</span><span class="p">;</span>
<a href="#__codelineno-10-7" id="__codelineno-10-7" name="__codelineno-10-7"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-10-8" id="__codelineno-10-8" name="__codelineno-10-8"></a><span class="w"> </span><span class="n">tar</span><span class="p">[</span><span class="o">*</span><span class="n">tarSize</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">pan</span><span class="p">;</span>
<a href="#__codelineno-10-9" id="__codelineno-10-9" name="__codelineno-10-9"></a><span class="w"> </span><span class="p">(</span><span class="o">*</span><span class="n">tarSize</span><span class="p">)</span><span class="o">++</span><span class="p">;</span>
<a href="#__codelineno-10-10" id="__codelineno-10-10" name="__codelineno-10-10"></a><span class="p">}</span>
<a href="#__codelineno-10-11" id="__codelineno-10-11" name="__codelineno-10-11"></a>
<a href="#__codelineno-10-12" id="__codelineno-10-12" name="__codelineno-10-12"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-10-13" id="__codelineno-10-13" name="__codelineno-10-13"></a><span class="kt">void</span><span class="w"> </span><span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">srcSize</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">bufSize</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">tarSize</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-10-14" id="__codelineno-10-14" name="__codelineno-10-14"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-10-15" id="__codelineno-10-15" name="__codelineno-10-15"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-10-16" id="__codelineno-10-16" name="__codelineno-10-16"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">srcSize</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">tarSize</span><span class="p">);</span>
<a href="#__codelineno-10-17" id="__codelineno-10-17" name="__codelineno-10-17"></a><span class="w"> </span><span class="k">return</span><span class="p">;</span>
<a href="#__codelineno-10-18" id="__codelineno-10-18" name="__codelineno-10-18"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-10-19" id="__codelineno-10-19" name="__codelineno-10-19"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-10-20" id="__codelineno-10-20" name="__codelineno-10-20"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">srcSize</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">tarSize</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">bufSize</span><span class="p">);</span>
<a href="#__codelineno-10-21" id="__codelineno-10-21" name="__codelineno-10-21"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-10-22" id="__codelineno-10-22" name="__codelineno-10-22"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">srcSize</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">tarSize</span><span class="p">);</span>
<a href="#__codelineno-10-23" id="__codelineno-10-23" name="__codelineno-10-23"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-10-24" id="__codelineno-10-24" name="__codelineno-10-24"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">bufSize</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">srcSize</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">tarSize</span><span class="p">);</span>
<a href="#__codelineno-10-25" id="__codelineno-10-25" name="__codelineno-10-25"></a><span class="p">}</span>
<a href="#__codelineno-10-26" id="__codelineno-10-26" name="__codelineno-10-26"></a>
<a href="#__codelineno-10-27" id="__codelineno-10-27" name="__codelineno-10-27"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-10-28" id="__codelineno-10-28" name="__codelineno-10-28"></a><span class="kt">void</span><span class="w"> </span><span class="nf">solveHanota</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">ASize</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">BSize</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">C</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="n">CSize</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-10-29" id="__codelineno-10-29" name="__codelineno-10-29"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-10-30" id="__codelineno-10-30" name="__codelineno-10-30"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="o">*</span><span class="n">ASize</span><span class="p">,</span><span class="w"> </span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">ASize</span><span class="p">,</span><span class="w"> </span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">BSize</span><span class="p">,</span><span class="w"> </span><span class="n">C</span><span class="p">,</span><span class="w"> </span><span class="n">CSize</span><span class="p">);</span>
<a href="#__codelineno-10-31" id="__codelineno-10-31" name="__codelineno-10-31"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.kt</span><pre><span></span><code><a href="#__codelineno-11-1" id="__codelineno-11-1" name="__codelineno-11-1"></a><span class="cm">/* Переместить один диск */</span>
<a href="#__codelineno-11-2" id="__codelineno-11-2" name="__codelineno-11-2"></a><span class="kd">fun</span><span class="w"> </span><span class="nf">move</span><span class="p">(</span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="n">MutableList</span><span class="o">&lt;</span><span class="kt">Int</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="n">MutableList</span><span class="o">&lt;</span><span class="kt">Int</span><span class="o">&gt;</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-11-3" id="__codelineno-11-3" name="__codelineno-11-3"></a><span class="w"> </span><span class="c1">// Снять диск с вершины src</span>
<a href="#__codelineno-11-4" id="__codelineno-11-4" name="__codelineno-11-4"></a><span class="w"> </span><span class="kd">val</span><span class="w"> </span><span class="nv">pan</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">src</span><span class="p">.</span><span class="na">removeAt</span><span class="p">(</span><span class="n">src</span><span class="p">.</span><span class="na">size</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">)</span>
<a href="#__codelineno-11-5" id="__codelineno-11-5" name="__codelineno-11-5"></a><span class="w"> </span><span class="c1">// Положить диск на вершину tar</span>
<a href="#__codelineno-11-6" id="__codelineno-11-6" name="__codelineno-11-6"></a><span class="w"> </span><span class="n">tar</span><span class="p">.</span><span class="na">add</span><span class="p">(</span><span class="n">pan</span><span class="p">)</span>
<a href="#__codelineno-11-7" id="__codelineno-11-7" name="__codelineno-11-7"></a><span class="p">}</span>
<a href="#__codelineno-11-8" id="__codelineno-11-8" name="__codelineno-11-8"></a>
<a href="#__codelineno-11-9" id="__codelineno-11-9" name="__codelineno-11-9"></a><span class="cm">/* Решить задачу Ханойской башни f(i) */</span>
<a href="#__codelineno-11-10" id="__codelineno-11-10" name="__codelineno-11-10"></a><span class="kd">fun</span><span class="w"> </span><span class="nf">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">:</span><span class="w"> </span><span class="kt">Int</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">:</span><span class="w"> </span><span class="n">MutableList</span><span class="o">&lt;</span><span class="kt">Int</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">:</span><span class="w"> </span><span class="n">MutableList</span><span class="o">&lt;</span><span class="kt">Int</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">:</span><span class="w"> </span><span class="n">MutableList</span><span class="o">&lt;</span><span class="kt">Int</span><span class="o">&gt;</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-11-11" id="__codelineno-11-11" name="__codelineno-11-11"></a><span class="w"> </span><span class="c1">// Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-11-12" id="__codelineno-11-12" name="__codelineno-11-12"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-11-13" id="__codelineno-11-13" name="__codelineno-11-13"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-11-14" id="__codelineno-11-14" name="__codelineno-11-14"></a><span class="w"> </span><span class="k">return</span>
<a href="#__codelineno-11-15" id="__codelineno-11-15" name="__codelineno-11-15"></a><span class="w"> </span><span class="p">}</span>
<a href="#__codelineno-11-16" id="__codelineno-11-16" name="__codelineno-11-16"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-11-17" id="__codelineno-11-17" name="__codelineno-11-17"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">)</span>
<a href="#__codelineno-11-18" id="__codelineno-11-18" name="__codelineno-11-18"></a><span class="w"> </span><span class="c1">// Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-11-19" id="__codelineno-11-19" name="__codelineno-11-19"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-11-20" id="__codelineno-11-20" name="__codelineno-11-20"></a><span class="w"> </span><span class="c1">// Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-11-21" id="__codelineno-11-21" name="__codelineno-11-21"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-11-22" id="__codelineno-11-22" name="__codelineno-11-22"></a><span class="p">}</span>
<a href="#__codelineno-11-23" id="__codelineno-11-23" name="__codelineno-11-23"></a>
<a href="#__codelineno-11-24" id="__codelineno-11-24" name="__codelineno-11-24"></a><span class="cm">/* Решить задачу Ханойской башни */</span>
<a href="#__codelineno-11-25" id="__codelineno-11-25" name="__codelineno-11-25"></a><span class="kd">fun</span><span class="w"> </span><span class="nf">solveHanota</span><span class="p">(</span><span class="n">A</span><span class="p">:</span><span class="w"> </span><span class="n">MutableList</span><span class="o">&lt;</span><span class="kt">Int</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">B</span><span class="p">:</span><span class="w"> </span><span class="n">MutableList</span><span class="o">&lt;</span><span class="kt">Int</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">C</span><span class="p">:</span><span class="w"> </span><span class="n">MutableList</span><span class="o">&lt;</span><span class="kt">Int</span><span class="o">&gt;</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<a href="#__codelineno-11-26" id="__codelineno-11-26" name="__codelineno-11-26"></a><span class="w"> </span><span class="kd">val</span><span class="w"> </span><span class="nv">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">A</span><span class="p">.</span><span class="na">size</span>
<a href="#__codelineno-11-27" id="__codelineno-11-27" name="__codelineno-11-27"></a><span class="w"> </span><span class="c1">// Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-11-28" id="__codelineno-11-28" name="__codelineno-11-28"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">C</span><span class="p">)</span>
<a href="#__codelineno-11-29" id="__codelineno-11-29" name="__codelineno-11-29"></a><span class="p">}</span>
</code></pre></div>
</div>
<div class="tabbed-block">
<div class="highlight"><span class="filename">hanota.rb</span><pre><span></span><code><a href="#__codelineno-12-1" id="__codelineno-12-1" name="__codelineno-12-1"></a><span class="c1">### Переместить один диск ###</span>
<a href="#__codelineno-12-2" id="__codelineno-12-2" name="__codelineno-12-2"></a><span class="k">def</span><span class="w"> </span><span class="nf">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-12-3" id="__codelineno-12-3" name="__codelineno-12-3"></a><span class="w"> </span><span class="c1"># Снять диск с вершины src</span>
<a href="#__codelineno-12-4" id="__codelineno-12-4" name="__codelineno-12-4"></a><span class="w"> </span><span class="n">pan</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">src</span><span class="o">.</span><span class="n">pop</span>
<a href="#__codelineno-12-5" id="__codelineno-12-5" name="__codelineno-12-5"></a><span class="w"> </span><span class="c1"># Положить диск на вершину tar</span>
<a href="#__codelineno-12-6" id="__codelineno-12-6" name="__codelineno-12-6"></a><span class="w"> </span><span class="n">tar</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="n">pan</span>
<a href="#__codelineno-12-7" id="__codelineno-12-7" name="__codelineno-12-7"></a><span class="k">end</span>
<a href="#__codelineno-12-8" id="__codelineno-12-8" name="__codelineno-12-8"></a>
<a href="#__codelineno-12-9" id="__codelineno-12-9" name="__codelineno-12-9"></a><span class="c1">### Решить задачу Ханойской башни f(i) ###</span>
<a href="#__codelineno-12-10" id="__codelineno-12-10" name="__codelineno-12-10"></a><span class="k">def</span><span class="w"> </span><span class="nf">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-12-11" id="__codelineno-12-11" name="__codelineno-12-11"></a><span class="w"> </span><span class="c1"># Если в src остался только один диск, сразу переместить его в tar</span>
<a href="#__codelineno-12-12" id="__codelineno-12-12" name="__codelineno-12-12"></a><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">1</span>
<a href="#__codelineno-12-13" id="__codelineno-12-13" name="__codelineno-12-13"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-12-14" id="__codelineno-12-14" name="__codelineno-12-14"></a><span class="w"> </span><span class="k">return</span>
<a href="#__codelineno-12-15" id="__codelineno-12-15" name="__codelineno-12-15"></a><span class="w"> </span><span class="k">end</span>
<a href="#__codelineno-12-16" id="__codelineno-12-16" name="__codelineno-12-16"></a>
<a href="#__codelineno-12-17" id="__codelineno-12-17" name="__codelineno-12-17"></a><span class="w"> </span><span class="c1"># Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar</span>
<a href="#__codelineno-12-18" id="__codelineno-12-18" name="__codelineno-12-18"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">)</span>
<a href="#__codelineno-12-19" id="__codelineno-12-19" name="__codelineno-12-19"></a><span class="w"> </span><span class="c1"># Подзадача f(1): переместить оставшийся один диск из src в tar</span>
<a href="#__codelineno-12-20" id="__codelineno-12-20" name="__codelineno-12-20"></a><span class="w"> </span><span class="n">move</span><span class="p">(</span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-12-21" id="__codelineno-12-21" name="__codelineno-12-21"></a><span class="w"> </span><span class="c1"># Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src</span>
<a href="#__codelineno-12-22" id="__codelineno-12-22" name="__codelineno-12-22"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">buf</span><span class="p">,</span><span class="w"> </span><span class="n">src</span><span class="p">,</span><span class="w"> </span><span class="n">tar</span><span class="p">)</span>
<a href="#__codelineno-12-23" id="__codelineno-12-23" name="__codelineno-12-23"></a><span class="k">end</span>
<a href="#__codelineno-12-24" id="__codelineno-12-24" name="__codelineno-12-24"></a>
<a href="#__codelineno-12-25" id="__codelineno-12-25" name="__codelineno-12-25"></a><span class="c1">### Решить задачу Ханойской башни ###</span>
<a href="#__codelineno-12-26" id="__codelineno-12-26" name="__codelineno-12-26"></a><span class="k">def</span><span class="w"> </span><span class="nf">solve_hanota</span><span class="p">(</span><span class="n">_A</span><span class="p">,</span><span class="w"> </span><span class="n">_B</span><span class="p">,</span><span class="w"> </span><span class="n">_C</span><span class="p">)</span>
<a href="#__codelineno-12-27" id="__codelineno-12-27" name="__codelineno-12-27"></a><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">_A</span><span class="o">.</span><span class="n">length</span>
<a href="#__codelineno-12-28" id="__codelineno-12-28" name="__codelineno-12-28"></a><span class="w"> </span><span class="c1"># Переместить верхние n дисков из A в C с помощью B</span>
<a href="#__codelineno-12-29" id="__codelineno-12-29" name="__codelineno-12-29"></a><span class="w"> </span><span class="n">dfs</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="n">_A</span><span class="p">,</span><span class="w"> </span><span class="n">_B</span><span class="p">,</span><span class="w"> </span><span class="n">_C</span><span class="p">)</span>
<a href="#__codelineno-12-30" id="__codelineno-12-30" name="__codelineno-12-30"></a><span class="k">end</span>
</code></pre></div>
</div>
</div>
</div>
<details class="pythontutor">
<summary>Визуализация кода</summary>
<p><div style="height: 549px; width: 100%;"><iframe class="pythontutor-iframe" src="https://pythontutor.com/iframe-embed.html#code=def%20move%28src%3A%20list%5Bint%5D%2C%20tar%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%D0%9F%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%BE%D0%B4%D0%B8%D0%BD%20%D0%B4%D0%B8%D1%81%D0%BA%22%22%22%0A%20%20%20%20%23%20%D0%A1%D0%BD%D1%8F%D1%82%D1%8C%20%D0%B4%D0%B8%D1%81%D0%BA%20%D1%81%20%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D1%8B%20src%0A%20%20%20%20pan%20%3D%20src.pop%28%29%0A%20%20%20%20%23%20%D0%9F%D0%BE%D0%BB%D0%BE%D0%B6%D0%B8%D1%82%D1%8C%20%D0%B4%D0%B8%D1%81%D0%BA%20%D0%BD%D0%B0%20%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D1%83%20tar%0A%20%20%20%20tar.append%28pan%29%0A%0A%0Adef%20dfs%28i%3A%20int%2C%20src%3A%20list%5Bint%5D%2C%20buf%3A%20list%5Bint%5D%2C%20tar%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%D0%A0%D0%B5%D1%88%D0%B8%D1%82%D1%8C%20%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D1%83%20%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%BE%D0%B9%20%D0%B1%D0%B0%D1%88%D0%BD%D0%B8%20f%28i%29%22%22%22%0A%20%20%20%20%23%20%D0%95%D1%81%D0%BB%D0%B8%20%D0%B2%20src%20%D0%BE%D1%81%D1%82%D0%B0%D0%BB%D1%81%D1%8F%20%D1%82%D0%BE%D0%BB%D1%8C%D0%BA%D0%BE%20%D0%BE%D0%B4%D0%B8%D0%BD%20%D0%B4%D0%B8%D1%81%D0%BA%2C%20%D1%81%D1%80%D0%B0%D0%B7%D1%83%20%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%B5%D0%B3%D0%BE%20%D0%B2%20tar%0A%20%20%20%20if%20i%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20move%28src%2C%20tar%29%0A%20%20%20%20%20%20%20%20return%0A%20%20%20%20%23%20%D0%9F%D0%BE%D0%B4%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%20f%28i-1%29%3A%20%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%B2%D0%B5%D1%80%D1%85%D0%BD%D0%B8%D0%B5%20i-1%20%D0%B4%D0%B8%D1%81%D0%BA%D0%BE%D0%B2%20%D0%B8%D0%B7%20src%20%D0%B2%20buf%20%D1%81%20%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E%20tar%0A%20%20%20%20dfs%28i%20-%201%2C%20src%2C%20tar%2C%20buf%29%0A%20%20%20%20%23%20%D0%9F%D0%BE%D0%B4%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%20f%281%29%3A%20%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%BE%D1%81%D1%82%D0%B0%D0%B2%D1%88%D0%B8%D0%B9%D1%81%D1%8F%20%D0%BE%D0%B4%D0%B8%D0%BD%20%D0%B4%D0%B8%D1%81%D0%BA%20%D0%B8%D0%B7%20src%20%D0%B2%20tar%0A%20%20%20%20move%28src%2C%20tar%29%0A%20%20%20%20%23%20%D0%9F%D0%BE%D0%B4%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%20f%28i-1%29%3A%20%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%B2%D0%B5%D1%80%D1%85%D0%BD%D0%B8%D0%B5%20i-1%20%D0%B4%D0%B8%D1%81%D0%BA%D0%BE%D0%B2%20%D0%B8%D0%B7%20buf%20%D0%B2%20tar%20%D1%81%20%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E%20src%0A%20%20%20%20dfs%28i%20-%201%2C%20buf%2C%20src%2C%20tar%29%0A%0A%0Adef%20solve_hanota%28A%3A%20list%5Bint%5D%2C%20B%3A%20list%5Bint%5D%2C%20C%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%D0%A0%D0%B5%D1%88%D0%B8%D1%82%D1%8C%20%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D1%83%20%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%BE%D0%B9%20%D0%B1%D0%B0%D1%88%D0%BD%D0%B8%22%22%22%0A%20%20%20%20n%20%3D%20len%28A%29%0A%20%20%20%20%23%20%D0%9F%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%B2%D0%B5%D1%80%D1%85%D0%BD%D0%B8%D0%B5%20n%20%D0%B4%D0%B8%D1%81%D0%BA%D0%BE%D0%B2%20%D0%B8%D0%B7%20A%20%D0%B2%20C%20%D1%81%20%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E%20B%0A%20%20%20%20dfs%28n%2C%20A%2C%20B%2C%20C%29%0A%0A%0A%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%D0%A5%D0%B2%D0%BE%D1%81%D1%82%20%D1%81%D0%BF%D0%B8%D1%81%D0%BA%D0%B0%20%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D1%83%D0%B5%D1%82%20%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%B5%20%D1%81%D1%82%D0%BE%D0%BB%D0%B1%D1%86%D0%B0%0A%20%20%20%20A%20%3D%20%5B5%2C%204%2C%203%2C%202%2C%201%5D%0A%20%20%20%20B%20%3D%20%5B%5D%0A%20%20%20%20C%20%3D%20%5B%5D%0A%20%20%20%20print%28%22%D0%98%D1%81%D1%85%D0%BE%D0%B4%D0%BD%D0%BE%D0%B5%20%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5%3A%22%29%0A%20%20%20%20print%28f%22A%20%3D%20%7BA%7D%22%29%0A%20%20%20%20print%28f%22B%20%3D%20%7BB%7D%22%29%0A%20%20%20%20print%28f%22C%20%3D%20%7BC%7D%22%29%0A%0A%20%20%20%20solve_hanota%28A%2C%20B%2C%20C%29%0A%0A%20%20%20%20print%28%22%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%20%D0%B7%D0%B0%D0%B2%D0%B5%D1%80%D1%88%D0%B5%D0%BD%D0%B8%D1%8F%20%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D1%8F%20%D0%B4%D0%B8%D1%81%D0%BA%D0%BE%D0%B2%3A%22%29%0A%20%20%20%20print%28f%22A%20%3D%20%7BA%7D%22%29%0A%20%20%20%20print%28f%22B%20%3D%20%7BB%7D%22%29%0A%20%20%20%20print%28f%22C%20%3D%20%7BC%7D%22%29&amp;codeDivHeight=472&amp;codeDivWidth=350&amp;cumulative=false&amp;curInstr=12&amp;heapPrimitives=nevernest&amp;origin=opt-frontend.js&amp;py=311&amp;rawInputLstJSON=%5B%5D&amp;textReferences=false" title="Визуализация кода"> </iframe></div>
<div style="margin-top: 5px;"><a href="https://pythontutor.com/iframe-embed.html#code=def%20move%28src%3A%20list%5Bint%5D%2C%20tar%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%D0%9F%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%BE%D0%B4%D0%B8%D0%BD%20%D0%B4%D0%B8%D1%81%D0%BA%22%22%22%0A%20%20%20%20%23%20%D0%A1%D0%BD%D1%8F%D1%82%D1%8C%20%D0%B4%D0%B8%D1%81%D0%BA%20%D1%81%20%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D1%8B%20src%0A%20%20%20%20pan%20%3D%20src.pop%28%29%0A%20%20%20%20%23%20%D0%9F%D0%BE%D0%BB%D0%BE%D0%B6%D0%B8%D1%82%D1%8C%20%D0%B4%D0%B8%D1%81%D0%BA%20%D0%BD%D0%B0%20%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D1%83%20tar%0A%20%20%20%20tar.append%28pan%29%0A%0A%0Adef%20dfs%28i%3A%20int%2C%20src%3A%20list%5Bint%5D%2C%20buf%3A%20list%5Bint%5D%2C%20tar%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%D0%A0%D0%B5%D1%88%D0%B8%D1%82%D1%8C%20%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D1%83%20%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%BE%D0%B9%20%D0%B1%D0%B0%D1%88%D0%BD%D0%B8%20f%28i%29%22%22%22%0A%20%20%20%20%23%20%D0%95%D1%81%D0%BB%D0%B8%20%D0%B2%20src%20%D0%BE%D1%81%D1%82%D0%B0%D0%BB%D1%81%D1%8F%20%D1%82%D0%BE%D0%BB%D1%8C%D0%BA%D0%BE%20%D0%BE%D0%B4%D0%B8%D0%BD%20%D0%B4%D0%B8%D1%81%D0%BA%2C%20%D1%81%D1%80%D0%B0%D0%B7%D1%83%20%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%B5%D0%B3%D0%BE%20%D0%B2%20tar%0A%20%20%20%20if%20i%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20move%28src%2C%20tar%29%0A%20%20%20%20%20%20%20%20return%0A%20%20%20%20%23%20%D0%9F%D0%BE%D0%B4%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%20f%28i-1%29%3A%20%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%B2%D0%B5%D1%80%D1%85%D0%BD%D0%B8%D0%B5%20i-1%20%D0%B4%D0%B8%D1%81%D0%BA%D0%BE%D0%B2%20%D0%B8%D0%B7%20src%20%D0%B2%20buf%20%D1%81%20%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E%20tar%0A%20%20%20%20dfs%28i%20-%201%2C%20src%2C%20tar%2C%20buf%29%0A%20%20%20%20%23%20%D0%9F%D0%BE%D0%B4%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%20f%281%29%3A%20%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%BE%D1%81%D1%82%D0%B0%D0%B2%D1%88%D0%B8%D0%B9%D1%81%D1%8F%20%D0%BE%D0%B4%D0%B8%D0%BD%20%D0%B4%D0%B8%D1%81%D0%BA%20%D0%B8%D0%B7%20src%20%D0%B2%20tar%0A%20%20%20%20move%28src%2C%20tar%29%0A%20%20%20%20%23%20%D0%9F%D0%BE%D0%B4%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%20f%28i-1%29%3A%20%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%B2%D0%B5%D1%80%D1%85%D0%BD%D0%B8%D0%B5%20i-1%20%D0%B4%D0%B8%D1%81%D0%BA%D0%BE%D0%B2%20%D0%B8%D0%B7%20buf%20%D0%B2%20tar%20%D1%81%20%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E%20src%0A%20%20%20%20dfs%28i%20-%201%2C%20buf%2C%20src%2C%20tar%29%0A%0A%0Adef%20solve_hanota%28A%3A%20list%5Bint%5D%2C%20B%3A%20list%5Bint%5D%2C%20C%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%D0%A0%D0%B5%D1%88%D0%B8%D1%82%D1%8C%20%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D1%83%20%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%BE%D0%B9%20%D0%B1%D0%B0%D1%88%D0%BD%D0%B8%22%22%22%0A%20%20%20%20n%20%3D%20len%28A%29%0A%20%20%20%20%23%20%D0%9F%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D0%B8%D1%82%D1%8C%20%D0%B2%D0%B5%D1%80%D1%85%D0%BD%D0%B8%D0%B5%20n%20%D0%B4%D0%B8%D1%81%D0%BA%D0%BE%D0%B2%20%D0%B8%D0%B7%20A%20%D0%B2%20C%20%D1%81%20%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E%20B%0A%20%20%20%20dfs%28n%2C%20A%2C%20B%2C%20C%29%0A%0A%0A%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%D0%A5%D0%B2%D0%BE%D1%81%D1%82%20%D1%81%D0%BF%D0%B8%D1%81%D0%BA%D0%B0%20%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D1%83%D0%B5%D1%82%20%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%B5%20%D1%81%D1%82%D0%BE%D0%BB%D0%B1%D1%86%D0%B0%0A%20%20%20%20A%20%3D%20%5B5%2C%204%2C%203%2C%202%2C%201%5D%0A%20%20%20%20B%20%3D%20%5B%5D%0A%20%20%20%20C%20%3D%20%5B%5D%0A%20%20%20%20print%28%22%D0%98%D1%81%D1%85%D0%BE%D0%B4%D0%BD%D0%BE%D0%B5%20%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5%3A%22%29%0A%20%20%20%20print%28f%22A%20%3D%20%7BA%7D%22%29%0A%20%20%20%20print%28f%22B%20%3D%20%7BB%7D%22%29%0A%20%20%20%20print%28f%22C%20%3D%20%7BC%7D%22%29%0A%0A%20%20%20%20solve_hanota%28A%2C%20B%2C%20C%29%0A%0A%20%20%20%20print%28%22%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%20%D0%B7%D0%B0%D0%B2%D0%B5%D1%80%D1%88%D0%B5%D0%BD%D0%B8%D1%8F%20%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D1%8F%20%D0%B4%D0%B8%D1%81%D0%BA%D0%BE%D0%B2%3A%22%29%0A%20%20%20%20print%28f%22A%20%3D%20%7BA%7D%22%29%0A%20%20%20%20print%28f%22B%20%3D%20%7BB%7D%22%29%0A%20%20%20%20print%28f%22C%20%3D%20%7BC%7D%22%29&amp;codeDivHeight=800&amp;codeDivWidth=600&amp;cumulative=false&amp;curInstr=12&amp;heapPrimitives=nevernest&amp;origin=opt-frontend.js&amp;py=311&amp;rawInputLstJSON=%5B%5D&amp;textReferences=false" rel="noopener noreferrer" target="_blank">Во весь экран &gt;</a></div></p>
</details>
<p>Как показано на рисунке 12-15, задача о Ханойской башне формирует дерево рекурсии высоты <span class="arithmatex">\(n\)</span> , в котором каждый узел представляет подзадачу и соответствует одному открытому вызову <code>dfs()</code>. <strong>Поэтому временная сложность равна <span class="arithmatex">\(O(2^n)\)</span> , а пространственная сложность равна <span class="arithmatex">\(O(n)\)</span></strong> .</p>
<p><ha-svg-figure class="animation-figure" data-book-key="ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_recursive_tree.png" data-dark-src="/assets/figure-svg/figures/ad62baee2ff6696462902606.json" data-src="/assets/figure-svg/figures/d21b71e65aed8ec2f914865a.json" style=";--figure-ratio:960.0/540.0"><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_recursive_tree.svg" data-theme="light" tabindex="-1" type="image/svg+xml">Дерево рекурсии задачи о Ханойской башне</object><object data="/ru/chapter_divide_and_conquer/hanota_problem.assets/hanota_recursive_tree.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">Дерево рекурсии задачи о Ханойской башне</object></ha-svg-figure></p>
<p align="center"> Рисунок 12-15   Дерево рекурсии задачи о Ханойской башне </p>
<div class="admonition quote">
<p class="admonition-title">Quote</p>
<p>Задача о Ханойской башне происходит из древней легенды. В одном из храмов древней Индии монахи имели три высоких алмазных стержня и <span class="arithmatex">\(64\)</span> золотых диска разного размера. Монахи непрерывно перекладывали диски и верили, что в тот момент, когда последний диск будет правильно перенесен, мир подойдет к концу.</p>
<p>Однако даже если бы монахи перемещали по одному диску в секунду, им понадобилось бы примерно <span class="arithmatex">\(2^{64} \approx 1.84×10^{19}\)</span> секунд, то есть около <span class="arithmatex">\(585\)</span> миллиардов лет, что намного превышает текущую оценку возраста Вселенной. Поэтому, если легенда и верна, нам, вероятно, пока не о чем беспокоиться.</p>
</div>
<!-- Source file information -->
<!-- Was this page helpful? -->
<!-- Previous and next pages link -->
<nav aria-label="Нижний колонтитул" class="md-footer__inner md-grid">
<!-- Link to previous page -->
<a aria-label="Назад: 12.3 Задача построения двоичного дерева" class="md-footer__link md-footer__link--prev" href="../build_binary_tree_problem/" rel="prev">
<div class="md-footer__button md-icon">
<svg class="lucide lucide-arrow-left" fill="none" stroke="currentColor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m12 19-7-7 7-7M19 12H5"></path></svg>
</div>
<div class="md-footer__title">
<span class="md-footer__direction">
Назад
</span>
<div class="md-ellipsis">
12.3 Задача построения двоичного дерева
</div>
</div>
</a>
<!-- Link to next page -->
<a aria-label="Вперед: 12.5 Резюме" class="md-footer__link md-footer__link--next" href="../summary/" rel="next">
<div class="md-footer__title">
<span class="md-footer__direction">
Вперед
</span>
<div class="md-ellipsis">
12.5 Резюме
</div>
</div>
<div class="md-footer__button md-icon">
<svg class="lucide lucide-arrow-right" fill="none" stroke="currentColor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M5 12h14M12 5l7 7-7 7"></path></svg>
</div>
</a>
</nav>
<!-- Comment system -->
<!-- Check-in button above comments -->
<h5 align="center" id="__comments">Оставляйте свои идеи, вопросы и предложения в комментариях</h5>
<!-- Insert generated snippet here -->
<script async="" crossorigin="anonymous" data-category="Announcements" data-category-id="DIC_kwDOIXtSq84CSZk_" data-emit-metadata="1" data-input-position="top" data-lang="ru" data-mapping="pathname" data-reactions-enabled="1" data-repo="krahets/hello-algo" data-repo-id="R_kgDOIXtSqw" data-strict="1" data-theme="light" src="https://giscus.app/client.js">
</script>
<!-- Synchronize Giscus theme with palette -->
<script>
var giscus = document.querySelector("script[src*=giscus]")
function getGiscusTheme() {
var palette = __md_get("__palette")
var isDark = palette && typeof palette.color === "object" && palette.color.scheme === "slate"
return isDark ? "noborder_dark" : "light"
}
/* Set palette on initial load */
giscus.setAttribute("data-theme", getGiscusTheme())
/* The Giscus client creates the iframe asynchronously with an English title. */
;(function() {
function labelCommentsFrame() {
var frame = document.querySelector("iframe.giscus-frame")
if (!frame) return false
frame.setAttribute("title", "Комментарии")
return true
}
if (labelCommentsFrame()) return
var observer = new MutationObserver(function() {
if (labelCommentsFrame()) observer.disconnect()
})
observer.observe(giscus.parentElement, { childList: true, subtree: true })
})()
/* Register event handlers after documented loaded */
document.addEventListener("DOMContentLoaded", function() {
var ref = document.querySelector("[data-md-component=palette]")
if (!ref) return
ref.addEventListener("change", function() {
var theme = getGiscusTheme()
/* Instruct Giscus to change theme */
var frame = document.querySelector(".giscus-frame")
if (!frame) return
frame.contentWindow.postMessage(
{ giscus: { setConfig: { theme } } },
"https://giscus.app"
)
})
})
</script>
</article>
</div>
<script>var tabs=__md_get("__tabs");if(Array.isArray(tabs))e:for(var set of document.querySelectorAll(".tabbed-set")){var labels=set.querySelector(".tabbed-labels");for(var tab of tabs)for(var label of labels.getElementsByTagName("label"))if(label.innerText.trim()===tab){var input=document.getElementById(label.htmlFor);input.checked=!0;continue e}}</script>
<script>var target=document.getElementById(location.hash.slice(1));target&&target.name&&(target.checked=target.name.startsWith("__tabbed_"))</script>
</div>
</main>
<footer class="md-footer">
<div class="md-footer-meta md-typeset">
<div class="md-footer-meta__inner md-grid">
<div class="md-copyright">
<div class="md-copyright__highlight">
Copyright © 2026 krahets<br/>The website content is licensed under <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC BY-NC-SA 4.0</a>
</div>
</div>
<div class="md-social">
<a class="md-social__link" href="https://github.com/krahets" rel="noopener" target="_blank" title="github.com">
<svg viewbox="0 0 512 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M173.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6m-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3m44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9M252.8 8C114.1 8 8 113.3 8 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C436.2 457.8 504 362.9 504 252 504 113.3 391.5 8 252.8 8M105.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1m-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7m32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1m-11.4-14.7c-1.6 1-1.6 3.6 0 5.9s4.3 3.3 5.6 2.3c1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2" fill="currentColor"></path></svg>
</a>
<a class="md-social__link" href="https://twitter.com/krahets" rel="noopener" target="_blank" title="twitter.com">
<svg viewbox="0 0 448 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M357.2 48h70.6L273.6 224.2 455 464H313L201.7 318.6 74.5 464H3.8l164.9-188.5L-5.2 48h145.6l100.5 132.9zm-24.8 373.8h39.1L119.1 88h-42z" fill="currentColor"></path></svg>
</a>
<a class="md-social__link" href="https://leetcode.cn/u/jyd/" rel="noopener" target="_blank" title="leetcode.cn">
<svg viewbox="0 0 576 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M360.8 1.2c-17-4.9-34.7 5-39.6 22l-128 448c-4.9 17 5 34.7 22 39.6s34.7-5 39.6-22l128-448c4.9-17-5-34.7-22-39.6m64.6 136.1c-12.5 12.5-12.5 32.8 0 45.3l73.4 73.4-73.4 73.4c-12.5 12.5-12.5 32.8 0 45.3s32.8 12.5 45.3 0l96-96c12.5-12.5 12.5-32.8 0-45.3l-96-96c-12.5-12.5-32.8-12.5-45.3 0zm-274.7 0c-12.5-12.5-32.8-12.5-45.3 0l-96 96c-12.5 12.5-12.5 32.8 0 45.3l96 96c12.5 12.5 32.8 12.5 45.3 0s12.5-32.8 0-45.3L77.3 256l73.3-73.4c12.5-12.5 12.5-32.8 0-45.3z" fill="currentColor"></path></svg>
</a>
</div>
</div>
</div>
</footer>
</div>
<div class="md-dialog" data-md-component="dialog">
<div class="md-dialog__inner md-typeset"></div>
</div>
<script id="__config" type="application/json">{"annotate":null,"base":"../../","features":["content.action.edit","content.code.annotate","content.code.copy","content.tabs.link","content.tooltips","navigation.indexes","navigation.tracking","search.highlight","search.share","search.suggest","toc.follow"],"search":"../../assets/javascripts/workers/search.b6b7e04f.min.js","tags":null,"translations":{"clipboard.copied":"Скопировано в буфер","clipboard.copy":"Копировать в буфер","search.result.more.one":"Ещё 1 на этой странице","search.result.more.other":"Ещё # на этой странице","search.result.none":"Совпадений не найдено","search.result.one":"Найдено 1 совпадение","search.result.other":"Найдено совпадений: #","search.result.placeholder":"Начните печатать для поиска","search.result.term.missing":"Отсутствует","select.version":"Выберите версию"},"version":null}</script>
<script src="../../assets/javascripts/bundle.0d441547851f63d0e6614369d827335a9b125feca310fe06e17e6b9e15f96fa1.min.js"></script>
<script src="../../javascripts/mathjax.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.2/es5/tex-mml-chtml.min.js"></script>
<script src="../../javascripts/animation_player.js"></script>
<script defer="" src="/assets/figure-svg/js/bcdea376f01bc2bc0cac7c6c.js"></script><script defer="" src="/assets/figure-svg/js/e84f59519170c0f5ef238548.js"></script><script defer="" src="/assets/figure-svg/js/99a707e9f0a14d8280f16808.js"></script><script defer="" src="/assets/figure-svg/js/855fb5bb73c22cf5c2cea474.js"></script></body>
</html>