ハーバード CS50: 第 3 週の課題 (講義 7 および 8)、パート 1

プログラミングの基礎に関するハーバード大学コースの講義 CS50 追加資料: 漸近記法、ソートおよび検索アルゴリズム 第 2 部。Cの「タグ」

準備

問題に取り組む前に、講義7 ～ 8を視聴し、「第 3 週目の追加資料」を読んで掘り下げてください。これらは、検索アルゴリズム (線形およびバイナリ)、並べ替え (多数あります!)、およびデバッガーの作業 (デバッガーを使用してプログラムをデバッグする能力は非常に重要なスキルです!) に専念します。講義と理論がすべて順調に進んでいる場合は、テストの問題に簡単に答えることができます。

• 二分探索にソートされた配列が必要なのはなぜですか?
• バブルソートが O(n2) と推定されるのはなぜですか?
• 挿入ソートの推定値が Ω(n) なのはなぜですか?
• 選択の並べ替えはどのように機能しますか? 3 文 (またはそれ以下) で説明してください。
• マージソートを実行できる時間の上限 (最悪の場合) はどれくらいですか?
• GDB デバッガーを使用すると、プログラムをデバッグできます。さらに具体的に定式化すると、具体的に何ができるようになるのでしょうか?

目標

• 複数のファイルを含むプロジェクトの操作方法を学ぶ
• 他人のソースコードを読む方法を学ぶ
• さまざまなアルゴリズムと再帰関数を理解する

これらの目標のほとんどは、正式に評価することが事実上不可能です。したがって、問題を正式に検証するという観点から見ると、難しいと思われることはほとんどありません。ただし、プログラミングは継続的な練習を通じてのみ学ぶことができることを思い出してください。したがって、タスクを解決するだけでなく、追加の時間と労力を費やして、今週説明したすべてのアルゴリズムを実装することをお勧めします。フォワード！

始める

第 1 週と第 2 週の練習問題では、プログラムを最初から作成し、 mkdirコマンドを使用して 独自のpset1 ディレクトリとpset2ディレクトリを作成したことを思い出してください。3 週目の練習課題では、私たちが作成したディストリビューション (または「ディストリビューション」と呼ぶ) をダウンロードし、そこに独自のコード行を追加する必要があります。まず、コードを読んで理解してください。今週最も重要なスキルは、他の人のコードを読む方法を学ぶことです。したがって、cs50.io にログインし、ターミナル ウィンドウでコマンドを実行して、 ワークスペースのバージョンが最新であることを確認します。ターミナル ウィンドウを誤って閉じてしまい、見つからない場合は、[表示]メニューに移動し、[コンソール] オプションがオンになっていることを確認します (オンになっていない場合はチェックしてください)。(+) をクリックし、ターミナル ウィンドウのフレーム上の緑色の円の内側で、[新しいターミナル]を選択します。 その後、コマンドを実行して 、ワークスペース ディレクトリ (これが実際のディレクトリ) 内にいることを確認します。その後、次のコマンドを実行して、 問題集の ZIP アーカイブをワークスペースにダウンロードします (wget は Linux のダウンロード コマンドです)。すべてが正常であれば、行に次のフレーズが表示されます。 コマンドを実行して、 pset3.zip を 本当にダウンロードしたことを確認してから 、実行して ファイルを解凍します。ここでlsコマンドを再度実行すると、 pset3ディレクトリも表示されます。コマンドを実行してそのディレクトリに移動し 、ディレクトリの内容を再度表示するように要求します。 このディレクトリには 2 つのサブディレクトリがあることがわかります 。 update50cd ~/workspacewget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip'pset3.zip' savedlsunzip pset3.zipcd pset3lsfifteen find

検索

