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

ハーバード大学プログラミング基礎講義 CS50 追加資料: 漸近記法、ソートおよび検索アルゴリズム 第 3 週の課題、パート 1. ソートと検索。

ゲームが始まります！

遊ぶ時間だよ！パズルゲーム「鬼ごっこ」は多くの人が知っているでしょう。形式的に言うと、「タグ」は 4x4 の 2 次元フィールドです。このフィールドには 16 個ではなく 15 個の正方形があり、つまり 1 つのスロットが空のままです。それぞれの四角形には番号が付けられており、フィールド内で水平または垂直に移動できます (もちろん、移動する余地がある場合)。目標は、1 から 15 までの数字を左から右、上から下に順番に配置することです。すると、右下隅に空きスペースができます。このゲーム空間では、任意のタイル (またはいくつか) の移動が「ステップ」です。上の図に示されている組み合わせはすでに積み重ねられていますが、空いたスペースに 12 または 15 個のタイルを押し込むことができることに注意してください。ルールでは、タイルを斜めに動かしたり、ボードから削除したりすることはできません。ゲームを開始するには実際には多くの構成があります (正確にいくつ数えることもできます) が、簡単にするために、タイルを最大から最小の順に配置し、ボードの右下隅に空きスペースを残しておきます。 。唯一のことは、パズルが解けるように 1 と 2 を交換しましょう。 次に、ワークベンチの~/ディレクトリに移動し、 /pset3/fifteenに移動して、fifteen.cを開きます。ゲームエンジンのコードが含まれています。タスクは、ゲームにコードを追加することです。まず、「エンジン」をコンパイルしましょう (おそらく、その方法はすでにご存知でしょう)。ゲームが終了していないにもかかわらず、アプリケーションを起動できます。通常より大きなターミナル ウィンドウで実行すると便利です。ターミナル ウィンドウは、コード タブの 1 つの横にある緑色のプラス (+) をクリックし、 [新しいターミナル] を選択すると開きます。または、コンソールの右上隅にある最大化アイコンをクリックして、ターミナル ウィンドウを全画面で開くこともできます。いくつかのことが何らかの形で機能していることがわかります。しかし実際には、ゲームの大部分はまだ書かれていません。そしてここで - 準備を - 出口です!

勉強

fifteen.c の コードとコメントを調べて、以下の質問に答えてください。

1. 4x4 ボードとは別に、私たちのエンジンはどのようなフィールド サイズを許可しますか?
2. ゲームフィールドはどのようなデータ構造ですか?
3. ゲームの開始時にプレイヤーに挨拶するために呼び出される関数は何ですか?
4. どのような機能を実装する必要がありますか?
5. 注: 質問に正しく答えたかどうかを自動チェックで確認したい場合は、ファイル fifteen.c の隣にあるファイル fifteen.txt を見つけて、その中に質問に対する答えを書き留めます。

実装

