点火式(TIL 42日目)

本托比文系,学数学

Intro

私は外国の小さな学校に通っています.一年生は13人ぐらいです.そのため、文系/理系の区別もなく、数学を深く勉強した経験もありません.だからアルゴリズムを勉強するとき、点火式を言うたびに、これはいったい何なのかと思っています.
点火式を検索するとウィキペディアと木の鍵のドキュメントが表示されます.難しいですが、ウィキペディアの説明はもっと簡単なようなので、ウィキペディアを基準に私が理解していることを書きたいと思います.

点火式とは何ですか。

ウィキペディアの点火方法の説明を参照してください.
数学では,漸化式または再帰式は,数列における隣接する2つの項の間に成立する関係式を表す.
数学が分からないのは誇りに思うことではありませんが、プログラミングを学ぶにはどんな概念も単語として理解する必要はないと思います.しかし、上記の説明では、粗処理された2つの内容を見ました.1つは再帰式であり,もう1つは隣接する2つの項の関係である.
引用の説明では再回帰式を点火式の別の名前と呼ぶ.ちょうどプログラミングでずっと勉強していた「在貴」という言葉があり、何か手がかりになるかもしれません.
プログラミングでは、ある関数で自分の関数を再呼び出して再帰関数と呼ぶ.このとき呼び出される関数自体と再帰的に呼び出される関数との間には必然的に何らかの関係がある.先ほど引用した説明では、点火式とは隣接する2つの項目の関係を指すことも言及しています.

したがって、上記の図を理解すると、次のようになります.anとan+1を隣接項と呼ぶと,ある関数をanに加算してan+1の結果を得ると,関数fは数列{an}の点化式である.
ウィキペディアの点火式の内容では、フィボナッチ数列とハノイの塔を通して、もっと分かりやすいと思います.これはプログラム設計でよく遭遇するアルゴリズムの問題である.
簡単に言えば、フィボナッチ数列を作成する際の再帰式は以下の通りである.

function fibonacci(n) {
  if ( n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

この場合,basecaseのifとしての内容のほか,fibonacci(n−1)+fibonacci(n−2)がフィボナッチ数列の点化式である.
ハノイのタワー問題も点火式で簡単に整理した内容で確認できます.
n個のディスクを移動する回数を数列anとして定義する.n個の円板を移動するためには、上のn−1個の円板を別のレバーに移動させ、次に一番下の円板を移動させ、さらにn−1個の円板を移動させることで、以下の点火方式が成立することが分かる.

5つの円板を移動する必要がある場合は、4つの円板を別の場所に2回繰り返し移動する必要があります.その間、一番下の円板を移動するために「回収1」が追加されます.だからこの方式は2 n-1になりやすい
もちろん、これは移動回数に関するプレースホルダですが、「最小回数に移動するときにディスクを移動する順序」などの問題が発生した場合は、他の方法を考慮する必要があります.興味のある人のためにリンクを残す