課題 1.7 2013年度情報オリンピック予選問題2
(2015.9.27の実習問題. 1回目の実習の最後の問題)

• 上の文字列str中、２番目の動物を表示する。

解答例 (制限時間は60分)


#include <stdio.h>

int main(void) {

    int n, m, i, check; /* n番目 mは部屋のカウンタ, iは部屋番号 */

    scanf("%d", &n); /* n番目を入力 */

    m = 0; /* 累計m号室目 */
    for (i = 1; ; i++) { /* 外側のループは部屋番号 i */
        check = i;

        /* 各桁に4,9が含まれないかをチェック。問題なければ0になる計算 */
        while (check != 0) {
            if (check %10 == 4 || check % 10 == 9)
                break;
            check /= 10;
        }

        if (check == 0) /* その部屋番号i をカウントする場合 */
            m++;        /* 1部屋増やす。checkが0でない部屋番号は使わないので、カウントしない */

        if (m==n) /* mがn番目に到達 。forループを抜ける */
            break;
    }

    printf("\n%d\n", i); /* 部屋番号 i を出力 */

    return 0;
}

もう一つの方法
/*
数える　  1 2 3 4 5 6 7  8  9  10 11  12　
部屋番号  1 2 3 5 6 7 8 10 11  12
  
8を基準にして部屋番号を振ることと同じ 8進数への変換 4と9を避けるために、4以上の値には+1する　
8番目の部屋には、部屋番号10 
*/
int main(void){

    int n, d, mul = 1, room = 0; /* 10進数 n室目は、8進数のroom室目 */

    scanf("%d", &n); /* n番目 */

    while (n > 0) {
        d = n % 8;   /* BASEは8 8進数へ変換。最後の桁 */
        if (d >=4)  /* 4より大きいければ、1つずらす */
            d++;
        room = d*mul + room; /* 8進数のmul桁目 */
        n = n / 8; /* 1つ桁を落として */
        mul *= 10; /* mul桁目 */
    }

    printf("%d\n", room); /* 現在の、部屋番号 i を出力 */

    return 0;

}

---------------
以下は、工夫のある方法　最初のアルゴリズムに対して、関数を使う。

#include <stdio.h>

/* どこかの桁に4,9があれば0。そうでなければ1。
             このような数は上の桁では連続する */
int checkok(int m){
    int j;

    while (m > 0) {
        j = m % 10; /* 1桁目を見る */
        if (j == 4 || j == 9) {
            return 0;
        } else {
            m = m / 10; /* 1桁目を切り捨てる */
        }
    }
    return 1;
}


int main(void){
    int n, m, i;  /* n番目、部屋のカウンターm、部屋番号i */

    scanf("%d", &n);

    m = 0; i = 0;

    while (m != n) {
        i++;
        while (checkok(i) == 0) i++;  /* 4,9のとき、番号は1つ増える */
        m++;
    }

    printf("%d\n",i);
}

8進数表現と部屋の番号の対応を配列を使って表現する。

#include <stdio.h>

/* 10進数nから、ansを計算 */
int main(void){
    int n;
    int d;
    int oct[]= { 0,1,2,3,5,6,7,8 }; /* 配列の添え字が8進 値が部屋に使う数 */
    int ans;

    d = 1;   /* 桁 */
    ans = 0; /* 部屋番号 */

    scanf("%d", &n);

    while (n > 0) {
        ans += oct[n % 8] * d;  /* nの1桁目 */
        n = n / 8;  /* 1桁目を捨てる */
        d *= 10; /* d桁目 */
    }

    printf("%d\n", ans);
}