PowerPoint Presentation

Size: px
Start display at page:

Download "PowerPoint Presentation"

Transcription

1 整列アルゴリズムの基礎

2 この回の要点 整列とは? 整列処理の意味 整列の種類 整列の計算量 整列の安定性 単純な整列アルゴリズム バブルソート 選択ソート 挿入ソート それぞれのソートの特徴と実装

3 整列 (Sorting) とは 整列という操作 レコードの集まりを キーの値の大小関係に従って並べ替える操作 小さい 大きい = 昇順 (ascending order) 大きい 小さい = 降順 (descending order) データには 同じキーを持つものがあってもよい 同じキーのデータは連続して整列される 整列アルゴリズムの種類 比較による整列 バブルソート 選択ソート 挿入ソート :O(n 2 ) シェルソート :O(n 1.5 ) ヒープソート マージソート クイックソート :O(n log n) 比較によらない整列 ( デジタルソート ) バケットソート ( ビンソート ) 分布数え上げソート 基数ソート :O(n)

4 整列の計算量 比較による整列 n 個のデータを整列するときに必要な処理 2 つのデータの大小を判定する ( 比較 ) 必要ならばそれらを入れ替える ( 交換 ) アルゴリズムによって 2 つの処理の回数の比率が異なる 扱うデータがどちらにコストがかかるか によって使い分ける データのサイズが大きい場合 データそのものを交換するのにコストがかかる キーの構造が複雑な場合 比較にコストがかかる 計算量だけでなく 定数項部分も重要 高速なアルゴリズムは処理が複雑である傾向がある n が小さいときは 単純なアルゴリズムのほうが速いこともある 比較によらない整列 時間的には O(n) で整列可能であるが メモリ量も O(n) である 時間的にも O(n) と O(n log n) とは 実用的にはそれほど差はない

5 O(n) と O(n log n) と O(n 2 ) との比較 1E+13 1E+11 1E+09 n n log(n) n*n

6 安定な整列 安定な (stable) 整列とは 同じキーを持つデータがある場合に それらの順序関係が保たれる整列 すべての整列アルゴリズムが安定であるとは限らない 単純な ( 遅い ) アルゴリズムは安定の傾向 複雑な ( 速い ) アルゴリズムは非安定の傾向 ただし サブキーを利用することで 確実に安定にできる 安定性の利点 複数のエントリーを持つレコードを 1 つのキーによって整列するような場合 安定なソートは必ずこうなる 整列前 : a b 2 整列後 1: a 5 b 非安定なソートはどちらになるかわからない 整列後 2: b 5 a 7 8 9

7 単純な整列アルゴリズム 以下の 3 種類 バブルソート 選択ソート 挿入ソート いずれも O(n 2 ) の計算量 プログラムとして実装した場合 データ数 n に対して 2 重の for ループ構造となる n が大きいと遅くて使いものにならない アルゴリズムが簡単ですぐに実装できる 少ないデータを整列するには重宝

8 ソート関数の形 任意のポインタの配列を並べ替える関数 sortxxxxx( 配列, サイズ, 比較関数 ) XXXXX は並べ替えのタイプ sortbubble() sortselection() sortinsertion() など 配列は任意のポインタの配列 サイズは配列の要素数 比較関数 int *compare(void *d1,void *d2) d1=d2 ならばゼロ d1<d2 ならば負の数 d1>d2 ならば正の数 を返す

9 Sort.h #ifndef Sort h #define Sort h /*** *** 並べ替え用 ***/ #include <stdio.h> #include <stdlib.h> 整列データ データ数 比較関数 // プロトタイプ宣言 void sortbubble(void*,int,int(*)(void*,void*)); void sortselection(void*,int,int(*)(void*,void*)); void sortinsertion(void*,int,int(*)(void*,void*)); #endif // Sort h

10 バブルソート 原理 配列の後ろから先頭に向かってスキャンし 隣り合う要素の大小関係が逆なら入れ替える 時間

11 Sort.cc /*** ソートの実装 ***/ #include "Sort.h" // バブルソート void sortbubble(void *d0,int s,int (*comp)(void*,void*)){ void **d=(void**)d0; 次のスライドで説明 for(int i=0;i<s-1;i++){ for(int j=s-1;j>i;j--){ if(comp(d[j-1],d[j])>0){ void *t=d[j]; d[j]=d[j-1]; d[j-1]=t; 3 2 1

12 整列データの受け渡し 整列データ配列 整列するためのデータ 任意のポインタである void* の配列 これは void** と表すことができる 実際に並べ替えるデータ PD のポインタ配列である PD** など PD** から void** への変換が必要となる この変換は暗黙には行われない void** 渡すデータ void* void* void* void* void* 任意 任意 そのための工夫 sortxxxxx(void*,int, ) のように void* で受ける void* は任意のポインタであるから PD** でも良い これを受け取った後に void** にキャストする ただし これによりコンパイラによる型チェックの恩恵にはあずかれなくなる 実際のデータ

