3.Algorithms

アルゴリズムとは

アルゴリズム(英: algorithm)とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。「算法(さんぽう)」と訳されることもある。

基本的なアルゴリズム

  • 順次
  • 条件判定と分岐 (if, switch)
  • 繰り返し (while, for)

 

順次

順次実行構造は,上に書かれた命令が先に実行され,下に書かれた命令が後に実行される構造のことです。なるべくこのようなシンプルで自然な構造になるようコードを書くべきです。

典型的な順次実行の例として,GSWPよりサンプルコードを引用します。

// Example 03-13 from "Getting Started with Processing" 
// by Reas & Fry. O'Reilly / Make 2010

size(480, 120);
smooth();
strokeWeight(12);
strokeJoin(ROUND);      // Round the stroke corners
rect(40, 25, 70, 70);
strokeJoin(BEVEL);      // Bevel the stroke corners
rect(140, 25, 70, 70);
strokeCap(SQUARE);      // Square the line endings
line(270, 25, 340, 95);
strokeCap(ROUND);       // Round the line endings
line(350, 25, 420, 95);

図5.2 Ex_03_13.pdeの実行結果

画像

画面の設定から描画まで,上から下へ順に実行されます。

条件判定と分岐 (if, switch)

 

条件に従って実行するコードブロックを切り替える仕組みは大変便利です。図5.3はif文の流れ図です。論理式が成り立つ場合,つまり「真」ならば直下のコードブロックを実行し,論理式が成り立たなければ,つまり「偽」ならば流れは右へ分岐し,右側のコードブロックが実行されます。

図5.3 if文の流れ図

画像

基本的に,条件分岐の流れ図では,論理式が成り立つ(すなわち真の)とき真下へ向かう流れ線をたどり,論理式が成り立たない(すなわち偽の)とき横へ向かう流れ線をたどります。流れ線に真や偽,TやFといった値が記されていない場合はそのように理解してください。

昼には太陽、夜には月が動くようなアニメーション

これを実現するためは、たとえば以下のようなプログラムを書く

 int scene;
 int x;
 float theta;
 void setup(){
  scene = 0;
  theta = 3.1;
  size(600,300);
 }
 void draw(){
  theta += 0.01;
  if(scene==0){
    background(100,100,200);
    noStroke();
    fill(250,250,250);
    ellipse(300*cos(theta)+300,300*sin(theta)+400,100,100);
    if(theta > 6.3){scene=1; theta=3.1;}
  }
  else {
    background(0);
    noStroke();
   fill(250,250,50);
   ellipse(300*cos(theta)+300,300*sin(theta)+400,100,100);
   if(theta > 6.3){scene=0; theta=3.1;}
 }
 }

ここでは、ふたつの場面のどちらであるかを表すために scene という変数を用意して、scene が0なら昼の場面、それ以外なら夜の場面を描くようにしている。実際にはscene は0か1である。

繰り返し (while, for)

 

同じような仕事を繰り返すことがあります。コンピュータは,繰り返しの仕事が得意です。人間なら早晩飽きて放り出してしまうことも,コンピュータは決して飽きません。

図5.4は繰り返しの基本形,while文の流れ図です。

図5.4 繰り返しの基本形,while文の流れ図

画像

while文による繰り返し構造の流れ図は次のように読みます。

  1. 論理式(条件式とも呼びます)が成り立てば,すぐ下のコードブロックへ実行が移ります。
  2. コードブロックの実行が終わると,論理式の直前に実行が戻ります。
  3. 論理式が成り立つ限り,コードブロックを繰り返し実行します。
  4. 論理式が成り立たない場合,実行は右側へ移り,コードブロックを実行せずwhile文の構造を終了します。

命令 for を使うと、同じ内容は以下のように書ける。

 int i;
 for(i=0; i<=90; i += 10){
  line(0,i,99,i);
 }

 

2016-09-02

 

参考:

  • いろいろなソートアルゴリズム http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/
  • Interactive Data Structure Visualizations http://student.seas.gwu.edu/~idsv/idsv.html

Leave a Reply

Your email address will not be published. Required fields are marked *

CAPTCHA


Related Post

12.Map12.Map

Map構造 コレクションクラス Map構造は、キーと値をセットにしたものを1つの要素として管理するデータ構造です。 「HashMap」「TreeMap」の2種類があります。 要素がキーと値で管理されているので、キーを指定して値の取得や更新、削除を行います。 Map構造は、キーによって値を管理するためキーの重複は不可です。 (同じキーがセット(put)された場合は上書きされます。) マップ(HashMap) HashMap は、名前(キー)と値の組み合わせを要素として持つ配列です。 HashMapは格納順は管理されません。キーと値にnullを使用することが可能です。 HashMap hm = new HashMap(); hm.put("Brian Kernighan","A REGULAR EXPRESSION […]

13.Web Application13.Web Application

Webアプリケーション作成に必要な概念を理解する Web Service Webサービスとは、大まかにいえば、Webの通信の仕組みを利用して、コンピュータ同士でさまざまなデータをやり取りし、分散処理を行うシステムです。 通信手順の取り決めのことを、「プロトコル」(Protocol)と呼びます。Webの世界では、「HTTP」(HyperText Transfer Protocol)というプロトコルで、通信が行われています。 HTTPは、WebブラウザなどのクライアントがWebサーバーにデータを要求し、それにWebサーバーが答える、という形のプロトコルです。 API アプリケーションプログラミングインタフェース (API、英: Application Programming Interface) とは、ソフトウェアコンポーネントが互いにやりとりするのに使用するインタフェースの仕様である。APIには、サブルーチン、データ構造、オブジェクトクラス、変数などの仕様が含まれる。 Webサービス大まかに言えば、以下のような流れで処理を進めます。 (1)クライアントからサーバーに対して、HTTPで接続して処理を要求します。 (2)サーバーは処理結果をクライアントに送信します。 (3)クライアントは(2)の結果を受信し、必要に応じて各種の処理を行います。 「HTTPで通信する」上位層に位置するプロトコル […]

Algorithms and Data StructuresAlgorithms and Data Structures

授業概要  ソートとコレクションを中心にアルゴリズムとデータ構造に関する基本を学習する。 Java言語によるプログラミング技術の基本事項を習得する。 特にアルゴリズムとデータ構造の理解を中心に、講義および演習を行う。 授業の到達目標 ・オブジェクト指向言語の概念を理解するとともに、Javaを用いて課題を解決するスキルを身につける。 ・アプリケーションの開発に必要な概念を理解するとともに、Java言語を用いて実用的なWebアプリケーションの開発が行えるようになる。 事前・事後学習の内容 予習としてMyWasedaに掲載するレジュメの事前読了を求めることがあります。各回の予習には90分~120分かかると想定されます。 授業計画 1: 本講義の目的と進め方について説明する。最終的に作成するアプリケーションの実例を説明する。 2: 基本概念を理解する。Javaのインストールからコマンドライン実行の方法を学ぶ。 3: 基本的なアルゴリズムを学ぶ。 4: 基本的なデータ構造を学ぶ。 5: 探索アルゴリズムを学ぶ。 […]