第12回:木構造

Size: px
Start display at page:

Download "第12回:木構造"

Transcription

1 アルゴリズムとデータ構造 講義スライド 木 グラフ 茨城大学工学部知能システム工学科井上康介 E 棟 8 号室

2 木とは リスト構造では枝分かれは起こらなかった. 枝分かれしながらデータが伸びていくデータ構造を木 (tree) と呼ぶ. 木はノード (node) とそれらを結ぶ枝 (branch) から構成される. データが記録されているのはノードであり, 枝はデータとデータの間の親子関係を示す. A ノード B C 枝 D E F G H p.-

3 木とは あるノードから下に分岐した先のノードを子, 分岐元のノードを親という. 木の一番最初のノードを特に, 根 (root) と呼び, 子を持たないノードを葉 (leaf) と呼ぶ. A 根 親 B C 子 D 親 E F 子 子 G H 葉

4 木とは あるノードから下につながった木構造の全体を部分木 (subtree) という. 根からあるノードに到達するまでに通る枝の数をそのノードの深さ (depth) といい, 根から最も深いノードまでの深さを木の高さ (height) という. A 深さ 部分木 B C 深さ D E F 深さ 深さ G H この木の高さ=

5 木とは ノードからの分岐が 以下の木を 分木 (binary tree) と呼ぶ. 親と子の関係が, ある規則 ( 大きい, 小さいなど ) に従って並べられている木を 分探索木 (binary search tree) という. 8 A 分木 B 9 C D E F I G 9 H 左の子 親 右の子

6 木とは 木構造はきわめて重要で, 多くの実用的対象が存在する. 組織データやファイルシステムなどの階層構造の表現 AI における論理的関係性の表現 探索を容易にする情報表現 ( 分探索木など ) ヒープ ソート 講義では, 分探索木およびヒープに重点を置いて解説する.

7 分探索木の配列表現 ノードに格納するデータが人名であるとき 名前を辞書順 に並べる分探索木が作れる 全ての親と子の間に 左の子 親 右の子という関係が成 立する 右側の子のノード番号 No. achilda No. No. Candy No. No. Ann No. Rolla No. Emy Nancy No. Eluza Lisa このようにノード番号を管理すれば 配列に格納できる p.8-8

8 分探索木の配列表現 各ノードに格納する情報は 人名 左の子へのポインタ (ノード番号) 右の子へのポインタ (ノード番号) のつで ある これを構造体にまとめ 配列にする struct tnode { int left; char name[]; int right; }; // 左部分木へのポインタ(番号) // データ(人名) // 右部分木へのポインタ(番号) 8

9 分探索木の配列表現 この配列を使って 分探索木を表現できる ただし nil はポインタが指し示すものがないという意味 で 具体的には - などを使う a[p].left a[p].name a[p].right No. achilda No. No. Candy No. No. Ann No. No. Emy Nancy No. Eluza Lisa Rolla achilda Candy Rolla nil nil Ann nil Emy nil Nancy nil nil Eluza nil nil Lisa nil 二分探索木の配列表現 9

10 分探索木の配列表現 分探索木から key という目的データを探すには root から初めて key がノードのデータより小さいときは左側 の木へ, 大きいときは右側の木へ探索すればよい 実質的に二分探索 O(log n) の計算量 a[p].left a[p].name a[p].right key が Eluza の場合 No. achilda No. No. Candy No. No. Ann No. No. Emy Nancy No. Eluza Lisa Rolla achilda Candy Rolla nil nil Ann nil Emy nil Nancy nil nil Eluza nil nil Lisa nil 二分探索木の配列表現

11 二分探索木の配列表現 (ソースコード) p.9 このコードでは 分探索木を初期化において与えてい る nil は - と定義 (プリプロセッサ) scanf() で key を読み込み p を (根ノード) で初期 化 p が nil にならない限り続けるループに入る strcmp() を使って 今見ているノード p の名前欄と key を照合し 合致していたら発見したことを表示して ループを抜ける もし key の方が小さいときは p を a[p].left に 逆の場合は p を a[p].right にする

12 分探索木へのデータの追加 先程の例では, 最初から 分探索木ができていたが, これを作るアルゴリズムが必要 すでに存在する 分探索木に対して, 新しいノードを追加する手順は, 以下の 段階を踏む 新ノードの親となるノードを探索 新ノードを親ノードに接続 現在調べているノードの番号を視点 p とし, この視点に一つ遅れで追従する視点 old も用意する p を進めていき,p が nil になったとき,old が指し示しているノードが新ノードの親

13 分探索木へのデータの追加 p=; while (p!=nil){ old=p; if (strcmp(key,a[p].name)<=) p=a[p].left; else p=a[p].right; } a[sp].left=a[sp].right=nil; strcpy(a[sp].name,key); if (strcmp(key,a[old].name)<=) a[old].left=sp; else a[old].right=sp; sp++; sp: key: Nancy Patie p: - p old achilda - p old Candy p old - Rolla Nancy - - Patie -

14 分探索木の動的表現 リストの場合と同様 ツリーもノードが動的に追加される データ構造である 従って 自己参照構造体としてノードを表現し 必要に応 じてメモリを動的に確保するのが適している struct tnode { struct tnode *left; /* 左部分木へのポインタ */ char name[]; /* 名前 */ struct tnode *right; /* 右部分木へのポインタ */ }; struct tnode *talloc(void) { return (struct tnode *)malloc(sizeof(struct tnode)); }; p.8-8

15 新規ノード作成手順 (コードを見つつ) 配列表現の時と同様 () 新規ノードの親となるノードの 探索 () 新規ノードの生成と親ノードからの接続を行う. Candy を追加 Emyを追加 視点 p を root で初期化 p:null p は新規データ dat の大小にした p=p->left がって木をたどり old は一つ遅れ p old achilda で追従 old=p としてから p を old->left=p 適切な方向へ進める p old p=p->right Candy p が NULL なら old が親ノード old->right=p p p=talloc()としてデータ記入 Emy 左右の子はいない NULL に 親ノードの名前と新ノードの名前の大小関係により 親ノードの左右どちらかのポインタを p に向ける

16 分探索木の動的表現 ( ソースコード ) まずはルートノード作成 root=talloc(); scanf("%s",root->name); root->left=root->right=null; root achilda

17 分探索木の動的表現 (ソースコード) while (scanf("%s",dat)!=eof){ p=root; while (p!=null){ old=p; if (strcmp(dat,p->name)<=) p=p->left; ここから下 p は else 視点 ではなく p=p->right; 新規ノード位置 } を示す p=talloc(); strcpy(p->name,dat); p->left=p->right=null; if (strcmp(dat,old->name)<=) old->left=p; else old->right=p; } 第ノード以降作成 (さきほどの手順) root dat: Rolla Nancy p: NULL p old achilda p old Rolla p Nancy

