第５章計算とプログラム本章で説明すること・計算の概観と記述法・代表的な計算モデル・プログラムとプログラム言語計算の方法の図 • 取り出し型 • 分割型 • 変数(variable) – 値を覚えておく”もの”（変数には型がある） -代入(assignment) • 変数に値を設定する操作， ”変数名” ← ”式” で表す a:変数とする a a+b a:=a+b a=a+b など (a:=a+1 は等式ではなく、代入を表す。) 条件判断 (a) if (条件C) then (A) endif 条件Cが成立すればAを実行する。そうでなければ何もせず次に進む (b) if (条件C) then (A) else (B) endif 条件Cが成立すればAを実行する。そうでなければ、Bを実行し、次に進む (a) if-then 文 (b) if-then-else 文 if 条件が成立するか？ if 条件が成立するか？ＹＥＳ then 実行文を実行するＹＥＳＮＯＮＯ then else 実行文１を実行文２を実行する実行する x＝あなたの体重(kg)；ｙ＝あなたの身長(cm)； if ( x> ((y-100)×0.9) then print( 太りすぎです) endif if ( x> ((y-100)×0.9) then print( 太りすぎです) else print (正常です) endif While 文の例 2 のk 乗がはじめて 10000 以上になる k を求める ------------------------------------------------------------------i, k: integer; i=2; k=0; while(j<10000) do i:=2i; k=k+1; end (2) 繰り返し(while文) i=1,k=0 i < 10000 ? while(i<10000) No Yes i = 2i, k=k+1 k を出力する (2k  10000 となる最初の k ) 手続き型の例 • 例：正の整数a, b，a/b の商q，余りr を求める – 計算の手順 • 被除数(a)から除数(b)を引けるだけ引く • 引いた回数を商，残りを余りとする – 計算の記述 r←a q←0 while r ≧ b do r←r-b q←q+1 done 添え字付き変数（配列) A[8] : 文字と定義すると 1 A 2 P x 3 4 5 6 7 8 1 % r H A L A[3] の値は 1 A[8] の値は L 例与えられた列を小さい順に並べかえる問題（ソーティング）での逐次的アルゴリズム ---バブルソート例与えられた列を小さい順に並べかえる問題（ソーティング）での再帰的アルゴリズム --- Quick Sort プログラム QuickSort(w); (ｗは数の配列) 1. wの要素の数が１以下の時はそのまま返す。 2. wの列中から任意にひとつ要素aを選ぶ; 3. 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 2341 678 7 3 21 2 1 4 6 8 プログラム • プログラム(program) – 計算を記述したもの – コンピュータを使った問題解決における活動単位 – 一般に，人間には読み書き不可能 • プログラム言語(programming language) – プログラムを記述するための約束事をまとめたもの – 人工的に作られた言語(人工言語) – 人間にも読み書き可能プログラム言語 • プログラムを記述するための種々の約束事 – ある内容のことがらを表すための表記法の集まり • 変数への代入(←) • 条件付き処理(if ... then ... else ... endif) • 反復処理(while ... do ... done) • "内容"の集まり – 意味(semantics) • "表記法"の集まり – 構文(syntax) 機械語とプログラム言語処理系 • 機械語(machine language) – すべて2進数か，決まった長さのビットパターン • バイナリ(binary)プログラム – 機械語で書かれたプログラム – コンピュータ(ハードウェア)が理解，実行できる • 言語処理系 – "プログラム言語で書かれたプログラム" を "バイナリプログラム"に変換(翻訳)するシステムアセンブリ言語とアセンブラ • アセンブリ言語 – 機械語の機能部分や，データの場所に人間が読めるような名前(ニーモニック)をつけた言語 • アセンブラ(assembler) – "アセンブリ言語で書かれたプログラム" を "バイナリプログラム"に変換(翻訳)するシステム – 最も初期から使われてきた言語処理系高水準言語 • 高水準言語 – 人間が理解しやすい形でプログラムを読み書きできる言語 – コンパイラを使ってバイナリプログラムに変換する – 高水準言語の例： C言語，C++言語, LISP, COBOL, Prolog, Java, Pascal コンパイラとインタプリタ • コンパイラ(compiler) – プログラム言語で書かれたプログラム(ソース)を機械語(オブジェクト)に変換（翻訳）するソフトウェア • インタプリタ – プログラム言語で書かれたプログラム（ソース）を解釈（interpret）してその意味通りの実行を行うソフトウェア 2. インタープリター方式高級言語で書かれたプログラムを１行ずつ解釈しながら実行する３．中間言語方式 JAVA (c)高級言語（ふつうのプログラミング言語のこと） 1.高水準言語（コンパイラ方式）ソースプログラムコンパイラ (文法上の誤りをチェック) オブジェクトプログラム I/Oなどのライブラリバイナリプログラム Javaの実行過程 Java のソースプログラムクラスファイル(中間言語) インタプリタA 機械 A インタプリタB インタプリタC 機械B 機械C 高水準言語の実行のされ方高水準言語プログラムコンパイラ中間言語プログラムコンパイラバイナリプログラム仮想機械プログラムコンピュータハードウェアインタプリタプログラム