段階的詳細化

・二分法
・万年カレンダー
・マージソート
・順列の辞書式配列 

---

二分法

#include ＜stdio.h> int main( ){     double a, eb, y;     <* その他の宣言 *>     printf("a="); scanf("%lf", &a);     printf("eb="); scanf("%lf", &eb);     while(1){         <* y*y ≒ a である y を計算 *>         <* |誤差|＜eb ならば break *>     }     printf("a の平方根は %f\n", y);     fflush(stdin); getchar( );     return 0; }

キー入力した整数 a の値の平方根の近似値を、所望の精度で計算する左記のプログラムを完成せよ。

☆ a' ≦ a ≦ a" である a' を a の下界(lower bound)、a" を a の上界(upper bound)という。
  a' ≦ a ≦ a" かつ a' ≦ y ≦ a" ならば a' - a" ≦ y - a ≦ a" - a' すなわち |y - a| ≦ a" - a'。
☆ 例外処理は省略。//if(a ＜= 0 || eb ＜= 0){return 0;}
☆ まず a == 2 の数値例で考える。

---

#include ＜stdio.h> int main( ){     double a, eb, y;     double lb=1, ub=2;     printf("a="); scanf("%lf", &a);     printf("eb="); scanf("%lf", &eb);     while(1){         <* y*y ≒ 2 である y を計算 *>         if(ub-lb < eb){break;}     }     printf("2 の平方根は %f\n", y);     fflush(stdin); getchar( );     return 0; }

2 の平方根を計算して表示する左記のプログラムを完成せよ。

☆ 1*1 < 2 < 2*2               (1 + 2)/2 = 3/2                  9/4 > 2
    1 < 2 < 9/4                   (1 + 3/2)/2 = 5/4               25/16 < 2
    25/16 < 2 < 9/4             (5/4 + 3/2)/2 = 11/8         121/64 < 2
    121/64 < 2 < 9/4           (11/8 + 3/2)/2 = 23/16      529/256 >  2
    121/64 < 2 < 529/256    (11/8 + 23/16)/2 = 45/32  2025/1024 < 2
    1.40625 = 45/32 < sqrt(2) <  23/16 = 1.4375
★ ２分法による近似計算（ニュートン法に比べて収束が遅い）

---

while(1){     y = (lb + ub)/2;     if(y*y < 2){         lb = y;             }else{         ub = y;     }     if(ub-lb < eb){break;} } printf("sqrt(2) = %f\n", y);

<* y*y ≒ 2 である y を計算 *>

☆ 他の a でも同様。 
① a == 5 のときの lb, ub の初期値は？
② a の立方根の計算法は ？

---

万年カレンダー

#include ＜stdio.h> int main( ){     int year, month;     <* その他の宣言 *>     printf("年＝");     scanf("%d", &year);     printf("月＝");     scanf("%d", &month);     <* year年month月１日の曜日を計算 *>     <* カレンダーを画面に表示 *>     fflush(stdin); getchar( );     return 0; }

キー入力した年、月のカレンダーを表示する左記のプログラムを完成せよ。

☆ 2000 年 1 月 1 日は土曜日。
☆ year 年がうるう年ならば 1、そうでなければ 0 となる式は
        year%400 == 0 || (year%100 > 0 && year%4 == 0)

---

int m[13]={0, 1, -2, 1, 0, 1, 0,               1, 1, 0, 1, 0, 1 }; int u; //uruu int n, t, y; //nen, tsuki, youbi int k;

<* その他の宣言 *>  (必要に応じて追加)

n%400 == 0 || n%100 != 0 && n%4 == 0

<* n は閏年 *>

---

n = 2000; y = 6; while(n > year){     n--; u = <* n は閏年 *>;     y += 6 - u; y %= 7; } while(n < year){     u = <* n は閏年 *>;     y += 1 + u; y %= 7; n++; } u = <* n は閏年 *>; for(t = 1; t < month; t++){  if(t == 2){y += u;}  y += 2 + m[t]; y %= 7; }

<* year年month月１日の曜日を計算 *>

☆ 関数を学べば 「u = <* n は閏年 *>;」は「u = uruu(n);」

---

printf(" 日 月 火 水 木 金 土\n"); for(k = y; k > 0; k--) printf("   "); for(k = 1; k     printf("%3d", k);     if((k+y)%7 == 0) printf("\n"); }

<* カレンダーを画面に表示 *>

☆ 

---

マージソート