18 分探索木の再帰的表現 (集中して聞くこと) 木構造は再帰的処理に向いている 例えば探索の場合 rootノード (achilda) 以下から Emy を探す と いう問題は root->left (Candy) 以下の部分木から Emy を探す という副問題に 分解 できる root この中からの探索 この中か らの探索 再帰の脱出条件 発見 or 行き先が NULL (不在) (例 Eluza) achilda Rolla Candy Ann p.8-88 (途中まで) Emy 8

19 ノード追加の再帰的方法 (集中して聞くこと) 既存の 分探索木に新しいデータ w を含むノードを追加す る処理を再帰的に記述することを考える 再帰関数のプロトタイプを以下の通りとする struct tnode *gentree(struct tnode *p, char w[]) p 起点ノード (このノード以下が作業対象) w 追加するデータ (名前) その動作は条件により異なる p が NULL ではないとき ノード p の適切な方の子 ノードを起点として gentree()を再帰呼び出しし 受け取ったポインタ p をそのまま返す (オウム返し) p が NULL のとき 新規ノードを作り w を格納 作った新規ノードへのポインタを返す 9

20 ノード追加の再帰的方法 ここでは データ Nancy を含むノードへの ポインタを [Nancy] と表記する root main() root = gentree(root, Emy ) 呼出 Nancy [Nancy] 第 引数が NULL 以外 適切な子を起点とする 再帰呼び出し 第一引数をオウム返し 第 引数が NULL 新規ノードを作成 新規ノードへのポイ ンタを返す gentree([nancy], Emy ) 同じポインタを上書き 元の構造を壊さない [Nancy]->left = gentree([nancy]->left, Emy ); 呼出 [Candy] gentree([candy], Emy ) NULL Candy [Candy]->right = gentree([candy]->right, Emy ); 呼出 Emy [Emy] gentree(null, Emy ) ノード作成 戻り値の利用方法 に注目

21 ノード追加の再帰的方法 同じ方法で 第一ノード (root ノード) 作成も できるだろうか root main() root = gentree(root, Nancy ) 呼出 [Nancy] 第 引数が NULL 以外 適切な子を起点とする 再帰呼び出し 第一引数をオウム返し 第 引数が NULL 新規ノードを作成 新規ノードへのポイ ンタを返す gentree(null, Nancy ) Nancy ノード作成 作ったノードへのポインタを返す 第一ノード作成もそれ以降も root = gentree(略) でOK 二分探索木の生成は root を NULL で初期化し root = gentree(略); を 繰り返せば全部できる void main(void) { char dat[]; struct tnode *root; } root = NULL; while (scanf("%s",dat)!= EOF){ root = gentree(root,dat); }

22 ノード追加の再帰的方法 (ソース) struct tnode *gentree(struct tnode *p, char *w) { if (p == NULL){ p = talloc(); 新規ノード作成 strcpy(p->name, w); p->left = p->right = NULL; p 新規ノード } else if (strcmp(w, p->name) < ) 適切な子の選択 p->left = gentree(p->left, w); 再帰 else 子ポインタへの代入 再帰呼出 呼出 p->right = gentree(p->right, w); return p; p 第一引数そのまま } ポインタを返す (新ノードを作ったときはそれへのポインタ そうでないときは 受け取った第一引数 p を (いじらずそのまま) オウム返し)

