プログラミングおよび実習II/20051110 の変更点

追加された行はこの色です。
削除された行はこの色です。
プログラミングおよび実習II/20051110 へ行く。
[ [[高橋のページ:http://tortoise1.math.ryukoku.ac.jp/~takataka/index-j.html]] ]
[ [[プログラミングおよび実習II]] ]

*プログラミングおよび実習II 2005年11月10日

#contents

**今日の課題: ヒープソート

[[解答例>プログラミングおよび実習II/解答例#ex1110]]

***課題1110-A （締切:11月10日，延長不可）

11月9日の演習問題を提出しチェックを受けて下さい．

***課題1110-B （締切:11月17日）

整数のデータが与えられたときに，

+ それを配列に格納する
+ それらをヒープソートで並べかえる
+ できた配列の内容を表示する

というプログラムを作りましよう．名前は heapsort.c としてください．
これまでの selectionsort.c などと同様に，

- データの数は最大100個
- まずデータの数を入力し，次に各データを順番に入力する

こととします．ただし，以下のことに気をつけて作成して下さい．

- データの並べかえには，課題1110-Aで紙に書いた関数 Heap&#x0053;ort() と11月2日に書いた関数 Down&#x0048;eap() を使う
- Heap&#x0053;ort() の中では，関数 Down&#x0048;eap() を呼び出した直後に  Print&#x0044;ata2() を呼ぶようにして，並べかえの途中経過がわかるようにして下さい．こんな感じでいい感じ
 printf("ヒープ作ってます♪\n");
 for(...){
   DownHeap(...);
   PrintData2(...);
 }
 printf("\n");
 
 printf("ならべかえてます♪\n");
 for(...){
   交換
   DownHeap(...);
   PrintData2(...);
 }

***課題1110-C （締切:11月17日，1110-A,Bを11月10日に提出した人のみ対象のボーナス課題）

以下の二つのプログラムを作成し動作確認して下さい．

+ フィボナッチ数(Fibonacci number)を計算するプログラム fibonacci.c
--自然数nの値を入力するとフィボナッチ数F(n)を計算して表示する
--F(n)の計算には，「int型の引数を一つ渡すとフィボナッチ数F(n)をint型で返す関数 Fibonacci() 」を使う
--Fibonacci()は，再帰呼び出しを使って定義する
--F(n)の定義は，
---F(n) = F(n-1) + F(n-2) 　　　nが3以上の自然数のとき
---F(2) = 1
---F(1) = 1
--ちなみに，F(10) = 55, F(20) = 6765
+ 二つの自然数の最大公約数(Greatest Common Divisor: GCD)を求めるプログラム gcd.c
--二つの自然数aとbを入力するとその最大公約数を計算して表示する
--最大公約数の計算には，「int型の引数を二つ渡すとそれらの最大公約数をint型で返す関数 GCD()」を使う
--GCD()は，ユークリッドの互除法に基づき再帰呼び出しを使って定義する

ユークリッドの互除法のアルゴリズムについては解説しません（検索エンジンで「互除法」「再帰」をキーワードに検索してみるとよいでせう）が，

GCD(a, b) = a　　　　　　　　　　　　　bが0のとき~
GCD(a, b) = GCD(b, aをbで割った余り) 　上記以外のとき

です．