情報処理Ⅱ 2007年12月17日(月) 本日の内容 関数,再帰,構造体を用いたプログラムの読解 ファレイ数列 両替 2 ファレイ数列 0より大きく1より小さい分数で,既約かつ分母が7以下のも のを,小さいものから順に出力できるか? 「既約」なので,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 両替問題の仕様(1) 両替機の両替部分をシミュレート(模倣)する. 入金に対して,どの紙幣・貨幣を何枚出せばいいかを出力す る. 「崩す」(一万円札を千円札10枚にするなど)のは考えない. 金額に関する情報 一万円,五千円,千円の各紙幣(bill)の枚数 500円,100円,50円,10円,5円,1円の各硬貨(coin)の 枚数 合計金額(amount) ⇒ 構造体のメンバ? 100 100 100 100 moneychanger.c 50 10 10 10 5 5 5 5 500 6 両替問題の考え方 知りたい情報,行いたい操作 紙幣・貨幣がそれぞれ何枚ある(入金された,出金しないとい けない)かを知る 合計金額を求める 両替する • 両替前の「紙幣・貨幣の枚数の情報」に対して, 両替後の「紙幣・貨幣の枚数の情報」を求める 7 両替問題のプログラミング(1) 金銭構造体 struct money { int bill_10000, bill_5000, bill_1000; int coin_500, coin_100, coin_50, coin_10, coin_5, coin_1; }; • • 8 両替問題のプログラミング(2) 定義した関数 void print_money(struct money *moneyp); • 枚数と総額を出力する int calc_amount(struct money *moneyp); • 総額を求める struct money *change_money(struct money *moneyp); • 両替する いずれの関数も,構造体ポインタを引数にとる 関数内では,「moneyp->メンバ名」でアクセスする 9 プログラムの読み方(1) 定義/宣言/参照しているヘッダファイル・型・変数・関数の 意味と関連付けを考えながら読む ⇒静的分析 変数に具体的な値を与える.各行でどんな処理が行われ, オブジェクト(メモリ)の中身がどのように変わっていくか考え ながら読む ⇒動的分析 10 プログラムの読み方(2) 技法(手段)に着目する ファレイ数列の問題では,再帰…全体と,その一部分とが相似 関係になっている 両替問題では,グリーディ法(貪欲法)…1万円札から順に枚数 を求める 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
© Copyright 2024 ExpyDoc