私の趣味は、数学とコンピューターサイエンスを学童に教えることです。 このプロセスでは、動機付けの問題が非常に重要であるため、素材の品質に慎重に取り組む必要があります。 さまざまな資料の読み方を列挙した後、「1つのタスク」プロジェクトのアイデアが生まれました。このプロジェクトでは、1つの問題だけを解決する例として、さまざまな新しい資料を提示して講義を行います。 そこで、このプロジェクトの最初の資料を紹介します。
タスク：サイズが1x1および1x2メートルのタイルがあります。 これらのタイルで1x15メートルの四角形を並べる方法はいくつありますか？
通常、このような組み合わせの問題を解決した経験のない人がこの問題の解決策を提案することは容易ではありません。 したがって、作業仮説を得るために、より単純なものに減らす価値があります。 小さな長方形を並べる方法のソートを始めましょう。
1x1の長方形は、一方向にのみ並べることができます。 長方形1x2-2。 より単純な長方形のテーブルを作成しましょう：
| 大きさ | オプションの数 |
| 1x1 | 1 |
| 1x2 | 2 |
| 1x3 | 3 |
| 1x4 | 5 |
| 1x5 | 8 |
念のため、1x5の長方形のすべてのオプションをリストします。ここで、番号1は1x1タイル、番号2は1x2タイルです。
1.1
2.11 2
3. 111 12 21
4.1111 112 121 211 22
5.11111 1112 1121 1211 2111 122 212 221
2列目の表にフィボナッチ数があることは簡単にわかります。 それらの外観は明らかに偶然ではありません。 彼らがどこから来たのか考えてみましょう。
左から右に長方形を並べていると想像してください。 次に、1x1タイルを1x長方形に追加する（N-1）か、1x2タイルを1x長方形に追加する（N-2）ことにより、1xN長方形を取得できます。 したがって、タイル1x（N-1）と1x（N-2）はそれぞれ1つのタイル1x（N）に対応します。 P（N）の1xNの四角形を並べるオプションの数を示すと、フィボナッチ数の式である式P（N）= P（N-1）+ P（N-2）が得られます。
フィボナッチ数を計算するプログラムを作成してみましょう。 明らかに、これらの数値の式は再帰的であるため、循環と再帰の2つの方法で問題を解決します。
プログラムProject2;
{$ APPTYPEコンソール}
使用する
SysUtils
var a：整数の配列[1..15]。
i：整数;
関数p（n：整数）：整数;
始める
n <3の場合、p：= n else p：= p（n-1）+ p（n-2）;
終わり;
始める
[1]：= 1;
a [2]：= 2;
iの場合：= 3から15 a [i]を実行します：= a [i-1] + a [i-2];
writeln（a [15]）;
writeln（p（15））;
readln;
終わり。
次に、このアルゴリズムで各引数に対して再帰関数が何回呼び出されるかを計算してみましょう。 引数nを使用したpの呼び出し回数をp（n）で示します。 明らかに、p（15）= 1およびp（14）= 1です。 しかし、p（n）= p（n + 1）+（n + 2）。 つまり、再び同じフィボナッチ数列を取得します。 例外は、p（1）= p（3）のみです。 したがって、素晴らしい事実を証明しました。
フィボナッチ数を計算するための再帰アルゴリズムの複雑さは、フィボナッチ数の合計によって測定されます。