23 分探索木のサーチ (再帰版) while (printf("search name -->"), scanf("%s",key)!=eof){ if ((p=search(root,key))!=null) p=search(root,key)) printf( %s printf("%s が見つかりました n,p->name); が見つかりました n",p->name); else printf("見つかりません n"); printf( 見つかりません n ); } key: Nancy Rolla p struct tnode *search(struct tnode *p,char *key) struct tnode *search(struct tnode *p,char *key) *p,char *key) { struct tnode *search(struct tnode (p: マチルダ) { (p: ローラ) (p: NULL) {if (p==null strcmp(key,p->name)==) if (p==null strcmp(key,p->name)==) if (p==null return p; strcmp(key,p->name)==) return p; return p; if (strcmp(key,p->name)<) if (strcmp(key,p->name)<) if (strcmp(key,p->name)<) return search(p->left,key); return search(p->left,key); elsereturn search(p->left,key); else else return search(p->right,key); return search(p->right,key); return search(p->right,key); } } } achilda p Rolla p: NULL

24 分探索木のトラバーサル (深さ優先) トラバーサル (traversal) 木の全てのノードを訪れるこ と (木の走査) (例 大学組織データ内からの教員捜し) 深さ優先探索 左向きにとにかく進んで 端に来たら つ前の親に戻って右に進む という行動を繰り返す 再帰的に記述すると 関数 treewalk(p)は 以下のよう な動作をすれば良い (p 起点ノードへのポインタ) void treewalk(struct tnode *p) { p が NULL なら戻る (終了条件) if (p!=null){ p の左の子を起点として再帰呼出 treewalk(p->left); printf("%s n",p->name); p での作業 (ノード内容表示) treewalk(p->right); p の右の子を起点として再帰呼出 } } 8

25 分探索木のトラバーサル (深さ優先) ノード内容表示の順序次第で 表示順序が変わる 行きがけ順 void treewalk(struct tnode *p) { if (p!=null){ printf("%s n",p->name); treewalk(p->left); treewalk(p->right); } } p NULL p achilda p p Emy p Rolla p Candy 画面表示 Lisa achilda Emy Candy Lisa Rolla 9

26 分探索木のトラバーサル (深さ優先) ノード内容表示の順序次第で 表示順序が変わる 通りがけ順 void treewalk(struct tnode *p) { if (p!=null){ treewalk(p->left); printf("%s n",p->name); treewalk(p->right); } } p NULL p achilda p p Emy p Rolla p Candy 画面表示 アルファベット順 Lisa Candy Emy Lisa achilda Rolla

27 レベルごとのトラバーサル (試験範囲外) 木のレベル (深さ) ごとに さらに同一レベルでは左から 右にノードをトラバーサルするには 配列 (TODOリスト) で実現 配列 q G BH A D CF E copy BH D CF E 配列 w G レベル終了時に配列 w が空なら終了 A レベル B C E D G レベル F H 教科書でこの配列を スタック と呼んでいるのは間違い レベル レベル

28 ヒープ ヒープ (heap 山 堆積) とは すべての親が必ずつの 子を持つ (最後の要素は左の子だけでも良い) 完全分木で どの親と子をとっても 親 子になっている木を言う 配列表現 ノードを深さごとに 左から順に配列に格 納する 9 ヒープにおいては添え字は でなく から始める 8 こうすると 子 s の親 p は p=s/ で求まる 例 /= (整数演算) 8 p.- 9

29 ヒープへのデータ追加 (上方移動) 既に存在するヒープへ新規データを追加することを考える その手順は以下の通りである () 新しいデータをヒープの最後の要素として格納する () その要素を子とする親のデータと比較し 親の方が大 きければ子と親を交換する () 次に その親を子とする親 (おじいちゃん) との間で 比較を行い 必要があれば交換 これを 子の位置が根ま で上がるか 親 子になるまで繰り返す 教科書 p. の図.を参照せよ この手順を上方移動 (shift up) という ソースコードは p..

30 ヒープへのデータ追加 (上方移動) () 新しいデータをヒープの最後の要素として格納する () その要素を子とする親のデータと比較し 親の方が大きければ子と親 を交換する () 次に その親を子とする親 (おじいちゃん) との間で比較を行い 必 要があれば交換 これを 子の位置が根まで上がるか 親 子になる まで繰り返す s= 9 p=

31 ヒープの作成 (下方移動) 上方移動では既存のヒープにデータを一つずつ追加することに よりヒープを作成したが 既存の全データをそのまま分木に 割り当ててから ヒープとして整えるという方法がある その 手順は以下の通り (教科書は分かりにくい) () 子を持つ最後の親 (データ数が n のとき n/) i から開始し 全ての親に対して逆順に (n/, n/-, n/-,, ) 以下の () () の手順を繰り返す () 親の番号を p とし 2つの子 (p, p+) のうちで小さい方を s とする (一番最後の親は 左側にしか子を持たない場合がある この場合は自動的に s = p とする.) () 子 s の値が 親 p 以上なら () のループで次へ () p と s の値を交換し 交換された子の方を親として (p = s s = p) () へ戻る

32 ヒープの作成 (下方移動) 図的に理解しよう () 子を持つ最後の親から開始してループ (最初は 9/ = から) () 親の番号を p とし p と p+ で小 さい方の子を s とする () s が p より大きいときは () ループで 次へ i= p= 8 s= () p と s を交換し p=s, s=p とする 8 9 s>n なら () ループで次へ s<=n なら () へ 8 () から () の手順を 下方移動 (shift down) と呼ぶ ソースコード p.

33 ヒープ ソート ヒープを用いたソーティングアルゴリズムがヒープ ソー トである 手順は大まかに以下の通り ()与えられた数列からヒープを作成する ()根ノードには最小値が来ているはずなので, これを取り外 す その代わり 最後のノード (データ数 n なら n番の要 素) を切り離して根ノードに持ってくる ()これにより残ったデータ (n-個) のヒープ条件が狂った ので 下方移動を使ってヒープの修正を行う. この場合 根ノードからの回の下方移動を行うだけでよい ()() に戻る 教科書 p.8 の図. を参照せよ 計算量のオーダは O (n log n) p.8-

34 ヒープ ソート (ソースコード) p.9 関数 swap() はつの配列要素の交換 main関数内 最初の whileループは初期ヒープの作成 データを入れるごとに 入れたデータを最後尾に格納した 上で 上方移動を使ってヒープを整える作業を繰り返して いる つめの whileループは データを取り出すごとのループ 最初にルート (番) と最後尾 (n番) を交換して 最後尾 をヒープから除外している (n--) 次のループは 視点 p を根に初期化して下方移動を回 行っている部分 p. では 初期ヒープ作成を下方移動で行っている 8

35 第章 グラフ リスト構造は ノード群を鎖状につないだもので 分岐は なかった 一方木構造は分岐はするが 分岐した枝同士は 分かれたまま これらをより一般化したものがグラフ (graph) である グラフでは ノード間の連結は任意であり ループを含む こともある 8 p.- 9

36 グラフとは 円で描いた部分はノード (node 節点 vertex 頂点ともい う) であり それを結んでいるのは エッジ (edge 辺 branch 枝) である ノードとはつながっているが とはつながっていない エッジ ノード 8

37 グラフとは グラフをデータとして表現するときに使われるのは隣接行 列 (adjacency matrix) である ノード i と j の間に接続 がある場合は ない場合は としておく 教科書ではノード番号はからとしている j 8 対角成分は 同じノードへの接続をあると するかどうかに関係する (この場合はなし としている) 8 i 8

38 グラフとは ここまでの例では グラフのエッジには向きはなかった このようなものを無向グラフ (undirected graph) という これに対して, 進める方向 のような向きを含んだグラ フを有向グラフ (directed graph) という この場合 隣 接行列は ノード i から j へのエッジに対して 要素 (i, j) は 要素 (j, i) は としておく (p. 図.) 8

39 深さ優先探索 グラフのノードにデータが記載されている場合 この中か ら特定のデータを探すとき グラフの全てのノードを巡る というアルゴリズムが必要となる その一つは 深さ優先探索 (depth first search, 縦型探索 とも呼ばれる) である ()始点を出発し ノード番号の若い順に進む位置を調べ い けるところ (エッジで連結されていてまだ訪問していない ノード) まで進む ()行き場所がなくなったら まだいける方向の残っている分 岐点まで戻り 再びいけるところまで進む ()行き場所が全てなくなったら終了 (来た道を戻る) p.-8

40 深さ優先探索 どのように探索が進むかを図で見てみよう () 始点を出発し ノード番号の若い順に進む位置を調べ いけるところ (エッジで連結されていてまだ訪問していないノード) まで進む () 行き場所がなくなったら まだいける方向の残っている分岐点まで戻 り 再びいけるところまで進む () 行き場所が全てなくなったら終了 (来た道を戻る) 8

41 深さ優先探索の再帰的解法 深さ優先探索を再帰 的に行う関数は右の 通り 未探索の行き先を順 番に探して 行ける ときは再帰呼び出し でそこに進む visit()を呼ぶと void visit(int i) { int j; } v[i]=; for (j=;j<=n;j++){ if (a[i][j]== && v[j]==){ printf("%d->%d ",i,j); visit(j); } } j= j= j= j= 8 8 j= j=

42 深さ優先探索 (ソースコード) 次元配列 a[][] によって隣接行列を記述 (初期化) これ がグラフの実体である 配列 v[n+] は 訪問済みフラグ を意味する これが となっているノードは未訪問 なら訪問済み main関数では訪問フラグの初期化の後 visit() を呼び 出しているだけ 関数 visit() は再帰的関数であり 引数 i は探索を開始 するノードの番号 要するに ノード i から先を探索せ よ という関数 visit() では まず起点ノード i の訪問済みフラグを立て る (にする) 次に他の全てのノード j を調べ ノード i とつながっており (a[i][j]==) 未訪問 (v[j]==) な らば, ノード j を起点として探索 (再帰呼出 visit(j))

43 深さ優先探索の応用 グラフ上の各ノードを起点として深さ優先探索を繰り返す 場合は 各探索の前に訪問済みフラグを下ろして置かなく てはならない p. 図. のように ノード群が分かれているグラフを 非連結グラフと呼ぶ これがどのように分かれているかを 調べるには 訪問済みフラグのリセットをせずに 各ノー ドを起点とする探索を繰り返せばよい 探索の起点となるノードが訪問済みの場合は次のノードへ 進む 訪問済みでないときは カウントをつ進める これにより カウント数 分かれている集団の数となる

44 幅優先探索 幅優先探索 (breadth first search 横型探索とも言う) で は これから進まなくてはならないノードのメモ を キューの中に保存し それを参照しながら探索を進める ()始点をキューに入れる ()キューからノードを取り出し そのノードに連結している 未訪問のノードを全てキューに入れておく ()キューが空なら終了 そうでないときは () へ これにより 始点から近いノードから順序よく探索が進め られる p.9-8

45 幅優先探索 ()始点をキューに入れる ()キューからノードを取り出し, 訪問済みとする. そのノー ドに連結している未訪問ノードを全てキューに入れておく ()キューが空なら終了 そうでないときは () へ ソースコード p.- 8 キュー 8 9

46 トポロジカル ソート グラフを見ると から仕事を始めたとき やができる ためには, が出来ていなければならないのと同時 に 右側では,, 8 が出来ていなければならない 教科書に誤植 つまり,,,, という系列と,,,, 8, とい う系列がある 従って の次に行いうる仕事 とでは どちらを先に行っても良い このように必ずしも順序を比 較できない場合がある順序関係を半順序関係 (partial order) という p.- 8

47 トポロジカル ソート 半順序関係が与えられたデータに対して 最初に行う仕事 から最後に行う仕事を列に並べることをトポロジカル ソート (topological sort) という どちらを先にやっても良い部分が含まれているので 解は つとは限らず どれかが得られればよい 8

48 トポロジカル ソート 有向グラフに対する深さ優先探索を繰り返し実行し 行き 着いたところから来た道を戻ろうとするときに そのノー ドを記録していけばよい 記録は 最後に行き着く場所 から順に行われるので逆 順 8 8

49 Euler の一筆書き 辺を消しながら深さ優先探索を行い, 出発点に戻った時に全ての経路が消えていれば, そのとき通った経路が求める経路である スタック v[n] ソースコード :p. p.8-

50 ネットワーク 各辺に重みが定義されているグラフを 重み付きグラフ あるいは ネットワーク (network) と呼ぶ 重みの意味は 例えば道路網については道路の長さであっ たり 水道網なら流量だったりである (p.9 図.) 8 データの実体は 重み行列 で 記述する e b a f d c g h 8 ( 無限大)

51 最短路問題 (Dijkstra のアルゴリズム) 解きたい問題 ノード a から h までの最短距離を求める 全てのノードの確定フラグを下ろし, 距離値を無限大で初期化 スタートノードの距離値を とする (), () を N 回繰り返す 距離値最小の未確定ノードの番号を p とし 確定フラグを立てる p につながる全ノードについて p から進んだときの距離値が現在の 距離値より小さくなるとき そのノードの距離値を更新する あるノードの距離値を更新するとき 距離値だけでなく この距離値に e なる場合 直前のノードはこれ と b いう 手前ノード情報 も記録する f 距離だけでなく経路も求まる () () () () a c p.-9 d g 9 h

52 最短路問題の例 障害物環境下での移動ロボットのナビゲーション コンフィギュレーション障害物の頂点をサブゴールとし, 可視グラフ (visibility graph) を構築, 最短路を探索 sub-goal obstacle start obstacle goal 移動ロボットのナビゲーションを主にやってるとこ : 城間研 configuration obstacle

53 講義のおわりに 本講義では, 知能システム工学科の趣旨に則って, メカと情報の融合分野を扱う上でのアルゴリズム データ構造を実践的に ( ソース コードをベースとして ) 解説した. 情報工学科における同名の講義とは異なり, 理論的な議論はほとんど行っておらず, 情報に興味のある学生にとっては不十分である. 一方, 組み込みシステムなど, ハードウェアに近いプログラミングでは, マイコンや電子回路など, 多くのハードウェアに関する知識が必要となる. それらについては, 各自が必要に応じてより深く勉強すること. 本講義は基礎の基礎しか扱っていない. 講義終了後もアルゴリズム データ構造に関する質問は随時受け付ける.

memo

memo 計数工学プログラミング演習 ( 第 6 回 ) 2016/05/24 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : 再帰呼び出し 2 分探索木 深さ優先探索 課題 : 2 分探索木を用いたソート 2 再帰呼び出し 関数が, 自分自身を呼び出すこと (recursive call, recursion) 再帰を使ってアルゴリズムを設計すると, 簡単になることが多い

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

Taro-2分探索木Ⅱ(公開版).jtd

Taro-2分探索木Ⅱ(公開版).jtd 2 分探索木 Ⅱ 0. 目次 5. 2 分探索木の操作 5. 1 要素の探索 5. 2 直前の要素の探索 5. 3 直後の要素の探索 5. 4 要素の削除 5. 5 問題 問題 1-1 - 5. 2 分探索木の操作 5. 1 要素の探索 要素 44 の探索 (1) 要素 と 44 を比較して 左部分木をたどる (2) 要素 33 と 44 を比較して 右部分木をたどる (3) 要素 44 を見つけた

More information

Microsoft PowerPoint - 05.pptx

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

More information

memo

memo 計数工学プログラミング演習 ( 第 6 回 ) 2017/05/16 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : 再帰呼び出し 2 分探索木 深さ優先探索 課題 : 2 分探索木を用いたソート 2 再帰呼び出し 関数が, 自分自身を呼び出すこと (recursive call, recursion) 再帰を使ってアルゴリズムを設計すると, 簡単になることが多い

More information

alg2015-6r3.ppt

alg2015-6r3.ppt 1 アルゴリズムとデータ 構造 第 6 回探索のためのデータ構造 (1) 補稿 : 木の巡回 ( なぞり ) 2 木の巡回 ( 第 5 回探索 (1) のスライド ) 木の巡回 * (traverse) とは 木のすべての節点を組織だった方法で訪問すること 深さ優先探索 (depth-first search) による木の巡回 *) 木の なぞり ともいう 2 3 1 3 4 1 4 5 7 10

