情報処理II

情報処理Ⅱ
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