これらのサブディレクトリの 1 つを見てみましょう。これを行うには、次のコマンドを実行します。 cd ~/workspace/pset3/find このフォルダーの内容を画面に表示すると (おそらくこの方法はすでに覚えているでしょう)、次のように表示されるはずです helpers.c helpers.h Makefile find.c generate.c 。でも心配しないでください。今すぐ対処します。ファイルgenerate.cには、「疑似乱数ジェネレータ」( drand48関数によって生成される)を使用して、多数の乱数(実際には疑似乱数であり、コンピュータは純粋な乱数を処理できない!)を生成するプログラムのコードが含まれています。を指定して、一度に 1 つずつ行に配置します。 プログラムmake generate をコンパイルします。次に、コマンドを実行して実行します。 ./generate プログラムは次のメッセージを表示します。 Usage: generate n [s] これは、プログラムが 1 つまたは 2 つのコマンド ライン引数を予期していることを意味します。最初の引数を使用すると、 n は必須です。この数値は、作成する擬似乱数の数を意味します。角括弧で示されているように、パラメーター s はオプションです。数値 s は、擬似乱数ジェネレーターの「シード」と呼ぶことができます。疑似乱数生成器への入力データがその出力に影響を与えることを意味します。たとえば、drand48 を使用している場合、まず srand48 (drand48 を「シード」することを目的とした別の関数) を引数 1 で呼び出します。次に、drand48 を 3 回呼び出すと、drand48 は 2728、次に 29785、次に 54710 を返す可能性があります。前の関数の代わりに、drand48 を使用して、最初に srand48 を、たとえば 2 の引数を指定して呼び出して、次に drand48 を再度 3 回使用すると、drand48 は次のようになります。 59797、10425、37569 が返されます。しかし、引数 1 を指定して srand48 を再度呼び出して drand48 を再度確認すると、次の 3 回の drand48 呼び出しの結果は、再び 2728、次に 29785、そして 54710 となります。ご存知のとおり、すべての出来事には理由があります。以下に示すように、今回は n=10 としてプログラムを再度実行します。10 個の疑似乱数のリストが表示されます。 ./generate 10 同じ値の n を使用してプログラムを 3 回実行してみましょう。10 個の数字の別のリストが表示されるはずです。次に、2 つのパラメーターを指定してプログラムを実行してみます。以下に示すように s=0 とします。 ./generate 10 0 ここで、同じコマンドをもう一度実行します。 ./generate 10 0 議論することさえできません。同じ 10 桁の「ランダムな」シーケンスが再び表示されました。擬似乱数ジェネレーターのシードを変更しないと、これが起こります。次に、 generate.cプログラム自体を見てみましょう。（方法を覚えていますか？）。このファイルの先頭にあるコメントは、プログラムの一般的な機能を説明しています。しかし、私たちはコード自体についてコメントするのを忘れているようです。コードを注意深く読み、各行の意味を理解するまで読んでください。次に、このコードをコメント アウトし、各 TODO を、対応するコード行の目的または機能を説明するフレーズに置き換えます。(注: unsigned int は「unsigned」int であり、負の値にすることはできないことを意味します)。rand または srand に関する詳細情報を取得するには、以下を実行します。 man drand48 または man srand48 、generate.c で可能な限りコメントアウトした後、プログラムを再コンパイルして、何も壊れていないことを確認します。 make generate Generate がコンパイルされなくなった場合は、次の内容を修正します。壊れた:)! 念のために言っておきますが、makeコマンドはコードのコンパイルを自動化するため、多数のスイッチを手動で挿入して Clang コマンドを実行する必要はありません。しかし、実際には、make は単に入力を単純化するだけですが、実際には、必要なパラメータに関する同じ動作がその背後に隠されています。ただし、プログラムが大きくなるにつれて、make はコードをコンパイルする方法をコンテキストから判断できなくなります。この場合、特に異なるソース ファイル (.c など) を使用する場合は、プログラムのコンパイル方法を make に指示する必要があります。この問題を解決するには、make に何をすべきかを正確に伝える設定ファイル (Makefile) を使用します。make コマンドはどのようにコンパイル生成を行うべきかをどのようにして認識したのでしょうか? 実際、チームはすでに作成した構成ファイルを使用しました。このファイルはMakefileと呼ばれ、 generate.cと同じディレクトリにあります。Makefile は、generate.c から生成されるファイルの作成方法を指定するルールのリストです。このファイルでは、特に関連する行が見つかります。 generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c 最初の行は、2 行目からコマンドを呼び出して、generate という名前の「ターゲット」を作成する必要があることを make に指示します。さらに、最初の行は、generate がgenerate.c に依存していることを make に伝えます。これは、そのファイルが変更されている場合、make はその後の実行でのみ Generate を再構築することを意味します。時間節約の良い方法ではないでしょうか? 実際、generate.cを変更しなかった場合は、以下のコマンドを再度実行します。 make generate 生成がすでに現在のバージョンに更新されていることが通知されます。 注: 2 行目の先頭のインデントは一連のスペースではなく、タブ文字です。残念ながら、make ではコマンドの前にタブを付ける必要があるため、タブをスペースに変更しないように注意してください。変更しないと、奇妙なエラーが発生します。-Werrorフラグは、clangコマンドに指示します。警告 (悪い) をエラー (さらに悪い) として扱うと、(良い教育的な方法で!) 警告を修正する必要が生じます。次に、 find.cファイルを見てみましょう。このプログラムは 1 つのコマンド ライン引数「igloo」を必要とすることに注意してください。これは、値の「干し草の山」の中にある必要があります。その後、コードを確認し、以下のコマンドを実行してプログラムをコンパイルします。 make find make は基本的に次のことを提供してくれました: clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm 注意してください! これで、 helpers.cとfind.cの 2 つのファイルで構成されるアプリケーションがコンパイルされました。どうやってこのことを知りましたか？これを理解するには、もう一度 Makefile を開いて実際に何が起こっているかを確認してください。関連する行は以下のとおりです。 依存関係 (コロンの後) が意味するのは、 find.c、helpers.c、またはhelpers.hfind: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm を変更すると、次回それらの目的で呼び出されたときに、 make が find を強制的に再構築することです。次に、たとえば次のようにしてこのプログラムを実行します。 この後、特定のスタック (つまり、整数) を提供し、一度に 1 本のストローを与えるように求められます。数字を入力するのに飽きたら、Ctrl+Dというキーの組み合わせを押します。この組み合わせにより、プログラムにファイルの終わり (EOF) 文字が送信されます。このシンボルは、CS50 ライブラリのGetInt関数が定数INT_MAXを返すように強制し、これにより、find.cでfind が「stack」の入力を強制的に停止します。プログラムは、指定された干し草の山から針を探し、最終的に針が見つかったかどうかを通知します。つまり、プログラムは配列内の値を検索します。少なくとも彼女はそうすべきですが、問題は彼女がまだ何も見つけられないということです。しかし、ここであなたが助けに来ます！あなたの役割の重要性については、後ほどお話します。実際、干し草の山を提供するプロセスは、少なくとも、generate の出力を入力として find に「マージ」することによって自動化できます。たとえば、以下のコマンドは、find に 1000 個の擬似乱数を渡し、それらの値の中から 42 を検索します。generate が find に生データを渡すと、generate の数値は表示されませんが、find が実行されているのが表示されることに注意してください。 。あるいは、次のようなコマンドを使用して、generate の出力をファイルに「リダイレクト」することもできます。 このファイルの内容は、次のコマンドを使用して find の入力にリダイレクトできます。 Makefile 内のコードをもう一度見てみましょう。次の行: これは、次のコマンドを実行すると、ビルド生成と検索ができることを意味します。 さらに、make はデフォルトで Makefile の最初のエントリをビルドするため、この行の下のコマンドはその上にあるコマンドと同等です。 ./find 13./generate 1000 | ./find 42./generate 1000 > numbers.txt./find 42 < numbers.txtall: find generatemake allmake これらすべての練習タスクを 1 つのコマンドに要約できればよかったのですが。しかし悲しいかな！最後に、Makefile の最後の行に注意してください。 clean: rm -f *.o a.out core find generate このエントリを使用すると、.o で終わるファイル、または core と呼ばれるすべてのファイルを削除できます (これについてはすぐに説明します!)。また、単純にプログラムの検索または生成を実行することもできます。次の行を実行します。 実験したい場合は make clean 、次の点に注意してください。Makefileの最後の行に、たとえば*.c などを追加しないでください。(なぜですか?) # 記号で始まる行はすべて単なるコメントです。