More information

Microsoft Word - 13

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

More information

第2回

第2回 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 第 回基本データ構造 連結リストとその操作 -. リスト構造 データ部 と ポインタ部 で構成され ポインタをたどることによりデータを扱うことができる構造 -. 単方向リストとその操作 --. 単方向リスト 次のデータへのポインタを つだけ持っているデータ構造 ( データ部は 複数のデータを持っている場合もある ) データ部

More information

Taro-2分探索木Ⅰ(公開版).jtd

Taro-2分探索木Ⅰ(公開版).jtd 2 分探索木 Ⅰ 0. 目次 1. 2 分探索木とは 2. 2 分探索木の作成 3. 2 分探索木の走査 3. 1 前走査 3. 2 中走査 3. 3 問題 問題 1 問題 2 後走査 4. 2 分探索木の表示 - 1 - 1. 2 分探索木とは 木はいくつかの節点と節点同士を結ぶ辺から構成される 2 つの節点 u,v が直接辺で結ばれているとき 一方を親節点 他方を子節点という ある節点の親節点は高々

More information

始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル

始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル 概略設計書 作成者築山修治作成日 2012 年 10 月 1 日 概要 ( どのような入力に対して, どのような出力をするかの概要説明 ) * 木 T および質問点対の集合 P が与えられたとき, 各質問点対 p = (v,w) P の最下位共通先祖 ( すなわち木 T において点 v と w の共通の先祖 a で,a の真の子孫には v と w の共通の先祖が無いような点 ) を見出す関数である.

