ロブ·ボウデンは：こんにちは、私は、ロブ·ボーデンよ そしてそれではquiz0について話しましょう​​。 だから、最初の質問。 これは質問場所です あなたは番号をコード化するために必要な バイナリ球根127。 あなたが望む場合は、可能性 定期的な変換を行う bi--から、または、小数からバイナリへ。 しかし、それはおそらく起こっている 多くの時間を取る。 私は、あなたがそれを見つけ出すことができ、意味、 [OK]を、1は2がそこにある、そこにある、 図4は、8がそこにある、そこにある。 簡単な方法は、127は128から1を引いている。 その左端の電球は、128ビットである。 だから、127はちょうど、すべて実際にある 他の電球の、 それは左端のだから 電球マイナス1。 つまり、その質問はこれでおしまい。 質問1。 あなたができる3ビットでそう 8個別の値を表している。 なぜ、その後、7最大の非負で あなたが表現できる進整数？ さて、唯一の私達ができる場合 8個別の値を表し、 その後、私たちがあることになるだろう 代表は0〜7です。 0のいずれかの値をとる。 質問2。 nビットで、どのように多くの異なる 値は、あなたが表現することができますか？ したがって、nビットでは、2を有している ビットごとに指定可能な値。 だから我々は2の可能な値を持っている 最初のビット、2の可能な値 第二のために、2 第三の可能な。 そしてそうそれは2倍2倍2だし、 最終的に答えはnに2である。 質問3。 バイナリで0x50のは何ですか？ だから進数が非常に持っていることを覚えている バイナリへの直接的な変換。 だからここ、私たちは見てする必要があり 5と独立して、0。 だから、バイナリで5何ですか？ 0101、それは1ビットおよび4ビットです。 バイナリで0は何ですか？ トリッキーではない。 0000。 だから、それらを一緒に入れて、 それは、バイナリでの完全数です。 01010000。 あなたが望んでいる場合、あなたは可能性 その左端のゼロを脱ぐ。 それは無関係だ。 それでは代わりに、 進数で0x50のは何ですか？ あなたが望む場合は、している場合は、could-- バイナリより快適、 あなたはそのバイナリ答えを取ることができる と小数にそれを変換します。 または私達はただ覚えることができる その進。 0ようにすると、0番目の場所にあり、かつ 図5は、最初の場所に16である。 だからここでは、5〜16倍を持っている まず、ゼロにプラス0回16、 80です。 そして、あなたが見ている場合 質問へのタイトル、 それはのようなものだった、CS 80、だった この問題への答えへのヒント。 質問5。 私たちは、このスクラッチスクリプトを持っている 4回ピーナッツバターゼリーを繰り返す。 では、どのようにC言語でコードになりましたことをやる？ まあ、我々は太字でhere--部分を持っている あなたが実装しなければならなかった唯一の部分である。 だから我々は4ループだ4ループを持っている 回、printfの - INGのピーナッツバターゼリー、 問題として持つ新しい行が要求されます。 質問6、別のスクラッチの問題。 私たちは永遠にループしていることがわかります。 私たちは、変数iを言っている その後iを1だけインクリメントする。 今、私たちはCでありますことをやってみたい 我々はこれを行っている可能性が複数の方法。 ここでは、コーディングすることが起こった しばらく（真）として永遠にループ。 だから私たちは私はちょうど、変数を宣言 我々はスクラッチで変数iを持っていたような。 変数iを宣言し、永遠に （真）しながら、我々は変数iを言う。 printfの％i--たり、％dを使用していたかもしれないので。 私たちは、その変数を言うと、 それをインクリメント、私はC ++。 質問7。 今、私たちは非常によく似た何かをしたい 問題からマリオドットcに1を設定します。 我々は、これらのハッシュタグを印刷したい、 私たちは5を印刷したい これらのハッシュの3長方形で。 では、どのようにそれを行うつもりですか？ さて、私たちはあなたに全体を与える コー​​ドの束、そしてあなただけの 印刷グリッド機能に記入しなければならない。 だから何PrintGridは次のようになりません？ さてあなたは過ぎている 幅と高さ。 だから我々は、外側を持っている4 ループは、それがループだ これのすべての行の上 私たちはプリントアウトしたいグリッド。 その後、我々は、インターネストされた4ループを持っている それは各列での印刷です。 だから、行ごとに、私達はのために印刷する 各列は、単一のハッシュ。 その行の終わりに、我々は印刷する 単一の新しい行が次の行に移動します。 そして、それはグリッド全体のためにそれだ。 質問8。 PrintGridのような関数はと言われている リターン副作用がないの 値。 区別を説明してください。 だから、これは覚えてあなたに依存しています 副作用は何であるか。 さて、復帰value-- 我々はPrintGridにはない知っている ので、戻り値を持つ 右ここでそれは無効と述べています。 voidを返すので、何でも 本当に何も返しません。 だから、副作用は何ですか？ さて、副作用である ソートの持続するもの 機能終了後 それは、単に返されませんでした そしてそれだけで入力からではなかった。 したがって、たとえば、我々は、可能性がある グローバル変数を変更します。 つまり副作用であろう。 この特定のケースでは、A 非常に重要な副作用 画面に印刷されている。 だから副作用である PrintGridが持っていること。 私たちは、画面にこれらの事を印刷してください。 そして、あなたは考えることができます その副作用として、 それはその何かだから この関数は終了後に持続する。 つまり、スコープ外の何か 最終的にはこの関数の 変更され、 画面の内容。 質問9。 以下のプログラムを考え、 どのライン番号へ 追加されました 議論のために。 したがって、このプログラムの中で私達はちょうどです それを保存、のGetStringを呼び出す この変数sで、その後、 その変数s印刷。 [OK]をクリックします。 ライン1が存在している理由をそう説明する。 インクルードCS50ドット時間。 なぜ我々はCS50ドットhのを#i​​ncludeする必要がありますか？ まあ我々は呼んでいる のGetString機能、 とのGetStringが定義されている CS50ライブラリ内の。 だから我々は持っていなかった場合は、 の#include CS50ドットhの、 我々はその暗黙的な宣言になるだろう のGetString関数エラーの コンパイラから。 だから我々はlibrary--を含める必要が 我々はヘッダファイルをインクルードする必要があり、 あるいはコンパイラはしません のGetStringが存在することを認識しています。 ライン2が存在する理由を説明する。 だから、標準入出力ドット時間。 それはまったく同じだ 以前の問題として、 代わりに対処するのを除いて のGetString、我々はprintfの話をしている。 だから我々は我々が必要と言っていなかった場合 標準IOドットhを含めるには、 その後、我々はできないだろう printf関数を使用するには、 コンパイラ理由 それについて知っているだろう。 Why--意義は何ですか ライン4におけるボイドの？ そこでここではint型メイン（ボイド）がある。 それはちょうど、その私たちを言っている 任意のコマンドラインを取得されていません 主への引数。 我々はint型を言うことができることを忘れないでください メインint型のargc文字列ARGVブラケット。 そこでここでは、単に私たちに言っても、ボイド言う コマンドライン引数を無視している。 正確に、メモリに関しては、説明 ライン内の何のGetString 6に戻ります。 のGetStringは、ブロックを返して メモリ、文字の配列。 それは本当に戻っています 最初の文字へのポインタ。 文字列はchar型の星であることを覚えておいてください。 だから、sが最初にへのポインタである 文字列が何であれ、文字 ユーザーがキーボードで入力されたもの。 そのメモリはmallocされるようなことが起こる、 その結果、メモリはヒープ内である。 質問13。 以下のプログラムを考えてみましょう。 だから、このすべてのプログラムがやっている 10で割ったのprintf - INGの1がある。 だから、コンパイルされたとき 実行され、このプログラム 出力は0.0、たとえ 10で割って1が0.1である。 では、なぜそれが0.0である？ まあ、これは理由である 整数除算の。 だから1は10の整数であり、整数である。 だから1すべて、10で割った 整数として扱われ、 とCで、我々は整数の除算を行うときに、 我々はすべて小数点以下を切り捨てる。 だから、1 10で割っている 0、その後、我々はしようとしている そう、floatとしてそれを印刷する floatとして印刷されたゼロは0.0です。 我々は0.0を取得した理由、それはです。 以下のプログラムを考えてみましょう。 今、私たちは0.1を印刷している。 だからなし整数除算、 私達はちょうど0.1を印刷している、 しかし、我々はそれを印刷している 28小数点以下まで。 そして、我々はこの0.1000、全体の束を取得 ゼロの、5 5 5、何とか何とか何とか。 それをしない理由ので、ここで質問です ことを、代わりに正確に0.1印刷？ だからここに理由が今ある 浮動小数点の不正確。 フロートが唯一の32ビットであることを覚えておいてください。 だから我々は唯一の有限数を表すことができます 業者32と浮動小数点値 ビット。 まあ、最終的には無限にあります 多くの浮動小数点値、 と浮動多くは無限にあります 0と1の間のポイント値、 そして我々は明らかにすることができるしている それよりも多くの値を表す。 だから我々はに犠牲をしなければならない ほとんどの値を表現することができる。 だから、0.1のような値、どうやら 我々はそれを正確に表すことはできません。 だからではなく、0.1を表現致しております 最高の私たちは、この0.100000 5を表すことができます 5。 そして、それはかなり近いですが、 多くのアプリケーションのための あなたが心配する必要は 浮動小数点の不正確さ、 我々だけで表すことはできませんので、 すべての浮動ポイントを正確に。 質問15。 以下のコードを考えてみましょう。 私達はちょうど1プラス1を印刷している。 だから、ここにはトリックはありません。 1プラス1が2と評価され、 それから私達はそれを印刷している。 これは単に2を印刷します。 質問16。 今、私たちは、文字を印刷している 1プラス1文字。 では、なぜこのません 同じことを印刷？ さて、文字1文字プラス 図1は、文字1はASCII値49を有している。 だから、これは本当に49プラス49を言っている、と 最終的にはこれが98を印刷しようとしている。 だから、これは2を印刷しません。 質問17。 実装を完了します そのような方法で、下記の奇数 関数は、以下の場合にtrueを返すこと nが偶数の場合nが奇数とfalseです。 これは素晴らしい目的です mod演算子のために。 だから我々は我々の引数nを取り、 n個のmod 2がウェル1に等しい場合 それは、n分割することを意味します 2で、残りを持っていた。 nは、2で割った場合は、残りの部分を持っていた nが奇数であるので、我々は真を返すことを意味します。 ほかに、我々はfalseを返します。 また、2等号をmod nを行っている可能性が ゼロは、他に、falseを返すtrueを返す。 下記の再帰関数を考えてみましょう。 だから、nが以下である場合 1戻り、1に等しく、 n個のfの他にリターンn回マイナス1。 この関数は何ですか？ まあ、これはただです 階乗関数。 これがうまく表現されている n個の階乗として。 だから我々がしたい、今19を疑問視 この再帰関数を取る。 我々は、それが反復的にしたい。 だから我々はそれをどのように行うのですか？ よくスタッフのための ソリューションは、再度あります あなたが行っている可能性が複数の方法 それが、我々はこのint型の製品で始まる 1に等しい。 そして、この全体 forループ、我々はつもりだ 最終的に製品を掛けるべき 完全要因で終わる。 int型のためにiが2に等しいだから、私はある n以下は、私は++。 iが2に等しいなぜあなたは不思議に思われるかもしれません。 さて、ここで私たちがしなければならないことを覚えている 私たちのベースケースが正しいことを確認してください。 そこで、nが以下である場合 1に、私達はちょうど1を返している。 だからここの上に、我々はiが2に等しいから始まります。 さて私は1であったならば、the--か nが1であった場合、forループ まったく実行しないであろう。 だから私達はちょうどだろう 1であるリターン製品。 同様に、nがあった 1--未満のもの それが0であった場合には負の1、whatever-- 我々はまだ、1を返すことだろう まさにこれです 再帰的なバージョンがやっている。 ここで、nが大きい場合 1よりも、我々はつもりだ 少なくとも一つを行うには このループの繰り返し。 それでは私たちがしている、のnが5であるとしましょう 製品の時間をするつもりは、2に等しい。 だから今の製品は2です。 今、私たちはやろうとしている 製品時間は3に等しい。 今では6です。 製品の倍になりましたそれは24だ、4に等しい。 製品の回今では120ですが、5に等しい。 それでは最終的に、我々は戻っている 正しく5階乗である120、。 質問20。 これは、あなたが入力する必要が1である 任意のアルゴリズムを用いて、この表の、 私たちが見てきたもの、その これらのアルゴリズムの実行にフィット 回これらの漸近実行時間。 だから、そのアルゴリズムは何ですか 1のオメガが、n個の大きなOで？ だから、無限にある可能性があり ここに多くの答え。 我々は、おそらく最も見てきた1 頻繁にちょうど線形検索です。 最良のケースで非常に シナリオ、我々はしているアイテム を探しているである リストの先頭 したがって1ステップのオメガで、 我々はチェックまず最初、 私達はちょうどすぐに戻り 私達が項目を見つけたこと。 最悪の場合、 項目は、最後にあり またはアイテムが全くリストにありません。 だから我々は検索する必要が リスト全体、すべてのn 要素、およびそれがn個のOが理由です。 だから今、それは両方だ何か n個のログのωn、およびnはログnの大きなO。 さて、最も関連性の高いもの 私たちはここで見てきたソートマージである。 だから、マージソート、覚えている、 最終的にはシータです シータが定義されているn個のログnの オメガとビッグOの両方が同じである場合。 両方N Nをログに記録します。 オメガの何か何ですか n個の、nがOの二乗？ さて、再びそこだ 複数の可能な答え。 ここでは、バブルソートを言うために起こる。 挿入ソートもここで働くだろう。 そのバブルソートを覚えている その最適化はどこにあります、 あなたが得ることができる場合 リスト全体を通して 何を必要とせず どんなスワップ、その後、よく、 我々はすぐにそれを返すことができます リストはそもそもソートした。 そこで最良のシナリオにおいて、 それはちょうど、オメガ、nのだ。 それだけでうまくはない場合 そもそもリストをソートし、 次に我々は、nのOがスワップを二乗している。 そして最後に、私たちは選択ソートを持っている nに、オメガとビッグOの両方を乗 質問21。 整数オーバーフローとは何ですか？ さて、再び、以前と同様に、 我々は唯一の有限個のビットを持っている 整数を表現する、 ので、多分32ビット。 それでは私たちは符号付き整数があるとしましょう​​。 そして、最終的に最も高い 私たちが表現できる正の数 ある2から31のマイナス1。 私たちがしようとした場合に何が起こる その整数をインクリメント？ さて、私たちは2から31に行くつもりだ マイナス1、ダウン負2へのすべての道 31。 したがって、この整数のオーバーフローがある あなたがインクリメント保つとき、 そして最終的にあなたがすることはできません ただの高く、かつそれを得る すべての道バックラップ 負の値に周り。 バッファオーバーフローはどう？ だから、バッファoverflow-- バッファが何であるかを覚えています。 これは、メモリのほんのチャンクです。 配列のようなものがバッファです。 だから、バッファオーバーフローがあるとき あなたは、メモリにアクセスしよう その配列の末尾を越えて。 だから、あなたが持っている場合 サイズ5、あなたの配列 配列ブラケットにアクセスしようとする 5またはブラケット6またはブラケット7、 か何かを越えて 最後、あるいは何か 負below--アレイ·ブラケット1-- それらのすべてがバッファオーバーフローである。 あなたが悪いかの方法でメモリに触れている。 質問23。 あなたが必要とするこの1中のSO のstrlenを実装する。 そして、我々はあなたができることを教えてくれ sがnullにすることはできませんと仮定し、 そうあなたがする必要はありません ヌルのための任意のチェックを行う。 そして、複数の方法があります あなたはこれを行っている可能性があります。 ここでは、ただ単純明快を取る。 我々はカウンターで始まり、n個。 nは ある文字数カウント。 だから我々は0から始まり、その後、私たち リスト全体を反復処理。 Sブラケット0に等しい ヌル終端文字？ 私たちが探している覚えている ヌル終端文字 私たちの文字列がどのくらいかを決定する。 つまり、終了しようとしている 関連するすべての文字列。 だからSブラケット0が等しい NULL終止符？ そうでない場合は、我々はするつもりだ Sブラケット1、Sブラケット2を見てください。 私達は私達まで続ける ヌルターミネータを見つける。 我々はそれを見つけたら、次にnが含まれています 文字列の長さの合計、 私たちはまさにそれを返すことができます。 質問24。 だから、これは1つのどこにある トレードオフを確認する必要があります。 だから、一つのことは、一つに良いです 方法があるが、どのような方法でそれが悪いのですか？ だからここに、マージソートする傾向 バブルソートよりも高速。 よく、そこにthat--言っても 複数回答はここにある。 しかし、主な1は、そのバブルソートです ソートされたリストのためのnのオメガです。 我々だけで前に見たそのテーブルを覚えています。 だからバブルはオメガをソート nは、最良のシナリオ それだけでオーバー行くことができますです 一度リスト、決定 ちょっとこの事は既にある ソートされ、リターン。 どんな、マージソートません あなたは、n個のログnのオメガです。 だから、ソートされたリストについては、バブル ソートより速いことになるだろう。 今何リンクリストはどうですか？ だから、リンクリストが成長し、縮小することができます 必要な数の要素を合わせて。 そうthat--言っても 通常、直接比較 リンクされようとしている 配列を持つリスト。 そうであってもアレイができますが 簡単に成長し、縮小 など多くの要素を合わせて 必要に応じて、リンクリストなど array-- ANに比べ アレイは、ランダムアクセスを有する。 私たちはどんなへのインデックスができます 配列の特定の要素。 だから、リンクリストのために、我々はできない ちょうど5番目の要素に移動し、 私たちは最初から横断する必要が 私たちは第5要素に到達するまで。 そして、それはから私たちを防ぐために起こっている バイナリサーチのようなものをやって。 バイナリサーチといえば、バイナリサーチ 線形検索よりも速くなる傾向にある。 that--言っても そう、一つの可能​​な事 あなたがバイナリを実行することができないということです リンクリストの検索、 あなただけのアレイ上でそれを行うことができます。 おそらくより重要なことに、 あなたがバイナリ検索を行うことはできません ソートされていないアレイ上。 Upfrontのあなたはソートする必要があるかもしれません アレイと、その場合にのみ、 あなたは、バイナリ検索を行う。 だから、あなたのものでない場合 そもそもソート、 線形検索は速くなるかもしれません。 質問27。 だから、下のプログラムを考え、 その次のスライドになります。 そして、これは私たちがしている一つです 明示的に指定したいだろう さまざまな変数の値。 それでは、その見てみましょう。 だから、1行目。 我々は整数、xは1に等しいがある。 それは起こっただけのことだ。 だから、行1で、私たちは私たちの中で参照してください。 テーブル、すなわちyは、a、bおよびtmpがすべてである ブラックアウト。 だから、xは何ですか？ まあ我々はちょうどそれは1に等しくなるように設定。 して、行2、よく、 我々は、yは2に設定されていることがわかる テーブルがすでにある 私たちのために記入。 そこで、xは1であり、yは2である。 さて、ライン3、我々は今だ スワップ関数内。 私たちは、スワップに合格しましたか？ 私達はのためにアンパサンドxを渡す bについて、およびアンパサンドyを。 どこに問題が早く のように述べているxのアドレス が0x10であり、yのアドレス0x14にある。 そこで、bは等しい それぞれの0x10と0x14に、。 今行3で、xとyは何ですか？ まあ、何も変わっていない この時点で、xおよびyは約。 彼らがしているにもかかわらず メインスタックフレームの内側、 彼らはまだ同じを持っている 彼らは前にやった値。 私たちは、任意のメモリを変更していない。 そこで、xは1であり、yは2である。 わかりました。 だから今、私たちは星に等しいint型のtmpが言った。 だから、ライン4、すべてのもので TMPを除いて同じである。 私たちはどんな値を変更していない tmpのため除いて何の。 私たちは星に等しいTMPを設定している。 スターaは何ですか？ さて、ポイントはxに、だからスター 1であるに等しいのx、しようとしている。 だから、すべてがコピーされます ダウン、そしてtmpには1に設定されます。 今すぐ次の行。 スターaはスターBに等しい。 だからラインによって、再びうまくすべてをfive-- スターaは何を除いて同じである。 スターaは何ですか？ さて、私たちは星のaはXであることを特徴とする。 だから我々は同じ星bにxと変更している。 スターbは何ですか？ Y。 yにBポイント。 だから、星bはyです。 だから我々はyに等しいxを設定している、 そして他のすべてが同じです。 だから我々は、xが今であることを次の行に表示 2、残りは単にダウンコピーされる。 今すぐ次の行に、スターbはTMPに等しい。 さて、私たちは星bはYであることを特徴とする、 私たちはtmpに等しいyと設定している。 他のすべてが同じであり、 そうすべてがダウンしてコピーされます。 私たちはあるtmpに、に等しいyと設定している 1、および他のすべてが同じです。 さて最後に、ライン7。 我々は戻っメイン関数にしている。 スワップが終了した後に私たちはいる。 私たちは、Bを失い、き TMPが、最終的に我々 どんな値を変更されていません この時点では何の、 私達はちょうどxとyを下にコピーします。 そして、我々は、xとyがあることがわかり 今2と1ではなく1と2。 スワップが正常に実行されました。 質問28。 あなたが遭遇すると仮定 エラーメッセージ 営業時間中に下記 CAまたはTFとして来年。 これらのエラーのそれぞれを修正する方法を助言する。 のGetStringにとても未定義参照。 なぜあなたはこれが表示されることがあります？ さて、学生が使用している場合 自分のコード内のgetString、 彼らは正しく含まCS50をハッシュしている ドットhはCS50ライブラリを含めます。 さて、彼らが何をすべきか このエラーを修正する必要がありますか？ 彼らは、ダッシュlcs50を行う必要があります 彼らはコンパイルしているコマンドライン。 だから、彼らが通過しない場合は、 打ち鳴らすダッシュlcs50、彼らがしている 実際に持っているつもりはない のGetStringを実装するコード。 質問29。 暗黙的に宣言 ライブラリ関数のstrlen。 さて、これは今、彼らはそうではありません 適切なハッシュを行っています。 この特定のケースでは、ヘッダファイル 彼らは、文字列のドットhでインクルードする必要があり、 そして今、文字列のドットhを含む 今student--コンパイラ へのアクセス権を持っている strlen関数の宣言、 そしてそれはあなたのコードを知っている strlenを正しく使用しています。 質問30。 もっとパーセントの変換 データ引数より。 だから、これは何ですか？ さて、これらのパーセントがあることを覚えている 彼らはprintfのに関連しているかをsigns--。 だからprintfの中で私たちはpercent--かもしれません 私たちは何かを印刷するかもしれない パーセントように私はnのスラッシュ。 または私達は、パーセント私のように印刷することがあります スペース、パーセントI、スペース、パーセントのi。 これらのそれぞれについて、そのように パーセント記号は、我々は必要とする のprintfの終わりに変数を渡すことができます。 だから、私たちが言う場合は、printfの括弧パーセント 私は、括弧閉じnのスラッシュ よく、私たちはしていると言う 整数を印刷しようとして、 しかし、その後、我々はprintfのを渡さない 実際に印刷する整数。 だからここにもっとパーセント データ引数よりもコンバージョン？ それは我々が持っていることを言っている パーセントの全体の束、 そして我々は十分な変数を持っていない 実際にそれらのパーセントで埋めるために。 その後、間違いなく、質問31のため、 間違いなく1ブロックに40バイトを失った。 だから、これはValgrindのエラーです。 これはと言っている あなたのコード内のどこかに、 あなたは40で割り当てを持っている あなたが40バイトをmallocさせ、大きなバイト、 そして、あなたはそれを解放したことはありません。 あなただけの必要性が最も高い いくつかのメモリリークを見つけるために、 そしてあなたがする必要がどこに見つける このメモリブロックを解放。 そして、32を疑問視 サイズ4の無効書き込み。 これもValgrindの誤差がある。 これは行う必要はありません 今メモリリークを持つ。 これは私が意味likely--ほとんどが、それはだ、である 無効なメモリの権利のいくつかの並べ替え。 そして最も可能性が高いこれはいくつかある バッファオーバーフローの一種。 あなたは多分、アレイを使用している 整数配列、およびレッツ それはサイズが5だと言う、そしてあなた アレイ·ブラケット5に触れてみてください。 だから、あなたがそれに書き込みをしようとした場合 値は、それはメモリの一部ではありません 実際にへのアクセスを持ち、こと だから、このエラーを取得するつもりだ、 サイズ4の無効な書き込みを言って。 Valgrindはあなたがしている認識しようとしている 不適切メモリに触れるしようとしています。 そして、それはquiz0のためにそれだ。 私はロブ·ボウデンだし、これはCS50です。