5after探索( )

Size: px
Start display at page:

Download "5after探索( )"

Transcription

1 探索アルゴリズム

2 探索とは? キー 一致するものを探す レコード フィールド

3 START n=10, i =0, target=54 i : n a[i] : target i++ < = 線形探索アルゴリズム (1) 前提 : 配列 a に n 個のデータが保存 処理 :target と同じデータが蓄えられている配列要素の添え字を返し, ない場合は -1 を返すフローチャートを記せ return i return -1 END

4 番人による少し早い線形探索 key data table[0] table[1] tabel[2] table[3] : : table[n-1] table[n] : : table[199] 75 福崎慎也 101 渡邊滋之 17 大野綾子 28 川島祐毅 : : : : 64 仲野弘幸 87 番人 (sentinel)

5 番人を利用した線形探索アルゴリズム START target = 54, i =0, a[n] = target a[i] : target i=i+1 = ループ毎に i と n-1 の比較が不要 i : N < return i return -1 END

6 2 つの線形探索アルゴリズムの比較 START n=10, target = 54, i =0 i : N < a[i] : target i=i+1 番人なし 前処理 = return i return -1 START n=10, target = 54, i =0, a[n] = target a[i] : target i=i+1 i : N < = 番人あり 前処理 return i return -1 END END

7 二分探索法 ( バイナリサーチ ) 探すキーの値は 14 とする low middle high a[0]=1 a[1]=3 a[2]=4 a[3]=8 a[4]=13 a[5]=14 a[6]=18 a[7]=20 a[8]=21 a[9]=25 <14 low =middle+1 middle high a[0]=1 a[1]=3 a[2]=4 a[3]=8 a[4]=13 a[5]=14 a[6]=18 a[7]=20 a[8]=21 a[9]=25 >14 a[0]=1 a[1]=3 a[2]=4 a[3]=8 a[4]=13 low, middle a[5]=14 =14 high a[6]=18 =middle-1 a[7]=20 a[8]=21 a[9]=25 探索範囲

8 二分探索アルゴリズム ( 半分ずつ捨てるのがポイント ) サイズnの配列 key(0~n-1) においてsを探す 1 first=0, last=n-1 2 mid = (first+last)/2 3 key(mid)=s -> Found key(mid)<s -> first=mid+1 Goto 2 key(mid)>s -> last=mid-1 Goto 2 上記アルゴリズムの問題点は? 完成させよ

9 線形探索の計算量 ( 比較の回数 ) は最良 1 最悪 n 平均 n/2 データ数 n に対して O(n) 二分探索の計算量 ( 比較の回数 ) は 2 k-1 n<2 k のとき k 回つまり データ数 n に対して約 O(log 2 n)

10 線形探索の計算量は O(n) 二分探索の計算量は O(log2 n) n=1,000 だったら? n=1,000 log 2 n= 約 10 ( なぜなら 2 10 =1,024) 100 倍違う! 定数係数が少しくらい違ったって 勝負は明らか!

11 ビッグ O のグラフ化 N O(2 n ) O(N 2 ) O(NlogN) O(N) O(logN) O(1)

12 O(2 n ) O(N 2 ) O(NlogN) ビッグオーの グラフ化 O(N) O(logN) O(1)

13 データの登録も考えると 登録 (n 要素当り ) 探索 (1 回当り ) 線形探索 O(n) O(n) 二分探索 O(n 2 ) O(log n) クイックソートで O(n log n)

14 登録 1 回あたりの探索回数を S とすると 線形探索 O(n)+S O(n) 二分探索 O(n log n)+s O(log n) n<<s でないと 二分探索は有利にならない! 頻繁にデータ集合が変わるような応用には二分探索は適さない

15 ハッシュ法

16 ハッシュ法 ハッシング (hashing) ともいう hash: 切りきざむ 挿入 探索 削除が O(1) でできるつまり データの個数 n に依存しない理想の探索技法!?

17 学生番号から氏名などを求めたい 2003 年度に入学した学生だけを考えると ~ 配列の 0 番目から 100 番目に氏名を格納 ( 学生番号下 3 桁 -1) 番目の配列要素を見ればよい direct access という でも 一般にキーはこのように順序よく並んでいない

18 英和辞書 5 万語の英和辞書の全体をメモリにのせて使いたい 各単語のインデクス番号が分かれば,O(1) である単語の意味を知ることができる インデクス番号 ,000 内容 hash: 切り刻む どうすれば各単語のインデクス番号が分かるか?

19 語を数に変換する ASCII( アスキー ) コード 大文字, 小文字, 数字, 記号などを 0 から 255 までの数で表現 a:97, b:98,, z:122 大文字, 数字, 記号などを使わないとしたら スペースを 0 として,a:1, b:2, c:3,, z:26 の 27 文字で表現できる