More information

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

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

More information

Taro-スタック(公開版).jtd

Taro-スタック(公開版).jtd 0. 目次 1. 1. 1 配列によるの実現 1. 2 再帰的なデータ構造によるの実現 1. 3 地図情報処理 1. 4 問題 問題 1 グラフ探索問題 - 1 - 1. は データの出し入れが一カ所で行われ 操作は追加と削除ができるデータ構造をいう 出入口 追加 削除 操作 最初 111 追加 111 222 追加 111 222 333 追加 111 222 333 444 追加 111 222

More information

PowerPoint Presentation

PowerPoint Presentation 幅優先探索アルゴリズム 復習 Javaでの実装 深さ優先探索 復習 Javaでの実装 1 探索アルゴリズムの一覧 問題を解決するための探索 幅優先探索 深さ優先探索 深さ制限探索 均一コスト探索 反復深化法 欲張り探索 山登り法 最良優先探索 2 Breadth-first search ( 幅優先探索 ) 探索アルゴリズムはノードやリンクからなる階層的なツリー構造で構成された状態空間を探索するアルゴリズムです

More information

Microsoft PowerPoint - kougi11.ppt

Microsoft PowerPoint - kougi11.ppt C プログラミング演習 中間まとめ 2 1 ソフトウエア開発の流れ 機能設計 外部仕様 ( プログラムの入力と出力の取り決め ) 構成設計 詳細設計 論理試験 内部データ構造や関数呼び出し方法などに関する取り決めソースプログラムの記述正しい入力データから正しい結果が得られるかテスト関数単位からテストをおこなう 耐性試験 異常な入力データに対して, 異常を検出できるかテスト異常終了することはないかテスト

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

Microsoft PowerPoint - ad11-09.pptx

Microsoft PowerPoint - ad11-09.pptx 無向グラフと有向グラフ 無向グラフ G=(V, E) 頂点集合 V 頂点の対を表す枝の集合 E e=(u,v) 頂点 u, v は枝 e の端点 f c 0 a 1 e b d 有向グラフ G=(V, E) 頂点集合 V 頂点の順序対を表す枝の集合 E e=(u,v) 頂点 uは枝 eの始点頂点 vは枝 eの終点 f c 0 a 1 e b d グラフのデータ構造 グラフ G=(V, E) を表現するデータ構造

More information

Microsoft PowerPoint - 06.pptx

Microsoft PowerPoint - 06.pptx アルゴリズムとデータ構造第 6 回 : 探索問題に対応するデータ構造 (2) 担当 : 上原隆平 (uehara) 2015/04/22 内容 スタック (stack): 最後に追加されたデータが最初に取り出される 待ち行列 / キュー (queue): 最初に追加されたデータが最初に取り出される ヒープ (heap): 蓄えられたデータのうち小さいものから順に取り出される 配列による実装 連結リストによる実装

More information

データ構造

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

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

PowerPoint Presentation

PowerPoint Presentation 最適化手法 第 回 工学部計数工学科 定兼邦彦 http://researchmap.jp/sada/resources/ 前回の補足 グラフのある点の隣接点をリストで表現すると説明したが, 単に隣接点の集合を持っていると思ってよい. 互いに素な集合のデータ構造でも, 単なる集合と思ってよい. 8 3 4 3 3 4 3 4 E v 重み 3 8 3 4 4 3 {{,},{3,8}} {{3,},{4,}}

More information

人工知能入門

人工知能入門 藤田悟 黄潤和 探索とは 探索問題 探索解の性質 探索空間の構造 探索木 探索グラフ 探索順序 深さ優先探索 幅優先探索 探索プログラムの作成 バックトラック 深さ優先探索 幅優先探索 n 個の ueen を n n のマスの中に 縦横斜めに重ならないように配置する 簡単化のために 4-ueen を考える 正解 全状態の探索プログラム 全ての最終状態を生成した後に 最終状態が解であるかどうかを判定する

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 4 回再帰的構造体 前回の出席確認演習 #include int main() { FILE *fp; int c, linecount, length, maxlength; fp=fopen("/usr/share/dict/words","r"); if (fp == NULL) return 1; linecount=0; length=0;

More information

memo

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

More information

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

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

More information

Microsoft PowerPoint - 7.pptx

Microsoft PowerPoint - 7.pptx 7. 木構造 7-1. データ構造としての木 グラフ理論での木の定義 根付き木 7-2.2 分探索木 7-3. 高度な木 ( 平衡木 ) AVL 木 B 木 1 7-1 1. データ構造としての木 2 木構造 木構造を表すデータ構造の一つとしてヒープがある しかし ヒープでは 配列を用いプではるため 要素数で木の形状が一通りに決定してしまった ここでは 再帰的なデータ構造を用いることにより より柔軟な木構造が構築可能なより柔軟な木構造が構築可能なことを見ていく

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

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

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

More information

Microsoft PowerPoint - DA2_2018.pptx

Microsoft PowerPoint - DA2_2018.pptx データ構造とアルゴリズム IⅠ 第 7 回幅優先 / 深さ優先探索 / トポロジカルソート. 基本的グラフアルゴリズム 無向グラフ 個の頂点と7 本の辺からなる無向グラフ 隣接リスト 各頂点に関して, 隣接する ( 直接, 辺で結ばれた ) 頂点集合をリストで表現 無向グラフ G=(V,E),V は頂点集合,E は辺集合.E の要素は頂点のペア {u,} によって表される.{u, } と {, u}

More information

Microsoft PowerPoint - exp2-02_intro.ppt [互換モード]

Microsoft PowerPoint - exp2-02_intro.ppt [互換モード] 情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ 0. プログラム書ける? 講義を聴いているだけで OK? 言語の要素技術を覚えれば OK? 目的のプログラム? 要素技術 データ型 配列 文字列 関数 オブジェクト クラス ポインタ 2 0.

More information

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

Microsoft PowerPoint - algo ppt [互換モード] 平衡木 アルゴリズム概論 - 探索 (2)- 安本慶一 yasumoto[at]is.naist.jp 二分探索木 高さがデータを挿入 削除する順番による 挿入 削除は平均 O(log n) だが, 最悪 O(n) 木の高さをできるだけ低く保ちたい 平衡木 (balanced tree) データを更新する際に形を変形して高さが log 2 n 程度に収まるようにした木 木の変形に要する時間を log

More information

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

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

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

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

Microsoft PowerPoint - DA2_2019.pptx

Microsoft PowerPoint - DA2_2019.pptx Johnon のアルゴリズム データ構造とアルゴリズム IⅠ 第 回最大フロー 疎なグラフ, 例えば E O( V lg V ) が仮定できる場合に向いている 隣接リスト表現を仮定する. 実行時間は O( V lg V + V E ). 上記の仮定の下で,Floyd-Warhall アルゴリズムよりも漸近的に高速 Johnon のアルゴリズム : アイデア (I) 辺重みが全部非負なら,Dikra

