計算の方法の図•

(1)

1

第５章計算とプログラム本章で説明すること

・計算の概観と記述法

・代表的な計算モデル

・プログラムとプログラム言語

22

5.1.1 計算の方法

1. 取り出し型(逐次処理 Sequential) 2. 分割型 (Branch & Bound) or

（再帰的方法, recursive）

再帰的アルゴリズム A

アルゴリズムの手続きの中で、サブルーチン(部分アルゴリズム)としてA自身を使う

33

例与えられた列を小さい順に並べかえる問題

（ソーティング）での逐次的アルゴリズムーバブル法など

例与えられた列を小さい順に並べかえる問題

（ソーティング）での再帰的アルゴリズムークイックソートなど

計算の方法の図

• 取り出し型

• 分割型

55

Quick Sort の説明

procedure Sort(数の列 wを入力とする);

w の要素の数が１以下の時はそのまま返す。

1. wの列中から任意にひとつ要素aを選ぶ;

2. wを順に見ていって、a以外の要素について、

a より以下のものは w1 の列に、 a より大きいものは w2 の列に付け加えていって列 w1, w2 を作る。

4. Sort を再帰的に (recursive

に

) 使って、

Sort(w)=Sort(w1)+a+Sort(w2) を答えとして出力する。

66

2 6 3 7 5 4 1 8 5

2 3 4 1 6 7 8

3 21 4

2 1

7 8 6 Quick

Ｓｏｒｔの

実行例

(2)

7

5.1.2 計算の記述 (1)変数と条件判断

a:変数(型が決まっている）

代入

a=a+1 は等式ではなく、代入を表す。

特に a:=a+1 と書くこともある。

a

8

• 変数(variable)

– 値を覚えておく”もの（変数には型がある：

整数型、実数型、文字型など）

-代入(assignment)

変数に値を設定する操作，表記は変数名 := 式、変数名←式など a: 変数としてそこに a+b を代入する a ← a+b a:=a+b a=a+b など

(a:=a+1 は等式ではなく、代入を表す。 )

9

添え字付き変数（配列)

A[8] : 文字と定義すると

P x 1 % r H A L 1 2 3 4 5 6 7 8

A

A[3] の値は 1 A[8] の値は L

10

条件判断

(a) if (条件C) then (A) endif

条件 C が成立すれば A を実行する。そうでなければ何もせず次に進む

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

11

x ＝あなたの体重 (kg) ；ｙ＝あなたの身長(cm)；