さて、ゲームの実装を始めましょう。覚えておいてください、私たちは小さなステップで進んでいます。一度にすべてをやろうとしないでください。代わりに、機能を一度に 1 つずつ実装し、機能することを確認してから次に進みましょう。特に、init (初期化)、draw (描画)、move (一歩踏み出す)、won (勝利) の順序でゲーム関数を実装することをお勧めします。デザイン上の決定 (番号タイル間に挿入するスペースの量など) はお客様自身で決定してください。競技フィールドは次のようになります。 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ 繰り返しになりますが、開始位置では 1 と 2 が逆の順序で配置されていることに注意してください (タイルの数が奇数の場合、これは古典的な 4x4 フィールドに当てはまります)。タイルの数が偶数で、フィールドが 3x3 の場合、2 つの「最も低い」タイルを交換する必要はありません。 8 7 6 5 4 3 2 1 _ 「タグ」の実装をテストするには、それらを再生してみる必要があります (忘れないでください。crtl+c のキーの組み合わせを押すと、自然に完了する前にプログラムを終了できます)。間違った数値が入力された場合でもプログラムが動作することを確認してください。find への入力を自動化したのと同じように、ゲームの「ウォークスルー」も自動化できることを忘れないでください。実際、~cs50/pset3フォルダーには、 3x3.txtおよび4x4.txtというファイルがあります。これらのファイルには、3x3 および 4x4 フィールドで勝つための一連のステップがすべて含まれています。たとえば、最初のファイルを使用してプログラムをテストするには、次のコマンドを実行します。 ./fifteen 3 < ~cs50/pset3/3x3.txt アニメーションの速度を上げるために必要な引数を設定します。そして一般的に、必要に応じていつでもゲームを変更できます。色も含めて「ANSIエスケープシーケンス」を楽しむために。Clear の実装を確認し、 http://isthe.com/chongo/tech/comp/ansi_escapes.htmlをチェックして新しいトリックを学びましょう。必要に応じて、独自の関数を作成するか、作成した関数のプロトタイプを変更してください。唯一の制限は、main 関数のロジックを変更しないことです。変更しないと、プログラムが正しく動作していることを確認するための自動テストを適用できなくなります。特に、ユーザーがパズルを解いた場合に限り、main は 0 を返さなければなりません。すべてのエラー オプションに対してゼロ以外の値を返す必要があります。エラーが発生した場合は、当社までご連絡ください。CS50 アシスタントによって準備されたアプリケーションの実装を試してみたい場合は、次のコマンドを実行します。 ~cs50/pset3/fifteen 自動パズル解決機能を備えたより優れた実装に興味がある場合は、プログラムの「Hacker」バージョンをチェックしてください。 ~cs50/hacker3/fifteen ゲームウィンドウに数字を入力する代わりに、「GOD」という単語を入力します。。素晴らしいですね。check50 を使用してプログラムの正しさを正式にチェックしたい場合、check50 はプレイフィールドの空きスペースが 0 で埋められていると想定していることに注意してください。別の値を選択した場合は、正しく検証するためにゼロに置き換えてください。また、check50 は、ボードフィールドのインデックスをボード [列] [行] ではなく、[行] [列] の順序で作成していることを前提としています。 check50 2015.fall.pset3.fifteen fifteen.c

Fifteen ゲーム機能の実装について詳しく見る

• init (初期化)
• 描く
• 動く（一歩を踏み出す）
• 勝ちました（勝ちました）

初期化

この機能では、競技場を紹介します。これを行うには、整数の 2 次元配列を使用します。配列の次元は MAX x MAX です。MAX は、フィールドの行または列に収まるタイルの最大数を示す定数です。したがって、変数int board[MAX][MAX]を定義する必要があります 。ただし、競技場のサイズはユーザーによって決定されることに注意してください。したがって、ユーザーが入力する必要がある基板サイズを示す変数を定義する必要があります。これはint dです。ここで、d は基板の寸法、d <= MAX です。ただし、C では配列のサイズを変更できないため、最大サイズを決める必要があります。initでは、ボードに値を配置する必要があります。 2 次元配列をまだ扱ったことがない場合は、詳細を読んでください。つまり、これらには 2 つのインデックスがあり、1 つ目は行番号を示し、2 つ目は列番号を示します。この問題では、最大数から開始し、d = 3 (「8」) の場合、1 と空の角で終了します。まだ「タグ」がある場合は、1 と 2 を交換します。空いたスペースをどうするか？配列は整数で構成されているため、空隙を整数で埋める必要があります。したがって、空のタイル (または、物理ゲームの場合はタイルが存在しない) を初期化するには、何らかの整数を選択する必要があります。ループを使用すると、ゲーム ボードを初期化し、タイルの開始セットでゲーム ボードを埋めることができます。インデックス i と j をループします。ここで、board[i][j]は行番号 i、列番号 j にあるタイルです。ボードを降順に埋めていきます。タイルの数（空のタイルを除く）が奇数の場合は、1 と 2 を交換します。

描く