20 語を数に変換する方法 1: 単語の各文字に対応する数の総和をインデクス番号とする cats = = 43 Dic[43] = cat: ネコ, 猫科の動物 ここで, 単語の最大文字数を 10 とすると, 辞書の一番最後の文字は, ( 理論的には ) zzzzzzzzzz(z が 10 個 ) = 26 X 10 = ,000( 単語あるとすれば ) 260 = 192 サイズ 260 の配列を準備すれば 1 つの配列要素に 192 語が該当する 例えば 単語の各文字に対応する数の総和が cat と同じ 43 になる単語 was( ), give( ), tend( ),.

21 語を数に変換する方法 2: 桁位置を利用する ( べき乗化 ) 数値の場合は0から9の10 種類 (10 進数 ) 各桁は10のべき乗 配列今回の前提では 1 要素あたり, スペース 1バイトとすると,aからzの27 種類, (27 進数 ) 約 190TB のメモリが必要!! 各桁は 27 のべき乗 1TB = 1024 * 1024 * 1024 * 1024 = cats = 3x x x x27 0 = 60,337 zzzzzzzzzz = 26x x x27 0 = 205,891,132,094,648 1,099,511,627,776 ( 約 1 兆バイト ) 200 兆以上!!

22 語を数に変換する方法 2: 桁位置を利用する ( べき乗化 ) 単語ではない fira firb firc fird fire firf firg 実在する単語

23 ハッシュ法 巨大な範囲の数を実用的なサイズの配列の添え字 ( インデクス ) に変換 簡単な方法としては, モジュロ演算子 (%) を使う %n は 0 から n- 1 までの数を作りだす ( 値域 :0~3) 23 % 4 = % 4 = 0 38 % 4 = 2 配列のインデクス = 巨大な数 % 配列サイズ

24 ハッシュ関数 (hash function) キーの値 x の集合添字 ( ハッシュ値 ) h(x) の集合 h(x) 0,1,2,, 大きな値域の数を小さな値域の数へとハッシュ ( 切り刻む ) する 文字列を一定範囲の整数に変換すること

25 ハッシュ関数の例 int hash(char *s) { int i = 0; while (*s) i += *s++; return i % 100} a:97 z:122 アスキーコードの総和を 100 で割った余りを配列添字とする a 97 b 98 c 99 d 100 e 101 f 102 g 103 h 104 i 105 j 106 k 107 l 108 m 109 n 110 o 111 p 112 q 113 r 114 s 115 t 116 u 117 v 118 w 119 x 120 y 121 z 122 この関数で求まるハッシュ値の例 文字列ハッシュ値 one 22 two 46 three four five six seven eight nine ten

26 ハッシュ表 ( テーブル ) ハッシュ値の例文字列ハッシュ値 one 22 two 46 three four five six seven eight nine ten ハッシュ関数を使ってデータを挿入した配列 five 27 ten eight..

27 ハッシュ (1) 問題 1: 以下のハッシュ関数を用いて 表の各文字列に対応するハッシュ値を求めよ ハッシュ関数 int hash(char *s) { int i = 0; while (*s) i += *s++; return i % 11} アルファベットに対応する数値 a:1, b:2, c:3, d:4, e:5, f:6, g:7, h:8, i:9, j:10, k:11, l:12, m:13, n:14,o:15, p:16, q:17, r:18, s:19, t:20, u:21, v:22, w:23, x:24, y:25, z:26 例 :yamaguti = ( ) % 11 = 2 文字列 fukuzaki watanabe oono kawashima nakano miura ハッシュ値

28 異なるキーが同じハッシュ値に写像されたら どうするか? 衝突の処理大きく分けて l チェイン法 l オープンアドレス法

29 チェイン法 ハッシュ表の同じ場所に写像されたデータを連結リストにつなぐ ハッシュ表は連結リストの先頭を指すポインタの配列

30 ハッシュ表 A C B 4 D E F G H J I

31 オープンアドレス法 ある一定の方法で, 空セルを探して, そこに新たな項目を挿入する方法 1 線形探査 (linear probing) 2 平方探査 (quadratic probing) 3 ダブルハッシュ (double hashing)

32 ハッシュ表 h(x)=h 0 (x) h 1 (x) h 2 (x) h 3 (x) オープンアドレス法は ハッシュ表の中で仮想的な連結リストを作るようなものただし 次の要素はポインタでなく 再ハッシュ関数によって決まる

33 オープンアドレス法 : 線形探査 配列を単純にシーケンシャルに辿って空きセルを探すやり方 0 1 nine = = 426 ハッシュ値 = 426%100 =26 衝突 衝突 OK.. 26 five 27 ten 28 nine 29 eight..

34 オープンアドレス法 : 線形探査 (2) 再ハッシュ (rehash) k 回目にアクセスする場所 : h k (x) x はキー k=0,1,2,,b-1 最も簡単な再ハッシュ関数は h k x = h x + k % B h x : 最初のハッシュ関数 B: ハッシュ表配列の大きさ

35 オープンアドレス法 : 線形探査の問題点 この状態でさらにハッシュ値が 26 のキーを挿入する場合データが連続してしまい, 効率が落ちる クラスター化 five 27 ten 28 nine 29 eight 30

