2013 Data Structures and Algorithms


コードを次のように変更してみよう。
  1. 1ではなく2が何個含まれているかを数えてみよう。
#include <stdio.h>
#include <stdlib.h>
 
int num_of_one(int value) {
    int ret;
    /* valueを次々に10で割って桁をずらしながら,
        最下位の桁が1であるかどうかを調べていく */
    for(ret = 0; value > 0; value /= 10) {
        if(value % 10 == 1) {
            ret++;
        }
    }
    return ret;
}
 
int main(void) {
    int i;
 
    scanf("%d", &i);
    printf("%d中に1は%d個含まれています\n", i, num_of_one(i));
    return EXIT_SUCCESS;
}



コードを次のように変更してみよう。
  1. 1ではなく4が何個含まれているかを数えてみよう。
#include <stdio.h>
#include <stdlib.h>
 
int num_of_one(unsigned long value) {
    int ret;
    /* valueが0桁(もうこれ以上解析する桁がない) */
    if(value == 0) {
        return 0;
    }
    if(value % 10 == 1) {     /* いちばん下の位が1 */
        ret = 1;
    } else {
        ret = 0;
    }
 
    /* 10で割って桁を1つずらし,再びnum_of_one()で調べる */
    return ret + num_of_one(value / 10);
}
 
int main(void) {
    int i;
 
    scanf("%d", &i);
    printf("%d中に1は%d個含まれています\n", i, num_of_one(i));
    return EXIT_SUCCESS;
}



コードを次のように変更してみよう。
  1. 最大公約数が6になるようにデータを変えて、実行してみよう。
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 6
int N[MAX] = {98, 140, 84, 28, 42, 126};
 
int gcd(int a, int b) {
  /* 2つの数の最大公約数を、再帰呼び出しを使って求める */
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}
 
int multi_gcd(int n) {
  /* n==1(数が2つしかない)の場合は,普通にgcdを呼ぶだけ */
  if(n == 1) {
    return gcd(N[0], N[1]);
  }
 
  /* n > 1の場合は,N[n]と,N[0]..N[n-1]のgcd を呼び出す */
  return gcd(N[n], multi_gcd(n - 1));
}
 
int main(void) {
  printf("配列Nの最大公約数は%dです\n", multi_gcd(MAX - 1));
  return EXIT_SUCCESS;
}



コードを次のように変更してみよう。
  1. 再帰呼び出しを使わないように変更してみよう。そして、実行時間の差を調べよう。
#include <stdio.h>
#include <stdlib.h>
 
/* 0〜9 のべき乗を1度だけ計算して,下記の配列に結果を格納しておく。
    (CheckNumber()関数のなかで使用) */
unsigned long power[10] = {0};
 
/* 現在使用している数字群の個数 */
int number_using[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
 
/* numberのなかに,digit(0 〜9 の1桁の整数)が
   何文字あるか数える関数 */
int NumOfDigit(unsigned long number,unsigned long digit) {
    int ret;
    ret = 0;
 
    /* 0桁ならば0を返す(何も含まれていない) */
    if(number == 0) {
        return 0;
    }
 
    /* 1の位が"digit"であるかどうかのチェック */
    if(number % 10 == digit) {
        ret=1;      /* "digit"であれば,返値に1つ足す */
    }
 
    /* 10で割ることによって
       次の桁以降のチェックを再帰的に行う */
    ret += NumOfDigit(number / 10, digit);
 
    return ret;
}
 
void CheckNumber(void) {
/* 数字群を元に計算した結果の数字の個数が */
/* 元の数字群と同じだけ使われているかどうかのチェック */
/* 0は考慮しない */
    int i;
    unsigned long result;
    result = 0;
 
    /* 数字群を元に,計算結果を作成する */
    for(i = 1; i <= 9; i++) {
        result += power[i] * number_using[i];
    }
 
    /* 計算結果のなかの数字の個数が,
       数字群と同じかどうかチェックする */
    for(i = 1; i <= 9; i++) {
        if(NumOfDigit(result, i) != number_using[i]) {
            return;     /* 1つでも違えば,それは解ではない */
        }
    }
 
    printf("%lu \n", result);    /* 計算結果は,解である */
    return;
}
 
void MakeNumbers(int start, int kosuu) {
    int i;
 
    /* 10桁を越えた数字に開き直り数は存在しない */
    if(kosuu > 10) {
        return;
    }
    /* start〜9までの数を新たに生成する */
    for(i = start; i <= 9; i++) {
        /* 新しい数を末尾に追加する */
        number_using[i]++;
        /* それが開き直り数になるかどうかのチェック */
        CheckNumber();
        /* 追加した数の後ろにさらに1桁追加した場合を調べる */
        MakeNumbers(i, kosuu + 1);
        /* 先ほど追加した数を消す */
        number_using[i]--;
    }
}
 
int main(void) {
    unsigned long i, j, k;
 
    /* あらかじめべき乗数を計算して,power配列に保存する */
    /* 0の0乗は0なので,1から9まで計算すればよい */
    for(i = 1; i <= 9; i++) {
        k = 1;
        for(j = 0; j < i; j++) {
            k *= i;
        }
        power[i] = k;
    }
 
    /* 1を1つ使うという条件から始める */
    MakeNumbers(1, 1);
 
    return EXIT_SUCCESS;
}