C言語「見知らぬ国の数え方」
上位カテゴリ : C言語目次
a. GitHub
Q. ある国では二進法が使われています。しかし、その国の人々はゼロが連続する数字を嫌います。また、ゼロが連続する数字を数えるのも嫌いです。そのため、他国と貿易する際には困難に直面することになる。この国の王様は、この問題を解決するために、自国の表記法の数字を10進法に変換するプログラムを作ろうと考えています。プログラムを書いて王様を助けましょう。
入力
この王国で使用されている数字 n を入力してください。 (入力は 2 進数であり、0 が連続する数値はありません。) (1 ≤ n ≤ 221)
注: 1 → 1、10 → 2、11 → 3、101 → 4、110 → 5、111 → 6、1010 → 7
出力
n を 10 進数で表示します。
#include <stdio.h>
#include <stdlib.h>
int Converting(char *array, int *Fibo, int array_size){
if(array_size <= 3){
if(array_size == 1) return 1;
if(array_size == 2) return 2 + array[1];
return 2*array[1] + array[2] + 3;
}
if(array[1] == 0){ // 101…
char array_2[array_size - 2];
int i;
for(i=2; i<array_size; i++){
array_2[i-2] = array[i];
}
return Fibo[array_size-1] + 1 + Converting(array_2, Fibo, array_size - 2);
/* Fibo[array_size] - 1 + Converting(array_2, Fibo, array_size - 2) - (Fibo(array_size - 2) - 1) */
}
else if(array[2] == 0){ // 110…
char array_2[array_size - 3];
int i;
for(i=3; i<array_size; i++){
array_2[i-3] = array[i];
}
return Fibo[array_size] + 1 + Converting(array_2, Fibo, array_size - 3);
/* Fibo[array_size] - 1 + Fibo[array_size - 1] - Fibo[array_size - 2] +
Converting(array_2, Fibo, array_size - 3) - (Fibo(array_size - 3) - 1) */
}
else{ // 111…
char array_2[array_size - 2];
int i;
for(i=2; i<array_size; i++){
array_2[i-2] = array[i];
}
return Fibo[array_size] + 1 + Converting(array_2, Fibo, array_size - 2);
/* Fibo[array_size] - 1 + Fibo[array_size - 1] - Fibo[array_size - 2] + Fibo[array_size - 2] -
Fibo[array_size - 3] + Converting(array_2, Fibo, array_size -
2) - (Fibo(array_size - 2) - 1) */
}
}
int main(int argc, char *argv[]) {
char array[23];
int Fibo[23];
int i; char ch;
Fibo[1] = 1;
Fibo[2] = 2;
for(i = 3; i <= 22; i++){ // Fibo[i] equals 1010…(2) (size: i) (inductively proven)
Fibo[i] = Fibo[i-1] + Fibo[i-2] + 1;
}
i = 0;
while(1){
ch = getchar();
if(ch < 30) break;
array[i] = ch - '0';
i ++;
}
printf("%d", Converting(array, Fibo, i));
return 0;
}
入力: 2016.02.16 11:31