タスク 1: 検索

何か面白いことをする時間です！find.c は、 helpers.hで宣言された関数searchを呼び出すことに注意してください。残念ながら、この関数をhelpers.cに完全に実装するのを忘れていました。( helpers.hとhelpers.cの内容を1 つのfind.cに入れることもできることに注意してください。しかし、場合によっては、プログラムを複数のファイルに分割した方が良い場合もあります。特に、いくつかの関数、またはむしろユーティリティ関数が役立つ場合は、他のプログラムの場合は、たとえば CS50 ライブラリ関数と同様です。helpers.cを見ると、指定された値が値に含まれるかどうかに関係なく、検索が常に false を返すことがわかります。線形検索を使用するように検索を書き換えて、true を返すようにしてください。 , value がvalues にある場合は、value がvalues にない場合は false を返します。n が正でない場合は、すぐに false を返すように注意してください。有効性を確認 する準備ができたら、次のコマンドを呼び出してみてください。 50 がシードされたときに生成された値が 127 の場合、コードはニードルを見つける必要があります! 対照的に、次のコマンドを試してみてください: 128 は、50 がシードされたときに生成 によって生成された数値のセットに含まれていないため、コードは「ニードル」を見つける必要はありません。いくつかのシードを使用して生成を実行し、出力を分析し、干し草の山の中にあるはずの針を探すことによって、他のテストを実行します。find.c の main は、「針」が見つかった場合は find が 0 を返し、見つからなかった場合は 1 を返すように書かれていることに注意してください。他のプログラムを実行した後に実行されたときに main が返すいわゆる「出力コード」を確認できます。コマンド 。たとえば、検索の実装が正しい場合、実行すると 0 が表示されますが、シード 50 で生成によって出力される 1000 個の数値には 127 が含まれるため、作成した検索は true を返すはずです。この場合、main (私たちが作成した) は 0 (つまり終了) を返す必要があります。次の入力を与えると 、128 はシード 50 で生成によって出力された 1000 個の数値の中に含まれていないため、1 が表示されます。この場合、search (ユーザーが作成した) は false を返し、main (弊社が作成した) は false を返します。 ) は 1 を返します (そしてジョブを終了します)。ロジックは理解できていますか？check50 を使用してすべてをチェックする準備ができたら、次のコマンドを実行します。 ./generate 1000 50 | ./find 127./generate 1000 50 | ./find 128echo $?./generate 1000 50 | ./find 127 echo $?./generate 1000 50 | ./find 128 echo $?check50 2015.fall.pset3.find helpers.c ちなみに、自分でコードをテストする前に、check50 を使用してコードをテストすることに慣れるべきではありません。結局のところ、check50 は実際には存在しないので、独自の入力サンプルを使用してコードを実行し、実際の出力と予想される出力を比較することが、現時点で身につけることができる最良の習慣です。それは本当です、依存症にならないでください！cs50 アシスタントの find 実装を試してみたい場合は、次のコマンドを実行します。 ~cs50/pset3/find

