[CS 50]-アルゴリズム
入る前に。
私たちは今、コンピュータに情報を入力する方法を学びました.では、コンピュータはどのようにしてこれらの情報を加工して出力しますか?私たちが日常生活で様々な問題を処理する方法のように、コンピュータも必要な操作と問題の処理を順番に行います.これをアルゴリズムと呼び、アルゴリズムをどのように定義し、その正確性と効率はどうですか.
学習目標
私たちが日常生活でやっていることは、コンピュータが理解するアルゴリズムで表現することができます.
効率的なアルゴリズムを記述します.
キーワード
アルゴリズム#アルゴリズム#
私は授業中にコンピューターで理解できるバイナリで数字、文字、色などを表すことを学びました.
これは入力(input)に相当します.
出力について話しましょうか?
では、入力(input)から出力(output)を得るにはどうすればいいのでしょうか.
計算は、入力を受信し、入力を処理し、出力するプロセスです.
アルゴリズムは,入力(input)から受信したデータを出力(output)形式に変換する処理過程である.
すなわち、アルゴリズムは、入力値を出力値に変換するためにどのコマンドを実行するかを要求する一連のルールの順序である.(難しい用語が出てきましたが 無理に理解しないで、まずスキップして、次の例を通して ご理解ください.
アルゴリズムの種類は,これらの順序規則の配列方式に依存する.
同じ出力値でもアルゴリズムによって出力時間が異なる場合があります.
せいみつアルゴリズム
例えば、電話帳でMike Smithを探します.
電話帳を手に取り、最初のページを開き、Mike Smithがページにあるかどうかを見つけます.
ない場合は、次のページに移動してください.
Mike Smithが見つかったり、電話帳が完了したりするまで、この操作を繰り返します.
しかし、Mike Smithが電話帳にある場合、このアルゴリズムはMike Smithを見つける可能性があります.
アルゴリズムを評価する際には,正確性と効率が重要である.
効率とは、仕事を完成するのに要する時間と精力を指す.
1ページ1ページのアルゴリズムは正しいと思いますが、時間がかかり、効率が悪いアルゴリズムです.
一度に2ページめくることで、アルゴリズムを改善することができます.
ただし、このアルゴリズムを使用している場合は、Mike Smithのページがスキップされる可能性があることに注意してください.
この場合、前のページを表示できますが、アルゴリズムでもこの問題を解決する最も効果的な方法ではありません.
正確で効率的なアルゴリズム
今回は、より直感的で効率的なアルゴリズムを使用してMike Smithを検索してみましょう.
まず、電話帳の真ん中を開けます.Mike Smithがそのページにいたら、私たちのアルゴリズムは終わります.
もしなかったら、電話帳は名前順に並んでいるので、Mike Smithが今ページの前にあるか後ろにあるか知っています.
したがって、本の半分を捨てて、残りの半分に対して同じアルゴリズムを実行することができます.
残り1ページになるまで実行を続けます.
最後のページにはMike Smithの名前があるか、ないか、どちらかがあるかもしれません.
このアルゴリズムは、既存のアルゴリズムよりも効率的です.
既存の電話帳が100ページ、さらに100ページあれば200ページとしましょう.
1番目のアルゴリズムは1枚ずつページをめくるのに100回以上ページをめくるが、2番目のアルゴリズムは半減してもう1つのステップを実行するだけだ.
1回の操作で200ページ半の100ページが消えてしまうからです.
前述したアルゴリズムの定義を再確認します.入力値を出力値に変換するには、どのコマンドを実行する必要があるかのルールを順番にリストします.
電話帳でMike Smithを見つけるには、どのコマンドを実行すればよいかについて、2つのアルゴリズムを見つけました.
最初のアルゴリズムは,1章の後にもう1章を順番にリストするルールである.
2番目のアルゴリズムは、半分を減らし、次の半分を減らすルールを順番にリストします.
前のアルゴリズムの定義に気づいたか?
ぎじふごう
上記のアルゴリズムは次のとおりです. これはより明確な符号化方式である.
コードは、コンピュータが実行すべき操作をステップ的に決定するために、必要な動作または条件を設定するのに役立ちます.
(中間インデント部分は依存関係を表し、後で詳細を説明します.)
黄色で強調表示されている部分を関数(functions)と呼びます.
関数は動詞のようなもので、この場合、コンピュータに何をするかを教えます.
次に黄色を強調する部分を条件と呼びます.
複数のオプションから1つを選択します.
上記の決定を下すには問題が必要です.これを「ブール」(Boolean)と呼ぶ.
答えがYes(Yes)、No(No)、True(真)またはFalse(偽)でない場合は、バイナリの0または1です.
最後に黄色でハイライトされた部分を「ループ」(loop)と呼びます.
これは繰り返しのサイクルです.
考える
1)友達と二十歩ゲームをして、1から100までの数字をつづりたいです.使用するアルゴリズムを偽コードとして表すとどうなりますか?
1. 1~100사이의 숫자를 말 한다.
2. 정답이면 종료
3. 정답이 말한 숫자보다 작으면
처음 말한 숫자의 1/2 의 숫자를 말 한다.
2번째 라인으로 다시 간다.
4. 정답이 말한 숫자보다 크면
처음 말한 숫자의 1/2보다 큰 숫자를 말 한다.
2번째 라인으로 다시 간다.
Reference
この問題について([CS 50]-アルゴリズム), 我々は、より多くの情報をここで見つけました https://velog.io/@jin_jin/CS50-알고리즘-ttofrvldテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol