C Language “Counting Method in a Strange Country”
Higher category : C Language Table of Contents
a. GitHub
Q. In a certain country, binary notation is used. However, the people of that country dislike numbers with consecutive zeros. They also dislike counting numbers with consecutive zeros. Therefore, they face difficulties when engaging in trade with other countries. The king of this country intends to create a program to convert numbers in their country’s notation to decimal notation in order to solve this problem. Help the king by writing a program.
Input
Enter the number n used in this kingdom. (The input is in binary notation, and there are no numbers with consecutive zeros.) (1 ≤ n ≤ 221)
Note: 1 → 1, 10 → 2, 11 → 3, 101 → 4, 110 → 5, 111 → 6, 1010 → 7
Output
Print n in decimal notation.
#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;
}
Input: 2016.02.16 11:31