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

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

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

ファレイ数列の構成

ファレイ数列生成のプログラミング 分母の最大値をコマンドライン引数から取る． 再帰呼び出しをする関数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以下のものを，小さいものから順に出力する．

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

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

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

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

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

プログラムの読み方（２） 技法（手段）に着目する ファレイ数列の問題では，再帰…全体と，その一部分とが相似関係になっている 両替問題では，グリーディ法（貪欲法）…１万円札から順に枚数を求める 再帰: http://ai6sys4.sys.wakayama-u.ac.jp/mod/resource/view.php?id=665 グリーディ法: http://itpro.nikkeibp.co.jp/article/COLUMN/20070914/281936/?P=3

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

Eclipse オープンソースの統合開発環境 もともとIBMが開発したもので，現在は Eclipse Foundationが開発・管理している． プラグインにより機能を付加できる． Javaに限らず様々なプログラミング言語の開発に利用可能 情報処理Ⅲで利用されている． 自宅で使いたい人へ ①Eclipse，②C/C++ Development Tools (CDT)， ③コンパイラ・デバッガをインストールする eclipse:食，日食，月食 http://www.ooyashima.net/db/prog.htm CDTについて http://eclipsewiki.net/eclipse/?C%2FC%2B%2B%20%A5%D7%A5%E9%A5%B0%A5%A4%A5%F3 http://freepg.fc2web.com/cpp/topic_eclipse_cdt_001.html http://www.seshop.com/detail.asp?pid=6709