if ( x> ((y-100) × 0.9) then print 太りすぎです endif

if ( x> ((y-100) × 0.9) then print 太りすぎです else print 正常です endif

12

if 条件が成立するか？

then 実行文１を実行する

ＹＥＳＮＯ

if 条件が成立するか？

then

実行文を実行する

ＹＥＳ

ＮＯ else

実行文２を実行する

(a) if-then 文 (b) if-then-else

文

(3)

13

(2) 繰り返し (while 文 )

i=1,k=0 i < 10000 ?

i = 2i, k=k+1

Yes No

while(i<10000)

k を出力する

( 2

^k

≥ 10000 となる最初の k )

¹⁴

While 文の例 (反復処理の例)

2

の

k

乗がはじめて

10000

以上になる

k

を求める

--- i, k: integer;

i=2;

k=0;

while (j<10000) do begin i:=2＊i;

k=k+1;

end write(k)

15

手続き型の例

• 例：正の整数a, b，a/b の商q，余りr を求める – 計算の手順

•

被除数(a)から除数(b)を引けるだけ引く

•

引いた回数を商，残りを余りとする

– 計算の記述

r ← a q ← 0

while r ≧ b do r ← r - b q ← q + 1 done

1616

手続き型の例

• 手続き型の計算の進行

• 変数値の変化を示すことをトレース (trace) と呼ぶ

計算の記述

• 問題

– 今年の八十八夜 ( 立春から数えて 88 日目 ) は何月何日か．ただし今年の立春は 2 月 4 日であり，今年は平年である．

• 考え方

– 2月4日の87日後は"2月をはみ出す" → 2月の残り日数(28 - 4 = 24日)を引く(87 - 24 = 63日) – 3月63日は3月を越す → 31日を引く(63 - 31 =

32日)

– 4 月 32 日は 4 月を越す → 30 日を引く (32 - 30 = 2

18

八十八夜問題

（今年の立春を２月４日とする）

• 2月4日の88日後

– <

残り日数

> = 4 + 88 → 2

月

92

日

• 92 > 28(2月の日数)

– <

残り日数

> = 92 - 2

月の日数

→ 3

月

64

日

• 64 > 31(3月の日数)

– <

残り日数

> = 64 - 3

月の日数

→ 4

月

33

日

• 33 > 30(4月の日数)

– <

残り日数

> = 33 - 4

月の日数

→ 5

月

3

日

• 3 < 31(5月の日数)なので計算終了

(4)

計算の記述 - より明確に

• 2月4日の87日後

– <

残り日数

> = 4 + 87 → 2 月 91 日

• 91 > 28(2月の日数)

– <残り日数> = 91 - 2月の日数 → 3月63日

• 63 > 31(3 月の日数 )

– <残り日数> = 63 - 3月の日数 → 4月32日

• 32 > 30(4月の日数)

– <残り日数> = 32 - 4月の日数 → 5月2日

• 2 < 31(5月の日数)なので計算終了

八十八夜問題の解法手順

<残り日数> ← 4+87

if <残り日数> ＞28（2月の日数）

then <残り日数> ← <残り日数> - 28

then （6月以降の処理）

else "5月"<残り日数>"日"と表示 endif

配列の例

例： daymonth [2] = 28

配列名 = daymonth 添え字 = 2

値 = 28

解法手順の改良

• 6 月以降については " （ 6 月以降の処理） " としか書いていない

– 実際に6月以降の処理が必要になったときに正しい答えが求まる保証がない

– もっとすっきりと， 12 月まで対処できる方法は？

• ”m（n月の日数）”という表現が何度も現れている

– 例： 28(2月の日数)

– もっとすっきりと記述する方法は？

23

八十八夜問題の解法手順 - 改良版

<残り日数> ← 4+88 m ← 2

while <残り日数> ＞ daymonth[m] do

<残り日数> ← <残り日数> - daymonth[m]

m ← m + 1 done

– ”< 残り日数 > と月の日数の比較を繰り返し行う”

手順を，”反復処理”と”配列”を使うことですっきりと記述することができた

2424

関数型の例

• 例：正の整数a, b，a/b の商q，余りr を求める

• 計算の記述

q(a, b) = a ＜ b なら 0,

a ≧ b なら q(a - b, b) + 1 r(a, b) = a ＜ b なら a,

a ≧ b ならr(a - b, b)

– 関数として”自分自身を呼び出す”ことも許される

•

これを”再帰”と呼ぶ

(5)

2525

関数型の例

• 商 q(44,13) の計算の進行

44割る13の商を求める

そのために…

31割る13の商を求める

そのために…

18

割る

13

の商を求める

26

5.3.2 プログラム言語処理系

1. 機械語のプログラム（バイナリプログラムとも言う） Æ 機械が直接実行できる

2. アセンブリ言語は、機械語に１対１に対応している。人間にとって意味の分かりやすい表現にしてある。（最も原始的だが、処理速度が抜群に速い） Æ7.1.2 機械語レベルのプログラム例 p.156 図 7.2 に、詳しい記述がある

3. アセンブラは、アセンブリ言語のプログラムを機械語に翻訳するソフト。

27

機械語とバイナリプログラム

• 機械語 (machine language)

1)

^機械

(CPU)

が直接実行する命令。

2)

すべて

2

進数で決まったビット長をもつ。

3) 32ビットの計算機というときは、その機械語の