この関数は、プレイフィールドの現在の状態を出力する必要があります。1 桁または 2 桁の値を指定できるため、1 ～ 9 の数字の後に美しい書式設定をするには、関数でスペース ( #s ) を出力する必要があることに注意してください。これは、 %2dプレースホルダーを使用して実行できます。 printf (“%2d”, board[i][j]); 空のセルも忘れないでください。それを表す文字を選択します (この例では、これはアンダースコアです)。描画関数は、空のセルに到達するとすぐにこの文字を描画する必要があります。したがって、ループは次のようになります。 for каждой строки for каждого element строки print meaning и пробел print новую строку 描画関数がタイルを画面に描画する順序は、 init 関数で定義された配列内のタイルの順序を反映する必要があることに注意してください。

動く

プレイフィールドを初期化し、タイルの初期位置を描画したら、ユーザーがタイルの位置を編集、つまり移動できるようにする必要があります。したがって、Fifteen.cでは、プログラムはユーザーからの出力を受け取り、ゲーム ボードを構築し、次に move 関数を呼び出して、どのタイルを移動したいかをユーザーに伝えます。注意してください。この関数は、ボード上 (配列内) の位置ではなく、タイル上の番号にのみ適用されます。したがって、タイルの実際の位置を見つける必要があります。さらに、可能な場合にのみ、ユーザーにタイルの移動を許可する必要があります。 上の図では、2、5、8 番のタイルのみを移動できます。これはどうやって判断するのでしょうか? 空のタイルの値による。したがって、move関数は次のように動作します。

• ユーザーが移動したいタイル番号を受け入れます
• このタイルの配列内で (競技フィールド上で) 位置を探します
• 空のタイルの位置を記憶します
• 空のタイルがユーザーが移動したいタイルに隣接している場合、それらは配列内で交換されます。

勝利した

この関数は、ユーザーの各ステップの後にゲームが終了したかどうかを確認します。タイルが正しい順序 (右下隅の空のタイルの位置を含む) にある場合は true を返します。この場合、プログラムを終了することができます。タイルがまだ分散している場合、関数は false を返し、手綱を移動関数に渡します。検査をどのように組織するか? ボードの初期化と描画の場合と同様に、2 つのネストされた for ループを使用します。たとえば、配列内の後続の各数値が前の数値より大きくなければならないという条件を設定できます。空のタイルにどのような値が書き込まれているかに注目してください。または、別の方法 - カウンターを使用して、すべてのタイルが所定の位置にあることを確認します (カウンターを処理して、それを取得するための式を書くことができる場合)。実験の成功を祈っています。

コードを検証してマークを取得する方法

注意！タスクの正確性のみをチェックすることが重要な場合は、cs50check を使用します。edx プラットフォームで成績を取得したい場合は、以下に説明する手順に従ってください。この手順では、同じ cs50check を使用してタスクをチェックすることに注意してください。唯一の違いは、結果を記憶し、総合スコアを計算することです。

1. CS50 IDEにログイン
2. CS50 IDE の左上隅付近(ターミナル ウィンドウ内ではなく) ファイル ブラウザが配置されている場所で、 pset3 ディレクトリを右クリックし、 [ダウンロード]をクリックします。ブラウザがpset3.tar.gzアーカイブをダウンロードしたことがわかります。
3. 別のウィンドウまたはタブで、CS50にログインします。
4. 画面の左上隅にある送信アイコンをクリックします
5. 左側のフォルダーのリストで、問題セット 3ディレクトリをクリックし、[新しい提出物のアップロード] ボタンをクリックします。それは右側にあります。
6. 表示される画面で、「ファイルを追加...」ボタンをクリックします。コンピュータからファイルを選択するためのウィンドウが開きます。
7. pset3.tar.gz を保存したフォルダーに移動します。おそらく、ダウンロードフォルダー、またはブラウザーがデフォルトでファイルを配置する場所に保存されています。pset3.tar.gz を見つけたら、それを 1 回クリックして選択し、「開く」をクリックします。
8. [アップロードの開始]をクリックします。ファイルはCS50サーバーにアップロードされます。
9. 表示される画面に、「ファイルが選択されていません」ウィンドウが表示されます。マウスカーソルを左に動かすと、ダウンロードしたファイルの一覧が表示されます。確認するには、それぞれをクリックしてください。何か不明な点がある場合は、同じ手順を繰り返してファイルを再アップロードできます。2016 年末までは何度でも行うことができます。