データ構造とアルゴリズム論 第２章 配列（構造）を使った処理

Presentation on theme: "データ構造とアルゴリズム論 第２章 配列（構造）を使った処理"— Presentation transcript:

1 データ構造とアルゴリズム論 第２章 配列（構造）を使った処理
データ構造とアルゴリズム論 第２章　配列（構造）を使った処理 平成15年10月7日 森田　彦

2 配列（構造）とは？ A[1]，A[2]，・・・，のように、カッコ内の数字（添え字）で変数の値を指定できるデータ構造
　例　1,5,3,9,7を配列変数に保存 大きさが「５」の配列変数Aを1個用意。 A 1 ５ ３ ９ ７ [1] [2] [3] [4] [5] ※一般の変数の場合 5個の変数を用意する。 １ ５ ３ ９ ７ A1 A2 A3 A4 A5

3 本章（本日）の学習のねらい 配列を使った（典型的な）処理を学習する。 処理内容（アルゴリズム）に応じて配列を利用できるようになる。
注意：配列を理解できなければ、次回以降の講義内容を理解できません。

4 2-1 配列の利点 例 5個の数値を順に表示させる。 ＜5個の変数＞ ＜１個の配列変数＞ i←i+1
2-1　配列の利点 例　5個の数値を順に表示させる。 ＜5個の変数＞ ＜１個の配列変数＞ 開始 開始 A1を表示 ｉ←1 A2を表示 No i≦5 i≦100 A3を表示 Yes A[i] を表示 A4を表示 終了 i←i+1 A5を表示 繰り返し処理の場合 → 配列を利用すると便利！ 終了

5 配列（利用）の利点 拡張が容易。上の例の場合、データ数が100になっても「5→100」に変えるだけで良い。
処理内容をコンパクトに記述できるので、見通しが良くなる。→アルゴリズムの構造がはっきりとする。

6 2-2 Java言語による配列の宣言 p.14～15を熟読して下さい。 プリントの訂正（p.14）
　double B[] = new double[] 　double B[] = new double[20]

7 2-3 配列の応用－最大・最小 4つの正の整数が変数A1～A4に入っている。この中の最大値を求める。 例：1,5,3,8の場合
2-3　配列の応用－最大・最小 4つの正の整数が変数A1～A4に入っている。この中の最大値を求める。 例：1,5,3,8の場合 終了！MAXに最大値が入っている。 １．A1とMAXの比較 ２．A2とMAXの比較 ３．A3とMAXの比較 ４．A4とMAXの比較 １ １ １ ５ ５ ５ ３ ３ ３ ８ ８ ８ ８ ０ ５ ０ １ A1 A2 A3 A4 MAX 勝ち抜き戦方式

8 流れ図で表すと・・・ 開始 No A3＞MAX MAX←0 Yes No A1＞MAX MAX←A3 Yes MAX←A1 No
終了

9 【基礎課題2-1】 配列A[1]～A[4]を用いて表すと・・・ 拡張が容易：整数の数が増えてもループの終値を変更するだけで良い。
開始 MAX←0 ループ i:1,1,4 　拡張が容易：整数の数が増えてもループの終値を変更するだけで良い。 記述がコンパクトに：繰り返し処理をループ内に一つだけ記述するだけで済む。 A[i]>MAX No Yes MAX←A[i] ループ MAX の表示 理解度チェック→【基礎課題2-2 】、【基礎課題2-3 】、【基礎課題2-4】 終了

10 2-4 配列要素の挿入・削除 例：配列A[1]～A[N]にデータa1～aNが入っている。→配列要素のm番目にデータXを挿入する。
2-4　配列要素の挿入・削除 例：配列A[1]～A[N]にデータa1～aNが入っている。→配列要素のm番目にデータXを挿入する。 a1 a2 ・・・ am am+1 aN A[1] A[2] A[m] A[m+1] A[N] X am以降を右にずらす a1 a2 ・・・ am am+1 ・・・ aN A[1] A[2] A[m] A[m+1] A[m+2] A[N+1] 挿入完了！ a1 a2 ・・・ X am am+1 ・・・ aN A[1] A[2] A[m] A[m+1] A[m+2] A[N+1]

11 流れ図で表すと・・・ A[N]→A[N+1] 右にずらす。 A[N-1]→A[N] ・・・ A[m]→A[m+1]
開始 X a1 a2 ・・・ am am+1 ・・・ aN ｍの入力 A[1] A[2] A[m] A[m+1] A[m+2] A[N+1] ループ i:N,-1,m A[N]→A[N+1] 右にずらす。 A[N-1]→A[N] A[i+1] ←A[i] ・・・ A[m]→A[m+1] ループ A[m]→A[m+1]から始めると、どうなるか？ A[m] ←X 終了 【基礎課題2-5】

12 2-5 添え字の参照 例：配列Data[1]～Data[N]にデータ（整数）が入っている。この中で、偶数および奇数の個数を数える。
2-5　添え字の参照 開始 例：配列Data[1]～Data[N]にデータ（整数）が入っている。この中で、偶数および奇数の個数を数える。 Gusu←0 Kisu←0 ループ i:1,1,N Kosu[1]：偶数の個数Kosu[2]：奇数の個数 を導入すると・・・ Y ←Data[i] % 2 No Y=0 Yes Gusu←Gusu+1 Kisu←Kisu+1 ループ 終了

13 Kosu[ ]内には、何が入る？ Y=0： Kosu[1]←Kosu[1]+1 Y=1： Kosu[2]←Kosu[2]+1
開始 Kosu[ ]内には、何が入る？ 初期化ループ i:1,1,2 Y=0： Kosu[1]←Kosu[1]+1 Kosu[i]←0 Y=1： Kosu[2]←Kosu[2]+1 となることに注目すると・・・ 初期化ループ ループ i:1,1,N 選択構造が不要になった！ Y ←Data[i] % 2 Kosu[Y+1]←Kosu[Y+1]+1 Kosu[ ]←Kosu[ ]+1 データ構造の変更→アルゴリズムの変更！ ループ p.28～p.29を熟読して【基礎課題2-7】へ 終了

14 テストのアナウンス 11/4に第１回目のテストを実施します。 要領は前期と同じペーパーテスト形式です。
試験欠席の場合は、単位を取得できません。→十分注意してください。 詳細は、追ってアナウンスします。 成績＝２回のテストの平均点＋応用課題数