Microsoft PowerPoint - prog13.ppt

(1)

1

プログラミング言語

2

第

12 回（

2007

年

07 月

23 日）

2/36

今日の配布物

片面の用紙

1 枚

今日の課題が書かれています。

本日の出欠を兼ねています

(2)

3/36

今日やること

http://www.tnlab.ice.uec.ac.jp/~s-okubo/class/language/ にアクセスすると、教材があります。 2007年07月30日分と書いてある部分が、本日の教材です。本日の内容前回の課題の解答授業でやってきたことの補足アルゴリズムとデータ構造 4/36

学期末の課題について

その

1

課題内容は、webを参照すること。〆〆〆切〆切切切はははは、、、、8月月2日月月日日日ののの12:00ですのですです。です。。。レポートボックスが出ますそので、そこに投函してください。 A4の紙で提出すること。別途、プログラムを、[email protected] まで送ること。

(3)

5/36

学期末の課題について

その

2

『Euler法, 改良Euler法, Runge-Kutta法に関する問題』

についてあまり面白いグラフは書けません。初期値問題の候補を追加しました。どちらかのグラフを書いて出して下さい。 6/36

前回の課題の解答

(4)

7/36

前回の課題

vi.キューとスタックにあるキューのサンプルプログラムについて、各行が何をやっているか、どのようにしてキューを実現しているかを、解説しなさい。 8/36

キュー（復習）

1 10 5 1 10 5 6 1 10 5 6 1 10 5 6 1 10 6 1 10 6 最後尾にデータを追加することができる。先頭のデータを取り出すことができる。取り出したデータを参照する。最初に入れたものが最初に出てくる

(5)

9/36

解説

その

1

#include<stdio.h> #define N 1000 キューを保存する構造体の定義キューを初期化する関数 initialize キューにデータを追加する関数 enqueue キューからデータを取り出す関数 dequeue main関数 #include<stdio.h> #define N 1000 キューを保存する構造体の定義キューを初期化する関数 initialize キューにデータを追加する関数 enqueue キューからデータを取り出す関数 dequeue main関数プログラム全体の構成について 10/36

解説

その

2

#include<stdio.h> // 入出力を伴うので、stdio.h をinclude する。

#define N 1000 // N を1000にdefineする。

#include<stdio.h> // 入出力を伴うので、stdio.h を include する。

#define N 1000 // N を1000にdefineする。

[1/9]

#define N 1000 については、

(6)

11/36

解説

その

3

structqueue{ char data[N]; inthead; inttail; }; struct queue{ char data[N]; int head; int tail; }; [2/9]キューを保存する構造体の定義キューの内容 data 10 0 1 5 0 1 2 3 4 5 0 0 4 tail 1 head queue キューに蓄えられたデータを保存する配列配列dataのどこが、キューの最後尾に相当するか配列dataのどこが、キューの先頭に相当するか 12/36

void initialize(struct queue *q){

int i; q->head=0; q->tail=0; for(i=0; i < N; ++i){ q->data[i]=' '; } }

void initialize(struct queue *q){

int i; q->head=0; q->tail=0; for(i=0; i < N; ++i){ q->data[i]=' '; } }

解説

その

3

[3/9]キューを初期化する関数この3行は、実は、あまり意味はありません。キューの中身が空であるときは、 headとtailの値が同じ時 headとtailに0を代入することが、キューを初期化することに data 0 0 0 0 0 1 2 3 4 5 0 0 0 tail 0 head queue

(7)

13/36

