前回(2020/05/29)の内容 再帰的定義と数学的帰納法 再帰的定義 C 言語での関数の定義 自分自身を呼び出す f(N) { ... f(N-1) .. } 数学的帰納法 数学上の証明の形式 P(N) { ... P(N-1) .. } 再帰的に定義された関数の性質は、 数学的帰納法で証明しやすい 数学的帰納法を利用した証明から、 再帰的に定義された関数が定義できる 一進数 1 を n 個数並べて、自然数 n を表現する数の表現方法 十進数 一進数 0 1 1 2 11 3 111 4 1111 5 11111 一進数 足し算 => 二つ数を並べるだけ 掛け算 => 足し算を繰り返す ( 再帰 ) 「計算」が printf *だけ* で # 裏側では C 言語の # 順接/条件分岐(if 構文)/繰り返し(再帰) # 三つの構文を組み合わせて => 万能だから... [2020/06/05] Hanoi の塔の問題 三本の棒 ( 1 〜 3 ) と、大きさの異る N 枚の円盤がある 最初は、その内の一番左の 1 番の棒に、大きさの順に円盤が積まれている その円盤を、全て、真ん中の 2 盤の棒に移動したい ただし、円盤を移動する場合には、次の制限を守る必要がある 一度に移動できるのは、棒の一番上の一枚の円盤のみである 空の棒にはどの大きさの円盤も積む事ができる 既に円盤が積まれた棒には、その一番上の円盤より小さい円盤しか積む事ができない [1|1] | | [22|22] | | [333|333] | | --------+---------+--------+------ (1) (2) (3) (1) から (2) に [1] の円盤を移動する | | | [22|22] | | [333|333] [1|1] | --------+---------+--------+------ (1) (2) (3) (1) から (3) に [2] の円盤を移動する | | | | | | [333|333] [1|1] [22|22] --------+---------+--------+------ (1) (2) (3) (2) から (3) に [1] の円盤を移動する | | | | | [1|1] [333|333] | [22|22] --------+---------+--------+------ (1) (2) (3) (1) から (2) に [3] の円盤を移動する | | | | | [1|1] | [333|333] [22|22] --------+---------+--------+------ (1) (2) (3) (3) から (1) に [1] の円盤を移動する | | | | | | [1|1] [333|333] [22|22] --------+---------+--------+------ (1) (2) (3) (3) から (2) に [2] の円盤を移動する | | | | [22|22] | [1|1] [333|333] | --------+---------+--------+------ (1) (2) (3) (1) から (2) に [1] の円盤を移動する | [1|1] | | [22|22] | | [333|333] | --------+---------+--------+------ (1) (2) (3) この手順で、 高さ 3 のハノイの塔を (1) の棒から、(2) の棒に移動できた [問題] 同様にして、 高さ 3 のハノイの塔を (1) の棒から、(3) の棒に移動 する手順を考えてください。 [解答] [1|1] | | [22|22] | | [333|333] | | --------+---------+--------+------ (1) (2) (3) (1) から (3) に [1] を移動する | | | [22|22] | | [333|333] | [1|1] --------+---------+--------+------ (1) (2) (3) (1) から (2) に [2] を移動する | | | | | | [333|333] [22|22] [1|1] --------+---------+--------+------ (1) (2) (3) (3) から (2) に [1] を移動する | | | | [1|1] | [333|333] [22|22] | --------+---------+--------+------ (1) (2) (3) (1) から (3) に [3] を移動する | | | | [1|1] | | [22|22] [333|333] --------+---------+--------+------ (1) (2) (3) (2) から (1) に [1] を移動する | | | | | | [1|1] [22|22] [333|333] --------+---------+--------+------ (1) (2) (3) (2) から (3) に [2] を移動する | | | | | [22|22] [1|1] | [333|333] --------+---------+--------+------ (1) (2) (3) (1) から (3) に [1] を移動する | | [1|1] | | [22|22] | | [333|333] --------+---------+--------+------ (1) (2) (3) まず、プログラムを作成するまえに、 自分の手で実現できるかどうかを試す # 小さい問題で... いきなりプログラムを書くの大変なので、手動で !!! 手でてきない事がプログラムでできるようにできない !!! ちいさな問題から解く 一般のハノイの塔の問題 なにもしない (N=0 の時) hanoi ( N, i, j, k ) = { 次の 3 ステップで行う hanoi ( N-1, i, k ) 円盤 N を i から j に移動 honai ( N-1, k, j ) 砂漠の旅行の問題 町ーーー砂漠ーーー町 ０１２３ ３２１０ 町ーー町 旅人は、一枡移動するときに、食料を一食分消費する もし、旅の途中で、食料がなくなったら、移動できなくなる => その場で餓死 旅人は、一度に三つまでの食料しかもてない 町では、いつでも、食料を買う事ができる => 目的の町が、３だけ離れているなら、問題ない ４以上離れていたらどうするか ? 目的の町が４以上離れている場合は、 途中の砂漠に、食料をおいて、途中で、補給する事を考える 砂漠には二個まで、食料を置く事ができる 食料数 位置 砂漠の状態 (0) 0 000G 三つ買う (3) 0 000G 前に進む (2) 1 000G 食料を置く (1) 1 100G 後ろに戻る (0) 0 100G 三つ買う (3) 0 100G 前に進む (2) 1 100G 食料を拾う (3) 1 000G 前に進む (2) 2 000G 前に進む (1) 3 000G 前に進む (0) 4[G] 000G [問題] 距離 4 の町までの手順を示した 距離 5 の町のまでの手順を考えなさい。 [解答] 食料数 位置 砂漠の状態 (0) 0 0000G 三つ買う (3) 0 0000G 前に進む (2) 1 1000G 食料を置く (1) 1 1000G 後ろに戻る (0) 0 1000G 三つ買う (3) 0 0000G 前に進む (2) 1 1000G 食料を置く (1) 1 2000G 後ろに戻る (0) 0 2000G 三つ買う (3) 0 2000G 前に進む (2) 1 2000G 食料を拾う (3) 1 1000G 前に進む (2) 2 1000G 食料を置く (1) 2 1100G 後ろに戻る (0) 1 1100G 食料を拾う (1) 1 0100G 後ろに戻る (0) 0 0100G 三つ買う (3) 0 0100G 前に進む (2) 1 0100G 食料を置く (1) 1 1100G 後ろに戻る (0) 0 1100G 三つ買う (3) 0 1100G 前に進む (2) 1 1100G 食料を拾う (3) 1 0100G 前に進む (2) 2 0100G 食料を拾う (3) 2 0000G 前に進む (2) 3 0000G 前に進む (1) 4 0000G 前に進む (0) 5(G) 0000G