仕分け

線形探索はそれほど印象に残るものではありませんが、最初の講義 (7 回目でこのトリックをもう一度繰り返しました!) で、干し草の山から針をはるかに速く見つけることができることを覚えているでしょう。しかし、まず干し草の山を分類する必要があります。find.c は、 helpers.hで宣言された関数であるsortを呼び出すことに注意してください。残念ながら、この機能をhelpers.cに完全に実装することを「忘れて」しまいました。helpers.cを調べてみる と、find の main 関数が実際には実際の配列を渡しているにもかかわらず、sort が即座に返されることがわかります。ここで、配列宣言の構文を思い出してください。この配列の要素タイプを指定するだけでなく、そのサイズも角かっこで指定します。これは、 find.cの haystack に対して行うことです。 ただし、配列を走査するときは、その名前のみを指定します。そして、 find.cでソートを行うために干し草の山を通過するときも、まったく同じ方法でそれを行います: (なぜその配列のサイズを個別に渡すかわかりますか?) 1 次元配列を引数として受け取る関数を宣言するとき、配列のサイズを指定する必要はありません。同様に、helpers.h (および helpers.c) で sort を宣言したときにこれを実行しませんでした。 関数が実際に数値の配列を小さい値から大きい値に並べ替えるように、sort を実装します。^{実行時間は O(n 2} )に等しい必要があります(n は配列のサイズです)。第 3 週で学習したように、バブル ソート、選択ソート、または挿入ソートを実装するとよいでしょう。ただし、これらのアルゴリズムを実装する「正しい」方法はないことに注意することが重要です。膨大な数のバリエーションがあります。^{実際、実装が O(n2 )}に収束する限り、適切だと思われる場合はいつでも改善できます。ただし、実験は関数本体に任せ、テストを簡素化するために、ソート宣言は変更しないでください。この 関数は void 値を返すため、ソートされた配列を返すべきではありません。代わりに、「実行」している実際の配列を「破壊的に」ソートし、その要素を移動する必要があります。第 4 週では、配列が値ではなく参照によって渡されることについて説明します。つまり、sort は配列のコピーではなく、元の配列自体を受け取ります。ソート宣言を変更することはできませんが、いつでも helpers.c で独自の関数を定義でき、その関数を sort から呼び出すことができます。ソートの実装をテストする最適な方法を自分で決定してください。printf と GDB が役に立つことを忘れないでください。また、生成のシード値を明示的に指定することで、同じ擬似乱数のシーケンスを何度も作成できることを忘れないでください。 int haystack [MAX];sort (haystack, size);void sort (int values [] int n);void sort (int values [] int n);