void enqueue(struct queue *q, int item){

if (q->tail >= N) {

printf("This queue is full! ¥n");

}else{

q->data[q->tail]=item;

q->tail++;

}

void enqueue(struct queue *q, int item){

if (q->tail >= N) {

printf("This queue is full! ¥n");

}else{ q->data[q->tail]=item; q->tail++; } }

解説

その

4

[4/9]キューにデータを追加する関数キューに蓄えられるデータが限界に達していたら、メッセージを表示 data 0 0 0 0 0 1 2 3 4 5 0 0 0 tail 0 head キューの末尾に相当する部分に、追加したいデータを書き込む data 0 6 0 0 0 1 2 3 4 5 0 0 0 tail 0 head キューの末尾を指す変数tail の値を更新 data 0 6 0 0 0 1 2 3 4 5 0 0 1 tail 0 head 14/36

int dequeue(struct queue *q){

int tmp; if(q->head == q->tail){ return -1; }else{ tmp=q->data[q->head]; q->head++; return tmp; } }

int dequeue(struct queue *q){

int tmp; if(q->head == q->tail){ return -1; }else{ tmp=q->data[q->head]; q->head++; return tmp; } }

解説

その

5

[5/9]キューからデータをとりだす関数キューが空なら-1を返すキューの先頭のデータをtmpに保存キューの先頭を指す変数headの値を更新 data 0 6 0 0 0 1 2 3 4 5 0 0 1 tail 0 head data 0 6 0 0 0 1 2 3 4 5 0 0 1 tail 0 head data 0 6 0 0 0 1 2 3 4 5 0 0 1 tail 1 head tmpを戻り値として返す 6 tmp 0 tmp 6 tmp

(8)

15/36 int main() { 変数の宣言キューの初期化条件を満たすまで繰り返しここから 1文字読み込みもし!なら、dequeueを実行もし@なら、1文字読み込み enqueueを実行キューの内容を全部表示繰り返しここまで } int main() { 変数の宣言キューの初期化条件を満たすまで繰り返しここから 1文字読み込みもし!なら、dequeueを実行もし@なら、1文字読み込み enqueueを実行キューの内容を全部表示繰り返しここまで }

解説

その

6

main関数の中身やりたいこと 1. 以下を繰り返す i. 1文字入力を貰って ii. もし、! だったら、キューからデータを取り出し iii. もし、@ だったら、入力を貰ってキューに追加 iv. 現時点のキューのデータを、全部出力 16/36 int main() { char symbol; int i, item; struct queue Q; initialize(&Q); 中略 } int main() { char symbol; int i, item; struct queue Q; initialize(&Q); 中略 }

解説

その

7

[6/9] 変数の宣言 symbol → 入力保存用 i → for ループ用 item → キューとのやりとり用 Q → キュー保存用キューの初期化 int int int int main() {main() {main() {main() {

変数変数変数変数ののの宣言の宣言宣言宣言キューキューキューキューのののの初期化初期化初期化初期化条件を満たすまで繰り返しここから 1文字読み込みもし!なら、dequeueを実行もし@なら、1文字読み込み enqueueを実行キューの内容を全部表示繰り返しここまで }}}} int int int int main() {main() {main() {main() {

変数変数変数変数のののの宣言宣言宣言宣言キューキューキューキューののの初期化の初期化初期化初期化条件を満たすまで繰り返しここから 1文字読み込みもし!なら、dequeueを実行もし@なら、1文字読み込み enqueueを実行キューの内容を全部表示繰り返しここまで }}}}

(9)

17/36 do{

printf("input ! or @:¥n");

scanf(" %c",&symbol);

中略

}while (symbol != EOF ); do{

printf("input ! or @:¥n");

scanf(" %c",&symbol);

中略

}while (symbol != EOF );

解説

その

8

[7/9] int main() { 変数の宣言キューの初期化条件条件条件条件ををを満を満満満たすまでたすまでたすまで繰たすまで繰り繰繰りりり返返返し返しししここからここからここからここから 1111文字読文字読文字読文字読みみみ込み込込込みみみみもし!なら、dequeueを実行もし@なら、1文字読み込み enqueueを実行キューの内容を全部表示繰繰繰繰りりりり返返返し返しししここまでここまでここまでここまで } int main() { 変数の宣言キューの初期化条件条件条件条件をををを満満満たすまで満たすまでたすまでたすまで繰繰り繰繰りり返り返返返しししここからしここからここからここから 1111文字読文字読文字読み文字読みみみ込込込込みみみみもし!なら、dequeueを実行もし@なら、1文字読み込み enqueueを実行キューの内容を全部表示繰繰繰繰りりり返り返返返しししここまでしここまでここまでここまで } 入力を促すメッセージの出力１文字入力入力された文字が EOF以外の間、 do～whileの間を繰り返し 18/36 if ( symbol == '!'){ item = dequeue(&Q); printf("dequeue %d ¥n",item);

}else if( symbol == '@'){

printf("input an integer:¥n"); scanf("%d",&item); enqueue(&Q, item); printf("enqueue %d ¥n",item); } if ( symbol == '!'){ item = dequeue(&Q); printf("dequeue %d ¥n",item);

}else if( symbol == '@'){

printf("input an integer:¥n"); scanf("%d",&item); enqueue(&Q, item); printf("enqueue %d ¥n",item); }

解説

その

9

[8/9] int main() { 変数の宣言キューの初期化条件を満たすまで繰り返しここから 1文字読み込みもしもしもし

もし!!!!ならならならなら、、、、dequeuedequeuedequeuedequeueをををを実行実行実行実行もし

もしもし

もし@@@@ならならなら、なら、、、1111文字読文字読文字読み文字読みみみ込込み込込みみみ enqueueenqueueenqueueenqueueををを実行を実行実行実行キューの内容を全部表示繰り返しここまで } int main() { 変数の宣言キューの初期化条件を満たすまで繰り返しここから 1文字読み込みもしもしもし

もし!!!!ならならならなら、、、、dequeuedequeuedequeuedequeueををを実行を実行実行実行もし

もしもし

もし@@@@ならならならなら、、、、1111文字読文字読文字読文字読みみみ込み込み込込みみ enqueueみenqueueenqueueをenqueueををを実行実行実行実行

キューの内容を全部表示繰り返しここまで } 入力が ! ならキューからデータを取り出し画面に表示もし、@ が入力されたら入力を貰いメッセージを表示してキューに追加しメッセージを表示

(10)

19/36

printf("¥n--- Now queue data:¥n");

for (i=Q.head; i < Q.tail; i++){

printf(" data[%d]=%d¥n", i, Q.data[i]);

}

printf("---¥n¥n");

printf("¥n--- Now queue data:¥n");

for (i=Q.head; i < Q.tail; i++){

printf(" data[%d]=%d¥n", i, Q.data[i]);

} printf("---¥n¥n");

解説

その

10

[9/9] int main() { 変数の宣言キューの初期化条件を満たすまで繰り返しここから 1文字読み込みもし!なら、dequeueを実行もし@なら、1文字読み込み enqueueを実行キューキューキューキューのののの内容内容内容を内容をを全部表示を全部表示全部表示全部表示繰り返しここまで } int main() { 変数の宣言キューの初期化条件を満たすまで繰り返しここから 1文字読み込みもし!なら、dequeueを実行もし@なら、1文字読み込み enqueueを実行キューキューキューキューののの内容の内容内容内容をををを全部表示全部表示全部表示全部表示繰り返しここまで } キューの中身は、 headとtailの間なので、その間繰り返し配列の中身を表示キューの内容 data 10 0 1 5 0 1 2 3 4 5 0 0 4 tail 1 head この部分を全部表示 20/36

今までの内容の追補

(11)

21/36 代入：整数型の変数 i に10を代入したい

代入

i=10; i=10; i+=2; i+=2; 他にも、減算代入（-=）、乗算代入（*=）、除算代入（/=）等、一通りあります。加算代入：整数型の変数 i に2を加えて i に代入したい i=i+2; とほとんど同じ意味。 22/36 コンパイル時、この行以降の文字列1が文字列2に置換されます。

#define

#define 文字列1 文字列2 #define 文字列1 文字列2 #include<stdio.h> #define N 10 #define N 10 #define N 10 #define N 10 main(){ int i[NNNN]; printf("%d",NNNN); } #include<stdio.h> #define N 10 #define N 10 #define N 10 #define N 10 main(){ int i[NNNN]; printf("%d",NNNN); } 例：これ以降の N は10 と define int i[10]と解釈される printf("%d",10)と解釈される

(12)

23/36 型1に、新しい型名1を定義します。

typedef

その

1

#typedef 型1 型名1 #typedef 型1 型名1 #include<stdio.h>

typedef int seisu typedef int seisu typedef int seisu

typedef int seisu;;;;

main(){ seisu seisuseisu seisu i;i;i;i; } #include<stdio.h>

typedef int seisu typedef int seisu typedef int seisu typedef int seisu;;;;

main(){ seisu seisu seisu seisu i;i;i;i; } 例： int型にseisuという別名を付ける seisu型の変数iを宣言ソースを分かり易くしたり、簡潔にしたりできる 24/36 型1に、新しい型名1を定義します。

typedef

その

2

#typedef 型1 型名1 #typedef 型1 型名1 typedef struct typedef struct typedef struct

typedef struct complex {complex {complex {complex {

double real; double real; double real; double real; double imaginary; double imaginary; double imaginary; double imaginary; } } }

} hukusosuhukusosuhukusosuhukusosu; ; ; ;

typedef struct typedef struct typedef struct

typedef struct complex {complex {complex {complex {

double real; double real; double real; double real; double imaginary; double imaginary; double imaginary; double imaginary; } } }

} hukusosuhukusosuhukusosu; hukusosu; ; ;

構造体の定義とかで、よく使われます。型1 型名1 main(){ hukusosu hukusosu hukusosu hukusosu com1;com1;com1;com1;

} main(){

hukusosu hukusosu hukusosu hukusosu com1;com1;com1;com1;

} このように宣言できるように struct complex { double real; double imaginary; }; struct complex { double real; double imaginary; }; main(){

struct complex com1; }

main(){

struct complex com1; }

(13)

25/36

C

言語について

1973年にAT&Tベル研究所のデニス・リッチーが主体となって作った。 ALGOL系の言語で、構造化プログラミングが可能。基本的に逐次実行繰り返し（for文、while文等）分岐（if文、switch文等）から構成される。俗に言うスパゲッティになりにくい。実行順序が、あっちこっちに飛び、全体が把握しづらいプログラムのこと 26/36

C

言語について

その

2

なんだかんだで、かなり普及している言語です。豊富なライブラリ（命令群）。いろんな環境で使用できる。計算機に対して、かなり強力なことまで行うことができる。やや使いづらい部分もある。配列の添え字をチェックしてくれない。宣言してない部分にまでアクセスできてしまう。文字列を扱う専用の型が存在しない。宣言してない部分にまでアクセスできてしまう。ここらへんは、プログラミング時に注意が必要。

(14)

27/36

計算機言語

他にも、色々な計算機言語があります。 C++ ：C言語の拡張として作られた Java ：機種に非依存 BASIC ：昔は、パソコンで一番メジャーだった。：構造化言語でなく、スパゲッティーなソースを：書きがち。 forthや：基本的に、すべての命令はスタックを postscript ：操作する命令。 awkやperl ：スクリプト型の言語。手軽に書ける。等々他の文法の言語を勉強することは、理解や技量の幅が広がる（と思います）後期に授業があります 28/36

アルゴリズムとデータ構造

(15)

29/36

プログラムとデータ構造

データ構造：コンピュータにどのように組織化して格納するかデータの格納方法が異なれば、その加工の仕方も変わる。プログラム：入力データを加工しつつ、正しい出力を求めていくプロセスの記述プログラム=アルゴリズム+データ構造入力データデータ出力データ … 格納加工加工 30/36

データ構造

コンピュータに、どのデータを、どのように格納するか。キューの実現の仕方 Romberg積分法の、データの種類と蓄え方 data 10 0 1 5 0 1 2 3 4 5 0 0 4 tail 1 head queue 構造体で実現 1 , 1 R 1 , 2 R 1 , 3 R M 1 , n R 2 , 2 R 2 , 3 R M 2 , n R 3 , 3 R M 3 , n R O n n R , 1 , 4 R 2 , 4 R 3 , 4 R 3 , 4 R L 4 , n R M 配列で実現依存関係や処理順を考慮して、全部保存キューの内容と、キューの先頭、末尾が必要

(16)

31/36

データの処理

入力データを加工しつつ、正しい出力を求めていくプロセスの記述キューへのデータの追加とか取り出し等 Romberg積分法で、解を出すまでの計算の順番等 data 10 0 1 5 0 1 2 3 4 5 0 0 4 tail 1 head queue 1 , 1 R 1 , 2 R 1 , 3 R M 1 , n R 2 , 2 R 2 , 3 R M 2 , n R 3 , 3 R M 3 , n R O n n R , 1 , 4 R 2 , 4 R 3 , 4 R 3 , 4 R L 4 , n R M 青い矢印、赤い矢印の順番に処理すれば大丈夫キューにデータを加えるときは、何を、どういう順番で行えば良い？ 32/36

プログラムを書くときには．．．

プログラムを行うときに考えること．．．データ構造：目的を達成するためには、どのようなデータが必要になるか。どのように保存したら良いか。目的を達成するためには、何を行えばよいか。どのような順番で行えばよいか。結局の所、色々練習して、経験値を積むのが良いです変数の宣言や、構造体の定義に関係処理の内容や順番等に関係

(17)

33/36

おわりに

34/36

プログラムを勉強する目的

プログラムを勉強すると．．．実際にプログラムを書くことで、数値計算の授業でやった内容を整理する。（基本的な）プログラミング能力を身につける。物事を実現するときにに必要な、データ構造とか処理方法とかの考え方を身につける。手法の理屈だけじゃなくて経験も積む将来、大規模な処理とかやりたいときに便利何をどのように、どういう順番でやればよいかを、整然と考えられるようになる（はず）

(18)

35/36

学期末の課題について

課題内容は、webを参照すること。〆〆〆切〆切切切はははは、、、、8月月2日月月日日日ののの12:00ですのですです。です。。。レポートボックスが出ますそので、そこに投函してください。 A4の紙で提出すること。別途、プログラムを、[email protected] まで送ること。課題の回答例を、お盆のあたりまでに、webに上げます。 36/36