13 整列データの受け渡し 整列関数 PD** void sortxxxxx(void *d0, ){ void **d=(void**)d0; void** void* void* void* void* void* void* void* void* PD* PD* PD* PD* PD* PD* PD* PD* 整列するデータ 関数の中では void* の配列として取り扱う 山田 18 森 55 中村 33 今井 60

14 バブルソートの計算量 二重ループ構造 (1 と 2) 1 のループは n-1 回 O(n-1) 2 のループは 平均 n/2 回 O(n/2) 3 の処理は n に無関係 O(1) 計算量 O(n-1) O(n/2) O(1)=O(n 2 ) となる 安定な整列アルゴリズム 前の要素が大きければ入れ替える 等しい場合は入れ替わらない 等しい要素の順番は保存される データの交換回数が多い ループ 2 の中で データが上位に上がるとデータの交換が起こる 処理効率の低下

15 TestSort1.cc /*** *** 整列のテスト ***/ #include "Sort.h" #include "PD.h" // 比較関数 int comp(void *d1,void *d2){ PD *pd1=(pd*)d1; PD *pd2=(pd*)d2; return pd1->age-pd2->age; // 表示 void print(pd **d,int s){ for(int i=0;i<s;i++) printf("%s(%d)-",d[i]->name,d[i]->age); printf(" n"); 続く

16 TestSort1.cc // メイン int main(int argc,char **argv){ PD *data[6]; data[0]=makepd(" 山田 ",18); data[1]=makepd(" 森 ",55); data[2]=makepd(" 中村 ",33); data[3]=makepd(" 石田 ",27); data[4]=makepd(" 東村 ",31); data[5]=makepd(" 牧 ",12); print(data,6); // 並べ換える前の表示 sortbubble(data,6,comp); // 並べ換え print(data,6); // 並べ換えた後の表示

17 実行結果 $./TestSort1 山田 (18)- 森 (55)- 中村 (33)- 石田 (27)- 東村 (31)- 牧 (12)- 牧 (12)- 山田 (18)- 石田 (27)- 東村 (31)- 中村 (33)- 森 (55)- 年齢順が若いに並んでいる

18 選択ソート 原理 整列されていない部分から最小の要素を選び それを先頭に移動する a[0]~a[n-1] の最小の要素を a[0] と交換 a[1]~a[n-1] の最小の要素を a[1] と交換 a[2]~a[n-1] の最小の要素を a[2] と交換 a[n-2]~a[n-1] の最小の要素を a[n-2] と交換 整列済み 未整列 最小を探す 整列済み 先頭に持ってくる ( 交換 )

19 Sort.cc( 続き ) // 選択ソート void sortselection(void *d0,int s,int (*comp)(void*,void*)){ void **d=(void**)d0; for(int i=0;i<s-1;i++){ int min=i; for(int j=i+1;j<s;j++){ if(comp(d[j],d[min])<0) min=j; void *t=d[i]; d[i]=d[min]; d[min]=t;

20 選択ソートの計算量 二重ループ構造 1 のループは n-1 回 O(n-1) 2 のループは 平均 n/2 回 O(n/2) 3 の処理は n に無関係 O(1) 4 の処理も n に無関係 O(1) 計算量 O(n-1) O(n/2) O(1) O(1)=O(n 2 ) となる 非安定な整列アルゴリズム 先頭要素との交換時に 同じ値を持つ要素の並びが変化する データの交換回数が少ない ループ 1 が 1 回まわると 交換が 1 回だけ起こる バブルソートより高速

21 挿入ソート 原理 配列の一部を整列済みにし 残りの要素を 1 つずつその中の適切な位置に挿入する 整列前 1 回ループ後 2 回ループ後 3 回ループ後 4 回ループ後 5 回ループ後 整列済み 先頭要素だけ整列済み整列済みに 8を挿入 ( 比較 1 回 ) 整列済みに 3を挿入 ( 比較 2 回 ) 整列済みに 18を挿入 ( 比較 1 回 ) 整列済みに 21を挿入 ( 比較 1 回 ) 整列済みに 4を挿入 ( 比較 4 回 )

22 InsertionSort.java // 挿入ソート void sortinsertion(void *d0,int s,int (*comp)(void*,void*)){ void **d=(void**)d0; for(int i=1;i<s;i++){ for(int j=i;j>0 && comp(d[j-1],d[j])>0;j--){ void *t=d[j]; d[j]=d[j-1]; d[j-1]=t;

23 挿入ソートの計算量 二重ループ構造 1 のループは n-1 回 O(n-1) 2 のループは 平均 n/2 回 O(n/2) 3 の処理は n に無関係 O(1) 計算量 O(n-1) O(n/2) O(1) =O(n 2 ) となる 安定な整列アルゴリズム 挿入するとき 1 つ前の要素が大きければ入れ替える 同じの場合は入れ替えないので 同じ要素の順番は保持される ほとんど整列済みのデータに有利 既に並んでいるデータについては比較と交換が発生しない この場合 ループ 2 は 1 回もまわらない ほとんど整列済みのデータに対しては ほぼ O(n) で整列可能

24 単純な整列アルゴリズムの比較 実験用プログラム 3 つのソートを実行し 以下の情報を測定 実行時間 データの比較回数 データの交換回数 Sort.ccに変数を追加する ( 後で ) 与えるデータ データ数を可変 (200 個 ~10000 個 ) データの分布を可変 ( ランダム ほぼ整列済み )

25 比較と交換の回数のカウント (1) Sort.cc にカウント用の変数を追加 整列前に 0 に初期化する 各アルゴリズムの sortxxxx() 関数内で 比較と交換の回数をカウント /*** *** ソートの実装 ***/ #include "Sort.h" int comp_count; int exchg_count; // 比較回数 // 交換回数 Sort.h の中で extern 宣言してないので Sort.cc の中でしか使えない変数 続く

26 比較と交換の回数のカウント (2) // バブルソート void sortbubble(void *d0,int s,int (*comp)(void*,void*)){ comp_count=exchg_count=0; void **d=(void**)d0; for(int i=0;i<s-1;i++){ for(int j=s-1;j>i;j--){ comp_count++; if(comp(d[j-1],d[j])>0){ exchg_count++; void *t=d[j]; d[j]=d[j-1]; d[j-1]=t; 続く

27 比較と交換の回数のカウント (3) // 選択ソート void sortselection(void *d0,int s,int (*comp)(void*,void*)){ comp_count=exchg_count=0; void **d=(void**)d0; for(int i=0;i<s-1;i++){ int min=i; for(int j=i+1;j<s;j++){ comp_count++; if(comp(d[j],d[min])<0) min=j; exchg_count++; void *t=d[i]; d[i]=d[min]; d[min]=t; 続く

28 比較と交換の回数のカウント (4) // 挿入ソート void sortinsertion(void *d0,int s,int (*comp)(void*,void*)){ comp_count=exchg_count=0; void **d=(void**)d0; for(int i=1;i<s;i++){ for(int j=i;j>0;j--){ comp_count++; if(comp(d[j-1],d[j])>0){ exchg_count++; void *t=d[j]; d[j]=d[j-1]; d[j-1]=t; else break; カウントするために 判断構造を少し変えた本質的には同じ 続く

29 比較と交換の回数のカウント (5) 各回数を得るための関数を追加 // 比較回数を得る int getcompcount(){ return comp_count; // 交換回数を得る int getexchgcount(){ return exchg_count;

30 比較と交換の回数のカウント (6) Sort.h にプロトタイプ宣言を追加 #ifndef Sort h #define Sort h /*** *** 並べ替え用 ***/ #include <stdio.h> #include <stdlib.h> // プロトタイプ宣言 void sortbubble(void*,int,int(*)(void*,void*)); void sortselection(void*,int,int(*)(void*,void*)); void sortinsertion(void*,int,int(*)(void*,void*)); int getcompcount(); int getexchgcount(); #endif // Sort h

31 テスト用 TestSort2.cc /*** *** 並べ換えのテスト 2 ***/ #include "Sort.h" #include "PD.h" #include <string.h> #include <time.h> // 比較関数 // 名前で比較し 同じなら年齢で比較する int compare(void *d1,void *d2){ PD *pd1=(pd*)d1; PD *pd2=(pd*)d2; int c=strcmp(pd1->name,pd2->name); if(c==0) return pd1->age-pd2->age; return c; 続く

32 テスト用 TestSort2.cc // メイン int main(int argc,char **argv){ int loop=1; double rand_rate=1.0; // 引数処理 if(argc!=3 && argc!=4 && argc!=5){ fprintf(stderr, "Usage: %s type max [rand=1.0] [loop=1]",argv[0]); exit(1); int type=atoi(argv[1]); int max=atoi(argv[2]); if(argc>=4) rand_rate=atof(argv[3]); if(argc>=5) loop=atoi(argv[4]); PD **data=(pd**)malloc(max*sizeof(pd*)); srand(time(null)); 続く

33 テスト用 TestSort2.cc // 実験 double lap=0; double comp_count=0; double exchg_count=0; for(int i=0;i<loop;i++){ // シリアルデータの準備 char s[]={ 'a','a','a','a','a',0 ; for(int i=0;i<max;i++){ int a=rand()%60+10; // 年齢はランダム data[i]=makepd(s,a); for(int j=4;j>=0;j--){ if(s[j]<'z'){ s[j]++; break; s[j]='a'; 続く

34 テスト用 TestSort2.cc // シャッフル int c=(int)(max*rand_rate); for(int i=0;i<c;i++){ int r1=(int)(((double)rand()/rand_max)*max); int r2=(int)(((double)rand()/rand_max)*max); PD *t=data[r1]; data[r1]=data[r2]; data[r2]=t; 続く

35 テスト用 TestSort2.cc // 並べ替え clock_t t1=clock(); switch(type){ case 0: sortbubble(data,max,compare); break; case 1: sortselection(data,max,compare); break; case 2: sortinsertion(data,max,compare); break; clock_t t2=clock(); lap+=((double)t2-t1)/clocks_per_sec; comp_count+=getcompcount(); exchg_count+=getexchgcount(); // 結果を表示 ( 時間 比較回数の平均 交換回数の平均 ) printf("%f %f %f ",lap*1000,comp_count/loop,exchg_count/loop);

36 データ数と並べ替え時間 b-lap s-lap i-lap n^2/

37 データ数と比較回数 b-comp s-comp i-cmop

38 データ数と交換回数 b-exchg s-exchg i-exchg

39 比較回数 交換回数 選択ソートはデータの交換回数が少ない 挿入ソートはデータの比較回数が少ない num b-lap b-comp b-exchg s-lap s-comp s-exchg i-lap i-cmop i-exchg

40 ほぼ揃ったデータの整列 ほぼ揃っている ランダム b-lap s-lap i-lap

41 ほぼそろったデータに対する比較回数 交換回数 データ数は に固定 挿入ソートは 比較回数が極端に少ない それに応じて 交換回数も少なくなる rand b-lap b-comp b-exchg s-lap s-comp s-exchg i-lap i-cmop i-exchg ランダム率

42 課題 この回に実装した整列プログラムは void* の配列を整列するので 通常の int の配列は整列できない そこで バブルソートで int の配列を整列する関数 sortbubble(int*,int,int(*)(int,int)) を実装せよ 実装は Sort.h にプロトタイプ宣言し Sort.cc にコードを追加すること 降順に整列する比較関数を書き 10 個のランダムな整数を降順に並べ替えるテストプログラム TestSort3.cc も示せ 提出方法 : レポートはワードで作成し メールに添付すること ファイル名は scxxxxxx-al docx とすること レポートには学籍番号と氏名を必ず書くこと メールで渕田まで送付すること 提出先 :fuchida@ibe.kagoshima-u.ac.jp メールタイトル : アルゴリズム課題 メール本文にも学籍番号と氏名を必ず書くこと 期限 :2019 年 1 月 6 日 ( 日 ) 24:00

43 整列アルゴリズムの基礎 終了

PowerPoint Presentation

PowerPoint Presentation 二分探索木 今回の要点 二分探索木の構造 どのような条件を満たさねばならないか? 二分探索が効率よく出来るため 二分探索木の操作 探索の方法 挿入の方法 削除の方法 各操作の実装コード 二分探索木の性質 どのような形がもっと探索に適しているか? 二分探索木とは 木構造 枝分かれした構造を表現するのに適する 根から葉に向かってたどる = 探索 何らかの特徴を持って構成されていると探索しやすい 二分探索木

More information

第3回 配列とリスト

第3回 配列とリスト 連結リスト Algorithms and Data Structures on C この回の要点 連結リストによるリスト 連結リストの構造 連結リストの利点と欠点 C 言語による連結リストの実現 ヘッダファイルによるソースファイルの分割 連結リスト (linked list) リストの実現の一種 リストに含まれる各要素をリンクによって連結した構造 リンクとは 他のデータへの参照のこと 各要素は 自分から次のデータへのリンクを持つ

More information

次に示す数値の並びを昇順にソートするものとする このソートでは配列の末尾側から操作を行っていく まず 末尾の数値 9 と 8 に着目する 昇順にソートするので この値を交換すると以下の数値の並びになる 次に末尾側から 2 番目と 3 番目の 1

次に示す数値の並びを昇順にソートするものとする このソートでは配列の末尾側から操作を行っていく まず 末尾の数値 9 と 8 に着目する 昇順にソートするので この値を交換すると以下の数値の並びになる 次に末尾側から 2 番目と 3 番目の 1 4. ソート ( 教科書 p.205-p.273) 整列すなわちソートは アプリケーションを作成する際には良く使われる基本的な操作であり 今までに数多くのソートのアルゴリズムが考えられてきた 今回はこれらソートのアルゴリズムについて学習していく ソートとはソートとは与えられたデータの集合をキーとなる項目の値の大小関係に基づき 一定の順序で並べ替える操作である ソートには図 1 に示すように キーの値の小さいデータを先頭に並べる

More information

PG13-6S

PG13-6S プログラム演習 I レポート 学籍番号 担当教員 : 小林郁夫 氏名 実習日平成 26 年 7 月 4 日 提出期限 7 月 11 日提出日 7 月 17 日 1 週遅れ 第 13 回 テーマ : 並べ替えのアルゴリズム 教員使用欄 15 S A B C 再提出 課題 1 バブルソートの実行画面 プログラムのソースコード // day13_akb1.cpp : コンソールアプリケーションのエントリポイントを定義します

More information

二分木の実装

二分木の実装 二分木の実装 この回の要点 二分木の C 言語による実装を理解する 再帰呼び出しによる木のなぞりの実装を理解する 関数ポインタを使った汎用処理の実装を理解する 実装コードの構成 汎用的構造 各ノードは void* を持つ 二分木のノード BinTreeNode.h BinTreeNode.cc 二分木 BinTree.h BinTree.cc テスト用 TestBinTree.cc BinTree

More information

Microsoft Word - no12.doc

Microsoft Word - no12.doc 7.5 ポインタと構造体 構造体もメモリのどこかに値が格納されているのですから 構造体へのポインタ も存在します また ポインタも変数ですから 構造体のメンバに含めることができます まずは 構造体へのポインタをあつかってみます ex53.c /* 成績表 */ #define IDLENGTH 7 /* 学籍番号の長さ */ #define MAX 100 /* 最大人数 */ /* 成績管理用の構造体の定義

More information

Microsoft PowerPoint - lec10.ppt

Microsoft PowerPoint - lec10.ppt 今日の内容, とポインタの組み合わせ, 例題 1. 住所録例題 2. と関数とは. を扱う関数. 例題 3. のリスト とポインタの組み合わせ 今日の到達目標 自分で を定義する 自分で定義したについて, 配列やポインタを作成する データ型 基本データ型 char 文字 (1 文字 ) int 整数 double 浮動小数など その他のデータ型配列 データの並び ( 文字列も, 文字の並び ) ポインタ

More information

memo

memo 数理情報工学演習第一 C プログラミング演習 ( 第 5 回 ) 2015/05/11 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : プロトタイプ宣言 ヘッダーファイル, プログラムの分割 課題 : 疎行列 2 プロトタイプ宣言 3 C 言語では, 関数や変数は使用する前 ( ソースの上のほう ) に定義されている必要がある. double sub(int

More information

program7app.ppt

program7app.ppt プログラム理論と言語第 7 回 ポインタと配列, 高階関数, まとめ 有村博紀 吉岡真治 公開スライド PDF( 情報知識ネットワーク研 HP/ 授業 ) http://www-ikn.ist.hokudai.ac.jp/~arim/pub/proriron/ 本スライドは,2015 北海道大学吉岡真治 プログラム理論と言語, に基づいて, 現著者の承諾のもとに, 改訂者 ( 有村 ) が加筆修正しています.

More information

Microsoft PowerPoint - 計算機言語 第7回.ppt

Microsoft PowerPoint - 計算機言語 第7回.ppt 計算機言語第 7 回 長宗高樹 目的 関数について理解する. 入力 X 関数 f 出力 Y Y=f(X) 関数の例 関数の型 #include int tasu(int a, int b); main(void) int x1, x2, y; x1 = 2; x2 = 3; y = tasu(x1,x2); 実引数 printf( %d + %d = %d, x1, x2, y);

More information

slide5.pptx

slide5.pptx ソフトウェア工学入門 第 5 回コマンド作成 1 head コマンド作成 1 早速ですが 次のプログラムを head.c という名前で作成してください #include #include static void do_head(file *f, long nlines); int main(int argc, char *argv[]) { if (argc!=

More information

PowerPoint プレゼンテーション - 物理学情報処理演習

PowerPoint プレゼンテーション  -  物理学情報処理演習 物理学情報処理演習 9. C 言語 5 2015 年 6 月 19 日 本日の推奨作業 directory lesson09 9.1 乱数 9.2 ポインタ 参考文献 やさしい C++ 第 4 版高橋麻奈 ( 著 ) ソフトバンククリエイティブ プログラミング言語 C++ 第 4 版ビャーネ ストラウストラップ, Bjarne Stroustrup, 柴田望洋 Numerical Recipes:

More information

DA13

DA13 データ構造とアルゴリズム第 13 回 知能情報学メジャー 和 俊和 5 整列 5.1 整列とは 5.2 単純な整列アルゴリズム 5.3 挿 ソートとその拡張 5.4 ヒープソート 5.5 クイックソート 5.6 マージソート 5.7 値の 較を いない整列 5.6 マージソート 1 与えられたデータ A を A " と A # にほぼ 等分する. 2A " と A # を整列する. このとき, データ数が

More information

プログラミング基礎

プログラミング基礎 C プログラミング Ⅱ 演習 2-1(a) BMI による判定 文字列, 身長 height(double 型 ), 体重 weight (double 型 ) をメンバとする構造体 Data を定義し, それぞれのメンバの値をキーボードから入力した後, BMI を計算するプログラムを作成しなさい BMI の計算は関数化すること ( ) [ ] [ ] [ ] BMI = 体重 kg 身長 m 身長

More information

第3回 配列とリスト

第3回 配列とリスト リストと配列 Algorithms and Data Structures on C この回の要点 C 言語における変数 プリミティブ型とポインタの違い 参照型における実体オブジェクトへの参照 リストとは? 配列によるリスト 配列の利点と欠点 C 言語による配列の実現 配列の代入と複製の違い データ構造 アルゴリズム + データ構造 = プログラム アルゴリズム データをどのように加工するか データ構造

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用 第 15 回 知的情報システム学科張 暁華 プログラミング応用 1 授業のマナー ------ 人の話を聞くときの社会常識 1. 欠席者のかわりに登録を行わない 倫理に反することをやらない あなたの信を問われている蟻の穴から堤防が決壊 2. 私語しないこと : 質問 意見は手を挙げて大きな声ではっきりと意思表示 3. 授業以外のことをしない : 携帯をカバンにいれ イヤホンを使って音楽等を聞かない授業中ゲームを遊ばない

More information

Taro-再帰関数Ⅲ(公開版).jtd

Taro-再帰関数Ⅲ(公開版).jtd 0. 目次 1 1. ソート 1 1. 1 挿入ソート 1 1. 2 クイックソート 1 1. 3 マージソート - 1 - 1 1. ソート 1 1. 1 挿入ソート 挿入ソートを再帰関数 isort を用いて書く 整列しているデータ (a[1] から a[n-1] まで ) に a[n] を挿入する操作を繰り返す 再帰的定義 isort(a[1],,a[n]) = insert(isort(a[1],,a[n-1]),a[n])

More information

木構造の実装

木構造の実装 汎用的構造と反復子 Algorithms and Data Structures on C この回の要点 汎用的構造とは これまでのリストでは何か問題か? 解決する方法は? 反復子とは 何をするものか? どのように使うか? 実装コード ListNode 型 List 型 ListIterator 型 個人情報 PD 型 ( 第 4 回で作成 ) 個人情報 名前 (char *name) 年齢 (int

More information

論理と計算(2)

論理と計算(2) 情報科学概論 Ⅰ アルゴリズムと計算量 亀山幸義 http://logic.cs.tsukuba.ac.jp/~kam 亀山担当分の話題 アルゴリズムと計算量 Fibonacci 数列の計算を例にとり アルゴリズムと計算量とは何か 具体的に学ぶ 良いアルゴリズムの設計例として 整列 ( ソーティング ) のアルゴリズムを学ぶ 2 Fibonacci 数 () Fibonacci 数 (2) = if

More information

プログラミング方法論 II 第 14,15 回 ( 担当 : 鈴木伸夫 ) 問題 17. x 座標と y 座標をメンバに持つ構造体 Point を作成せよ 但し座標 は double 型とする typedef struct{ (a) x; (b) y; } Point; 問題 18. 問題 17 の

プログラミング方法論 II 第 14,15 回 ( 担当 : 鈴木伸夫 ) 問題 17. x 座標と y 座標をメンバに持つ構造体 Point を作成せよ 但し座標 は double 型とする typedef struct{ (a) x; (b) y; } Point; 問題 18. 問題 17 の プログラミング方法論 II 第 14,15 回 ( 担当 : 鈴木伸夫 ) 問題 17. x 座標と y 座標をメンバに持つ構造体 Point を作成せよ 但し座標 は double 型とする typedef struct{ (a) x; (b) y; Point; 問題 18. 問題 17 の Point を用いて 2 点の座標を入力するとその 2 点間の距 離を表示するプログラムを作成せよ 平方根は

More information

Microsoft PowerPoint - 11.pptx

Microsoft PowerPoint - 11.pptx ポインタと配列 ポインタと配列 配列を関数に渡す 法 課題 : 配列によるスタックの実現 ポインタと配列 (1/2) a が配列であるとき, 変数の場合と同様に, &a[0] [] の値は配列要素 a[0] のアドレス. C 言語では, 配列は主記憶上の連続領域に割り当てられるようになっていて, 配列名 a はその配列に割り当てられた領域の先頭番地となる. したがって,&a[0] と a は同じ値.

More information

02: 変数と標準入出力

02: 変数と標準入出力 C プログラミング入門 基幹 7 ( 水 5) 12: コマンドライン引数 Linux にログインし 以下の講義ページを開いておくこと http://www-it.sci.waseda.ac.jp/ teachers/w483692/cpr1/ 2016-06-29 1 まとめ : ポインタを使った処理 内容呼び出し元の変数を書き換える文字列を渡す 配列を渡すファイルポインタ複数の値を返す大きな領域を確保する

More information

簡単な検索と整列(ソート)

簡単な検索と整列(ソート) フローチャート (2) アルゴリズム論第 2 回講義 2011 年 10 月 7 日 ( 金 ) 反復構造 ( 一定回数のループ処理 ) START 100 回同じ処理を繰り返す お風呂で子供が指をおって数を数える感じ 繰り返し数を記憶する変数をカウンター ( 変数名 I をよく使う ) と呼ぶ カウンターを初期化して, 100 回繰り返したかどうか判定してそうならば終了そうでなければ処理を実行して

More information

関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include <stdiu.h> #define InFile "data.txt" #define OutFile "surted.txt" #def

関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include <stdiu.h> #define InFile data.txt #define OutFile surted.txt #def C プログラミング演習 1( 再 ) 6 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include #define InFile "data.txt" #define OutFile "surted.txt"

More information

プログラム言語及び演習Ⅲ

プログラム言語及び演習Ⅲ 平成 28 年度後期データ構造とアルゴリズム期末テスト 各問題中のアルゴリズムを表すプログラムは, 変数の宣言が省略されているなど, 完全なものではありませんが, 適宜, 常識的な解釈をしてください. 疑問があれば, 挙手をして質問してください. 時間計算量をオーダ記法で表せという問題では, 入力サイズ n を無限大に近づけた場合の漸近的な時間計算量を表せということだと考えてください. 問題 1 入力サイズが

More information

コマンドラインから受け取った文字列の大文字と小文字を変換するプログラムを作成せよ 入力は 1 バイトの表示文字とし アルファベット文字以外は変換しない 1. #include <stdio.h> 2. #include <ctype.h> /*troupper,islower,isupper,tol

コマンドラインから受け取った文字列の大文字と小文字を変換するプログラムを作成せよ 入力は 1 バイトの表示文字とし アルファベット文字以外は変換しない 1. #include <stdio.h> 2. #include <ctype.h> /*troupper,islower,isupper,tol コマンドラインから受け取った文字列の大文字と小文字を変換するプログラムを作成せよ 入力は 1 バイトの表示文字とし アルファベット文字以外は変換しない 1. #include 2. #include /*troupper,islower,isupper,tolowerを使うため宣言*/ 3. 4. int get_n(char *); 5. void replace(char

More information

バイオプログラミング第 1 榊原康文 佐藤健吾 慶應義塾大学理工学部生命情報学科

バイオプログラミング第 1 榊原康文 佐藤健吾 慶應義塾大学理工学部生命情報学科 バイオプログラミング第 1 榊原康文 佐藤健吾 慶應義塾大学理工学部生命情報学科 ポインタ変数の扱い方 1 ポインタ変数の宣言 int *p; double *q; 2 ポインタ変数へのアドレスの代入 int *p; と宣言した時,p がポインタ変数 int x; と普通に宣言した変数に対して, p = &x; は x のアドレスのポインタ変数 p への代入 ポインタ変数の扱い方 3 間接参照 (

More information

Prog1_6th

Prog1_6th 2012 年 5 月 24 日 ( 木 ) 実施 多分岐のプログラム 前回は多段階の 2 分岐を組み合わせて 3 種類以上の場合分けを実現したが, 式の値の評価によって, 一度に多種類の場合分けを行う多分岐の利用によって見通しのよいプログラムを作成できる場合がある ( 流れ図は右図 ) 式の評価 : 値 1 : 値 2 : 値 n : 該当値無し 処理 1 処理 2 処理 n 既定の処理 switch

More information

6 文字列処理 ( 教科書 p.301p.332) 今回は 言語の文字列処理について復習し, 文字列の探索手法について学びます. 文字列とはプログラム上での文字の並びを表すのが文字列です. これは中身が空であっても同様に呼ばれます. 言語では "STRING" のように文字の並びを二重引用符 " で囲んだものを文字列リテラルと呼びます. SII コードの場合, 割り当てられる数値は図 1 のようになっています.

More information

kiso2-09.key

kiso2-09.key 座席指定はありません 計算機基礎実習II 2018 のウェブページか 第9回 ら 以下の課題に自力で取り組んで下さい 計算機基礎実習II 第7回の復習課題(rev07) 第9回の基本課題(base09) 第8回試験の結果 中間試験に関するコメント コンパイルできない不完全なプログラムなど プログラミングに慣れていない あるいは複雑な問題は 要件 をバラして段階的にプログラムを作成する exam08-2.c

More information

C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ

C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 今回のプログラミングの課題 次のステップによって 徐々に難易度の高いプログラムを作成する ( 参照用の番号は よくわかる C 言語 のページ番号 ) 1. キーボード入力された整数 10 個の中から最大のものを答える 2. 整数を要素とする配列 (p.57-59) に初期値を与えておき

More information

PowerPoint Presentation

PowerPoint Presentation スタックと待ち行列 Algorithms and Data Structures on C この回の要点 スタック スタックの構造 最後に入れたものが 最初に取り出される (LIFO) 日常に良くある ちょっと置いといて の概念 C 言語の配列による実装 スタックオーバーフロー スタックアンダーフロー 逆ポーランド記法電卓 待ち行列 待ち行列の構造 最初に入れたものが 最初に取り出される (FIFO)

More information

PowerPoint Template

PowerPoint Template プログラミング演習 Ⅲ Linked List P. Ravindra S. De Silva e-mail: ravi@cs.tut.ac.jp, Room F-413 URL: www.icd.cs.tut.ac.jp/~ravi/prog3/index_j.html 連結リストとは? 一つひとつの要素がその前後の要素との参照関係をもつデータ構造 A B C D 連結リストを使用する利点 - 通常の配列はサイズが固定されている

More information

データ構造

データ構造 アルゴリズム及び実習 3 馬青 1 バブルソート 考え方 : 隣接する二つのデータを比較し データの大小関係が逆のとき 二つのデータの入れ替えを行って整列を行う方法である 2 バブルソートの手順 配列 a[0],a[1],,a[n-1] をソートする場合 ステップ 1: 配列 a[0] と a[1],a[1] と a[2],,a[n-2] と a[n-1] と となり同士を比較 ( 大小が逆であれば

More information

模擬試験問題(第1章~第3章)

模擬試験問題(第1章~第3章) 基本情報技術者試験の練習問題 - 第 10 回 この問題は平成 19 年度春期の問題から抜粋しています 問 1 次のプログラムの説明及びプログラムを読んで, 設問 1~3 に答えよ プログラムの説明 整数型の 1 次元配列の要素 A[0],,A[N](N>0) を, 挿入ソートで昇順に整列する副プログラム InsertSort である (1) 挿入ソートの手順は, 次のとおりである (i) まず,A[0]

More information

Microsoft PowerPoint - kougi7.ppt

Microsoft PowerPoint - kougi7.ppt C プログラミング演習 第 7 回メモリ内でのデータの配置 例題 1. 棒グラフを描く 整数の配列から, その棒グラフを表示する ループの入れ子で, 棒グラフの表示を行う ( 参考 : 第 6 回授業の例題 3) 棒グラフの1 本の棒を画面に表示する機能を持った関数を補助関数として作る #include "stdafx.h" #include void draw_bar( int

More information

6 関数 6-1 関数とは少し長いプログラムを作るようになると 同じ処理を何度も行う場面が出てくる そのたびに処 理を書いていたのでは明らかに無駄であるし プログラム全体の見通しも悪くなる そこで登場す るのが 関数 である 関数を使うことを 関数を呼び出す ともいう どのように使うのか 実際に見て

6 関数 6-1 関数とは少し長いプログラムを作るようになると 同じ処理を何度も行う場面が出てくる そのたびに処 理を書いていたのでは明らかに無駄であるし プログラム全体の見通しも悪くなる そこで登場す るのが 関数 である 関数を使うことを 関数を呼び出す ともいう どのように使うのか 実際に見て 6 関数 6-1 関数とは少し長いプログラムを作るようになると 同じ処理を何度も行う場面が出てくる そのたびに処 理を書いていたのでは明らかに無駄であるし プログラム全体の見通しも悪くなる そこで登場す るのが 関数 である 関数を使うことを 関数を呼び出す ともいう どのように使うのか 実際に見てみよう 次のプログラムは 2 つの数字のうち 大きい方を求 めるものである int max(int a,

More information

C 言語講座 Vol 年 5 月 29 日 CISC

C 言語講座 Vol 年 5 月 29 日 CISC C 言語講座 Vol.3 2009 年 5 月 29 日 CISC 字下げ 見やすく書こう! #include int main(void) int a; printf(" 値 =>"); scanf("%d",&a); if(a>10) printf("10 より大きい値です \n"); else printf("10 以下の値です \n"); return 0; #include

More information

関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include <stdio.h> #define InFile "data.txt" #define OutFile "sorted.txt" #def

関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include <stdio.h> #define InFile data.txt #define OutFile sorted.txt #def C プログラミング演習 1( 再 ) 6 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include #define InFile "data.txt" #define OutFile "sorted.txt"

More information

1. 入力した正の整数を降順に並べ換えて出力するプログラムを作成せよ プログラムは個別にコンパイルし make コマンドで実行すること 入力データは 50 以下とし 以下の数が混在しているとする 16 進数 : 先頭 1 文字が x または X( エックスの小文字か大文字 ) 8 進数 : 先頭 1

1. 入力した正の整数を降順に並べ換えて出力するプログラムを作成せよ プログラムは個別にコンパイルし make コマンドで実行すること 入力データは 50 以下とし 以下の数が混在しているとする 16 進数 : 先頭 1 文字が x または X( エックスの小文字か大文字 ) 8 進数 : 先頭 1 1. 入力した正の整数を降順に並べ換えて出力するプログラムを作成せよ プログラムは個別にコンパイルし make コマンドで実行すること 入力データは 50 以下とし 以下の数が混在しているとする 16 進数 : 先頭 1 文字が x または X( エックスの小文字か大文字 ) 8 進数 : 先頭 1 文字が 0( 零 ) 10 進数 : 先頭 1 文字が 0( 零 ) 以外の数字 1.1 プログラム

More information

プログラミング基礎

プログラミング基礎 C プログラミング 演習 プログラミング基礎 II 演習 II 2012 年 12 月 10 日 第 11 回 今後の予定 2012/12/10 C プログラミング及びプログラミング演習 II 2 2012/12/17 期末試験 (60 分間 ) 場所 :A0542 時間 :4 時限 (15:00~16:00) 2012/12/16 課題の最終提出締切 課題の提出方法 電子メールで提出 提出先 (

More information

第9回 配列(array)型の変数

第9回 配列(array)型の変数 第 12 回 配列型の変数 情報処理演習 ( テキスト : 第 4 章, 第 8 章 ) 今日の内容 1. 配列の必要性 2. 配列の宣言 3. 配列変数のイメージ 4. 配列変数を使用した例 5. 範囲を超えた添字を使うと? 6. 多次元配列変数 7. 多次元配列変数を使用した例 8. データのソーティング 9. 今日の練習問題 多数のデータ処理 1. 配列の必要性 ( テキスト 31 ページ )

More information

02: 変数と標準入出力

02: 変数と標準入出力 C プログラミング入門 基幹 7 ( 水 5) 1 12: コマンドライン引数 Linux にログインし 以下の講義ページを開いておくこと http://www-it.sci.waseda.ac.jp/teachers/w48369 2/CPR1/ 2017-07-05 まとめ : ポインタを使った処理 2 内容呼び出し元の変数を書き換える文字列を渡す 配列を渡すファイルポインタ複数の値を返す大きな領域を確保する

More information

第2回

第2回 第 4 回基本データ構造 1 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 1 配列 スタック キューとその操作 4-1. 配列とその操作 配列型 同じ型の変数を並べたもの 配列にする型は 基本型 配列型 構造体 ポインタいずれでもよい 要素の並べ方を 次元 という 1 次元配列 ( 直線状 ) 2 次元配列 ( 平面状 ) 3 次元配列 ( 立体状 ) a[5]

More information

情報処理Ⅰ

情報処理Ⅰ Java フローチャート -1- フローチャート ( 流れ図 ) プログラムの処理手順 ( アルゴリズム ) を図示したもの 記号の種類は下記のとおり 端子記号 ( 開始 終了 ) 処理記号計算, 代入等 条件の判定 条件 No ループ処理 LOOP start Yes データの入力 出力 print など 定義済み処理処理名 end サンプルグログラム ( 大文字 小文字変換 ) 大文字を入力して下さい

More information

講習No.12

講習No.12 前回までの関数のまとめ 関数は main() 関数または他の関数から呼び出されて実行される. 関数を呼び出す側の実引数の値が関数内の仮引数 ( 変数 ) にコピーされる. 関数内で定義した変数は, 関数の外からは用いることができない ( ローカル変数 ). 一般に関数内で仮引数を変化しても, 呼び出し側の変数は変化しない ( 値渡し ). 関数内で求めた値は return 文によって関数値として呼び出し側に戻される.

More information

2006年10月5日(木)実施

2006年10月5日(木)実施 2010 年 7 月 2 日 ( 金 ) 実施 ファイル処理ファイルとはファイル (file) は日常用語では紙などを綴じたものを表すが, コンピュータ用語ではデータの集合体を指す言葉である ファイルは例えば, 文書ファイルやプログラムファイルのように, 用途によって分類されることもあれば, また, テキストファイルやバイナリファイルのように, ファイルの作り方によって分類されることもある なお,

More information

Prog1_15th

Prog1_15th 2012 年 7 月 26 日 ( 木 ) 実施構造体と typedef typedef 宣言によって,struct 構造体タグ名という表記を再定義し, データ型名のように扱うことができる 構文は typedef struct 構造体タグ名 再定義名 ; となり, この場合の構造体変数の宣言は, 再定義名を用いて行うことができる なお, ここでは 構造体タグ名は省略可能である 構造体を指すポインタ

More information

memo

memo 数理情報工学演習第一 C ( 第 8 回 ) 206/06/3 DEPARTMENT OF MATHEMATICAL INFORMATICS 今日の内容 : プロトタイプ宣言 ヘッダーファイル, プログラムの分割 プライオリティキュー ヒープ 課題 : ヒープソート 2 プロトタイプ宣言 C 言語では, 関数や変数は使用する前 ( ソースの上のほう ) に定義されている必要がある. double sub(int

More information

Microsoft PowerPoint - 05.pptx

Microsoft PowerPoint - 05.pptx アルゴリズムとデータ構造第 5 回 : データ構造 (1) 探索問題に対応するデータ構造 担当 : 上原隆平 (uehara) 2015/04/17 アルゴリズムとデータ構造 アルゴリズム : 問題を解く手順を記述 データ構造 : データや計算の途中結果を蓄える形式 計算の効率に大きく影響を与える 例 : 配列 連結リスト スタック キュー 優先順位付きキュー 木構造 今回と次回で探索問題を例に説明

More information

Prog1_10th

Prog1_10th 2012 年 6 月 20 日 ( 木 ) 実施ポインタ変数と文字列前回は, ポインタ演算が用いられる典型的な例として, ポインタ変数が 1 次元配列を指す場合を挙げたが, 特に,char 型の配列に格納された文字列に対し, ポインタ変数に配列の 0 番の要素の先頭アドレスを代入して文字列を指すことで, 配列そのものを操作するよりも便利な利用法が存在する なお, 文字列リテラルは, その文字列が格納されている領域の先頭アドレスを表すので,

More information

<4D F736F F D20438CBE8CEA8D758DC03389F0939A82C282AB2E646F63>

<4D F736F F D20438CBE8CEA8D758DC03389F0939A82C282AB2E646F63> C 言語講座第 3 回 キャスト ( 型変換 ) 強制的に式の型を変換する ( 変換したい型名 ) 変換元で記述する int num_a = 10, num_b = 3; float result1, result2; // 結果格納用 // 計算用 result1 = num_a / num_b; // 通常のint/int 割り算 result2 = (float)num_a / num_b;//

More information

/*Source.cpp*/ #include<stdio.h> //printf はここでインクルードして初めて使えるようになる // ここで関数 average を定義 3 つの整数の平均値を返す double 型の関数です double average(int a,int b,int c){

/*Source.cpp*/ #include<stdio.h> //printf はここでインクルードして初めて使えるようになる // ここで関数 average を定義 3 つの整数の平均値を返す double 型の関数です double average(int a,int b,int c){ ソフトゼミ A 第 6 回 関数 プログラムは関数の組み合わせでできています 今までのゼミAでも printf や scanf など様々な関数を使ってきましたが なんと関数は自分で作ることもできるのです!! 今日は自作関数を中心に扱っていきます ゲーム制作でも自作関数は避けては通れないので頑張りましょう そもそもまず 関数とは 基本的には 受け取った値に関数によって定められた操作をして その結果の値を返す

More information

Microsoft Word - no15.docx

Microsoft Word - no15.docx 7. ファイルいままでは プログラムを実行したとき その結果を画面で確認していました 簡単なものならそれでもいいのですか 複雑な結果は画面で見るだけでなく ファイルに保存できればよいでしょう ここでは このファイルについて説明します 使う関数のプロトタイプは次のとおりです FILE *fopen(const char *filename, const char *mode); ファイルを読み書きできるようにする

More information

PowerPoint Presentation

PowerPoint Presentation 算法数理工学 第 2 回 定兼邦彦 クイックソート n 個の数に対して最悪実行時間 (n 2 ) のソーティングアルゴリズム 平均実行時間は (n log n) 記法に隠された定数も小さい in-place ( 一時的な配列が必要ない ) 2 クイックソートの記述 分割統治法に基づく 部分配列 A[p..r] のソーティング. 部分問題への分割 : 配列 A[p..r] を 2 つの部分配列 A[p..q]

More information

Microsoft PowerPoint - kougi10.ppt

Microsoft PowerPoint - kougi10.ppt C プログラミング演習 第 10 回二分探索木 1 例題 1. リストの併合 2 つのリストを併合するプログラムを動かしてみる head1 tail1 head2 tail2 NULL NULL head1 tail1 tail1 があると, リストの併合に便利 NULL 2 #include "stdafx.h" #include struct data_list { int data;

More information

Microsoft Word - Cプログラミング演習(12)

Microsoft Word - Cプログラミング演習(12) 第 12 回 (7/9) 4. いくつかのトピック (5)main 関数の引数を利用したファイル処理 main 関数は, 起動する環境から引数を受け取ることができる 例えば 次に示すように,main 関数に引数を用いたプログラムを作成する 01 /* sample */ 02 /* main 関数の引数 */ 03 #include 04 05 main(int argc, char

More information

PowerPoint Presentation

PowerPoint Presentation ファイルの入出力 芝浦工業大学情報工学科 青木義満 今回の講義内容 ファイル入出力 ファイルからのデータ読込み ファイルと配列 2 1 ファイルへのデータ書き込み ( 復習 ) ソースファイル名 :fileio1.c データをファイルに書き込み #include int main(void) { ファイルポインタ宣言 int student_id = 100; char name[

More information

gengo1-11

gengo1-11 関数の再帰定義 自然数 n の階乗 n! を計算する関数を定義してみる 引数は整数 返却値も整数 n! = 1*2*3*... * (n 1)*n である ただし 0! = 1 とする int factorial(int n) int i, tmp=1; if( n>0 ) for(i=1; i

More information

Microsoft Word - 3new.doc

Microsoft Word - 3new.doc プログラミング演習 II 講義資料 3 ポインタ I - ポインタの基礎 1 ポインタとは ポインタとはポインタは, アドレス ( データが格納されている場所 ) を扱うデータ型です つまり, アドレスを通してデータを間接的に処理します ポインタを使用する場合の, 処理の手順は以下のようになります 1 ポインタ変数を宣言する 2 ポインタ変数へアドレスを割り当てる 3 ポインタ変数を用いて処理 (

More information

今回のプログラミングの課題 ( 前回の課題で取り上げた )data.txt の要素をソートして sorted.txt というファイルに書出す ソート (sort) とは : 数の場合 小さいものから大きなもの ( 昇順 ) もしくは 大きなものから小さなもの ( 降順 ) になるよう 並び替えること

今回のプログラミングの課題 ( 前回の課題で取り上げた )data.txt の要素をソートして sorted.txt というファイルに書出す ソート (sort) とは : 数の場合 小さいものから大きなもの ( 昇順 ) もしくは 大きなものから小さなもの ( 降順 ) になるよう 並び替えること C プログラミング演習 1( 再 ) 4 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 今回のプログラミングの課題 ( 前回の課題で取り上げた )data.txt の要素をソートして sorted.txt というファイルに書出す ソート (sort) とは : 数の場合 小さいものから大きなもの ( 昇順 ) もしくは 大きなものから小さなもの ( 降順

More information

£Ã¥×¥í¥°¥é¥ß¥ó¥°ÆþÌç (2018) - Â裵²ó ¨¡ À©¸æ¹½Â¤¡§¾ò·ïʬ´ô ¨¡

£Ã¥×¥í¥°¥é¥ß¥ó¥°ÆþÌç (2018) - Â裵²ó  ¨¡ À©¸æ¹½Â¤¡§¾ò·ïʬ´ô ¨¡ (2018) 2018 5 17 0 0 if switch if if ( ) if ( 0) if ( ) if ( 0) if ( ) (0) if ( 0) if ( ) (0) ( ) ; if else if ( ) 1 else 2 if else ( 0) 1 if ( ) 1 else 2 if else ( 0) 1 if ( ) 1 else 2 (0) 2 if else

More information

第1回 プログラミング演習3 センサーアプリケーション

第1回 プログラミング演習3 センサーアプリケーション C プログラミング - ポインタなんて恐くない! - 藤田悟 fujita_s@hosei.ac.jp 目標 C 言語プログラムとメモリ ポインタの関係を深く理解する C 言語プログラムは メモリを素のまま利用できます これが原因のエラーが多く発生します メモリマップをよく頭にいれて ポインタの動きを理解できれば C 言語もこわくありません 1. ポインタ入門編 ディレクトリの作成と移動 mkdir

More information

Microsoft PowerPoint - kougi9.ppt

Microsoft PowerPoint - kougi9.ppt C プログラミング演習 第 9 回ポインタとリンクドリストデータ構造 1 今まで説明してきた変数 #include "stdafx.h" #include int _tmain(int argc, _TCHAR* argv[]) { double x; double y; char buf[256]; int i; double start_x; double step_x; FILE*

More information

Microsoft Word - 03

Microsoft Word - 03 平成 24 年度講義 アルゴリズムとデータ構造 第 3 回変数のスコープルール 関数 担当 : 富井尚志 (tommy@ynu.ac.jp) 選択計算 ( 条件判断 ) 第 2 回 基本的制御構造 の復習 if 文 : ある条件に応じて別々の計算を行う. 式が真 (0 以外 ) であれば文 1 が実行され, 偽であれば文 2 が実行される. なお,else 以下は省略可能である. if ( 式 )

More information

Microsoft PowerPoint ppt

Microsoft PowerPoint ppt 基礎演習 3 C 言語の基礎 (5) 第 05 回 (20 年 07 月 07 日 ) メモリとポインタの概念 ビットとバイト 計算機内部では データは2 進数で保存している 計算機は メモリにデータを蓄えている bit 1bit 0 もしくは 1 のどちらかを保存 byte 1byte 1bitが8つ集まっている byte が メモリの基本単位として使用される メモリとアドレス メモリは 1byte

More information

論理と計算(2)

論理と計算(2) 情報科学概論 Ⅰ アルゴリズムと計算 亀山幸義 http://logic.cs.tsukuba.ac.jp/~kam 計算とは? コンピュータが計算できることは? 1 2 関数 = 計算? NO 部分関数と計算 入力 1 入力 2 関数 出力 入力 1 入力 2 部分関数 出力 停止しない 入力 1 入力 2 コンピュータ 止まらないことがある出力 3 入力 1 入力 2 コンピュータ 出力 停止しない

More information

DVIOUT

DVIOUT 2009 年度情報科学 & 情報科学演習レポート 7 学生用 学籍番号 : 氏名 : 下記の注意事項を守り 次ページ以降の問いに答え レポートを完成させなさい 提出期限 : 2009 年 6 月 16 日 ( 火 ) 13:00 まで提出場所 : 理学部棟正面玄関内に設置のレポートボックス 注意事項 : (1) このページを印刷し 必要事項を記入の上 ( 学籍番号欄と氏名欄は 2 箇所あるので忘れずに記入すること

More information

file:///D|/C言語の擬似クラス.txt

file:///D|/C言語の擬似クラス.txt 愛知障害者職業能力開発校 システム設計科 修了研究発表会報告書 題名 : C 言語の擬似クラス あらまし : C 言語でクラスを作れるという噂の真偽を確かめるために思考錯誤した まえがき : VC++ や Java その他オブジェクト指向の言語にはクラスが存在して クラスはオブジェクトの設計図である 手法 : C++ のクラスを解析して C++ のクラスを作成して C 言語に翻訳する class struct

More information

Prog1_12th

Prog1_12th 2013 年 7 月 4 日 ( 木 ) 実施 ファイル処理ファイルとはファイル (file) は日常用語では紙などを綴じたものを表すが, コンピュータ用語ではデータの集合体を指す言葉である ファイルは例えば, 文書ファイルやプログラムファイルのように, 用途によって分類されることもあれば, また, テキストファイルやバイナリファイルのように, ファイルの作り方によって分類されることもある なお,

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 5 回演習 前回までのお話 ポインタ ポインタを用いた文字列処理 構造体 ファイル 再帰的構造体 リスト構造 動的メモリ管理 今日のお題 ポインタやファイルなど これまでの内容の練習 教材 以前 以下に単語を収録したファイルがあることを紹介した : /usr/share/dict/words この中からランダムに単語を取り出したファイルを用意した http://sun.ac.jp/prof/yamagu/2019app/

More information

プログラミング基礎

プログラミング基礎 C プログラミング 演習 アルゴリズム基礎論 演習 第 10 回 今後の予定 12/22( 月 ) 期末試験 (60 分間 ) 場所 :A1611 時間 :16:20~17:20 課題の最終提出締切 :12/19( 金 ) これ以降の新規提出は評価されない 12/22までに最終状況を提示するので, 提出したのに や になってる人は自分の提出内容や提出先を再確認した上で12/26までに問い合わせること

More information

RX ファミリ用 C/C++ コンパイラ V.1.00 Release 02 ご使用上のお願い RX ファミリ用 C/C++ コンパイラの使用上の注意事項 4 件を連絡します #pragma option 使用時の 1 または 2 バイトの整数型の関数戻り値に関する注意事項 (RXC#012) 共用

RX ファミリ用 C/C++ コンパイラ V.1.00 Release 02 ご使用上のお願い RX ファミリ用 C/C++ コンパイラの使用上の注意事項 4 件を連絡します #pragma option 使用時の 1 または 2 バイトの整数型の関数戻り値に関する注意事項 (RXC#012) 共用 RX ファミリ用 C/C++ コンパイラ V.1.00 Release 02 ご使用上のお願い RX ファミリ用 C/C++ コンパイラの使用上の注意事項 4 件を連絡します #pragma option 使用時の 1 または 2 バイトの整数型の関数戻り値に関する注意事項 (RXC#012) 共用体型のローカル変数を文字列操作関数で操作する場合の注意事項 (RXC#013) 配列型構造体または共用体の配列型メンバから読み出した値を動的初期化に用いる場合の注意事項

More information

memo

memo 計数工学プログラミング演習 ( 第 3 回 ) 2017/04/25 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 内容 ポインタの続き 引数の値渡しと参照渡し 構造体 2 ポインタで指されるメモリへのアクセス double **R; 型 R[i] と *(R+i) は同じ意味 意味 R double ** ポインタの配列 ( の先頭 ) へのポインタ R[i]

More information

Microsoft Word - report#8.docx

Microsoft Word - report#8.docx プログラミング I report#8 提出日 :7 月 18 日 ( 木 ) 所属 : 工学部情報工学科学籍番号 :135713B 氏名 : 天願寛之 目次 ソース cardinal についての考察ソース conv10 についての考察ソース select_sort.c についての考察ソース print_num.c についての考察ソース msg.c についての考察感想 P4 P7 P10 P13 P14

More information

Microsoft Word - no206.docx

Microsoft Word - no206.docx 3.2 双方向リスト 今までのリストは 前から順にたどることしかできませんでした 今度は逆にもたどることができる 双方向リストを扱います この場合は 構造体には次を表すポインタの他に前を表すポインタを持つ ことになります 今回は最初と最後をポインタを使うと取り扱いが面倒になるので 最初 (start) と最後 (end) を どちらとも構造体 ( 値は意味を持たない ) を使うことにします こうすることによって

More information

プログラミングI第10回

プログラミングI第10回 プログラミング 1 第 10 回 構造体 (3) 応用 リスト操作 この資料にあるサンプルプログラムは /home/course/prog1/public_html/2007/hw/lec/sources/ 下に置いてありますから 各自自分のディレクトリにコピーして コンパイル 実行してみてください Prog1 2007 Lec 101 Programming1 Group 19992007 データ構造

More information

データ構造

データ構造 アルゴリズム及び実習 7 馬青 1 表探索 定義表探索とは 表の形で格納されているデータの中から条件に合ったデータを取り出してくる操作である 但し 表は配列 ( 連結 ) リストなどで実現できるので 以降 表 の代わりに直接 配列 や リスト などの表現を用いる場合が多い 表探索をただ 探索 と呼ぶ場合が多い 用語レコード : 表の中にある個々のデータをレコード (record) と呼ぶ フィールド

More information

double float

double float 2015 3 13 1 2 2 3 2.1.......................... 3 2.2............................. 3 3 4 3.1............................... 4 3.2 double float......................... 5 3.3 main.......................

More information

問 2 ( 型変換 ) 次のプログラムを実行しても正しい結果が得られない 何が間違いかを指摘し 正しく修正せよ ただし int サイズが 2 バイト long サイズが 4 バイトの処理系での演算を仮定する #include <stdio.h> int main( void ) { int a =

問 2 ( 型変換 ) 次のプログラムを実行しても正しい結果が得られない 何が間違いかを指摘し 正しく修正せよ ただし int サイズが 2 バイト long サイズが 4 バイトの処理系での演算を仮定する #include <stdio.h> int main( void ) { int a = 問 1 配列の宣言整数型配列 data1 にデータが初期設定されている この配列 data1 のデータを下図のように 整数型配列 data2 に代入しなさい また data2 の内容を printf( "data2[0] = %d\n", data2[0] ); printf( "data2[5] = %d\n", data2[5] ); を用いて出力しなさい 実行結果 data2[0] = 76

More information

memo

memo 計数工学プログラミング演習 ( 第 4 回 ) 2016/05/10 DEPARTMENT OF MATHEMATICA INFORMATICS 1 内容 リスト 疎行列 2 連結リスト (inked ists) オブジェクトをある線形順序に並べて格納するデータ構造 単方向連結リスト (signly linked list) の要素 x キーフィールド key ポインタフィールド next x->next:

More information

Microsoft Word - Training10_プリプロセッサ.docx

Microsoft Word - Training10_プリプロセッサ.docx Training 10 プリプロセッサ 株式会社イーシーエス出版事業推進委員会 1 Lesson1 マクロ置換 Point マクロ置換を理解しよう!! マクロ置換の機能により 文字列の置き換えをすることが出来ます プログラムの可読性と保守性 ( メンテナンス性 ) を高めることができるため よく用いられます マクロ置換で値を定義しておけば マクロの値を変更するだけで 同じマクロを使用したすべての箇所が変更ができるので便利です

More information

Taro-最大値探索法の開発(公開版

Taro-最大値探索法の開発(公開版 最大値探索法の開発 0. 目次 1. 開発過程 1 目標 1 : 4 個のデータの最大値を求める 目標 2 : 4 個のデータの最大値を求める 改良 : 多数のデータに対応するため 配列を使う 目標 3 : n 個のデータの最大値を求める 改良 : コードを簡潔に記述するため for 文を使う 目標 4 : n 個のデータの最大値を求める 改良 : プログラムをわかりやすくするため 関数を使う 目標

More information

PowerPoint プレゼンテーション - 物理学情報処理演習

PowerPoint プレゼンテーション  -  物理学情報処理演習 物理学情報処理演習 8. C 言語 5 文字列 ポインタ 2016 年 6 月 7 日 ver20160607_2 本日の推奨作業 directory lesson08 8.1 文字列 8.2 ポインタ 参考文献 やさしい C++ 第 4 版高橋麻奈 ( 著 ) ソフトバンククリエイティブ プログラミング言語 C++ 第 4 版ビャーネ ストラウストラップ, Bjarne Stroustrup, 柴田望洋

More information

Microsoft PowerPoint - kougi6.ppt

Microsoft PowerPoint - kougi6.ppt C プログラミング演習 第 6 回ファイル処理と配列 1 ファイル処理 2 ファイル読み込み ファイル プログラム ファイルの中身は変わらない 3 ファイル書き出し ファイル プログラム ファイルの中身が変わる ファイルは伸び縮みすることがある 4 例題 1. テキストファイル形式の ファイルからのデータ読み込み 次のような名簿ファイル ( テキストファイル形式 ) を読み込んで,1 列目の氏名と,3

More information

Taro-リストⅠ(公開版).jtd

Taro-リストⅠ(公開版).jtd 0. 目次 1. 再帰的なデータ構造によるリストの表現 1. 1 リストの作成と表示 1. 1. 1 リストの先頭に追加する方法 1. 1. 2 リストの末尾に追加する方法 1. 1. 3 昇順を保存してリストに追加する方法 1. 2 問題 問題 1 問題 2-1 - 1. 再帰的なデータ構造によるリストの表現 リストは データの一部に次のデータの記憶場所を示す情報 ( ポインタという ) を持つ構造をいう

More information

02: 変数と標準入出力

02: 変数と標準入出力 C プログラミング入門 基幹 2 ( 月 4) 09: ポインタ 文字列 Linux にログインし 以下の講義ページを開いておくこと http://www-it.sci.waseda.ac.jp/ teachers/w483692/cpr1/ 2014-06-09 1 関数できなかったこと 配列を引数として渡す, 戻り値として返す 文字列を扱う 呼び出し元の変数を直接書き換える 例 : 2 つの変数の値を入れ替える関数

More information

7 ポインタ (P.61) ポインタを使うと, メモリ上のデータを直接操作することができる. 例えばデータの変更 やコピーなどが簡単にできる. また処理が高速になる. 7.1 ポインタの概念 変数を次のように宣言すると, int num; メモリにその領域が確保される. 仮にその開始のアドレスを 1

7 ポインタ (P.61) ポインタを使うと, メモリ上のデータを直接操作することができる. 例えばデータの変更 やコピーなどが簡単にできる. また処理が高速になる. 7.1 ポインタの概念 変数を次のように宣言すると, int num; メモリにその領域が確保される. 仮にその開始のアドレスを 1 7 ポインタ (P.61) ポインタを使うと, メモリ上のデータを直接操作することができる. 例えばデータの変更 やコピーなどが簡単にできる. また処理が高速になる. 7.1 ポインタの概念 変数を次のように宣言すると, int num; メモリにその領域が確保される. 仮にその開始のアドレスを 10001 番地とすると, そこから int 型のサイズ, つまり 4 バイト分の領域が確保される.1

More information

プログラミング実習I

プログラミング実習I プログラミング実習 I 05 関数 (1) 人間システム工学科井村誠孝 m.imura@kwansei.ac.jp 関数とは p.162 数学的には入力に対して出力が決まるもの C 言語では入出力が定まったひとまとまりの処理 入力や出力はあるときもないときもある main() も関数の一種 何かの仕事をこなしてくれる魔法のブラックボックス 例 : printf() 関数中で行われている処理の詳細を使う側は知らないが,

More information

Microsoft Word - 13

Microsoft Word - 13 担当 : 富井尚志 (tommy@ynu.ac.jp) アルゴリズムとデータ構造 講義日程 1. 基本的データ型 2. 基本的制御構造 3. 変数のスコープルール. 関数 4. 配列を扱うアルゴリズムの基礎 (1). 最大値, 最小値 5. 配列を扱うアルゴリズムの基礎 (2). 重複除去, 集合演算, ポインタ 6. ファイルの扱い 7. 整列 (1). 単純挿入整列 単純選択整列 単純交換整列

More information

PowerPoint Presentation

PowerPoint Presentation 今週のトピックス アルゴリズムとデータ構造 第 10 回講義 : 探索その 1 探索 (search) 逐次探索 (sequential search) 2 分探索 (binary search) 内挿探索 (interpolation search) Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 1 Produced

More information

Microsoft Word - Cプログラミング演習(10)

Microsoft Word - Cプログラミング演習(10) 第 10 回 (6/25) 3. ファイルとその応用 (3) ファイルの更新 シーケンシャルファイルの更新 シーケンシャルファイルでは, 各レコードが可変長で連続して格納されており, その中の特定のレコードを変更することができない そこで一般的には, マスタファイルからデータを取り出し, 更新処理を行ったあとに新マスタファイルに書き込む 注 ) マスタファイル : 主ファイル, 基本ファイルと呼ばれるファイルで内容は比較的固定的であり,

More information

Microsoft PowerPoint - algo ppt [互換モード]

Microsoft PowerPoint - algo ppt [互換モード] ( 復習 ) アルゴリズムとは アルゴリズム概論 - 探索 () - アルゴリズム 問題を解くための曖昧さのない手順 与えられた問題を解くための機械的操作からなる有限の手続き 機械的操作 : 単純な演算, 代入, 比較など 安本慶一 yasumoto[at]is.naist.jp プログラムとの違い プログラムはアルゴリズムをプログラミング言語で表現したもの アルゴリズムは自然言語でも, プログラミング言語でも表現できる

More information

Microsoft PowerPoint - 09.pptx

Microsoft PowerPoint - 09.pptx 情報処理 Ⅱ 第 9 回 2014 年 12 月 22 日 ( 月 ) 関数とは なぜ関数 関数の分類 自作関数 : 自分で定義する. ユーザ関数 ユーザ定義関数 などともいう. 本日のテーマ ライブラリ関数 : 出来合いのもの.printf など. なぜ関数を定義するのか? 処理を共通化 ( 一般化 ) する プログラムの見通しをよくする 機能分割 ( モジュール化, 再利用 ) 責任 ( あるいは不具合の発生源

More information

02: 変数と標準入出力

02: 変数と標準入出力 C プログラミング入門 基幹 2 ( 月 4) 11: 動的メモリ確保 Linux にログインし 以下の講義ページを開いておくこと http://www-it.sci.waseda.ac.jp/ teachers/w483692/cpr1/ 2014-06-22 1 まとめ : ポインタを使った処理 内容 説明 呼び出し元の変数を書き換える第 9 回 文字列を渡す 配列を渡す 第 10 回 ファイルポインタ

More information

02: 変数と標準入出力

02: 変数と標準入出力 C プログラミング入門 基幹 7 ( 水 5) 09: ポインタ 文字列 Linux にログインし 以下の講義ページを開いておくこと http://www-it.sci.waseda.ac.jp/ teachers/w483692/cpr1/ 2016-06-08 1 関数できなかったこと 配列を引数として渡す, 戻り値として返す 文字列を扱う 呼び出し元の変数を直接書き換える 例 : 2 つの変数の値を入れ替える関数

More information

Microsoft Word - Cプログラミング演習(9)

Microsoft Word - Cプログラミング演習(9) 第 9 回 (6/18) 3. ファイルとその応用 外部記憶装置に記録されたプログラムやデータを, ファイルと呼ぶ シーケンシャルファイルやランダムファイルへのデータの記録や読み出し, 更新の手順について学習する (1) ファイルとレコードファイル複数の関連したデータを一つに集めたり プログラムを外部記憶装置に保存したものレコードファイルを構成する一塊のデータ ex. 個人カードフィールドレコードを構成する個別の要素

More information

Microsoft PowerPoint - 13.ppt [互換モード]

Microsoft PowerPoint - 13.ppt [互換モード] 第 13 回構造体 1 今回の目標 構造体を理解する 構造体の定義の仕方を理解する 構造体型を理解する 構造体型の変数 引数 戻り値を理解する 複素数同士を足し算する関数を作成し その関数を利用するプログラムを作成する 2 複素数の足し算 複素数は実部と虚部の2つの実数で 表現される z = a+ bi z = a + bi z = a + b i 2 つの複素数 1 1 1 と 2 2 2 の和

More information

gengo1-8

gengo1-8 問題提起その 1 一文字ずつ文字 ( 数字 ) を読み込み それぞれの文字が何回入力されたかを数えて出力するプログラム int code, count_0=0, count_1=0, count_2=0, count_3=0,..., count_9=0; while( (code=getchar())!= EOF ){ } switch(code){ case 0 : count_0++; break;

More information

memo

memo 数理情報工学演習第一 C ( 第 12 回 ) 2016/07/11 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : ファイルの入出力 コマンドライン引数 2 分探索 クイックソート ( ライブラリ ) 文字列検索 2 ファイル操作の手続き : ファイル操作 ファイルからのデータ読み込み ファイルへのデータ書き出し 基本的な手順 読みこむ / 書き出すファイルを開く

More information