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

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

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

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

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

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

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

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

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

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

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

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

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

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

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