36 オープンアドレス法 : 平方探査 線形探査のように, 隣接するセルに挿入してい くとクラスターができやすいので, もっと離れた 場所に挿入しようというやり方 h k x = h x + k 2 % B h x : 最初のハッシュ関数 B: ハッシュ表配列の大きさ 注意点 : 配列のサイズを素数にしなければ同じ場所を探し続けることがある

37 オープンアドレス法 : 平方探査の問題点 サイズ 59 の配列 ( 要素 7 に値が入っているとする ) に, 184,302,420,538 というキーを順番に挿入することを考えると 184 % 59 = 7 1 ステップで配列の要素 8 へ 302 % 59 = 7 2 ステップで配列の要素 11 へ 420 % 59 = 7 3 ステップで配列の要素 16 へ 538 % 59 = 7 4 ステップで配列の要素 23 へ 第 2 種クラスター化

38 オープンアドレス法 : ダブルハッシュ キーの値によって探査の歩幅が異なるようにする方法 キーに対して 2 度目のハッシュを行い, 得られた結果をステップ幅として使う h k x = h x + k h s x % B h s x = C (x % C) % B B: ハッシュ表配列の大きさ h x : 最初のハッシュ関数 C: 定数 ( 配列サイズより小さい素数 )

39 オープンアドレス法 : ダブルハッシュの注意点 最初のハッシュ関数と同じであってはならない 0 が作られることのある関数であってはならない ハッシュ表のサイズは素数でなければならない サイズ 59 の配列 ( 要素 7 に値が入っているとする ) に,184,302,420,538 というキーを順番に挿入することを考えると?

40 オープンアドレス法 : ダブルハッシュの注意点 h 5 x = h x + k h 8 x % 59 h 8 x = 11 (x % 11) % 59 (B = 59, C = 11) とすると h 184 = 184 % 59 = 7 h = 11 (184 % 11) % 59) = 3 h D 184 = % 59 = 10 h 302 = 302 % 59 = 7 h = 11 (302 % 11) % 59) = 6 h D 302 = % 59 = 13 h 420 = 420 % 59 = 7 h = 11 (420 % 11) % 59) = 9 h D 420 = % 59 = 16 h 538 = 538 % 59 = 7 h = 11 (538 % 11) % 59) = 10 h D 538 = % 59 = 17 配列の要素 10へ 配列の要素 13へ 配列の要素 16へ 配列の要素 17へ

41 良いハッシュ関数とは 手早い計算 ハッシュ法の利点はスピードなので, ハッシュ関数は高速であるべき ランダムキー Index = key % arraysize で得られるインデクスもランダム ( 均等 ) に分布 ノンランダムキー テーブルサイズには素数を使う 多くのキーと配列サイズに共通の公約数がある場合, それらが同じ位置へハッシュされるため

42 問題 1: ハッシュ (2) (2) (1) の表に示した文字列を上から順番に 要素数 11 のハッシュ表に格納せよ (3) 衝突が発生した場合には チェイン法とオープンアドレス法でそれぞれどのように衝突が回避されるかを図で示せ (4) オープンアドレス法は線形探査とダブルハッシュの両方を示すこと 線形探査とダブルハッシュのハッシュ関数は以下のとおり 線形探査のハッシュ関数 h F x = h x + k % B ダブルハッシュのハッシュ関数 h F x = h x + k h H x % B h H x = C (x % C) % B B = 11, C = 7 とする k 回目にアクセスする場所 (k=0, 1, 2,, 10)

組合せ爆発の対処

組合せ爆発の対処 探 索 アルゴリズム 探 索 とは? キー 一 致 するものを 探 す レコード : : : フィールド START n=10, i =0, target=54 i : n a[i] : target i++ < = 線 形 探 索 アルゴリズム(1) 前 提 : 配 列 aにn 個 のデータが 保 存 処 理 :target と 同 じデータが 蓄 えら れている 配 列 要 素 の 添 え 字

More information

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

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

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 Word - no103.docx

