Problem 763 Fibinary Numbers，費氏級數顯示方式

費氏級數進位的有些數值可能會有不只一種情況，例如：10 可表示為 10010 (8 + 2)，但也可表示為 1110 (5 + 3 + 2)，題目會給你兩個費氏級數，請你相加之後，要轉成前者，而不是後者，也就是說，不允許 1 相連。

首先，讀入兩字串，將這兩字串反向擺入一個整數陣列，方便相加：

mIndex = strlen(str);
for (i = mIndex - 1, j = 0; i >= 0 ; i--, j ++)
    m[j] = str[i] - '0';    
memset(str, 0, strlen(str)); 
scanf("%s", str); 
nIndex = strlen(str);
for (i = nIndex - 1, j = 0; i >= 0 ; i--, j ++)
    n[j] = str[i] - '0';

寫一函式，相加兩陣列到 sum 陣列：

void add(int index)
{ 
    int i;
    for (i = 0; i < index; i ++)
        sum[i] = m[i] + n[i];
}

相加之後，就判斷 1 相連的位置，並且使它進位，直到判斷沒有任何數要進位為止。 C 語言程式碼如下：

isChange = 1;
while (isChange)
{
    isChange = 0;
    index = sumLength();  
    for (i = index ; i >= 2; i --)
        if (sum[i] > 1) sum[i]--, sum[i - 1] ++, sum[i - 2] ++, isChange = 1;
    for (i = index; i >= 1; i --)
        if (sum[i] >= 1 && sum[i - 1] >= 1) sum[i]--, sum[i - 1]--, sum[i + 1] ++, isChange = 1;
    if (sum[0] >= 2)
       sum[1] ++, sum[0] -= 2, isChange = 1;
    if (sum[1] >= 2)
       sum[1] -= 2, sum[2] ++, sum[0] ++, isChange = 1;            
}

最後反向印出即可。

By David.K

p763題目連結
回ACM題庫目錄
回首頁