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

2573 lines
204 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="ja">
<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/ja/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:"Noto Sans JP";--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/e5c971c8d6831a5e9f627022.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>
</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/ja/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="この見出しへのリンク"></a></h1>
<p>マージソートと二分木の構築では、元の問題をそれぞれ半分の大きさの二つの部分問題に分解しました。一方、ハノイの塔の問題では、別の分解戦略を使います。</p>
<div class="admonition question">
<p class="admonition-title">問題</p>
<p>3 本の柱 <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>一度に動かせる円盤は 1 枚だけです。</li>
<li>小さな円盤は、常に大きな円盤の上に置かなければなりません。</li>
</ol>
</div>
<p><ha-svg-figure class="animation-figure" data-book-key="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_example.png" data-dark-src="/assets/figure-svg/figures/9e649c6522dae0931485eba3.json" data-src="/assets/figure-svg/figures/2ed43d164ceb46a5f8c9cdb2.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_example.svg" data-theme="light" tabindex="-1" type="image/svg+xml">ハノイの塔の問題の例</object><object data="/ja/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> は、<span class="arithmatex">\(3\)</span> 枚の円盤を <code>A</code> から <code>C</code> に移す問題です。</p>
<h3 id="1">1.   基本的な場合を考える<a class="headerlink" href="#1" title="この見出しへのリンク"></a></h3>
<p>図 12-11 のように、問題 <span class="arithmatex">\(f(1)\)</span>、つまり円盤が 1 枚だけの場合は、その円盤を <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="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step1.png" data-dark-src="/assets/figure-svg/figures/4f2f2466718f180c3a0e311d.json" data-src="/assets/figure-svg/figures/47a5d2183d07d819fcc0f044.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step1.svg" data-theme="light" tabindex="-1" type="image/svg+xml">大きさ 1 の問題の解</object><object data="/ja/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="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step2.png" data-dark-src="/assets/figure-svg/figures/898bfe6c6e2e5d1ca6a62e2a.json" data-src="/assets/figure-svg/figures/a1ae57cb57937fc290fc2758.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step2.svg" data-theme="light" tabindex="-1" type="image/svg+xml">円盤が 1 枚のハノイの塔:手順 2</object><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f1_step2.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">円盤が 1 枚のハノイの塔:手順 2</object></ha-svg-figure></p>
</div>
</div>
</div>
<p align="center"> 図 12-11   大きさ 1 の問題の解 </p>
<p>図 12-12 のように、問題 <span class="arithmatex">\(f(2)\)</span>、つまり円盤が 2 枚の場合は、<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="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step1.png" data-dark-src="/assets/figure-svg/figures/c2ef307ddee844ceb6e9a4d4.json" data-src="/assets/figure-svg/figures/e60962e8fe62341e74836337.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step1.svg" data-theme="light" tabindex="-1" type="image/svg+xml">大きさ 2 の問題の解</object><object data="/ja/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="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step2.png" data-dark-src="/assets/figure-svg/figures/2cd109351e93c471a2ffc196.json" data-src="/assets/figure-svg/figures/020a9ab191afe96aae2a3bc8.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step2.svg" data-theme="light" tabindex="-1" type="image/svg+xml">円盤が 2 枚のハノイの塔:手順 2</object><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step2.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">円盤が 2 枚のハノイの塔:手順 2</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step3.png" data-dark-src="/assets/figure-svg/figures/86a6a9a6d3c9a563c699ef98.json" data-src="/assets/figure-svg/figures/a0411e66d57b9f48ddc24fdc.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step3.svg" data-theme="light" tabindex="-1" type="image/svg+xml">円盤が 2 枚のハノイの塔:手順 3</object><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step3.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">円盤が 2 枚のハノイの塔:手順 3</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step4.png" data-dark-src="/assets/figure-svg/figures/e77a92ad881072ee8bd65cfd.json" data-src="/assets/figure-svg/figures/32d2cf59653e3bb4ca62476c.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step4.svg" data-theme="light" tabindex="-1" type="image/svg+xml">円盤が 2 枚のハノイの塔:手順 4</object><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f2_step4.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">円盤が 2 枚のハノイの塔:手順 4</object></ha-svg-figure></p>
</div>
</div>
</div>
<p align="center"> 図 12-12   大きさ 2 の問題の解 </p>
<p>問題 <span class="arithmatex">\(f(2)\)</span> を解く手順は、<strong><code>B</code> を使って 2 枚の円盤を <code>A</code> から <code>C</code> に移すこと</strong>とまとめられます。このとき、<code>C</code> を目的の柱、<code>B</code> を補助の柱と呼びます。</p>
<h3 id="2">2.   部分問題への分解<a class="headerlink" href="#2" title="この見出しへのリンク"></a></h3>
<p>問題 <span class="arithmatex">\(f(3)\)</span>、つまり円盤が 3 枚の場合は、少し複雑になります。</p>
<p><span class="arithmatex">\(f(1)\)</span> と <span class="arithmatex">\(f(2)\)</span> の解はわかっているので、分割統治の観点から、<strong><code>A</code> の上側の 2 枚を一つのまとまりとみなし</strong>、図 12-13 の手順を実行します。これで 3 枚の円盤を <code>A</code> から <code>C</code> に移せます。</p>
<ol>
<li><code>B</code> を目的の柱、<code>C</code> を補助の柱として、2 枚の円盤を <code>A</code> から <code>B</code> に移します。</li>
<li><code>A</code> に残った 1 枚を、<code>A</code> から <code>C</code> に直接移します。</li>
<li><code>C</code> を目的の柱、<code>A</code> を補助の柱として、2 枚の円盤を <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="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step1.png" data-dark-src="/assets/figure-svg/figures/bad0756348f5a1c39ff5fa45.json" data-src="/assets/figure-svg/figures/17c4362ce12138cf08b03b51.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step1.svg" data-theme="light" tabindex="-1" type="image/svg+xml">大きさ 3 の問題の解</object><object data="/ja/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="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step2.png" data-dark-src="/assets/figure-svg/figures/32aaaeb5e2f23bbfcb5dab94.json" data-src="/assets/figure-svg/figures/e28b4bb5893a351f8b5bb955.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step2.svg" data-theme="light" tabindex="-1" type="image/svg+xml">円盤が 3 枚のハノイの塔:手順 2</object><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step2.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">円盤が 3 枚のハノイの塔:手順 2</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step3.png" data-dark-src="/assets/figure-svg/figures/063d80c6f2441c7d716d1d58.json" data-src="/assets/figure-svg/figures/7c2165c23fbdd4afef162533.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step3.svg" data-theme="light" tabindex="-1" type="image/svg+xml">円盤が 3 枚のハノイの塔:手順 3</object><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step3.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">円盤が 3 枚のハノイの塔:手順 3</object></ha-svg-figure></p>
</div>
<div class="tabbed-block">
<p><ha-svg-figure class="animation-figure" data-book-key="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step4.png" data-dark-src="/assets/figure-svg/figures/837281f99ae376c85d59c54b.json" data-src="/assets/figure-svg/figures/9167bebba0c01d5ae2c0a86f.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step4.svg" data-theme="light" tabindex="-1" type="image/svg+xml">円盤が 3 枚のハノイの塔:手順 4</object><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_f3_step4.dark.svg" data-theme="dark" tabindex="-1" type="image/svg+xml">円盤が 3 枚のハノイの塔:手順 4</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><code>C</code> を使って <span class="arithmatex">\(n-1\)</span> 枚の円盤を <code>A</code> から <code>B</code> に移します。</li>
<li>残りの <span class="arithmatex">\(1\)</span> 枚を <code>A</code> から <code>C</code> に直接移します。</li>
<li><code>A</code> を使って <span class="arithmatex">\(n-1\)</span> 枚の円盤を <code>B</code> から <code>C</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> の解はわかっており、1 回移動するだけです。</p>
<p><ha-svg-figure class="animation-figure" data-book-key="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_divide_and_conquer.png" data-dark-src="/assets/figure-svg/figures/cb5a36974b1b3cef71612109.json" data-src="/assets/figure-svg/figures/426ced688e2fa19532497a48.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_divide_and_conquer.svg" data-theme="light" tabindex="-1" type="image/svg+xml">ハノイの塔を解く分割統治戦略</object><object data="/ja/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="この見出しへのリンク"></a></h3>
<p>コードでは、再帰関数 <code>dfs(i, src, buf, tar)</code> を定義します。この関数は、柱 <code>src</code> の上側にある <span class="arithmatex">\(i\)</span> 枚の円盤を、補助の柱 <code>buf</code> を使って目的の柱 <code>tar</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">"""円盤を 1 枚移動する"""</span>
<a href="#__codelineno-0-3" id="__codelineno-0-3" name="__codelineno-0-3"></a> <span class="c1"># src の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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"># A の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// A の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// A の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// A の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// A の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// src の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// A の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// A の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// A の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// A の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// A の上から n 枚の円盤を、B を使って C に移す</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">/* 円盤を 1 枚移動する */</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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">// A の上から n 枚の円盤を、B を使って C に移す</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">### 円盤を 1 枚移動する ###</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 の一番上から円盤を 1 枚取り出す</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 に円盤が 1 枚だけ残っている場合、そのまま 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) :src の上から i-1 枚の円盤を、tar を使って buf に移す</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 に残った 1 枚の円盤を 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) :buf の上から i-1 枚の円盤を、src を使って tar に移す</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"># A の上から n 枚の円盤を、B を使って C に移す</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,%20tar%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%E5%86%86%E7%9B%A4%E3%82%92%201%20%E6%9E%9A%E7%A7%BB%E5%8B%95%E3%81%99%E3%82%8B%22%22%22%0A%20%20%20%20%23%20src%20%E3%81%AE%E4%B8%80%E7%95%AA%E4%B8%8A%E3%81%8B%E3%82%89%E5%86%86%E7%9B%A4%E3%82%92%201%20%E6%9E%9A%E5%8F%96%E3%82%8A%E5%87%BA%E3%81%99%0A%20%20%20%20pan%20%3D%20src.pop%28%29%0A%20%20%20%20%23%20tar%20%E3%81%AE%E4%B8%80%E7%95%AA%E4%B8%8A%E3%81%AB%E5%86%86%E7%9B%A4%E3%82%92%E7%BD%AE%E3%81%8F%0A%20%20%20%20tar.append%28pan%29%0A%0A%0Adef%20dfs%28i%3A%20int,%20src%3A%20list%5Bint%5D,%20buf%3A%20list%5Bint%5D,%20tar%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94%E3%81%AE%E5%95%8F%E9%A1%8C%20f%28i%29%20%E3%82%92%E8%A7%A3%E3%81%8F%22%22%22%0A%20%20%20%20%23%20src%20%E3%81%AB%E5%86%86%E7%9B%A4%E3%81%8C%201%20%E6%9E%9A%E3%81%A0%E3%81%91%E6%AE%8B%E3%81%A3%E3%81%A6%E3%81%84%E3%82%8B%E5%A0%B4%E5%90%88%E3%80%81%E3%81%9D%E3%81%AE%E3%81%BE%E3%81%BE%20tar%20%E3%81%AB%E7%A7%BB%E3%81%99%0A%20%20%20%20if%20i%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20move%28src,%20tar%29%0A%20%20%20%20%20%20%20%20return%0A%20%20%20%20%23%20%E9%83%A8%E5%88%86%E5%95%8F%E9%A1%8C%20f%28i-1%29%20%EF%BC%9Asrc%20%E3%81%AE%E4%B8%8A%E3%81%8B%E3%82%89%20i-1%20%E6%9E%9A%E3%81%AE%E5%86%86%E7%9B%A4%E3%82%92%E3%80%81tar%20%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%20buf%20%E3%81%AB%E7%A7%BB%E3%81%99%0A%20%20%20%20dfs%28i%20-%201,%20src,%20tar,%20buf%29%0A%20%20%20%20%23%20%E9%83%A8%E5%88%86%E5%95%8F%E9%A1%8C%20f%281%29%20%EF%BC%9Asrc%20%E3%81%AB%E6%AE%8B%E3%81%A3%E3%81%9F%201%20%E6%9E%9A%E3%81%AE%E5%86%86%E7%9B%A4%E3%82%92%20tar%20%E3%81%AB%E7%A7%BB%E3%81%99%0A%20%20%20%20move%28src,%20tar%29%0A%20%20%20%20%23%20%E9%83%A8%E5%88%86%E5%95%8F%E9%A1%8C%20f%28i-1%29%20%EF%BC%9Abuf%20%E3%81%AE%E4%B8%8A%E3%81%8B%E3%82%89%20i-1%20%E6%9E%9A%E3%81%AE%E5%86%86%E7%9B%A4%E3%82%92%E3%80%81src%20%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%20tar%20%E3%81%AB%E7%A7%BB%E3%81%99%0A%20%20%20%20dfs%28i%20-%201,%20buf,%20src,%20tar%29%0A%0A%0Adef%20solve_hanota%28A%3A%20list%5Bint%5D,%20B%3A%20list%5Bint%5D,%20C%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94%E3%81%AE%E5%95%8F%E9%A1%8C%E3%82%92%E8%A7%A3%E3%81%8F%22%22%22%0A%20%20%20%20n%20%3D%20len%28A%29%0A%20%20%20%20%23%20A%20%E3%81%AE%E4%B8%8A%E3%81%8B%E3%82%89%20n%20%E6%9E%9A%E3%81%AE%E5%86%86%E7%9B%A4%E3%82%92%E3%80%81B%20%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%20C%20%E3%81%AB%E7%A7%BB%E3%81%99%0A%20%20%20%20dfs%28n,%20A,%20B,%20C%29%0A%0A%0A%22%22%22%E5%AE%9F%E8%A1%8C%E7%94%A8%E3%82%B3%E3%83%BC%E3%83%89%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E3%83%AA%E3%82%B9%E3%83%88%E3%81%AE%E6%9C%AB%E5%B0%BE%E3%81%8C%E6%A3%92%E3%81%AE%E4%B8%80%E7%95%AA%E4%B8%8A%E3%81%AB%E5%AF%BE%E5%BF%9C%E3%81%99%E3%82%8B%0A%20%20%20%20A%20%3D%20%5B5,%204,%203,%202,%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%E5%88%9D%E6%9C%9F%E7%8A%B6%E6%85%8B%EF%BC%9A%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,%20B,%20C%29%0A%0A%20%20%20%20print%28%22%E5%86%86%E7%9B%A4%E3%81%AE%E7%A7%BB%E5%8B%95%E5%AE%8C%E4%BA%86%E5%BE%8C%EF%BC%9A%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,%20tar%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%E5%86%86%E7%9B%A4%E3%82%92%201%20%E6%9E%9A%E7%A7%BB%E5%8B%95%E3%81%99%E3%82%8B%22%22%22%0A%20%20%20%20%23%20src%20%E3%81%AE%E4%B8%80%E7%95%AA%E4%B8%8A%E3%81%8B%E3%82%89%E5%86%86%E7%9B%A4%E3%82%92%201%20%E6%9E%9A%E5%8F%96%E3%82%8A%E5%87%BA%E3%81%99%0A%20%20%20%20pan%20%3D%20src.pop%28%29%0A%20%20%20%20%23%20tar%20%E3%81%AE%E4%B8%80%E7%95%AA%E4%B8%8A%E3%81%AB%E5%86%86%E7%9B%A4%E3%82%92%E7%BD%AE%E3%81%8F%0A%20%20%20%20tar.append%28pan%29%0A%0A%0Adef%20dfs%28i%3A%20int,%20src%3A%20list%5Bint%5D,%20buf%3A%20list%5Bint%5D,%20tar%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94%E3%81%AE%E5%95%8F%E9%A1%8C%20f%28i%29%20%E3%82%92%E8%A7%A3%E3%81%8F%22%22%22%0A%20%20%20%20%23%20src%20%E3%81%AB%E5%86%86%E7%9B%A4%E3%81%8C%201%20%E6%9E%9A%E3%81%A0%E3%81%91%E6%AE%8B%E3%81%A3%E3%81%A6%E3%81%84%E3%82%8B%E5%A0%B4%E5%90%88%E3%80%81%E3%81%9D%E3%81%AE%E3%81%BE%E3%81%BE%20tar%20%E3%81%AB%E7%A7%BB%E3%81%99%0A%20%20%20%20if%20i%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20move%28src,%20tar%29%0A%20%20%20%20%20%20%20%20return%0A%20%20%20%20%23%20%E9%83%A8%E5%88%86%E5%95%8F%E9%A1%8C%20f%28i-1%29%20%EF%BC%9Asrc%20%E3%81%AE%E4%B8%8A%E3%81%8B%E3%82%89%20i-1%20%E6%9E%9A%E3%81%AE%E5%86%86%E7%9B%A4%E3%82%92%E3%80%81tar%20%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%20buf%20%E3%81%AB%E7%A7%BB%E3%81%99%0A%20%20%20%20dfs%28i%20-%201,%20src,%20tar,%20buf%29%0A%20%20%20%20%23%20%E9%83%A8%E5%88%86%E5%95%8F%E9%A1%8C%20f%281%29%20%EF%BC%9Asrc%20%E3%81%AB%E6%AE%8B%E3%81%A3%E3%81%9F%201%20%E6%9E%9A%E3%81%AE%E5%86%86%E7%9B%A4%E3%82%92%20tar%20%E3%81%AB%E7%A7%BB%E3%81%99%0A%20%20%20%20move%28src,%20tar%29%0A%20%20%20%20%23%20%E9%83%A8%E5%88%86%E5%95%8F%E9%A1%8C%20f%28i-1%29%20%EF%BC%9Abuf%20%E3%81%AE%E4%B8%8A%E3%81%8B%E3%82%89%20i-1%20%E6%9E%9A%E3%81%AE%E5%86%86%E7%9B%A4%E3%82%92%E3%80%81src%20%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%20tar%20%E3%81%AB%E7%A7%BB%E3%81%99%0A%20%20%20%20dfs%28i%20-%201,%20buf,%20src,%20tar%29%0A%0A%0Adef%20solve_hanota%28A%3A%20list%5Bint%5D,%20B%3A%20list%5Bint%5D,%20C%3A%20list%5Bint%5D%29%3A%0A%20%20%20%20%22%22%22%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94%E3%81%AE%E5%95%8F%E9%A1%8C%E3%82%92%E8%A7%A3%E3%81%8F%22%22%22%0A%20%20%20%20n%20%3D%20len%28A%29%0A%20%20%20%20%23%20A%20%E3%81%AE%E4%B8%8A%E3%81%8B%E3%82%89%20n%20%E6%9E%9A%E3%81%AE%E5%86%86%E7%9B%A4%E3%82%92%E3%80%81B%20%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%20C%20%E3%81%AB%E7%A7%BB%E3%81%99%0A%20%20%20%20dfs%28n,%20A,%20B,%20C%29%0A%0A%0A%22%22%22%E5%AE%9F%E8%A1%8C%E7%94%A8%E3%82%B3%E3%83%BC%E3%83%89%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E3%83%AA%E3%82%B9%E3%83%88%E3%81%AE%E6%9C%AB%E5%B0%BE%E3%81%8C%E6%A3%92%E3%81%AE%E4%B8%80%E7%95%AA%E4%B8%8A%E3%81%AB%E5%AF%BE%E5%BF%9C%E3%81%99%E3%82%8B%0A%20%20%20%20A%20%3D%20%5B5,%204,%203,%202,%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%E5%88%9D%E6%9C%9F%E7%8A%B6%E6%85%8B%EF%BC%9A%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,%20B,%20C%29%0A%0A%20%20%20%20print%28%22%E5%86%86%E7%9B%A4%E3%81%AE%E7%A7%BB%E5%8B%95%E5%AE%8C%E4%BA%86%E5%BE%8C%EF%BC%9A%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> の再帰木をなします。各ノードは一つの部分問題を表し、1 回の <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="ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_recursive_tree.png" data-dark-src="/assets/figure-svg/figures/2477c295fbdb1e818a2dc7e0.json" data-src="/assets/figure-svg/figures/13006213be4f187c2a83fc79.json" style=";--figure-ratio:960.0/540.0"><object data="/ja/chapter_divide_and_conquer/hanota_problem.assets/hanota_recursive_tree.svg" data-theme="light" tabindex="-1" type="image/svg+xml">ハノイの塔の問題の再帰木</object><object data="/ja/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">引用</p>
<p>ハノイの塔の問題は、古い伝説に由来します。古代インドのある寺院に、3 本の高いダイヤモンドの柱と、大きさの異なる <span class="arithmatex">\(64\)</span> 枚の金の円盤がありました。僧侶たちは円盤を動かし続け、最後の円盤を正しい位置に置いた瞬間に、この世界が終わると信じていました。</p>
<p>しかし、仮に毎秒 1 回ずつ動かしても、合計で約 <span class="arithmatex">\(2^{64} \approx 1.84×10^{19}\)</span> 秒、すなわち約 <span class="arithmatex">\(5850\)</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="ja" 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/>このサイトのコンテンツのライセンス: <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.4b65e87068ac38235d9f2cf93ce9d63bc8183b8a230a27c7b45fcfe8aa24e133.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>