二分探索、ヒント

find関数 について最初に理解する必要があるのは、コード (配布) がすでに記述されていることです。既存のコードのいくつかのギャップを埋めているだけです。find.cプログラムは、数値の入力を要求し (つまり、「スタック」を埋めるため)、ユーザーの要求に応じて、 helpers.c で定義されているソート関数と検索関数を使用して、その中の「針」を検索します。したがって、findはすでに書かれているので、ヘルパーを書く必要があります。したがって、次のことを行う必要があります。

1. 検索を実装します。この関数は、スタック内に値が見つかった場合は true を返し、スタックに値が見つからない場合は false を返す必要があります。
2. 値の配列を並べ替える関数、sort を実装します。

当初、検索は線形として実装されました。しかし、もっとうまくやることもできます。線形探索アルゴリズムはO(n)時間で実行されます。あなたのタスクは、二分探索アルゴリズムを作成することです。実行時間はO(log n)です。ただし、問題は、入力としてソートされたデータが必要であり、そうでないと機能しないことです。破れた本の例を覚えているでしょうし、なぜそうなるのかはおそらくご存知でしょう。要素の二分探索を実行し、要素がもう残っていない場合 (つまり、この「スタック」に単に「針」がない場合)、関数が false を返す必要があります。二分探索は反復的または再帰的に実装できます (David Malan は第 8 回の講義で再帰について話しました)。