キャッシュ

IT関連教材の cache です。旧 URL のまま随時変更しています。

文字列の操作

2014-04-20 21:51:40 | 教材


文字列の結合
文字列の移動
文字列の置換
ポインタの配列


文字列の結合

 

#include stdio.h>
int main( ){
    char s[80]="ABCDE", *p="XYZ";
    int k;
    for(k = 0; /*あ*/; k++){;}
    while(/*い*/){
        s[k] = *p; k++; p++;
    }
    s[k] = '\0';
    printf("%s\n", s); 
    fflush(stdin); getchar( );
    return 0;
}

文字列sの後に文字列pを付け加える左のプログラムを完成せよ。


 

☆ 文字列の末尾は「'\0'」で表示('\0' == 0)。
★ 「while(*p){s[k++]=*p++;}」でもよい。


文字列の移動

 

#include stdio.h>
int main( ){
    char s1[80]="ABCDE";
    char s2[ ]=/*か*/; int k, n;
    <* s2 の長さを n に設定 *>
    <* s1 の位置を n 文字だけ移動 *>
    <* s1 の先頭に s2 を埋め込む *>
    printf("s1 = %s\n", s1); 
    fflush(stdin); getchar( );
    return 0;
}

文字列s2の初期値/*か*/"XYZ"とし,文字列s1の前にs2を挿入する左のプログラムを完成せよ。


 

☆ <* s2 の長さを n に設定 *>文字列の結合 の for文 と同様。
☆ <* s1 の先頭に s2 を埋め込む *>文字列の結合 の while文 と同様。
◎ <* s1 の位置を n 文字だけ移動 *> は,移動前と移動後の領域が重複する場合要注意。0<n<m のときの移動は
  ---------------------------
  for(k = 0; k = m; k++){s[k] = s[k+n];} /* s[n+m] == '\0' */
  for(k = m; k >= 0; k--){s[k+m] = s[k];} /* s[m] == '\0' */
  ---------------------------
★ 標準ライブラリ関数の 「strcpy( )」は領域の重複を想定していない。


文字列の置換

 

#include stdio.h>
int main( ){
    char s1[80]=/*さ*/, s2[80];
    char *p1=s1, *p2=s2;
    while(*p1 != '\0'){/*し*/}
    *p2 = '\0';
    printf("%s\n", p2); 
    fflush(stdin); getchar( );
    return 0;
}

文字列s1の初期値を/*さ*/"543\n21\012345"とし,s1に含まれるすべての"\n""\r\n"に変換してs2に格納するプログラムを完成して実行結果を示せ。


 

☆ 「if(*p1 == '\n'){*p2 = '\r'; p2++;} *p2 = *p1; p1++; p2++;
☆ 実行結果は『543』『21』『345』(3行)。
"\012"(8進数による表示)は"\n"と同じ。
★ 標準ライブラリ関数の 「strncmp(cs, ct, n)」は「ct」,「cs」からの「n」文字を比較する。


ポインタの配列

 

#include stdio.h>
int main( ){
    char s[80]="Spring Summer "
               "Autumn Winter ";
    char *p[4], *q=s; int k=0;
    while(k < 4){
        p[k] = q; k++; q++;
        while(/*た*/){q++;}
        *q = '\0'; q++;
    }
    for(k = 0; k < 4; k++){
        printf("%s\n", p+k); 
    }
    fflush(stdin); getchar( );
    return 0;
}

文字列sの文字' ''\0'に変換して,分割された文字列のアドレスをポインタの配列に格納する左のプログラムを完成せよ。 
注: 「"Spring Summer " "Autumn Winter "」は
     「"Spring Summer Autumn Winter "」と同じ。

☆ 2次元配列char s2[4][8];の「s2[k]」に「p[k]」に対応する文字列置くには1文字ずつコピーが必要。
★ 「p[1] = "Summer";」を実行すると,適当な場所に文字列「"Summer"」を作成してその(先頭)アドレスを「p[1]」に設定する。


 


ポインタ

2014-04-20 08:25:34 | 教材


