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

Slides:



Advertisements
Similar presentations
プログラミング実習(C言語) ハードウェアとソフトウェアとの関係の理解のためのプログラミング体験
Advertisements

データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
プログラミング基礎I(再) 山元進.
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
基礎プログラミングおよび演習 第9回
Q q 情報セキュリティ 第6回:2005年5月20日(金) q q.
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
第2回ネットワークプログラミング 中村 修.
2009/10/9 良いアルゴリズムとは 第2講: 平成21年10月9日 (金) 4限 E252教室 コンピュータアルゴリズム.
地理情報システム論 第3回 コンピュータシステムおける データ表現(1)
第10回 ソート(1):単純なソートアルゴリズム
情報科学1(G1) 2016年度.
第9回 今日の目標 §3.2 アルゴリズム 問題解決の手順を示せる アルゴリズムの条件と処理要素を示せる
データ構造と アルゴリズム 知能情報学部 新田直也.
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
①データ構造 ②アルゴリズム ③プログラム言語 ④マークアップ言語
データベース設計 第9回 Webインタフェースの作成(1)
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
二分探索木によるサーチ.
第7回 条件による繰り返し.
表計算 Excel 演習 4.検索,条件付き書式設定,並べ替え.
ちょっとした練習問題① 配列iroを['R', 'W', 'R', 'R', 'W' , 'W' , 'W']を宣言して、「W」のときの配列の番号をprintfで表示するようなプログラムを記述しなさい。
プログラムの制御構造 選択・繰り返し.
アルゴリズムとデータ構造1 2006年6月16日
プログラミング演習I 2003年5月7日(第4回) 木村巌.
第7回 条件による繰り返し.
復習 前回の関数のまとめ(1) 関数はmain()関数または他の関数から呼び出されて実行される.
データ構造とアルゴリズム論 第1章 アルゴリズムの表現-流れ図
プログラミング基礎a 第1回 ハードウェアとソフトウェア プログラミング総論 ~プログラミング言語とは~
プログラミング基礎a 第10回 Javaによる図形処理入門(2) GUIの使い方
プログラミング基礎a 第7回 C言語によるプログラミング入門 ファイル入出力
アルゴリズムとプログラミング (Algorithms and Programming)
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
プログラミング 4 整列アルゴリズム.
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
復習 一定回数を繰り返す反復処理の考え方 「ループ」と呼ぶ false i < 3 true i をループ変数あるいはカウンタと呼ぶ
11.再帰と繰り返しの回数.
プログラミングⅠ 平成31年1月7日 森田 彦.
C言語 はじめに 2016年 吉田研究室.
プログラミング基礎a 第6回 C言語によるプログラミング入門 配列と文字列(その2)
補講:アルゴリズムと漸近的評価.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
地理情報システム論(総)/ 国民経済計算論(商)
知能情報工学演習I 第11回( C言語第5回) 課題の回答
情報基礎Ⅱ (第1回) 月曜4限 担当:北川 晃.
プログラミングⅡ 第2回.
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
計算機プログラミングI 木曜日 1時限・5時限 担当: 増原英彦 第1回 2002年10月10日(木)
プログラミング基礎a 第4回 C言語によるプログラミング入門 条件判断と反復
アルゴリズムとプログラミング (Algorithms and Programming)
計算機プログラミングI 第4回 2002年10月31日(木) 問題解決とアルゴリズム クラスメソッドと手続きの抽象化 最大公約数
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
復習 if ~ 選択制御文(条件分岐) カッコが必要 true 条件 false 真(true)なら この中が aを2倍する 実行される
情報コミュニケーション入門b 第9回 表計算ソフト入門(3)
プログラミング基礎a 第3回 C言語によるプログラミング入門 データ入力
オブジェクト指向言語論 第二回 知能情報学部 新田直也.
情報実習I (第1回) 木曜4・5限 担当:北川 晃.
コンパイラ 2012年10月11日
プログラミング基礎a 第7回 C言語によるプログラミング入門 ファイル入出力
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
プログラミング基礎a 第5回 C言語によるプログラミング入門 配列と文字列
情報処理Ⅱ 小テスト 2005年2月1日(火).
プログラミング基礎a 第3回 C言語によるプログラミング入門 データ入力
プログラミング入門2 第3回 条件分岐(2) 繰り返し文 篠埜 功.
プログラミング論 バイナリーサーチ 1.
ファーストイヤー・セミナーⅡ 第10回 if文による選択処理(2).
Presentation transcript:

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

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

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

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

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

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

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

配列データの並べ替え 配列内のデータを昇順に並び替える 2.5 x[0] 4.2 x[1] 3.5 x[2] 6.9 x[3] 2.5 2011.11.30 プログラミング基礎a

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

単純選択法(1) i imin 基準の位置以降の中で,最小値の場所を見出す 2.5 x[0] 4.2 x[1] 3.5 x[2] 6.9 プログラミング基礎a 2011.11.30 単純選択法(1) 基準の位置以降の中で,最小値の場所を見出す 2.5 x[0] 4.2 x[1] 3.5 x[2] 6.9 x[3] 2.5 x[4] i imin j に関して反復 iから右の範囲にある最小値の場所を見つける 2011.11.30 プログラミング基礎a 坂口 利裕

単純選択法(2) i imin 最小値の位置と基準の位置が異なっていたら交換 2.5 x[0] 4.2 x[1] 3.5 x[2] 6.9 xdummy i imin 2011.11.30 プログラミング基礎a

単純選択法(3) 以上のステップを左端(i=0)から始めて,残りの配列すべてにわたって(i=n-1まで)繰り返す 効率はよくない! O(n2) 2011.11.30 プログラミング基礎a

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

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

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