ビット

長が

32

であることを意味する。

機械語はそのままでは人間には読み書きできないので、プログラミング言語を用いる

• バイナリ(binary)プログラム

–

コンピュータ(ハードウェア)がそのまま実行できる機械語で書かれたプログラム

–

通常

.exe という拡張子をつけてある。

28

プログラム言語

• アセンブリ言語 --- 機械語に同等

• 高級言語

–

人間が理解しやすい形でプログラムを読み書きできる言語

– コンパイラ、インタープリターを使ってバイナリプ

ログラムに変換する

– 高級言語の例： C 言語， C++ 言語 , LISP, COBOL, Prolog, Java, Pascal, BASIC

29

（ｂ）アセンブリ言語（低級言語とは言わないが）

• 個々の機械語に英語のニックネームをつけて人間が使いやすくしたもので、ニーモニックとも呼ばれる。機械語に１対１に対応している。

• アセンブリ言語のプログラムを機械語に翻訳するソフトをアセンブラという。

30

アセンブリ言語 --- 命令の例 (テキスト p.155)

種類内容意味

データ転送命令 load A store A

アドレスAのデータを演算レジスタ(AC) に読み込む

ACのデータをアドレスAに書き込む 計算命令 add A

subtract A

アドレスAのデータをACの値に加えるアドレスAのデータをACの値から引く

分岐命令 jump A

jumpzero A アドレスAにプログラムの実行を移す ACのデータが0の場合，アドレスAにプ ログラムの実行を移す

その他 write

halt ACのデータを出力する

プログラムの実行を停止する

(6)

31

1から10までの和のアセンブリプログラム

アドレ

ス命令意味高水準言語

1001 load 2001 AC ← 2001

sum ← sum+1 1002 add 2002 AC ← AC + 2002

1003 store 2001 2001 ← AC 1004 load 2002 AC ← 2002

i ← i - 1 1005 subtract 2003 AC ← AC - 2003 1006 store 2002 2002 ← AC 1007 jumpzero 1009 条件分岐（ジャンプ）

while i ≠ 0

1008 jump 1001 無条件ジャンプ

1009 load 2001 AC ← 2001

1010 write 結果の出力 write(sum)

1011 halt プログラム停止

2001 0 変数（結果） sum ← 0

2002 10 変数（i の初期値） i ← 10

2003 1 定数 1

32

(c)高級言語（ふつうのプログラミング言語のこと）

1.高水準言語（コンパイラ方式）

ソースプログラム

(文法上の誤りをチェック)

バイナリプログラムコンパイラ

I/Oなどのライブラリオブジェクトプログラム

33

2. インタープリター方式

高級言語で書かれたプログラムを１行ずつ解釈しながら実行する

３．中間言語方式 JAVA

34

Javaの実行過程

Java のソースプログラム

クラスファイル(中間言語)

インタプリタA インタプリタB インタプリタC 機械 A 機械B 機械C

35

高水準言語の実行のされ方

コンピュータハードウェアバイナリプログラム

コンパイラ

高水準言語プログラム

中間言語プログラム

仮想機械プログラム

インタプリタプログラムコンパイラ

計算の方法の図•

第５章 計算とプログラム 本章で説明すること

・計算の概観と記述法

・代表的な計算モデル

・プログラムとプログラム言語

5.1.1 計算の方法

1. 取り出し型(逐次処理 Sequential) 2. 分割型 (Branch & Bound) or

（再帰的方法, recursive）

再帰的アルゴリズム A

アルゴリズムの手続きの中で、サブ ルーチン(部分アルゴリズム)としてA自 身を使う

例 与えられた列を小さい順に並べかえる問題

（ソーティング）での逐次的アルゴリズム ーバブル法など

例 与えられた列を小さい順に並べかえる問題

（ソーティング）での再帰的アルゴリズム ークイックソートなど

計算の方法の図

• 取り出し型

• 分割型

