Ctrl+K

Assingment 1

Assingment 1#

Note

ChatGPTとの対話によって科学史を遡り、ChatGPTによってプログラムを生成する例です。

ChatGPIとの次のやりとりを参考にして、「末尾再帰」を行う関数を実装せよ#

  • Tail call - Wikipedia

    • プログラミング言語で繰り返し実行を行う際に、関数を「末尾再帰」で再帰的に呼び出す実装方法がある。

    • 機械的にループに置き換えることができるため、プログラムを高速に実行するための技法として黎明期から活用されてきた。

  • 以下のやりとりを参考にして、自然数列の和を求める際にガウスが用いたアルゴリズムを末尾再帰によって実装せよ。

    • 他の実装方法との実行時間の比較方法を聞き出せるとなおよい。

%%ai vioras
ガウスについて

カール・フリードリヒ・ガウス（Johann Carl Friedrich Gauss, 1777年4月30日 - 1855年2月23日）は、ドイツの数学者であり、物理学者であり、天文学者です。彼は「数学の王子」と呼ばれ、その広範な貢献は数学のほぼすべての分野に及びます。

ガウスは、数論、統計学、解析学、微分幾何学、地磁気学、天文学などの分野で多大な貢献をしました。彼の名前は、ガウス分布（正規分布）、ガウスの法則、ガウスの素数定理など、数学と物理学の数々の概念と定理に冠されています。

彼の著名な業績の中には、以下のものがあります:

  1. 数論: ガウスは若くして「算術の基本定理」を証明しました。これは、任意の自然数は一意的に素数の積に分解できるという定理です。

  2. 天文学: ガウスは天体の軌道を計算する新しい方法を開発しました。彼はこの方法を用いて、小惑星ケレスの位置を正確に予測しました。

  3. 統計学: ガウスは最小二乗法を発展させ、これが統計学の基本的なツールとなりました。また、ガウス分布（正規分布）は彼の名前にちなんで名付けられました。

  4. 地磁気学: ガウスは地磁気の研究においても重要な貢献をしました。彼の名前は、地磁気の強度を測定する単位「ガウス」にも使われています。

  5. 非ユークリッド幾何学: ガウスは非ユークリッド幾何学の可能性を初めて認識しましたが、その発見は公にはされませんでした。しかし、彼の手紙やノートから、彼がこの分野を深く理解していたことが明らかになりました。

以上のように、ガウスは数学と科学の多くの分野で深遠な影響を与えました。ガウスの多大な貢献により、彼は数学史上最も偉大な数学者の一人と広く認識されています。

%%ai vioras
ガウスの少年時代の有名なエピソードを語ってください

カール・フリードリヒ・ガウスの少年時代には、彼の驚異的な数学的才能が明らかになった有名なエピソードがあります。

このエピソードは、彼がまだ小学生だったときのことです。ガウスの先生は、生徒たちに1から100までの全ての自然数を足す課題を出しました。これは生徒たちを忙しくさせ、先生が他の仕事をする間に時間を稼ぐためのものでした。

しかし、ガウスはほんの数秒で答えを見つけてしまいました。彼は1と100を足し、次に2と99を足し、3と98を足し…というように、対になる数を足しました。それぞれの対の和は101で、それが50対あるため、答えは101×50=5050だとすぐに計算しました。

このエピソードは、ガウスが数学的なパターンや関係性を直感的に理解し、それを用いて複雑な問題を素早く解く能力を早くから持っていたことを示しています。このような直感と洞察力は、彼が数学の多くの分野で重要な発見をする基礎となりました。

%%ai vioras
その計算をPythonの関数にすると？

Pythonで1から100までの全ての自然数を足す関数を作成すると以下のようになります：

def sum_numbers(n):
    return sum(range(1, n + 1))

print(sum_numbers(100))

この関数sum_numbersは、引数nまでの全ての自然数を足すものです。Pythonのrange関数は指定した範囲の数列を生成し、sum関数はその数列の合計を計算します。

print(sum_numbers(100))を実行すると、1から100までの全ての自然数の合計である5050が得られます。

ただし、ガウスが使用した方法は、以下のように数列の最初の数と最後の数を足し、それを数列の半分の長さ（対の数）と掛けるというものでした。これをPythonで表現すると以下のようになります：

def gauss_sum(n):
    return (n * (n + 1)) // 2

print(gauss_sum(100))

この関数gauss_sumでも、1から100までの全ての自然数の合計である5050が得られます。これはガウスの方法が正確であり、また計算が非常に効率的であることを示しています。

%%ai vioras
具体的な実行方法は？

Pythonを実行するためには、まずPythonがインストールされている環境が必要です。それが確認できたら、Pythonのコードを記述したファイルを作成し、そのファイルをPythonのインタープリタで実行します。

以下に、詳細な手順を示します。

  1. テキストエディタ（例えば、Notepad++やSublime Textなど）を開き、新しいファイルを作成します。

  2. 次のPythonコードをそのファイルに貼り付けます：

    def gauss_sum(n):
    return (n * (n + 1)) // 2

