[ 高橋のページ ] [ プログラミングおよび実習II ]

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

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

解答例

課題1110-A (締切:11月10日,延長不可)

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

課題1110-B (締切:11月17日)

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

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

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

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

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

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

  1. フィボナッチ数(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
  2. 二つの自然数の最大公約数(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で割った余り)  上記以外のとき

です.


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2014-08-13 (水) 13:45:19