Microsoft Word - no103.docx 次は 数える例です ex19.c /* Zeller の公式によって 1 日の曜日の分布を求めるプログラム */ int year, month, c, y, m, wnumber, count[7] = {0, i; for(year = 2001; year

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

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

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

More information

データ構造

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

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 PowerPoint - 05.pptx

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

More information

情報処理Ⅰ

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

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

Microsoft PowerPoint - 5.pptx

Microsoft PowerPoint - 5.pptx 5. サーチ 5-1. 線形探索 5-2.2 分探索 5-3. ハッシュ 1 サーチ問題 入力 :n 個のデータ a, a,, an a n 0 1 1 ( ここで 入力サイズは とします ) さらに キー k 出力 : k = a となる a があるときは i i となるがあるときは その位置 i,(0 i n 1) キーが存在しないとき -1 2 探索 ( サーチ ) 入力 : 5 3 8 1

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

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

データ構造と  アルゴリズムⅠ 算法数理工学 第 5 回 定兼邦彦 ハッシュ表 辞書操作 (INSERT, DELETE, SEARCH) を効率よく実現するデータ構造 応用 :C 言語のコンパイラでの記号表の管理 キー : 変数名などの文字列 ハッシュ表は実際的な場面では極めて速い 妥当な仮定の下で,SEARCH の時間の期待値は O() 最悪の場合 () 2 チェイン法を用いるハッシュ法の解析 SEARCH は最悪の場合 ()

More information

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

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

More information

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

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

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

スライド 1

スライド 1 知識情報演習 Ⅲ( 後半第 3 回 ) 辻慶太 http://slis.sakura.ne.jp/cje3 1 索引付けの手順概要 ( 復習 ) (1) 索引語の候補の抽出 文字バイグラム, 単語, フレーズなど (2) 不要語の削除 (3) 接辞処理 (4) 索引語の重み付け 検索手法 ( 検索モデル ) によっては不要例えば, 論理式によるブーリアンモデルでは不要 (5) 索引ファイルの編成 stopword.prl

More information

PowerPoint プレゼンテーション

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

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

始めに, 最下位共通先祖を求めるための関数 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

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

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

More information

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

More information

* ライブラリ関数 islower(),toupper() を使ったプログラム 1 /* 2 Program : trupper.c 3 Student-ID : K 4 Author : TOUME, Kouta 5 Comments : Used Library function i

* ライブラリ関数 islower(),toupper() を使ったプログラム 1 /* 2 Program : trupper.c 3 Student-ID : K 4 Author : TOUME, Kouta 5 Comments : Used Library function i 1. ライブラリ関数 islower(), toupper() を使い 下記の trlowup プログラムを書き換えて 新規に trupper プログラムを作成せよ * サンプルプログラム 1 /* 2 Program : trlowup.c 3 Comments : translate lower case characters into upper case ones. 4 */ 5 6 #include

More information

基礎プログラミング2015

基礎プログラミング2015 応用プログラミング 第 5 回 テキスト入力処理 2017 年 10 月 18 日 ( 水 ) 第 7 章 テキスト入力処理 1 文字ずつの処理 (P.58) char 型などに入力する cin >> x や fin >> x はホワイトスペースが読み飛ばされる仕様 ホワイトスペース : スペース ( 空白 ), Tab( タブ ), 改行 // sample.cpp char ch; while(cin

More information

スライド 1

スライド 1 知識情報演習 Ⅲ( 後半第 3 回 ) 辻慶太 http://slis.sakura.ne.jp/cje3 1 索引付けの手順概要 ( 復習 ) (1) 索引語の抽出 文字バイグラム, 単語, フレーズなど (2) 不要語の削除 (3) 接辞処理 (4) 索引語の重み付け 検索手法 ( 検索モデル ) によっては不要例えば, 論理式によるブーリアンモデルでは不要 (5) 索引ファイルの編成 extract.prl

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

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

Microsoft PowerPoint - 6.pptx

Microsoft PowerPoint - 6.pptx 6. データ構造入門 6-1. 連結リスト (Linked List) 6-2. スタック (Stack) 6-. キュー (Queue) 6-4. デク (Double-Ended-Queue) 6-. 抽象データ型 (Abstract Data Type) データ構造とは データの保存を効率的に行うもの 1 ito 2.712.14 suzuki データ構造 1 2 6-1. 連結リスト (Linked

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

02: 変数と標準入出力

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

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション 2018/10/05 竹島研究室創成課題 第 2 回 C 言語演習 変数と演算 東京工科大学 加納徹 前回の復習 Hello, world! と表示するプログラム 1 #include 2 3 int main(void) { 4 printf("hello, world! n"); 5 return 0; 6 } 2 プログラム実行の流れ 1. 作業ディレクトリへの移動 $ cd

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

情報工学実験 C コンパイラ第 2 回説明資料 (2017 年度 ) 担当 : 笹倉 佐藤

情報工学実験 C コンパイラ第 2 回説明資料 (2017 年度 ) 担当 : 笹倉 佐藤 情報工学実験 C コンパイラ第 2 回説明資料 (2017 年度 ) 担当 : 笹倉 佐藤 2017.12.7 前回の演習問題の解答例 1. 四則演算のできる計算機のプログラム ( 括弧も使える ) 2. 実数の扱える四則演算の計算機のプログラム ( 実数 も というより実数 が が正しかったです ) 3. 変数も扱える四則演算の計算機のプログラム ( 変数と実数が扱える ) 演習問題 1 で行うべきこと

More information

Microsoft PowerPoint - 11.pptx

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

More information

Microsoft PowerPoint - 説柔5_間勊+C_guide5ï¼›2015ã•’2015æŒ°æŁŽæš’å¯¾å¿œç¢ºèª“æ¸‹ã†¿ã•‚.pptx

Microsoft PowerPoint - 説柔5_間勊+C_guide5ï¼›2015ã•’2015æŒ°æŁŽæš’å¯¾å¿œç¢ºèª“æ¸‹ã†¿ã•‚.pptx 情報ネットワーク導入ユニット Ⅰ C 言語 配列 5 章 : 配列同じ型 (int, double など ) の変数の集まりを 番号 ( 添字 ) で管理する変数 int vc[5]; // 要素数が 5 の配列 vc[0] = 1; vc[1] = 2; vc[2] = 3; vc[3] = 4; vc[4] = 5; printf("vc[0] = %d n", vc[0] ); printf("vc[1]

More information

PowerPoint プレゼンテーション

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

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 ポインタ (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

コンピュータリテラシ 第 6 回表計算 2 このスライド 例題 /reidai6.xlsx /reidai6a.xlsx 課題 12 /reidai6b.xlsx /table12_13.xlsx

コンピュータリテラシ 第 6 回表計算 2 このスライド 例題   /reidai6.xlsx /reidai6a.xlsx 課題 12 /reidai6b.xlsx /table12_13.xlsx コンピュータリテラシ 第 6 回表計算 2 このスライド 例題 http://cobayasi.com/jm/6th/6th.pdf /reidai6.xlsx /reidai6a.xlsx 課題 12 /reidai6b.xlsx /table12_13.xlsx 今日の学習要点 ( テキスト P152-167) IF 関数の使い方 IF 関数による条件判定 複合条件による判定 順位付け (RANK.EQ)

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

プログラミング実習I

プログラミング実習I プログラミング実習 I 03 変数と式 人間システム工学科井村誠孝 m.imura@kwansei.ac.jp 3.1 変数と型 変数とは p.60 C 言語のプログラム中で, 入力あるいは計算された数や文字を保持するには, 変数を使用する. 名前がついていて値を入れられる箱, というイメージ. 変数定義 : 変数は変数定義 ( 宣言 ) してからでないと使うことはできない. 代入 : 変数には値を代入できる.

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 プレゼンテーション

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

More information

program7app.ppt

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

More information

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

模擬試験問題(第1章~第3章) 基本情報技術者試験の練習問題 - 第 8 回 この問題は平成 19 年度秋期の問題から抜粋しています 問 1 次のプログラムの説明及びプログラムを読んで, 設問 1,2 に答えよ プログラムの説明 スタックを使って, 実数値を 10 進数字列 ( 文字列 ) に変換する副プログラム FloatFormat である (1) FloatFormat は, 実数 Float の値を 10 進数字列に変換し,

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

講習No.8

講習No.8 配列変数の要素 復習 int x[5]; x[0] x[1] x[2] x[3] x[4] 5 は配列の要素数 これらの変数をそれぞれ配列の要素と呼ぶ この数字を配列の添え字, またはインデックスと呼ぶ! 重要! インデックスの最大値 = 要素数ー 1 int x = 7; float aa[x]; int x = 7; float aa[7];! 重要! 配列宣言時の要素数は定数でなければならない

More information

Microsoft Word - no15.docx

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

More information

Microsoft PowerPoint - lec10.ppt

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

More information

memo

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

More information

Microsoft Word _VBAProg1.docx

Microsoft Word _VBAProg1.docx 1. VBA とマクロ 1.1 VBA とは VBA(Visual Basic for Applications) は 1997 年に Microsoft 社がマクロを作成するために開発された言語である Windows 対応のアプリケーションを開発するためのプログラミング言語 Visual Basic をもとにしているため 次のような特徴がある 1 VBA は Excel Word, Access,

More information

Python @HACHINONE 10 1 V Python 2014 2 : L[i] # -*- coding: utf-8 -*- def search(l, e): """L をリスト e をオブジェクトとする L に e が含まれていれば True そうでなければ False を返す """ for i in range(len(l)): if L[i] == e: return True

More information

講習No.9

講習No.9 日本語は通常 2 バイトの文字コード.JIS コード, シフト JIS コード, Unicode (UTF-8) 等の様々な文字コードがある. アスキーコード表 (ASCII code) アスキーコード ( 値 ) 漢字変換無しでキーボードから直接入力できる半角文字 32 48 0 64 @ 80 P 96 ` 112 p 33! 49 1 65 A 81 Q 97 a 113 q 34 " 50

More information

PowerPoint Presentation

PowerPoint Presentation 算法数理工学 第 回 定兼邦彦 クイックソートの 確率的アルゴリズム クイックソートの平均的な場合の実行時間を解析する場合, 入力の頻度を仮定する必要がある. 通常は, すべての順列が等確率で現れると仮定 しかし実際にはこの仮定は必ずしも期待できない この仮定が成り立たなくてもうまく動作するクイックソートの確率的アルゴリズムを示す 確率的 radomized) アルゴリズム 動作が入力だけでなく乱数発生器

More information

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

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

More information

Microsoft Word - 3new.doc

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

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

Microsoft PowerPoint - 06.pptx

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

More information

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

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

More information

FORTRAN( と C) によるプログラミング 5 ファイル入出力 ここではファイルからデータを読みこんだり ファイルにデータを書き出したりするプログラムを作成してみます はじめに テキスト形式で書かれたデータファイルに書かれているデータを読みこんで配列に代入し 標準出力に書き出すプログラムを作り

FORTRAN( と C) によるプログラミング 5 ファイル入出力 ここではファイルからデータを読みこんだり ファイルにデータを書き出したりするプログラムを作成してみます はじめに テキスト形式で書かれたデータファイルに書かれているデータを読みこんで配列に代入し 標準出力に書き出すプログラムを作り FORTRAN( と C) によるプログラミング 5 ファイル入出力 ここではファイルからデータを読みこんだり ファイルにデータを書き出したりするプログラムを作成してみます はじめに テキスト形式で書かれたデータファイルに書かれているデータを読みこんで配列に代入し 標準出力に書き出すプログラムを作ります FORTRAN の場合 OPEN 文でファイルを開いた後 標準入力の場合と同様に READ 文でデータを読みこみます

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション 講座準備 講座資料は次の URL から DL 可能 https://goo.gl/jnrfth 1 ポインタ講座 2017/01/06,09 fumi 2 はじめに ポインタはC 言語において理解が難しいとされる そのポインタを理解することを目的とする 講座は1 日で行うので 詳しいことは調べること 3 はじめに みなさん復習はしましたか? 4 & 演算子 & 演算子を使うと 変数のアドレスが得られる

More information

ポインタ変数

ポインタ変数 プログラミング及び実習 5 馬青 1 文字処理 数値処理 : 整数 浮動小数点数 単一の文字は と ( シングルクォーテーション ) で囲んで表現される 文字のデータ型は char または int である int を用いたほうが ライブラリの関数の引数の型と一致する 以下は全部 int の使用に統一する 従って int ch; で文字変数を宣言しておくと ch= A ; のように ch に文字 A

More information

第2回

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

More information

第 3 回 Java 講座 今回の内容 今週の Java 講座はコレクション 拡張 for 文, ガベージコレクションについて扱う. 今週の Java 講座は一番内容が薄いも のになるだろう. コレクション コレクションとは大きさが決まっていない配列だと考えればよい. コレクションには List 先

第 3 回 Java 講座 今回の内容 今週の Java 講座はコレクション 拡張 for 文, ガベージコレクションについて扱う. 今週の Java 講座は一番内容が薄いも のになるだろう. コレクション コレクションとは大きさが決まっていない配列だと考えればよい. コレクションには List 先 第 3 回 Java 講座 今回の内容 今週の Java 講座はコレクション 拡張 for 文, ガベージコレクションについて扱う. 今週の Java 講座は一番内容が薄いも のになるだろう. コレクション コレクションとは大きさが決まっていない配列だと考えればよい. コレクションには List 先頭の要素要素から最後までが直線的に直結している構造 Set 同じものは含まないという構造. 要素間につながりはない

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

Microsoft PowerPoint - IntroAlgDs pptx

Microsoft PowerPoint - IntroAlgDs pptx アルゴリズムとデータ構造入門 -14 2014 年 1 月 21 日 大学院情報学研究科知能情報学専攻 http://winni.kuis.kyoto-u.ac.jp/~okuno/lctur/13/introalgds/ okuno@i.kyoto-u.ac.jp,okuno@nu.org if mod( 学籍番号の下 3 桁,3) 0 if mod( 学籍番号の下 3 桁,3) 1 if mod(

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

Excel2013 データベース1(テーブル機能と並べ替え)

Excel2013 データベース1(テーブル機能と並べ替え) OA スキルアップ EXCEL2013 データベース 1( テーブル機能と並べ替え ) 1 / 8 Excel2013 データベース 1( テーブル機能と並べ替え ) データベース機能概要 データベース機能とは データベース とは売上台帳 顧客名簿 社員名簿など 特定のルールに基づいて集められたデータを指します Excel のデータベース機能には 並べ替え 抽出 集計 分析 といった機能があります

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

Taro-ポインタ変数Ⅰ(公開版).j

Taro-ポインタ変数Ⅰ(公開版).j 0. 目次 1. ポインタ変数と変数 2. ポインタ変数と配列 3. ポインタ変数と構造体 4. ポインタ変数と線形リスト 5. 問題 問題 1 問題 2-1 - 1. ポインタ変数と変数 ポインタ変数には 記憶領域の番地が格納されている 通常の変数にはデータが格納されている 宣言 int *a; float *b; char *c; 意味ポインタ変数 aは 整数型データが保存されている番地を格納している

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション 講座を行う前に 自己紹介 僕と上回生について 1 年生同士で少しお話しよう! オリエンテーションの宿題 アルゴロジック http://home.jeita.or.jp/is/highschool/algo/index3.html どこまでできましたか? あまりできなかった人はこれから全部クリアしよう! 2016 年度 C 言語講座 第一回目 2016/6/11 fumi 今回の目標 プログラムを書いて実行するやり方を覚える

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

フィルタとは

フィルタとは フィルタコマンドの使い方 フィルタとは? 一般的にはフィルタとは, 与えられたものの特定成分を取り除いたり, 弱めたりする機能を持つものをいう ( コーヒーのフィルタ, レンズのフィルタ, 電気回路のフィルタ, ディジタルフィルタなど ). Unix では, 入力されたデータを加工して出力するプログラム ( コマンド ) をフィルタと呼ぶ. ここでは,Unix の代表的なフィルタコマンドとして次のものを取り上げる.

More information

論理と計算(2)

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

More information

nlp1-04a.key

nlp1-04a.key 自然言語処理論 I. 文法 ( 構文解析 ) その 構文解析 sytctic lysis, prsig 文の構文的な構造を決定すること句構造文法が使われることが多い文法による構文木は一般に複数ある 構文木の違い = 解釈の違い 構文解析の目的 句構造文法の規則を使って, 文を生成できる構文木を全て見つけだすこと 文法が入力文を生成できるかどうかを調べるだけではない pro I 構文解析とは 構文木の違い

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 2 回文字列とポインタ 先週のパズルの解説 答え : 全部 p a 1 図の書き方 : p+1 は式であって その値を格納する記憶場所を考えないので 四角で囲まない 2 p+1 同じものを表すいろいろな書き方をしてみましたが パズル以上の意味はありません プログラム中に書くときは p+1 が短くていいんじゃないかな p+1 は 2 の記憶場所 p[1] は 2 に格納されている値

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション シミュレーション基礎 (8) 第 6 章ファイル入出力 7.2 テキストファイルの読み書き ファイルに書き込む : EX70201: X=1:10;Y=[X;X.^2]; Fid=fopen('datal.txt', wt'); fprintf(fid,'%2d%5d n',y); C 言語と同じ手順 : ファイルをオープンするファイルに変数の値を書き込む ( 整数 2 桁, 整数 5 桁, 改行

More information

Microsoft PowerPoint - IntroAlgDs ppt

Microsoft PowerPoint - IntroAlgDs ppt アルゴリズムとデータ構造入門 -4 006 年 月 7 日 アルゴリズムとデータ構造入門 Sorting( 整列 ) Hashing( ハッシュ法 ) 奥乃 博 年前の今朝阪神 淡路大震災犠牲者死者だけで 6434 人天災は忘れた頃にやってくる ( 寺田寅彦 ) 天才は忘れた頃にやってくる ( 奥乃博 ) 月 7 日 本日のメニュー. vector ( ベクタ ). Sorting ( 整列 ) 3.

More information

目次

目次 http://www0.info.kanagawa-u.ac.jp/~kaiya/p1/ dotcampus ショートコード 221137 プログラミング I 数理物理, 総合理学等向け 2017 年 12 月 11 日 海谷治彦 1 目次 11 章 [ レ ] 10 章 [ 明 ] ポインタ C 言語の最大難関といわれています orz コンピュータ内の情報表現 ( 復習 ) 演習の解答例 (isbn,

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 次の文は 問題の把握からプログラムの完成までのプログラミング過程 を 5 段階に分けて示したものである 下記の [a.]~[x.] に当てはまる語句を記入せよ (ⅰ) 問題の把握と対策 : 何が問題か その問題を解決するにはどのようなシステムで対処するのかを考え, 全体を見渡して人手や機械で処理し部分と, 計算機で処理する部分とを明らかにする (ⅱ) プログラミングの設計 : フローチャートを用いてシステムの開発工程を管理することを考えると,

More information

Microsoft Word - no12.doc

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

More information

目次 1. 変換の対象 砂防指定地 XML 作成メニュー シェープファイルからXMLへ変換 砂防指定地 XMLとシェープファイルの対応.csv 変換処理 CSVファイルによる属性指定... 5

目次 1. 変換の対象 砂防指定地 XML 作成メニュー シェープファイルからXMLへ変換 砂防指定地 XMLとシェープファイルの対応.csv 変換処理 CSVファイルによる属性指定... 5 砂防指定地 XML 作成説明書 2012/12/18 有限会社ジオ コーチ システムズ http://www.geocoach.co.jp/ info@geocoach.co.jp 砂防指定地 XML 作成 プログラムについての説明書です この説明書は次のバージョンに対応しています アプリケーション名バージョン日付 砂防指定地 XML 作成 7.0.5 2012/12/18 プログラムのインストールについては

More information

char int float double の変数型はそれぞれ 文字あるいは小さな整数 整数 実数 より精度の高い ( 数値のより大きい より小さい ) 実数 を扱う時に用いる 備考 : 基本型の説明に示した 浮動小数点 とは数値を指数表現で表す方法である 例えば は指数表現で 3 書く

char int float double の変数型はそれぞれ 文字あるいは小さな整数 整数 実数 より精度の高い ( 数値のより大きい より小さい ) 実数 を扱う時に用いる 備考 : 基本型の説明に示した 浮動小数点 とは数値を指数表現で表す方法である 例えば は指数表現で 3 書く 変数 入出力 演算子ここまでに C 言語プログラミングの様子を知ってもらうため printf 文 変数 scanf 文 if 文を使った簡単なプログラムを紹介した 今回は変数の詳細について習い それに併せて使い方が増える入出力処理の方法を習う また 演算子についての復習と供に新しい演算子を紹介する 変数の宣言プログラムでデータを取り扱う場合には対象となるデータを保存する必要がでてくる このデータを保存する場所のことを

More information

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

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

More information

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

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

More information

Taro-ファイル処理(公開版).jtd

Taro-ファイル処理(公開版).jtd ファイル処理 0. 目次 1. はじめに 2. ファイル内容の表示 3. ファイル内容の複写 3. 1 文字単位 3. 2 行単位 4. 書式付き入出力 5. 文字配列への入出力 6. 課題 6. 1 課題 1 ( ファイル圧縮 復元 ) - 1 - 1. はじめに ファイル処理プログラムの形は次のようになる #include main() { FILE *fp1,*fp2; ファイルポインタの宣言

More information

情報量と符号化

情報量と符号化 I. ここでの目的情報量の単位はビットで 2 種の文字を持つ記号の情報量が 1 ビットです ここでは 一般に n 種の文字を持つ記号の情報量を定義します 次に 出現する文字に偏りがある場合の平均情報量を定義します この平均情報量は 記号を適当に 0,1 で符号化する場合の平均符号長にほぼ等しくなることがわかります II. 情報量とは A. bit 情報量の単位としてbitが利用されます 1bitは0か1の情報を運びます

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

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

Microsoft PowerPoint - ca ppt [互換モード] 008//8 大阪電気通信大学情報通信工学部光システム工学科 年次配当科目 コンピュータアルゴリズム 探索アルゴリズム () 第 8 講 : 平成 0 年 月 8 日 ( 金 ) 4 限 E5 教室 中村嘉隆 ( なかむらよしたか ) 奈良先端科学技術大学院大学助教 y-nkmr@is.nist.jp http://nrym.nist.jp/~y-nkmr/ 第 講の復習 探索アルゴリズム 探索するデータ構造

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 2 回文字列とポインタ 先週のパズルの解説 答え : 全部 p a 1 図の書き方 : p+1 は式であって その値を格納する記憶場所を考えないので 四角で囲まない 2 p+1 同じものを表すいろいろな書き方をしてみましたが パズル以上の意味はありません プログラム中に書くときは p+1 が短くていいんじゃないかな p+1 は 2 の記憶場所 p[1] は 2 に格納されている値

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

「不動産リスト」を解く

「不動産リスト」を解く Microsoft2010 不動産リスト を解く IF 関数 VLOOKUP 関数 CHOOSE 関数 LEFT 関数 MOD 関数 INT 関数 INDEX 関数 2015/01/27 パソコン技能検定 Ⅱ 種試験 Excel 1 級検定過去問題 ここで使用する関数の種類 よく使われる関数として SUM IF,AVERAGE AND,OR などがありますが そのほかにも 今回次のような関数を単独で

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

< F2D837C E95CF CF68A4A94C5816A2E6A>

< F2D837C E95CF CF68A4A94C5816A2E6A> 0. 目次 6. ポインタ変数と文字処理 6. 1 文字 6. 2 文字列定数 6. 3 文字列 6. 4 文字列配列 7. ポインタ変数と関数 8. 問題 7. 1 引数とポインタ変数 7. 1. 1 変数が引数の場合 7. 1. 2 ポインタ変数が引数の場合 7. 2 引数と配列 7. 3 戻り値とポインタ変数 問題 1 問題 2-1 - 6. ポインタ変数と文字処理 6. 1 文字 文字の宣言

More information

第二回独習 Java ゼミ 第二章クラスとメソッド 2.1 メソッドの構造 2.2 静的メソッドと静的変数の概要 2.3 インスタンスメソッドとインスタンス変数の概要 2.4 Integerクラス 2006/04/19 神津健太

第二回独習 Java ゼミ 第二章クラスとメソッド 2.1 メソッドの構造 2.2 静的メソッドと静的変数の概要 2.3 インスタンスメソッドとインスタンス変数の概要 2.4 Integerクラス 2006/04/19 神津健太 第二回独習 Java ゼミ 第二章クラスとメソッド 2.1 メソッドの構造 2.2 静的メソッドと静的変数の概要 2.3 インスタンスメソッドとインスタンス変数の概要 2.4 Integerクラス 2006/04/19 神津健太 2.1 メソッドの構造 メソッドとは プログラムステータメントの集合体 Java の基本的な実行単位 クラスの一部 メソッドの外部にプログラムコードを置いたり クラスの外部にメソッドを置くことはできない

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション コンパイラとプログラミング言語 第 3 4 週 プログラミング言語の形式的な記述 2014 年 4 月 23 日 金岡晃 授業計画 第 1 週 (4/9) コンパイラの概要 第 8 週 (5/28) 下向き構文解析 / 構文解析プログラム 第 2 週 (4/16) コンパイラの構成 第 9 週 (6/4) 中間表現と意味解析 第 3 週 (4/23) プログラミング言語の形式的な記述 第 10 週

More information