Quick Sort の説明

procedure Sort(数の列 wを入力とする);

w の要素の数が１以下の時はそのまま返す。

1. wの列中から任意にひとつ要素aを選ぶ;

2. wを順に見ていって、a以外の要素について、

a より以下のものは w1 の列に、 a より大きいものは w2 の列に付け加えていって列 w1, w2 を作る。

4. Sort を再帰的に (recursive

) 使って、

Sort(w)=Sort(w1)+a+Sort(w2) を答えとして出力する。

2 6 3 7 5 4 1 8 5

2 3 4 1 6 7 8

3

21 4

2 1

7 8 6 Quick

Ｓｏｒｔの

実行例

5.1.2 計算の記述 (1)変数と条件判断

a:変数(型が決まっている）

代入

a=a+1 は等式ではなく、代入を表す。

特に a:=a+1 と書くこともある。

a

• 変数(variable)

– 値を覚えておく”もの（変数には型がある：

整数型、実数型、文字型など）

-代入(assignment)

変数に値を設定する操作，表記は 変数名 := 式、変数名←式 など a: 変数としてそこに a+b を代入する a ← a+b a:=a+b a=a+b など

(a:=a+1 は等式ではなく、代入を表す。 )

添え字付き変数（配列)

A[8] : 文字 と定義すると

A

A[3] の値は 1 A[8] の値は L

条件判断

(a) if (条件C) then (A) endif

条件 C が成立すれば A を実行する。そう でなければ何もせず次に進む

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

x ＝あなたの体重 (kg) ； ｙ＝あなたの身長(cm)；

if ( x> ((y-100) × 0.9) then print 太りすぎです endif

if ( x> ((y-100) × 0.9) then print 太りすぎです else print 正常です endif

(a) if-then 文 (b) if-then-else

(2) 繰り返し (while 文 )

i=1,k=0 i < 10000 ?

i = 2i, k=k+1

while(i<10000)

( 2

≥ 10000 となる最初の k )

While 文の例 (反復処理の例)

2

k

10000

k

--- i, k: integer;

i=2;

k=0;

while (j<10000) do begin i:=2＊i;

k=k+1;

end write(k)

手続き型の例

• 例： 正の整数a, b，a/b の商q，余りr を求める – 計算の手順

•

•

– 計算の記述

第５章計算とプログラム本章で説明すること

アルゴリズムの手続きの中で、サブルーチン(部分アルゴリズム)としてA自身を使う

例与えられた列を小さい順に並べかえる問題

（ソーティング）での逐次的アルゴリズムーバブル法など

例与えられた列を小さい順に並べかえる問題

（ソーティング）での再帰的アルゴリズムークイックソートなど

変数に値を設定する操作，表記は変数名 := 式、変数名←式など a: 変数としてそこに a+b を代入する a ← a+b a:=a+b a=a+b など

A[8] : 文字と定義すると

条件 C が成立すれば A を実行する。そうでなければ何もせず次に進む

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

x ＝あなたの体重 (kg) ；ｙ＝あなたの身長(cm)；

• 例：正の整数a, b，a/b の商q，余りr を求める – 計算の手順

• 変数値の変化を示すことをトレース (trace) と呼ぶ

– 今年の八十八夜 ( 立春から数えて 88 日目 ) は何月何日か．ただし今年の立春は 2 月 4 日であり，今年は平年である．

– 2月4日の87日後は"2月をはみ出す" → 2月の残り日数(28 - 4 = 24日)を引く(87 - 24 = 63日) – 3月63日は3月を越す → 31日を引く(63 - 31 =

• 6 月以降については " （ 6 月以降の処理） " としか書いていない

– 実際に6月以降の処理が必要になったときに正しい答えが求まる保証がない

• ”m（n月の日数）”という表現が何度も現れている

手順を，”反復処理”と”配列”を使うことですっきりと記述することができた

• 例：正の整数a, b，a/b の商q，余りr を求める