◎第5回 段階的詳細化

○テキスト
3章(3.3-3.4)
◇下へ・一覧へ
○「段階的詳細化」とは何か
これまでの例の大部分は計算式があって計算する形
(最大値最小値はちょっと違う)
複雑になるとどこから手をつけてよいのかわからなくなる。
→系統的な方法が必要
  段階的詳細化

  まず、処理の大枠を決めてから、
  徐々に細かい所を決めていき、
  最後に、自然にプログラムになる。
(この簡単な例は、第3回に反復処理のアルゴリズムを作成する時に
すでに示してある)

  トップダウン ( top down )「上から下へ」
          ←→ ボトムアップ ( bottom up )「下から上へ」
               必要と考えられる部分を作り、
               組み合わせて行く。

◇下へ・上へ
・テキストでは打撃十傑を求める場合で
  段階的詳細化を説明している。
{
  1.データの入力 ;
  2.処理する     ;
  3.結果の出力(表示) ;
}

※ 多くのプログラムはこの形

  1.データを入力する
          ↓
  {
    1.1 規定打席数を読む ;
    1.2 全選手の打撃成績を読む ;
  }
  1.2 全選手の打撃成績を読む ;
          ↓
  while( 選手がまだ残っている ){
     1.2.1 次の選手の打撃成績を読む ;
  }

◇下へ・上へ
  2. 処理する
       ↓
{
  2.1 打席数が規定打席数に満たない選手を除く ;
  2.2 残った選手について、、打率を計算する   ;
  2.3 打率が大きい順に上位 10 人を求める     ;(後に詳述)
}

  3.結果の出力(表示) ;
       ↓
  3.1 見出しの表示 ;
  3.2 for( i=1 ; i<=10 ; i++ ){
        3.2.1 打撃順位 i の選手の選手名と打撃成績を表示する ;
      }

◇下へ・上へ
この段階的詳細化をを発展させると
構造化プログラミング
下降型プログラミング
につながる。

・テキストの電話をかける例
  ダイアルを回す。
      国番号をを回す
      市外局番を回す
      市内局番を回す
      加入番号を回す

   市外局番を回す→ 
   第1数字を回す
   第2数字を回す
   ...

◇下へ・上へ
○ソート(整列)
(テキスト例題 3.3)
  n 個の数値 a[1],...,a[n]がある。
  大きい順に並べ変えよ。
 (データがすでに入っているものと
 してする入力・出力は今は考えない)

 方針: 
 1. a[1],...,a[n]の中から最大値を求め、
    それと a[1]を入れ換える。
 2. 1の結果得られる a[2],...,a[n] の中
    から最大値を求め、それとa[2]を入れ換える。
    ...
{
 for( i=1 ; i<=n-1 ; i=i+1 ){
    1. 最大値を求めて入れ換える。
 }
}

◇下へ・上へ
1. 最大値を求めて入れ換える。
          ↓
  {
   1.1 最大値を求める。
   1.2 入れ換える。
  }

1.1 最大値を求める。( 第3回演習(d)参照 )
    a[i]からa[n]の中から最大値を求める。
          ↓
  {
     a[i]を仮の最大値とする ;
     while(  a[i] の次のから最後のデータまで ){
        if( データが仮の最大値より大きい ){
	    仮の最大値をそのデータで置き換える ;
        }
     }
  }
          ↓
  {
     max=a[i] ;
     for( j=i+1 ; j<=n ; j=j+1 ){
        if( a[j]>max ){            
           max=a[j];
        }
     }
  }

◇下へ・上へ
 1.2 入れ換える。
   1.2.1 a[i]を max とする。
   1.2.2 ?? を a[i] とする。
     a[j]のどれが max になったのか ?
    入れ換えるには何番目の要素が
    max を与えるのかが
    わからないといけない!!

    max を与える要素の番号 jmax を求めるように
    1.1 を修正

◇下へ・上へ
1.1' 最大値を求める。
     a[i]からa[n]の中から「最大値を与える添字」を求める。
     (ついでにその最大値も)
          ↓
  {
     max=a[i] ;
     jmax=i   ;
     for( j=i+1 ; j<=n ; j=j+1 ){
        if( a[j]>max ){
           max=a[j];
           jmax=j;
        }
     }
  }

◇下へ・上へ
 1.2 入れ換える。
        ↓
 {
   1.2.1 a[jmax]をa[i] とする。;
   1.2.2 a[i]を max とする。;
 }
        ↓
 {
   a[jmax]=a[i];
   a[i]=max;
 }

◇下へ・上へ
・分割された各段階間でのどんなデータの受渡しが必要かが重要
  分割された各処理は、まったく独立でないので、あとの段階に何が必要で
  それは、どの段階で作られるかを考える。

◇下へ・上へ
○演習
  上に示したデータを大きい順(降順)にソートするアルゴリズム全体をまとめ、
  PAD と 擬似コードで記述すると次のようになる。それぞれ空欄を埋めよ。
  ・降順ソートのアルゴリズムのPADと疑似コードを次に示す。
  PAD(psfile)・擬似コード
  これに、宣言と入出力を加えて、C プログラムにすると次のようになる。
  空欄を埋めてプログラムを完成し、コンパイル・実行せよ。
 ・降順ソートのCプログラム C プログラム

◇一覧へ・上へ
○レポート課題(解答)
1.データを小さい順(昇順)にソートするアルゴリズムを作成する場合の段階的
  詳細化の過程を説明せよ。各段階のアルゴリズムは、 PAD または 擬似コー
  ドで記述して説明せよ。(図等を含む文章をレポートとして書くこと)
2. nibunhou.ps は2分法によって方程式 f(x)=0 を解くためのプログラムを
  段階的詳細化により作成する過程を説明したものである。
  空欄を埋めて説明を完成させよ。空欄を埋める内容だけでなく、その理由も
  書くこと。
  また、完成したプログラムをコンパイル・実行し、動作を確認せよ。
  実行時には、a には 1 を, b には 3.14を, epsilon には、1e-6 を
入力すること。結果として得られる値は、何か考えよ。
( 1e-6 は 「1×10の-6乗」を意味する )
(空欄のあるプログラムは ~eenagai/ic2/nibun.c にある。)