配列要素のアドレス
ポインタの宣言
ポインタによる参照


配列要素のアドレス

 

#include stdio.h>
int main( ){
    char s[8]=/*あ*/;
    int m[4]=/*い*/;
    printf("s = %d, ", s);
    printf("s+1 = %d, ", s+1);
    printf("&s[1] = %d\n", &s[1]);
    printf("&s[1]-s = %d\n",
            &s[1]-s);
    printf("m = %d, ", m);
    printf("m+1 = %d, ", m+1);
    printf("&m[1] = %d\n", &m[1]);
    printf("&m[1]-m = %d\n",
            &m[1]-m);
    fflush(stdin); getchar( );
    return 0;
}

初期値/*あ*//*い*/を次の各値にしたときの実行結果を示せ。
(1) "ABC"{48, 49, 50}
(2) "012"{65, 66, 67} 

 

◎ 「s」や「m」の値は状況によって異なるが,「&s[1]」は「&s[0](==s)より1(==sizeof(char))大きく,「&m[1]」は「&m[0]」より4(==sizeof(int))大きい。(1)の実行結果は,例えば
  ----------------------
  s = 3668520, s+1 = 3668521, &s[1] = 3668521

  &s[1]-s = 1
  m = 3668496, m+1 = 3668500, &m[1] = 3668500
  &m[1]-m = 1
  ------------------------
のようになる。「&m[1]-m」の値が4でなく1であることに注意。
★ アドレスの表示には「"%p"」を用いるが16進表示になる --- 分かりやすいように 「"%d"」を使用。
☆ 「m+(&m[1]-m) == m+1」であるから辻褄は合っている。しかし(当然ながら)「(m+&m[1])-m」はエラー --- アドレスの和や積は無意味,アドレスの差は整数。
★ 「int k0, k1; k0 = &m[0]; k1 = &m[1]; printf("%d\n", k1-k0);」を実行すると (警告は出るが,ビルドされ) 『4』が表示される。


ポインタの宣言

 

#include stdio.h>
int main( ){
    char s[8]=/*あ*/, *p=s+1;
    int m[4]=/*い*/, *q=m+1;
    printf("s = %d, ", s);
    printf("p = %d, ", p);
    printf("*p = %c\n", *p);
    printf("m = %d, ", m);
    printf("q = %d, ", q);
    printf("*q = %d\n", *q);
    fflush(stdin); getchar( );
    return 0;
}

初期値/*あ*//*い*/を次の各値にしたときの実行結果を示せ。
(1) "ABC"{48, 49, 50}
(2) "012"{65, 66, 67} 

 

☆ (1)の場合,例えば
  -------------------------
  s = 3864612, p = 3864613, *p = B
  m = 3864576, q = 3864580, *q = 49
  -------------------------
◎ 「char *p=s+1;」は「char *p; p=s+1;」と同じで,「*p」は「s[1]」に等しい。「*q」についても同様であり,一般に「*(p+k) == p[k]」,「p+k == &p[k]


ポインタによる参照

 

#include stdio.h>
int main( ){
    char s[8]=/*あ*/, *p=s+1;
    int m[4]=/*い*/, *q=m+1;
    printf("p[-1] = %c, ", p[-1]);
    printf("p[0] = %c, ", p[0]);
    printf("p[1] = %c, ", p[1]);
    p[-1] = *p; *p = p[1];
    printf("p[-1] = %c, ", p[-1]);
    printf("p[0] = %c, ", p[0]);
    printf("p[1] = %c, ", p[1]);
    for(p = s; *p != '\0'; p++){
        printf("*p = %c\n", *p)
    } 
    fflush(stdin); getchar( );
    return 0;
}

初期値/*あ*//*い*/を次の各値にしたときの実行結果を示せ。
(1) "ABC"{48, 49, 50}
(2) "012"{65, 66, 67} 

 

