情報処理Ⅱ ２００７年１２月１７日（月）.

Presentation on theme: "情報処理Ⅱ ２００７年１２月１７日（月）."— Presentation transcript:

1 情報処理Ⅱ ２００７年１２月１７日（月）

2 本日の内容 関数，再帰，構造体を用いたプログラムの読解 ファレイ数列 両替

3 ファレイ数列 ０より大きく１より小さい分数で，既約かつ分母が７以下のものを，小さいものから順に出力できるか？
「既約」なので，2/4 は出してはいけない． 3/7 と 2/5 って，どっちが大きい？？ 再帰関数を使えば，すっきり書ける． 理論的には，「木の探索」と関係がある． farey.c

4 ファレイ数列の構成

5 ファレイ数列生成のプログラミング 分母の最大値をコマンドライン引数から取る． 再帰呼び出しをする関数print_numbersを定義する．
再帰関数を作るとき，最初に引数の意味・用途を決める！ 引数は，a1/b1 < a2/b2 を満たす非負整数a1, b1, a2, b2と，分母の上限n．戻り値なし． a1/b1より大きくa2/b2より小さい分数で，既約かつ分母がn以下のものを，小さいものから順に出力する． mainから print_numbers(0,1,1,1,n); と呼び出す． 0/1より大きく1/1より小さい分数で，既約かつ分母がn以下のものを，小さいものから順に出力する．

6 両替問題の仕様（１） 両替機の両替部分をシミュレート（模倣）する． 入金に対して，どの紙幣・貨幣を何枚出せばいいかを出力する．
「崩す」（一万円札を千円札１０枚にするなど）のは考えない． 金額に関する情報 一万円，五千円，千円の各紙幣(bill)の枚数 ５００円，１００円，５０円，１０円，５円，１円の各硬貨(coin)の枚数 合計金額(amount) ⇒ 構造体のメンバ？ ○ シミュレート，シミュレーション × シュミレート，シュミレーション 理由: 英語のつづりがsimulate, simulationだから． 100 100 100 100 500 50 10 10 10 5 5 5 5 moneychanger.c

7 両替問題の考え方 知りたい情報，行いたい操作 紙幣・貨幣がそれぞれ何枚ある（入金された，出金しないといけない）かを知る 合計金額を求める
両替する 両替前の「紙幣・貨幣の枚数の情報」に対して， 両替後の「紙幣・貨幣の枚数の情報」を求める

8 両替問題のプログラミング（１） 金銭構造体 struct money {
　int bill_10000, bill_5000, bill_1000; 　int coin_500, coin_100, coin_50, coin_10, coin_5, coin_1; 　};

9 両替問題のプログラミング（２） 定義した関数 いずれの関数も，構造体ポインタを引数にとる
void print_money(struct money *moneyp); 枚数と総額を出力する int calc_amount(struct money *moneyp); 総額を求める struct money *change_money(struct money *moneyp); 両替する いずれの関数も，構造体ポインタを引数にとる 関数内では，「moneyp->メンバ名」でアクセスする 「calc」は，「calculate （計算する）」という単語による．

10 プログラムの読み方（１） 定義／宣言／参照しているヘッダファイル・型・変数・関数の意味と関連付けを考えながら読む ⇒静的分析
変数に具体的な値を与える．各行でどんな処理が行われ，オブジェクト（メモリ）の中身がどのように変わっていくか考えながら読む ⇒動的分析 関連付けを考える際のアドバイス ・ライブラリ関数を使う際，どんなヘッダファイルをインクルードすべき（している）か？ ・関数プロトタイプがあれば，関数の実体はどこで定義されているか？ ・変数は，どこで宣言されているか？ 有効範囲はどこからどこまでか？ どこで初期化（宣言時かもしれないし，そうでないかもしれないし，&変数名による関数呼び出しの中で代入されるかもしれない）されているか？ ・代入文の左辺と右辺の型は何か？ 合っているか？ 暗黙の型変換が起こるか？ （実引数と仮引数の受け渡しでも，代入が行われることに注意する．）

11 プログラムの読み方（２） 技法（手段）に着目する ファレイ数列の問題では，再帰…全体と，その一部分とが相似関係になっている
両替問題では，グリーディ法（貪欲法）…１万円札から順に枚数を求める 再帰: グリーディ法:

12 IDE Integrated Development Environmentの略， 統合開発環境とも呼ばれる．
ハードディスクのIDEは，Integrated Drive Electronicsの略 エディタ，コンパイラ，デバッガなど，プログラミングに必要なツールが一つのインターフェースで統合して扱えるような環境のこと． デバッガとは…プログラムの不具合（バグ）の発見や修正を支援するソフトウェア．Linuxではgdbコマンドが利用可能． IDEの例：Eclipse，Visual C++，Turbo C++ など

13 Eclipse オープンソースの統合開発環境
もともとIBMが開発したもので，現在は Eclipse Foundationが開発・管理している． プラグインにより機能を付加できる． Javaに限らず様々なプログラミング言語の開発に利用可能 情報処理Ⅲで利用されている． 自宅で使いたい人へ ①Eclipse，②C/C++ Development Tools (CDT)， ③コンパイラ・デバッガをインストールする eclipse:食，日食，月食 CDTについて