More information

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

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

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 4 回再帰的構造体 プログラミングを 余談 : 教えることの難しさ 丁寧に説明しないと分かってもらえない 説明すると 小難しくなる学生が目指すべきところプログラム例を説明されて理解できる違うやり方でも良いので自力で解決できる おっけー 動けば良い という意識でプログラミング 正しく動くことのチェックは必要 解答例と自分のやり方との比較が勉強になる 今日のお題 再帰的構造体

More information

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

Microsoft PowerPoint - 06graph3.ppt [互換モード] I118 グラフとオートマトン理論 Graphs and Automata 担当 : 上原隆平 (Ryuhei UEHARA) uehara@jaist.ac.jp http://www.jaist.ac.jp/~uehara/ 1/20 6.14 グラフにおける探索木 (Search Tree in a Graph) グラフG=(V,E) における探索アルゴリズム : 1. Q:={v { 0 }

More information

Microsoft Word - no12.doc

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

More information

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

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

More information

program7app.ppt

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

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

PowerPoint プレゼンテーション

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

More information

離散数学

離散数学 離散数学 グラフ探索アルゴリズム 落合秀也 今日の内容 グラフの連結性 の判定 幅優先探索 幅優先探索の実現方法 深さ優先探索 深さ優先探索の実現方法 木の構造 探索木 パトリシア トライ 2 連結性の判定問題を考える グラフ G(V,E) が与えられたとき G が連結かどうか を判定したい 小さいグラフなら 紙に書いてみればよい 一般には簡単ではない 大きいグラフの場合 コンピュータに判断させる場合

More information

情報処理Ⅰ

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

More information

Microsoft PowerPoint - DA2_2017.pptx

Microsoft PowerPoint - DA2_2017.pptx 1// 小テスト内容 データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (I) 1 1 第 章の構成. 単一始点最短路問題 単一始点最短路問題とは 単一始点最短路問題の考え方 単一始点最短路問題を解くつのアルゴリズム ベルマン フォードのアルゴリズム トポロジカル ソートによる解法 ダイクストラのアルゴリズム 1 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

プログラミング方法論 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

memo

memo 計数工学プログラミング演習 ( 第 3 回 ) 2016/04/26 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 内容 ポインタ malloc 構造体 2 ポインタ あるメモリ領域 ( アドレス ) を代入できる変数 型は一致している必要がある 定義時には値は不定 ( 何も指していない ) 実際にはどこかのメモリを指しているので, #include

More information

Microsoft PowerPoint - DA2_2018.pptx

Microsoft PowerPoint - DA2_2018.pptx 1//1 データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (I). 単一始点最短路問題 第 章の構成 単一始点最短路問題とは 単一始点最短路問題の考え方 単一始点最短路問題を解くつのアルゴリズム ベルマン フォードのアルゴリズム トポロジカル ソートによる解法 ダイクストラのアルゴリズム 単一始点最短路問題とは 単一始点最短路問題とは 前提 : 重み付き有向グラフ 特定の開始頂点 から任意の頂点

More information

Microsoft PowerPoint - mp13-07.pptx

Microsoft PowerPoint - mp13-07.pptx 数理計画法 ( 数理最適化 ) 第 7 回 ネットワーク最適化 最大流問題と増加路アルゴリズム 担当 : 塩浦昭義 ( 情報科学研究科准教授 ) hiour@di.i.ohoku.c.jp ネットワーク最適化問題 ( 無向, 有向 ) グラフ 頂点 (verex, 接点, 点 ) が枝 (edge, 辺, 線 ) で結ばれたもの ネットワーク 頂点や枝に数値データ ( 距離, コストなど ) が付加されたもの

More information

グラフの探索 JAVA での実装

グラフの探索 JAVA での実装 グラフの探索 JAVA での実装 二つの探索手法 深さ優先探索 :DFS (Depth-First Search) 幅優先探索 :BFS (Breadth-First Search) 共通部分 元のグラフを指定して 極大木を得る 探索アルゴリズムの利用の観点から 利用する側からみると 取り替えられる部品 どちらの方法が良いかはグラフに依存 操作性が同じでなければ 共通のクラスの派生で作ると便利 共通化を考える

More information

オートマトンと言語

オートマトンと言語 オートマトンと言語 4 回目 5 月 2 日 ( 水 ) 3 章 ( グラフ ) の続き 授業資料 http://ir.cs.yamanashi.ac.jp/~ysuzuki/public/automaton/ 授業の予定 ( 中間試験まで ) 回数月日 内容 4 月 日オートマトンとは, オリエンテーション 2 4 月 8 日 2 章 ( 数式の記法, スタック,BNF) 3 4 月 25 日 2

More information

プログラミング実習I

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

More information

Prog1_10th

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

More information

Microsoft PowerPoint - lec10.ppt

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

More information

Microsoft Word - no205.docx

Microsoft Word - no205.docx 3 応用 3.1 連結リスト 前回 先頭に追加する例を扱いました しかし start が指す node を変更することから 関数 の戻り値として作成しました 今回は ポインタ変数 start の値を関数で変更できるように ポイ ンタ変数へのポインタを利用します 先頭を削除するものと 最後を削除する関数を追加します ex25.c /* リストの追加と削除 */ typedef struct node

More information

第2回

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

More information

第12回:木構造

第12回:木構造 アルゴリズムとデータ構造 講義スライド 4 スタック キュー リスト 茨城大学工学部知能システム工学科井上康介 E2 棟 801 号室 第5章 データ構造 授業の最初で述べたとおり 大量 複雑なデータを扱う上 では データを構造化 組織化する必要がある どのようなデータ構造 (data structure) を採用するかに よって 問題解決のアルゴリズムも異なってくる つまり アルゴリズムとデータ構造とは密接な関係にあり

More information

Microsoft Word - no15.docx

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

More information

Microsoft Word - 12

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

More information

Microsoft PowerPoint - mp11-06.pptx

Microsoft PowerPoint - mp11-06.pptx 数理計画法第 6 回 塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 第 5 章組合せ計画 5.2 分枝限定法 組合せ計画問題 組合せ計画問題とは : 有限個の もの の組合せの中から, 目的関数を最小または最大にする組合せを見つける問題 例 1: 整数計画問題全般

More information

二分木の実装

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

More information

Microsoft Word - no202.docx