☆ (1)の実行結果は『p[-1] = A, p[0] = B, p[1] = C』『p[-1] = B, p[0] = C, p[1] = C』『*p = B』『*p = C』『*p = C
◎ 「p[k]」は 0 ≦ k < 8 でなくても使えることに注意 --- 「p[-1] = *p;」を「p[-100] = *p;」で置換してもビルド時にエラーにならない (プログラムを壊す場所が悪いと実行時エラーになって気づくが,誤った計算をしたまま気づかない可能性もある).
★ 「p = q; printf("p[-1] = %c, p[1] = %c\n", p[-4], p[4]);」を「getchar( );」の前に挿入しても警告が出るだけで,ビルドは“正常終了”で,実行結果に『p[-1] = 0, p[1] = 2』が追加される --- 「m[0]」, 「m[2]」 の最初の8ビットは 48 =='0', 50 =='2'


Prog3

2013-12-28 17:37:45 | 教材

#include <stdio.h>
int main( ){
//
    char s[ ]="012345"; int n = 5;
    int i, k; char c;
    printf("%s\n", s);
    while(1){
        for(k = n-1; k >= 0; k--){
            if(s[k] < s[k+1]) break;
        }
        if(k < 0) break;
        for(i = n; i > k; i--){
            if(s[i] > s[k]) break;
        }
        c = s[k]; s[k] = s[i]; s[i] = c;
        for(i = 0; i < (n-k)/2; i++){
            c = s[k+1+i];
            s[k+1+i] = s[n-i]; s[n-i] = c;
        }
        printf("%s\n", s);
    }
/*-----------------------------------------
//
    int a[8]={7, 2, 5, 1, 4, 9, 6, 3};
    int b[8], n, m, n2, mn;
    for(n = 2; n <= 8; n += n){
        for(m = 0; m < 8/n; m++){
            n2 = n/2; mn = m*n;
            i = mn; j = mn + n2;
            while(i < mn+n2 && j < mn+n){
                if(a[i] < a[j]){b[k] = a[i]; k++; i++;}
                else{b[k] = a[j]; k++; j++;}
            }
            while(i < mn+n2){b[k] = a[i]; k++; i++;}
            while(j < mn+n){b[k] = a[j]; k++; j++;}
        }
        for(k = 0; k < 8; k++){a[k] = b[k];}
    }
    for(k = 0; k < 8; k++){
        printf("%d, ", a[k]);
    }
    printf("\n");
//
    int year, month;
    int m[13]={0, 1, -2, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1 };
    int u, n, t, y;// uruu, nen, tsuki, youbi
    int k;
    printf("年=");
    scanf("%d", &year);
    printf("月=");
    scanf("%d", &month);
    n = 2000; y = 6;
    while(n > year){
        n--;
        u = n%400 == 0 || n%100 != 0 && n%4 == 0;
        y += 6 - u; y %= 7;
    }
    while(n < year){
        u = n%400 == 0 || n%100 != 0 && n%4 == 0;
        y += 1 + u; y %= 7; n++;
    }
    u = n%400 == 0 || n%100 != 0 && n%4 == 0;
    for(t = 1; t < month; t++){
        if(t == 2){y += u;}
        y += 2 + m[t]; y %= 7;
    }
    //printf("n = %d, t = %d, y = %d\n", n, t, y);
    printf(" 日 月 火 水 木 金 土\n");
    for(k = y; k > 0; k--) printf("   ");
    for(k = 1; k <= 30 + m[t]; k++){
        printf("%3d", k);
        if((k+y)%7 == 0) printf("\n");
    }
//
    double a, eb, y;
    double lb=0, ub;
    printf("a="); scanf("%lf", &a);
    if(a <= 0) return 0; ub = a;
    printf("eb="); scanf("%lf", &eb);
    while(1){
        y = (lb + ub)/2;
        if(y*y < a){lb = y;}
        else{ub = y;}
        if(ub-lb < eb){break;}
    }
    printf("a の平方根は %f\n", y);
//
    double x[10], y;
    int m[10], n, k;
    printf("y = "); scanf("%lf", &y);
    printf("n = "); scanf("%d", &n);
    if(n > 1000){return 0;}
    x[0] = y; m[0] = 1;
    for(k = 0; n > m[k]; k++){
        x[k+1] = x[k]*x[k];
        m[k+1] = m[k]*2;
    }printf("%d\n", k);
    k--;
    for(y = 1; n > 0; k--){
        if(n >= m[k]){
            y *= x[k]; n -= m[k];
        }
    }
    printf("y^n = %e\n", y);
/*-----------------------------------------
//
    double x[10], y;
    int m[10], n, k;
    printf("y = "); scanf("%lf", &y);
    printf("n = "); scanf("%d", &n);
    x[0] = y; m[0] = 1;
    for(k = 0; n > m[k]; k++){
        x[k+1] = x[k]*x[k];
        m[k+1] = m[k]*2;
    }
    k--;
    for(y = 1; n > 0; k--){
        if(n >= m[k]){
            y *= x[k]; n -= m[k];
        }
    }
    printf("y^n = %f\n", y);
//
    int m[10], n1, n2, n3, k;
    for(k = 0; k < 10; k++){
        printf("m[%d] = ", k);
        scanf("%d", &m[k]);
    }
    n1 = 0;
    if(m[n1] >= m[1]){
        n1 = 1; n2 = 0;
    }else{n2 = 1;}
    if(m[n1] >= m[2]){
        n3 = n2; n2 = n1; n1 = 2;
    }else if(m[n2] >= m[2]){
        n3 = n2; n2 = 2;
    }else{
        n3 = 2;
    }
    for(k = 3; k < 10; k++){
        if(m[n1] >= m[k]){
            n3 = n2; n2 = n1; n1 = k;
        }else if(m[n2] >= m[k]){
            n3 = n2; n2 = k;
        }else if(m[n3] >= m[k]){
            n3 = k;
        }
    }
    if(m[n3] > m[n2] &&
       m[n2] > m[n1])
    {
        printf("ブービーは %d\n", n2);
    }else{
        printf("ブービーはなし\n");
    }
//
    char s[80]="Hello, world.";
    int k, n=0;
    while(s[n] != 0){n++;}
    if(n > 75){return 0;}
    for(k = n - 1; k >= 0; k--){
        s[k+4] = s[k];
    }
    for(k = 0; k < 4; k++){
        s[k] = ' ';
    }
    printf("%s\n", s);
//
    int m[10], k, n;
    double a, v, y;
    for(y = k = 0; k < 10; k++){
        printf("m[%d] = ", k);
        scanf("%d", &m[k]);
        y += m[k];
        if(m[k] == 0){break;}
    }
    if(k == 0){return 0;}
    n = k; a = y / n;
    for(y = k = 0; k < n; k++){
        y += (m[k] - a)*(m[k] - a);
    }
    v = y / n;
    printf("%f, %f\n", a, v);
//
    char s[40], c; int n, k=0;
    printf("n = "); scanf("%d", &n);
    while(n > 0){
        s[k] = n % 2; n /=2; k++;
    }
    while(k > 0){
        k--; printf("%d", s[k]);
    }
    printf("\n");
//
    char s[40], c; int n, k=0;
    printf("n = "); scanf("%d", &n);
    while(n > 0){
        s[k] = n % 2; n = n / 2; k++;
    }
    while(k > 0){
        k--; printf("%d", s[k]);
    }
    printf("\n");
//
    char s[80]=
        "Good morning.  \0"       
        "Good afternoon.\0"       
        "Good night.    \0"
        "Good bye.      \0";
    char c; int k;
    printf("c = "); scanf("%c", &c);
    switch(c){
        case 'm': k = 0; break;
        case 'a': k = 16; break;
        case 'n': k = 32; break;
        default: k = 48;
    }
    printf("%s\n", s+k);
//
    int m1[4]={3, 2, 5, 6};
    int m2[4], n=1380;
    if(n/500 < m1[0]){m2[0] = n / 500;}
    else{m2[0] = m1[0];}
    n -= m2[0]*500;
    if(n/100 < m1[1]){m2[1] = n / 100;}
    else{m2[1] = m1[1];}
    n -= m2[1]*100;
    if(n/50 < m1[2]){m2[2] = n / 50;}
    else{m2[2] = m1[2];}
    n -= m2[2]*50;
    m2[3] = n / 10;
    printf("500円:%d枚\n", m2[0]);
    printf("100円:%d枚\n", m2[1]);
    printf(" 50円:%d枚\n", m2[2]);
    printf(" 10円:%d枚\n", m2[3]);
//
    double a, b, c, y;
    printf("三角形の三辺の長さを長い順"
           "に入力:\n");
    scanf("%lf %lf %lf", &a, &b, &c);
    printf("三角形は");
    if(a >= b && b >= c && c > 0){
        y = a*a - b*b - c*c;
        if(y < 0){
            printf("鋭角三角形\n");
        }else if(y == 0){
            printf("直角三角形\n");
        }else{
            printf("鈍角三角形\n");
        }
    }else{
        printf("不当なデータ\n");
    }
//
    int m1[4]={3, 2, 5, 6};
    int m2[4], n=1380;
    m2[0] = n/500; n -= m2[0]*500;
    if(m2[0] > m1[0]){
        m2[0] = m1[0];
    }
    printf("500円:%d枚\n", m2[0]);
    printf("100円:%d枚\n", m2[1]);
    printf(" 50円:%d枚\n", m2[2]);
    printf(" 10円:%d枚\n", m2[3]);
-----------------------------------------*/
    fflush(stdin); getchar( );
    return 0;
}


