プログラミング基礎ａ 第８回 プログラムの設計 アルゴリズムとデータ構造

Presentation on theme: "プログラミング基礎ａ 第８回 プログラムの設計 アルゴリズムとデータ構造"— Presentation transcript:

1 プログラミング基礎ａ 第８回 プログラムの設計 アルゴリズムとデータ構造
プログラミング基礎ａ 第８回 プログラムの設計 アルゴリズムとデータ構造 坂口 利裕

2 複雑な問題の考え方 （人間にとっては簡単でも）コンピュータにとっては，理解できる言葉（プログラミング言語）でないと伝わらない
プログラミング基礎ａ 複雑な問題の考え方 （人間にとっては簡単でも）コンピュータにとっては，理解できる言葉（プログラミング言語）でないと伝わらない 条件判断 if 反復処理 for （やwhile） 計算処理 x= 式（代入） データの入力 scanf メッセージやデータの表示 printf の組み合わせで表現し直すのが非常にやっかい プログラミング基礎ａ 坂口 利裕

3 アルゴリズムの役割と重要性 アルゴリズム（算法）の要件 アルゴリズムの良否 オーダー（Order） 一定の順序に従って行えば，
プログラミング基礎ａ アルゴリズムの役割と重要性 アルゴリズム（算法）の要件 一定の順序に従って行えば， 答が存在しない時も含めて， 必ず有限回の手順で， 正確な（あるいは十分に実用的な範囲の）解を， 基本演算のみで導ける アルゴリズムの良否 正確さ 速さ（いかに速く導けるか） データ量の少なさ（いかに節約できるか） オーダー（Order） 速さや記憶量をデータ数ｎの関数Ｏとして略記→高次の部分のみに着目 Ｏ（１）…データ数に依存しない Ｏ（ｎ）…データ数に比例 Ｏ（ｎ２）…データ数の２乗に比例 プログラミング基礎ａ 坂口 利裕

4 代表的なアルゴリズム（１） ユークリッドの互除法－最大公約数の導出 計算機以前から存在 有限回の繰り返しにより答が必ず求まる
プログラミング基礎ａ

5 プログラム作成上のポイント 反復回数が決められない 余り（剰余）→ 演算子 % を使用 変数内容の交換→ a=b ; b=a ; ではダメ
有限回ではあるが，回数は不明 １回目は無条件に実行 終了条件 → a == 0 do ~ while構文 を用いるので，継続条件に読み替えて指示 余り（剰余）→ 演算子 % を使用 変数内容の交換→ a=b ; b=a ; ではダメ プログラミング基礎ａ

6 練習（１） 手計算にて 3510 と 5355 の最大公約数（Greatest Common Divisor）を求めよ
プログラム例の骨格 prog14.c をダウンロード 不足部分をテキストを参照して補完 コンパイル＆実行して手計算の結果と比較 プログラミング基礎ａ

7 代表的なアルゴリズム（２） ソート（並べ替え） メリット データを一定の順序（昇順あるいは降順）に並べ替える操作
検索（サーチ）の効率がよくなる その他の計算技法でも，処理が単純化できることが多い プログラミング基礎ａ

8 配列データの並べ替え 配列内のデータを昇順に並び替える ２．５ x［０］ ４．２ x［１］ ３．５ x［２］ ６．９ x［３］ ２．５
プログラミング基礎ａ

9 プログラムによるソート処理のポイント 一時には２つの数値しか比較できない データの交換は慎重に 比較の方法によって効率が変わる
一定のルールの元で，2つの数値を比較する データの交換は慎重に AとBの内容を交換するには A=B; B=A; ではマズイ！ 第3の変数を用いて，C=A; A=B; B=C; とする 比較の方法によって効率が変わる 単純選択法・バブル法・シェル法・クイック法などが有名 プログラミング基礎ａ

10 単純選択法（１） ｉ ｉmin 基準の位置以降の中で，最小値の場所を見出す ２．５ x［０］ ４．２ x［１］ ３．５ x［２］ ６．９
プログラミング基礎ａ 単純選択法（１） 基準の位置以降の中で，最小値の場所を見出す ２．５ x［０］ ４．２ x［１］ ３．５ x［２］ ６．９ x［３］ ２．５ x［４］ ｉ ｉmin j に関して反復 iから右の範囲にある最小値の場所を見つける プログラミング基礎ａ 坂口 利裕

11 単純選択法（２） ｉ ｉmin 最小値の位置と基準の位置が異なっていたら交換 ２．５ x［０］ ４．２ x［１］ ３．５ x［２］ ６．９
xdummy ｉ ｉmin プログラミング基礎ａ

12 単純選択法（３） 以上のステップを左端（i=0）から始めて，残りの配列すべてにわたって（i=n-1まで）繰り返す
効率はよくない！ O（ｎ２） プログラミング基礎ａ

13 練習（２） プログラム例の骨格 prog15.c をダウンロード 不足部分をテキストを参照して補完
コンパイル＆実行してソートされることを確認 プログラミング基礎ａ

14 データ構造の工夫 構造型データ C言語での構文（一般にmainより上側に記述） 変数の定義 値の参照・代入
互いに関連しあうデータをひとつの「型」に集約 C言語での構文（一般にmainより上側に記述） struct 型名 { メンバーの型名 メンバー名 ; … } ; ← 例外的に }の後に ; が必要 変数の定義 struct 型名 変数名【[配列サイズ]】 ; 単純変数でも，配列変数でもよい （構造データのメンバーにもなれる） 値の参照・代入 メンバーごとの参照・代入は，ピリオド「．」で連結 単純代入のみ，変数単位で可能 プログラミング基礎ａ

15 練習（３） プログラム例 prog16.c と genso.txt をダウンロード
プログラミング基礎ａ 練習（３） プログラム例 prog16.c と genso.txt をダウンロード コンパイル＆実行して機能することを確認 He と Xe を調べよ 英字名による検索バージョンを作成 プログラミング基礎ａ 坂口 利裕