第５章　計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語

計算の方法の図 取り出し型 分割型

変数(variable) 値を覚えておく”もの”（変数には型がある） -代入(assignment) 変数に値を設定する操作， ”変数名” ← ”式” で表す 　　a:変数とする 　　a a+b a:=a+b a=a+b など (a:=a+1 は等式ではなく、代入を表す。)

条件判断 if (条件C) then (A) endif 条件Cが成立すればAを実行する。そうでなければ何もせず次に進む (b) if (条件C) then (A) else (B) endif 条件Cが成立すればAを実行する。そうでなければ、Bを実行し、次に進む

(b) if-then-else 文 (a) if-then 文 if 条件が成立するか？ then 実行文を実行する ＹＥＳ ＮＯ if　条件が成立するか？ ＹＥＳ ＮＯ then 実行文１を 実行する else 実行文２を 実行する

x＝あなたの体重(kg)； ｙ＝あなたの身長(cm)； if ( x> ((y-100)×0.9) then print( 太りすぎです) endif then print( 太りすぎです) else print (正常です)

While 文の例 　2 のk 乗がはじめて 10000 以上になる k を求める ------------------------------------------------------------------- i, k: integer; i=2; k=0; while(j<10000) do i:=2i; k=k+1; end

i < 10000 ? while(i<10000) i = 2i, k=k+1 (2) 繰り返し(while文) No Yes i = 2i, k=k+1 k を出力する

手続き型の例 例： 正の整数a, b，a/b の商q，余りr を求める 計算の手順 計算の記述 r ← a q ← 0 引いた回数を商，残りを余りとする 計算の記述 　　　r ← a 　　　q ← 0 　　　while r ≧ b do 　　 r ← r - b 　　 q ← q + 1 　　　done

A 添え字付き変数（配列) A[8] : 文字 と定義すると A[3] の値は 1 A[8] の値は L 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 A P x 1 % r H A L A[3] の値は 1 A[8] の値は L

例 与えられた列を小さい順に並べかえる問題 （ソーティング）での逐次的アルゴリズム ---バブルソート （ソーティング）での再帰的アルゴリズム --- Quick Sort

プログラム QuickSort(w);　(ｗは数の配列) wの列中から任意にひとつ要素aを選ぶ; wを順に見ていって、a以外の要素について、 a より小さいものはw1 の列に、 a より大きいものは w2 の列に付け加えていって列 w1, w2 を作る。 4. Sort を使って、 w1’=Sort(w1), w2’=Sort(w2) としてw1, ｗ２ の並べ替えを行う 5. w=w1+a+w2 を答えとして出力する。

2 6 3 7 5 4 1 8 Ｓｏｒｔの実行例 5 2 3 4 1 6 7 8 7 3 6 8 2 1 4 2 1

プログラム プログラム(program) プログラム言語(programming language) 計算を記述したもの コンピュータを使った問題解決における活動単位 一般に，人間には読み書き不可能 プログラム言語(programming language) プログラムを記述するための約束事をまとめたもの 人工的に作られた言語(人工言語) 人間にも読み書き可能

プログラム言語 プログラムを記述するための種々の約束事 "内容"の集まり "表記法"の集まり ある内容のことがらを表すための表記法の集まり 変数への代入(←) 条件付き処理(if ... then ... else ... endif) 反復処理(while ... do ... done) "内容"の集まり 意味(semantics) "表記法"の集まり 構文(syntax)

機械語とプログラム言語処理系 機械語(machine language) バイナリ(binary)プログラム 言語処理系 すべて2進数か，決まった長さのビットパターン バイナリ(binary)プログラム 機械語で書かれたプログラム コンピュータ(ハードウェア)が理解，実行できる 言語処理系 "プログラム言語で書かれたプログラム" を "バイナリプログラム"に変換(翻訳)するシステム

アセンブリ言語とアセンブラ アセンブリ言語 アセンブラ(assembler) 機械語の機能部分や，データの場所に人間が読めるような名前(ニーモニック)をつけた言語 アセンブラ(assembler) "アセンブリ言語で書かれたプログラム" を "バイナリプログラム"に変換(翻訳)するシステム 最も初期から使われてきた言語処理系

高水準言語 高水準言語 人間が理解しやすい形でプログラムを読み書きできる言語 コンパイラを使ってバイナリプログラムに変換する 高水準言語の例： C言語，C++言語, LISP, COBOL, Prolog, Java, Pascal

コンパイラとインタプリタ コンパイラ(compiler) インタプリタ プログラム言語で書かれたプログラム(ソース)を機械語(オブジェクト)に変換（翻訳）するソフトウェア インタプリタ プログラム言語で書かれたプログラム（ソース）を解釈（interpret）してその意味通りの実行を行うソフトウェア

2. インタープリター方式 高級言語で書かれたプログラムを１行ずつ解釈しながら実行する ３．中間言語方式 JAVA

(c)高級言語（ふつうのプログラミング言語のこと） 1.高水準言語（コンパイラ方式） ソースプログラム　　 (文法上の誤りをチェック) バイナリプログラム コンパイラ オブジェクトプログラム I/Oなどのライブラリ

Javaの実行過程 Java のソースプログラム クラスファイル(中間言語) インタプリタA インタプリタB インタプリタC 　　　　　　　 　クラスファイル(中間言語) インタプリタA インタプリタB インタプリタC 機械 A 機械B 機械C

高水準言語の実行のされ方 高水準言語プログラム コンパイラ 中間言語 プログラム インタプリタ プログラム コンパイラ 仮想機械 プログラム バイナリプログラム コンピュータハードウェア