段階的詳細化

2013-12-28 17:32:44 | 教材

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


二分法

 

#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
2分法による近似計算(ニュートン法に比べて収束が遅い)


 

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月1日の曜日を計算 *>
    <* カレンダーを画面に表示 *>
    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月1日の曜日を計算 *>

 

☆ 関数を学べば 「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


 


繰り返し

2013-12-08 14:39:17 | 教材

 


問: 与えられた整数の配列 a[4] の要素の値の総和を表示するプログラムを示せ。ただし、初期値は適当に設定してよい。

考え方: sum = a[0] + a[1] + a[2] + a[3];のような式では大きい配列に使いづらいので {sum = sum + a[i];}の繰り返しで計算する。 

#include stdio.h>
int main( ){
    int a[4]={3, 7, -2, 5};
    int i, sum;
    sum = a[0];
    <* i=1 to 3 *>{
        sum = sum + a[i];
    }
    printf("総和は %f\n", S);
    return 0;
}

 

#include stdio.h>
int main( ){
    int a[4]={3, 7, -2, 5};
    int i, sum;
    sum = a[0];
    for(i = 1; i < 4; i = i+1){
        sum = sum + a[i];
    }
    printf("総和は %f\n", S);
    return 0;
}

<* i=1 to 3 *>{sum = sum + a[i];}
     <* 順に実行 *>{
        sum = sum + a[1];
        sum = sum + a[2];
        sum = sum + a[3];
   }
  の意味。書きかえると
     <* 順に実行 *>{
        i = 1; sum = sum + a[i];
        i = 2; sum = sum + a[i];
        i = 3; sum = sum + a[i];
   }
  。すなわち 1 ≦ i ≦ 3  の範囲で
