情報処理Ⅱ ２００７年１２月１７日（月）本日の内容  関数，再帰，構造体を用いたプログラムの読解   ファレイ数列両替 2 ファレイ数列  ０より大きく１より小さい分数で，既約かつ分母が７以下のものを，小さいものから順に出力できるか？    「既約」なので，2/4 は出してはいけない． 3/7 と 2/5 って，どっちが大きい？？再帰関数を使えば，すっきり書ける．  farey.c 理論的には，「木の探索」と関係がある． 3 ファレイ数列の構成 0 1 1 1 1 2 1 3 2 3 3 4 1 4 1 5 2 5 4 5 3 5 5 6 1 6 2 7 1 7 1 7 1 6 1 5 1 4 2 7 3 7 1 3 2 5 3 7 4 7 1 2 4 7 5 7 3 5 2 3 5 7 6 7 3 4 4 5 5 6 6 7 4 ファレイ数列生成のプログラミング   分母の最大値をコマンドライン引数から取る．再帰呼び出しをする関数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以下のものを，小さいものから順に出力する． 5 両替問題の仕様（１）   両替機の両替部分をシミュレート（模倣）する．入金に対して，どの紙幣・貨幣を何枚出せばいいかを出力する．   「崩す」（一万円札を千円札１０枚にするなど）のは考えない．金額に関する情報    一万円，五千円，千円の各紙幣(bill)の枚数５００円，１００円，５０円，１０円，５円，１円の各硬貨(coin)の枚数合計金額(amount) ⇒ 構造体のメンバ？ 100 100 100 100 moneychanger.c 50 10 10 10 5 5 5 5 500 6 両替問題の考え方  知りたい情報，行いたい操作    紙幣・貨幣がそれぞれ何枚ある（入金された，出金しないといけない）かを知る合計金額を求める両替する • 両替前の「紙幣・貨幣の枚数の情報」に対して，両替後の「紙幣・貨幣の枚数の情報」を求める 7 両替問題のプログラミング（１）  金銭構造体  struct money { int bill_10000, bill_5000, bill_1000; int coin_500, coin_100, coin_50, coin_10, coin_5, coin_1; }; • •  8 両替問題のプログラミング（２）  定義した関数     void print_money(struct money *moneyp); • 枚数と総額を出力する int calc_amount(struct money *moneyp); • 総額を求める struct money *change_money(struct money *moneyp); • 両替するいずれの関数も，構造体ポインタを引数にとる  関数内では，「moneyp->メンバ名」でアクセスする 9 プログラムの読み方（１）   定義／宣言／参照しているヘッダファイル・型・変数・関数の意味と関連付けを考えながら読む ⇒静的分析変数に具体的な値を与える．各行でどんな処理が行われ，オブジェクト（メモリ）の中身がどのように変わっていくか考えながら読む ⇒動的分析 10 プログラムの読み方（２）  技法（手段）に着目する   ファレイ数列の問題では，再帰…全体と，その一部分とが相似関係になっている両替問題では，グリーディ法（貪欲法）…１万円札から順に枚数を求める 11 IDE  Integrated Development Environmentの略，統合開発環境とも呼ばれる．   エディタ，コンパイラ，デバッガなど，プログラミングに必要なツールが一つのインターフェースで統合して扱えるような環境のこと．   ハードディスクのIDEは，Integrated Drive Electronicsの略デバッガとは…プログラムの不具合（バグ）の発見や修正を支援するソフトウェア．Linuxではgdbコマンドが利用可能． IDEの例：Eclipse，Visual C++，Turbo C++ など 12 Eclipse     オープンソースの統合開発環境もともとIBMが開発したもので，現在は Eclipse Foundationが開発・管理している．プラグインにより機能を付加できる． Javaに限らず様々なプログラミング言語の開発に利用可能   情報処理Ⅲで利用されている．自宅で使いたい人へ  ①Eclipse，②C/C++ Development Tools (CDT)， ③コンパイラ・デバッガをインストールする 13