Microsoft Word - no202.docx 1.4 ポインタと配列 ポインタ変数は前回説明したように 値の入っているアドレスを示す変数です では 配列はどの ようにメモリ上に格納されるか調べてみましょう ex07.c /* ポインタと配列の関係 */ int a[3]={1, 2, 3; /* int 型の大きさ 3 の配列として宣言 */ int *i; /* int 型へのポインタとして宣言 */ double x[3] = {1.0,

More information

memo

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

More information

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

Taro-再帰関数Ⅱ(公開版).jtd 0. 目次 6. 2 項係数 7. 二分探索 8. 最大値探索 9. 集合 {1,2,,n} 上の部分集合生成 - 1 - 6. 2 項係数 再帰的定義 2 項係数 c(n,r) は つぎのように 定義される c(n,r) = c(n-1,r) + c(n-1,r-1) (n 2,1 r n-1) = 1 (n 0, r=0 ) = 1 (n 1, r=n ) c(n,r) 0 1 2 3 4 5

More information

離散数学

離散数学 離散数学 最小全域木と最大流問題 落合秀也 今日の内容 最小全域木 プリムのアルゴリズム 最大流問題 フォード ファルカーソンのアルゴリズム 今日の内容 最小全域木 プリムのアルゴリズム 最大流問題 フォード ファルカーソンのアルゴリズム 最小全域木を考える Minimum Spanning Tree Problem ラベル付 ( 重み付 ) グラフ G(V, E) が与えられたとき ラベルの和が最小となる全域木を作りたい

More information

Microsoft Word - no11.docx

Microsoft Word - no11.docx 3. 関数 3.1 関数関数は数学の関数と同じようなイメージを持つと良いでしょう 例えば三角関数の様に一つの実数値 ( 角度 ) から値を求めますし 対数関数の様に二つの値から一つの値を出すものもあるでしょう これをイメージしてもらえば結構です つまり 何らかの値を渡し それをもとに何かの作業や計算を行い その結果を返すのが関数です C 言語の関数も基本は同じです 0 cos 1 cos(0) =

More information

Microsoft PowerPoint - DA2_2017.pptx

Microsoft PowerPoint - DA2_2017.pptx // データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (II)/ 全点対最短路 トポロジカル ソート順による緩和 トポロジカル ソート順に緩和 閉路のない有向グラフ限定 閉路がないならトポロジカル ソート順に緩和するのがベルマン フォードより速い Θ(V + E) 方針 グラフをトポロジカル ソートして頂点に線形順序を与える ソート順に頂点を選び, その頂点の出辺を緩和する 各頂点は一回だけ選択される

More information

離散数学

離散数学 離散数学 最短経路問題 落合秀也 その前に 前回の話 深さ優先探索アルゴリズム 開始点 から深さ優先探索を行うアルゴリズム S.pu() Wl S not mpty v := S.pop() I F[v] = l Tn, F[v] := tru For no u n A[v] S.pu(u) EnFor EnI EnWl (*) 厳密には初期化処理が必要だが省略している k 時間計算量 :O(n+m)

More information

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

Microsoft PowerPoint - handout07.ppt [互換モード] Outline プログラミング演習第 7 回構造体 on 2012.12.06 電気通信大学情報理工学部知能機械工学科長井隆行 今日の主眼 構造体 構造体の配列 構造体とポインタ 演習課題 2 今日の主眼 配列を使うと 複数の ( 異なる型を含む ) データを扱いたい 例えば 成績データの管理 複数のデータを扱う 配列を使う! 名前学籍番号点数 ( 英語 ) 点数 ( 数学 ) Aomori 1 59.4

More information

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

Microsoft PowerPoint - ca ppt [互換モード] 大阪電気通信大学情報通信工学部光システム工学科 2 年次配当科目 コンピュータアルゴリズム 良いアルゴリズムとは 第 2 講 : 平成 20 年 10 月 10 日 ( 金 ) 4 限 E252 教室 中村嘉隆 ( なかむらよしたか ) 奈良先端科学技術大学院大学助教 y-nakamr@is.naist.jp http://narayama.naist.jp/~y-nakamr/ 第 1 講の復習

More information

memo

memo 計数工学プログラミング演習 ( 第 5 回 ) 2017/05/09 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 内容 文字列 双方向リスト ハッシュ 2 文字列 文字列は char の配列 char name[] = ABC ; name は ABC を格納するのに十分な長さの配列 長さは, 文字列の長さ + 1 ( 終端記号用 ) char name[4]

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

関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (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

Microsoft Word - NonGenTree.doc

Microsoft Word - NonGenTree.doc ジェネリクスとコンパレータを使用しない 2 分探索木のプログラム例 BinTreeNG.java: 2 分探索木のクラス BinTreeNG BinTreeTesterNG.java: BinTreeNG を利用するプログラム例 === BinTreeNG.java =========================================================================

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

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング初級 第 7 回 2017 年 5 月 29 日 配列 ( 復習 )~ 文字列 1 配列とは 2 配列 : 複数の変数をグループとしてまとめて扱うもの 配列 変数 int data[10]; 整数型の配列 同種のデータ型を連続して確保したものを配列とよぶ = 整数がそれぞれにひとつずつ入る箱を 10 個用意したようなもの int data; 整数型の変数 = 整数がひとつ入る dataという名前の箱を用意したようなもの

More information

Microsoft PowerPoint - 5Chap15.ppt

Microsoft PowerPoint - 5Chap15.ppt 第 15 章文字列処理 今日のポイント 15.1 文字列処理の基本 strcpy strcat strlen strchr などの使い方をマスターする strcpy はなんて読むの? 普通はストリングコピー C のキーワードの読み方に悩んだら下記サイトを参考 ( 前回紹介とは別サイト ) http://www.okakogi.go.jp/people/miwa/program/c_lang/c_furoku.html

More information

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

Taro-リストⅢ(公開版).jtd リスト Ⅲ 0. 目次 2. 基本的な操作 2. 1 リストから要素の削除 2. 2 リストの複写 2. 3 リストの連結 2. 4 問題 問題 1 問題 2-1 - 2. 基本的な操作 2. 1 リストから要素の削除 まず 一般的な処理を書き つぎに 特別な処理を書く 一般的な処理は 処理 1 : リスト中に 削除するデータを見つけ 削除する場合への対応 特別な処理は 処理 2 : 先頭のデータを削除する場合への対応

More information

プログラミング基礎

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

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

関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (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

メソッドのまとめ

メソッドのまとめ 配列 (2) 2 次元配列, String http://jv2005.cis.k.hosei.c.jp/ 授業の前に自己点検 配列変数に格納される配列の ID と配列の実体の区別ができていますか 配列変数の宣言と配列の実体の生成の区別ができていますか メソッドの引数に配列が渡されるとき 実際に渡されるものは何ですか このことの重要な帰結は何ですか 引数の値渡しと参照渡しということばを例を挙げて説明できますか

More information

cp-7. 配列

cp-7. 配列 cp-7. 配列 (C プログラムの書き方を, パソコン演習で学ぶシリーズ ) https://www.kkaneko.jp/cc/adp/index.html 金子邦彦 1 本日の内容 例題 1. 月の日数配列とは. 配列の宣言. 配列の添え字. 例題 2. ベクトルの内積例題 3. 合計点と平均点例題 4. 棒グラフを描く配列と繰り返し計算の関係例題 5. 行列の和 2 次元配列 2 今日の到達目標

More information

PowerPoint Presentation

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

More information

Microsoft Word - 中間試験 その1_解答例.doc

Microsoft Word - 中間試験 その1_解答例.doc 問題 1.C 言語 情報技術 Ⅱ 前半中間試験 次の宣言をしている時 以下の問いに答えよ unsigned char moji_1; struct Kouzou { unsigned char code; unsigned char str[10]; }; struct Kouzou mk[3]; 明星大学情報学科 3 年後期 情報技術 Ⅱ 中間試験その 1 Page 1 1-1. 各値を求めよ (1)sizeof(

More information

関数の中で宣言された変数の有効範囲はその関数の中だけです さっきの rectangle _s で宣言されている変数 s は他の関数では使用できません ( 別の関数で同じ名前の変数を宣言することはできますが 全く別の変数として扱われます このように ある関数の中で宣言されている変数のことをその関数の

関数の中で宣言された変数の有効範囲はその関数の中だけです さっきの rectangle _s で宣言されている変数 s は他の関数では使用できません ( 別の関数で同じ名前の変数を宣言することはできますが 全く別の変数として扱われます このように ある関数の中で宣言されている変数のことをその関数の ソフトゼミ A 第 6 回関数 はじめに今まで printf や scanf など 予め用意されていた関数を使ってきました これら標準で用意されている関数を作ることは ( 特に入出力系は ) とても難しいのですが 関数は自作することができます というわけで 今回は自分で関数を定義して使っていく方法について学びましょう 関数とは C 言語での 関数 は 処理の途中で呼び出すことによって 定義されている

More information

プログラミング入門1

プログラミング入門1 プログラミング入門 1 第 8 回メソッド (2) 授業開始前に自己点検 前回までの必須課題はすべてできていますか 前回までの学習項目であいまいな所はありませんか 理解できたかどうかは自分自身の基準をもとう Java 1 第 8 回 2 前回のテーマ メソッドとは いくつかの命令の列を束ねて 一つの命令として扱えるようにしたもの 今回学ぶメソッドの役割は その他のプログラミング言語では関数またはサブルーチンと呼ばれることがある

More information

LIFO(last in first out, ) 1 FIFO(first in first out, ) 2 2 PUSH POP : 1

LIFO(last in first out, ) 1 FIFO(first in first out, ) 2 2 PUSH POP : 1 2007 7 17 2 1 1.1 LIFO(last in first out, ) 1 FIFO(first in first out, ) 2 2 PUSH POP 2 2 5 5 5 1: 1 2 データの追加 データの取り出し 5 2 5 2 5 2: 1.2 [1] pp.199 217 2 (binary tree) 2 2.1 (three: ) ( ) 秋田高専 校長 準学士課程学生

More information

4 月 東京都立蔵前工業高等学校平成 30 年度教科 ( 工業 ) 科目 ( プログラミング技術 ) 年間授業計画 教科 :( 工業 ) 科目 :( プログラミング技術 ) 単位数 : 2 単位 対象学年組 :( 第 3 学年電気科 ) 教科担当者 :( 高橋寛 三枝明夫 ) 使用教科書 :( プロ

4 月 東京都立蔵前工業高等学校平成 30 年度教科 ( 工業 ) 科目 ( プログラミング技術 ) 年間授業計画 教科 :( 工業 ) 科目 :( プログラミング技術 ) 単位数 : 2 単位 対象学年組 :( 第 3 学年電気科 ) 教科担当者 :( 高橋寛 三枝明夫 ) 使用教科書 :( プロ 4 東京都立蔵前工業高等学校平成 30 年度教科 ( 工業 ) 科目 ( プログラミング技術 ) 年間授業計画 教科 :( 工業 ) 科目 :( プログラミング技術 ) 単位数 : 2 単位 対象学年組 :( 第 3 学年電気科 ) 教科担当者 :( 高橋寛 三枝明夫 ) 使用教科書 :( プログラミング技術 工業 333 実教出版 ) 共通 : 科目 プログラミング技術 のオリエンテーション プログラミング技術は

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

関数の動作 / printhw(); 7 printf(" n"); printhw(); printf("############ n"); 4 printhw(); 5 関数の作り方 ( 関数名 ) 戻り値 ( 後述 ) void である. 関数名 (

関数の動作 / printhw(); 7 printf( n); printhw(); printf(############ n); 4 printhw(); 5 関数の作り方 ( 関数名 ) 戻り値 ( 後述 ) void である. 関数名 ( 概要 プログラミング 関数 http://www.ns.kogakuin.ac.jp/~ct40/progc/ A- 関数の作り方を学ぶ 関数名, 引数, 戻り値 プログラミング で最も重要な事項 関数 プログラミング で最も重要な事項 制御 (for, if) プログラミング で最も重要な事項 ポインタ A- 関数名 引数 戻り値 E- E-4 関数の概要 0/ 関数とは, 複数の処理をひとまとめにしたもの.

More information

コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n

コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n を入力してもらい その後 1 から n までの全ての整数の合計 sum を計算し 最後にその sum

More information

(2) 構造体変数の宣言 文法は次のとおり. struct 構造体タグ名構造体変数名 ; (1) と (2) は同時に行える. struct 構造体タグ名 { データ型変数 1; データ型変数 2;... 構造体変数名 ; 例 : struct STUDENT{ stdata; int id; do

(2) 構造体変数の宣言 文法は次のとおり. struct 構造体タグ名構造体変数名 ; (1) と (2) は同時に行える. struct 構造体タグ名 { データ型変数 1; データ型変数 2;... 構造体変数名 ; 例 : struct STUDENT{ stdata; int id; do 8 構造体と供用体 ( 教科書 P.71) 構造体は様々なデータ型,int 型,float 型や char 型などが混在したデータを一つのまとまり, 単位として扱える.( 配列は一つのデータ型しか扱えない.) 構造体は柔軟なデータ構造を扱えるので, プログラムを効率よく開発できる. つまり構造体を使用すると, コード量を抑え, バグを少なくし, 開発時間を短くし, 簡潔なプログラムが作れる. 共用体は,

More information

Microsoft Word - 3new.doc

Microsoft Word - 3new.doc プログラミング演習 II 講義資料 3 ポインタ I - ポインタの基礎 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

CプログラミングI

CプログラミングI C プログラミング I Swap 関数を作る Stack データ構造のための準備 整数変数 x と y の値を取り替える関数 swap を作る 最初の試み : swap-01.c #include void swap(int a, int b) { int tmp; tmp = a; a = b; b = tmp; int main(void) { int x=10, y=30;

More information

プログラミング入門1

プログラミング入門1 プログラミング入門 1 第 9 回 メソッド (3) 授業の前に自己点検 以下の質問に答えられますか? メソッドの宣言とは 起動とは何ですか メソッドの宣言はどのように書きますか メソッドの宣言はどこに置きますか メソッドの起動はどのようにしますか メソッドの仮引数 実引数 戻り値とは何ですか メソッドの起動にあたって実引数はどのようにして仮引数に渡されますか 戻り値はどのように利用しますか 変数のスコープとは何ですか

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