sum = sum + a[i];を繰り返す。
i = i+1よりi++を使うことが多い。
for(i = 1; i < 4; i = i+1){sum = sum + a[i];}
   i = 1;
   while(i < 4){
       sum = sum + a[i];
       i = i+1;
   }
 
 と同じ。したがって for(i = 1; i = 3; i = i+1)等でもよい。  


擬似コード<* i=m to n *>に関する補足:

<* i=m to n *> は Algol の for i := m step 1 until n do に対応する基本的な繰り返し構造で、BASIC ではFOR I = 1 TO 3 と書く(末尾にNEXT)。 K&R2, p.74 でも for(i = 0; i < n; i++) を “これは Fortran の DO ループや、Pascal の for と同様な、配列の最初の n 要素を処理するための C の慣用句である” と書かれている。 しかし、一般形 for(式1; 式2; 式3){文}
    式1; while(式2){文 式3;}
すなわち

    (1) 「式1;」を実行。
    (2) 「式2」 でなければ (5) へジャンプ。
    (3) 「文」「式3;」 を実行。
    (4) (2) へジャンプ。
    (5) 次へ進む。

と等価であり、処理の流れを見にくい。 for(i = 0; i < n; i++) を使うときは初期化 「i = 0;」 が終了した直後は 「i < n」 であるから、このような場合は
    式1; do{文 式3;}while(式2);