print(gauss_sum(100))

  3. このファイルをgauss_sum.pyという名前（拡張子は.py）で保存します。

  4. コマンドプロンプト（Windows）またはターミナル（macOSやLinux）を開きます。

  5. gauss_sum.pyが保存されたディレクトリに移動します。例えば、もしファイルがデスクトップに保存されているなら、以下のコマンドを使います：

    cd Desktop

  6. 次に、以下のコマンドを使ってPythonスクリプトを実行します：

    python gauss_sum.py

  7. 正しく実行された場合、ターミナルには5050と表示されます。これが1から100までの全ての自然数の合計です。

以上が具体的なPythonの実行方法です。ただし、この手順はあくまで一例であり、使用する環境やエディタにより異なる場合があります。

%%ai vioras
ここはJupyterであなたはJupyternautのはずです。

あ、すみません、その通りですね。JupyterLabの環境であることを見落としていました。

JupyterLabでは、新しいノートブックを作成し、その中にPythonのコードを入力して実行します。以下に具体的な手順を示します。

  1. JupyterLabを開き、左上の「File」メニューから「New」を選び、「Notebook」を選択します。

  2. 新しいノートブックが開かれ、セルが一つ表示されます。このセルに以下のPythonのコードを入力します：

    def gauss_sum(n):
    return (n * (n + 1)) // 2

print(gauss_sum(100))

  3. コードを入力したら、セルを実行します。これには、上部のツールバーにある「Run」ボタンを押すか、キーボードショートカットのShift + Enter（またはCtrl + Enter）を使用します。

  4. セルが実行され、出力エリアに5050と表示されます。これが1から100までの全ての自然数の合計です。

このように、JupyterLabではノートブック内で直接Pythonのコードを実行でき、結果も同じ場所で確認できます。また、Markdownを使って説明文を加えるなど、コードとその説明を一緒に記録することも可能です。

%%ai vioras
この関数を末尾再帰を使うように書き換えることはできますか？

末尾再帰（Tail Recursion）は、再帰の一種で、再帰呼び出しが関数の最後の操作となる形式のことを指します。これはスタックの深さを抑制するのに役立ちます。

しかし、Pythonは末尾再帰の最適化をサポートしていません。つまり、Pythonでは末尾再帰を使用したとしても、再帰呼び出しでスタックオーバーフローを引き起こす可能性があります。

したがって、Pythonで大きな数を扱う場合は、再帰よりも反復（ループ）を使用することが推奨されます。しかし、あくまで学習目的であれば、以下にガウスの加算問題を末尾再帰で解くPythonのコードを示します：

def gauss_sum(n, acc=0):
    if n == 0:
        return acc
    else:
        return gauss_sum(n-1, acc+n)

print(gauss_sum(100))

ここでaccは「accumulator」（累積器）の略で、これまでの加算結果を保持します。各再帰呼び出しでは、nを1つずつ減らし、accにnを加えます。nが0になったとき、accが最終結果となります。

%%ai vioras
末尾再帰とループの実行速度を比較したい。

Pythonのtimeitモジュールを使用して、末尾再帰版とループ版のガウスの加算問題の実行速度を比較することができます。以下にそのためのコードを示します：

import timeit

# Tail recursion version
def gauss_sum_rec(n, acc=0):
    if n == 0:
        return acc
    else:
        return gauss_sum_rec(n-1, acc+n)

# Loop version
def gauss_sum_loop(n):
    acc = 0
    for i in range(1, n + 1):
        acc += i
    return acc

# Measure time of tail recursion version
start_time = timeit.default_timer()
gauss_sum_rec(100)
end_time = timeit.default_timer()
print(f"Tail recursion: {end_time - start_time} seconds")

# Measure time of loop version
start_time = timeit.default_timer()
gauss_sum_loop(100)
end_time = timeit.default_timer()
print(f"Loop: {end_time - start_time} seconds")

このコードは、gauss_sum_recとgauss_sum_loopの実行時間を計測し、その結果を表示します。timeit.default_timerを使用して計測を開始し、再度timeit.default_timerを呼び出して計測を終了し、その差を計算することで、関数の実行時間を測定します。

ただし、Pythonは末尾再帰の最適化をサポートしていないため、再帰版はループ版に比べて実行時間が長くなる可能性があります。

import timeit

# Tail recursion version
def gauss_sum_rec(n, acc=0):
    if n == 0:
        return acc
    else:
        return gauss_sum_rec(n-1, acc+n)

# Loop version
def gauss_sum_loop(n):
    acc = 0
    for i in range(1, n + 1):
        acc += i
    return acc

# Measure time of tail recursion version
start_time = timeit.default_timer()
gauss_sum_rec(100)
end_time = timeit.default_timer()
print(f"Tail recursion: {end_time - start_time} seconds")

# Measure time of loop version
start_time = timeit.default_timer()
gauss_sum_loop(100)
end_time = timeit.default_timer()
print(f"Loop: {end_time - start_time} seconds")

Tail recursion: 5.140100256539881e-05 seconds
Loop: 4.2400992242619395e-05 seconds
Contents