#include ＜stdio.h> int main( ){     int a[8]={7, 2, 5, 1,               4, 9, 6, 3};     int b[8], n, m;     <* その他の宣言 *>     for(n = 2; n ＜= 8; n += n){         for(m = 0; m < 8/n; m++){             <* a[k](n*m≦k＜n*m+n)             を並べ替えて b[k] に *>         }         <* a の値を b にコピー *>     }     <* a の値を画面に表示 *>     fflush(stdin); getchar( );     return 0; }

配列 a[8] のデータを小さい順に並べる次のプログラムを完成せよ。

☆ 次のように処理したい（マージソート）。
    (7)(2)(5)(1)(4)(9)(6)(3)
    (2, 7)(1, 5)(4, 9)(3, 6)
    (1, 2, 5, 7)(3, 4, 6, 9)
    (1, 2, 3, 4, 5, 6, 7, 9)
☆ (4, 9)(3, 6) から (3, 4, 6, 9) を作るとき a[i]（i = 4, 5）と a[j]（j = 6, 7）の小さい方を b[k]（k = 4, 5, 6）にする。
 (1) 「a[4] > a[6]」 だから 「b[4] = a[6];」
 (2) 「a[4] < a[7]」 だから 「b[5] = a[4];」
 (3) 「a[5] > a[7]」 だから 「b[6] = a[7];」
 (4) a[j] 側に残りが無いから 「b[7] = a[5];」

---

int i, j, k; while(<* a[i], a[j] に残りがある *>){     <* a[i], a[j] の小さい方を b[k]     にして、i, j, k を更新 *> } <* b[k] に残りをコピー *>

<* a[k](n*m≦k＜n*m+n)を並べ替えて b[k] に *>

☆

---

int i, j, k, n2, mn ;

<* その他の宣言 *>

n2 = n/2; mn = m*n; k = i = mn; j = mn + n2;  while(i < mn+n2 && j < mn+n)

while(<* a[i], a[j] に残りがある *>)

if(a[i] < a[j]){     b[k] = a[i]; k++; i++; }else{     b[k] = a[j]; k++; j++; }

<* a[i], a[j] の小さい方を b[k]にして、i, j, k を更新 *>

while(i < mn+n2){     b[k] = a[i]; k++; i++; } while(j < mn+n){     b[k] = a[j]; k++; j++; }

<* b[k] に残りをコピー *>

☆

---

順列の辞書式配列 

#include ＜stdio.h> int main( ){     char s[ ]="012345"; int n = 5;     int i, k; char c; //自由に使ってよい     <* 最小の順列を表示 *>     while(1){         if(<* 表示順列は最大 *>) break;         <* 直後の順列を求める *>         <* この順列を表示 *>     }     fflush(stdin); getchar( );     return 0; }

与えられた集合の要素を並べた順列を辞書式に配列する左記のプログラムを完成せよ。

☆ 順列 α 、β について、辞書式配列で α の方が β より前にあれば  α ＜ β と考える。
    最小の順列は "012345"、最大の順列は "543210" である。
☆ 順列 "312540" の直後の順列 "314025" は次のようにして得られる。
   (1) {'5', '4', '0'}の中で '2' の次に小さい '4' を選ぶ。
   (2) "314" の後に "520" を付ける。
   (3) "520" を反転して "025" にする。

---

for(k = n-1; k >= 0; k--){     if(s[k] < s[k+1]) break; } if(k < 0) break;

if(<* 表示順列は最大 *>) break;

for(i = n; i > k; i--){     if(s[i] > s[k]) break; } <* s[k]とs[i]の値を交換 *> <* s[k+1]からs[n]までを小さい順に *>

<* 直後の順列を求める *>

for(i = 0; i < (n-k)/2; i++){     c = s[k+1+i];     s[k+1+i] = s[n-i]; s[n-i] = c; }

<* s[i]からs[n]までを小さい順に *>

☆ 応用例（s[ ]="0123456789"）
 3094*7=21658
 3907*4=15628
 4093*7=28651
 5694*3=17082
 5817*6=34902
 6819*3=20457
 6918*3=20754
 7039*4=28156
 8169*3=24507
 9127*4=36508
 9168*3=27504
 9304*7=65128
 9403*7=65821

☆ 応用例（s[ ]="123456789": if(s[0] != '0'){continue;}で共用)
 5/34+7/68+9/12=1
 5/34+9/12+7/68=1
 7/68+5/34+9/12=1
 7/68+9/12+5/34=1
 9/12+5/34+7/68=1
 9/12+7/68+5/34=1

---