すなわち

    (1) 「式1;」を実行。
    (2) 「文」「式3;」 を実行。
    (3) 「式2」 でなければ (2) へジャンプ。

に対応させると分かり易くなる。例えば <* i=1 to 3 *>{sum = sum + a[i];}
    i = 1; do{sum = sum + a[i]; i++;}while(++i = 3);

★ コンマ演算子を使えば 式1; do{文}while(式3,式2); (K&R2, p.258)。
★ 一般形の別表現は 式1; if(式2)do{文 式3;}while(式2);
   break 文を使えば  式1; while(1){if(式2) break; 文 式3;} 


問: 与えられた文字の配列 s[80] に書かれている文字列の長さを表示するプログラムを示せ。ただし、初期値は適当に設定してよい。

考え方: 文字列の最後に '\0' があるから、これを s[0]、s[1]、・・・を順に調べ、s[k] == '\0'となる k が見つかれば長さは k 。

#include stdio.h>
int main( ){
    char s[80]="Hello!";
    int k=0;
    <*s[k] != '\0'の間 *>{
        k = k+1;
    }
    printf("長さは %d\n", k);
    return 0;
}

 

#include stdio.h>
int main( ){
    char s[80]="Hello!";
    int k=0;
    while(s[k] != '\0'){
        k = k+1;
    }
    printf("長さは %d\n", k);
    return 0;
}

<*s[k] != '\0'の間 *>{k = k+1;}<*
      (1) s[k] != '\0'でなければ(3)にジャンプ。
      (2) k = k+1;を実行して(1)に戻る。
      (3) 次へ進む。
   *> を意味する。この場合の“次”は「printf("長さは %d\n", k);
while(s[k] != '\0')for(;s[k] != '\0';)と同じ。
while(s[k] != '\0'){k = k+1;}は「while(s[k++]);」と同じ。


問: 整数の配列 m[100] にテストの点数をキー入力して、平均点を表示するプログラムを示せ。ただし、テストの答案数は100以下で、答案がなくなったときは -1 をキー入力することを前提にする。

考え方: キー入力の値が繰り返しの有無を定めるので do-while 文が適している。

#include stdio.h>
int main( ){
    int m[100], k;
    double x;
    printf("データ:\n");
    k = 0; x = 0;
    {
        scanf("%d", &m[k]);
        x = x + m[k]; k++;
    }<*m[k] >= 0の間 *>;
    k--; if(k == 0){return 0;}
    printf("平均値は %f\n", x/k);
    return 0;
}

 

#include stdio.h>
int main( ){
    int m[100], k;
    double x;
    printf("データ:\n");
    k = 0; x = 0;
    do{
        scanf("%d", &m[k]);
        x = x + m[k]; k++;
    }while(m[k] >= 0);
    k--; if(k == 0){return 0;}
    printf("平均値は %f\n", x/k);
    return 0;
}
 

{・・・}<*m[k] >= 0の間 *>;m[k] >= 0である間は{・・・}を繰り返す。
k++;k = k + 1;と、k--;k = k - 1;と同じ。
if(k == 0){return 0;}は(データ 0 個の)例外処理。
x = 0; k = 0;x = k = 0;でもよい。
do{scanf("%d", &m[k]); x = x + m[k]; k++;}while(m[k] >= 0);
    scanf("%d", &m[k]);
    while(m[k] >= 0){x = x + m[k]; k++; scanf("%d", &m[k]);}
  や、break 文を用いた
    while(1){
        scanf("%d", &m[k]); x = x + m[k]; k++;
        if(m[k] < 0){break;
    }
  と同じ。