005.Representation in Fibonaccimal base

[LarryLuTW]

內容:

The well known Fibonacci sequence is obtained by starting with 0 and 1 and then adding the two last numbers to get the next one. For example the third number in the sequence is 1 (1=1+0), the forth is 2 (2=1+1), the fifth is 3 (3=2+1) and so on.

The sequence appears on many things in our life, in nature, and has a great significance. Among other things, do you know that all positive integer numbers can be represented as a sum of numbers in the Fibonacci sequence? More than that, all positive integers can be represented as a sum of a set of Fibonacci numbers, that is, numbers from the sequence, without repetition. For example: 13 can be the sum of the sets {13}, {5,8} or {2,3,8} and 17 is represented by {1,3,13} or {1,3,5,8}. Since all numbers have this property (do you want to try to prove this for yourself?) this set could be a nice way to use as a "base" to represent the number. But, as we have seen, some numbers have more than one set whose sum is the number. How can we solve that? Simple! If we add the constraint that the sets cannot have two consecutive Fibonacci numbers, than we have a unique representation for each number! This restriction is because the sum of any two consecutive Fibonacci numbers is just the following Fibonacci number. Now that we know all this we can prepare a nice way to represent any positive integer. We will use a binary sequence (just zeros and ones) to do that. For example, 17 = 1 + 3 + 13 (remember that no two consecutive Fibonacci numbers can be used). Let’s write a zero for each Fibonacci number that is not used and one for each one that is used, starting at the right. Then, 17 = 100101. See figure 2 for a detailed explanation. In this representation we should not have zeros at the left, this is, we should only write starting with the first one. In order for you to understand better, note that in this scheme, not using two consecutive Fibonacci numbers means that the binary sequence will not have two consecutive ones. When we use this representation for a number we say that we are using the Fibonaccimal base, and we write it like 17 = 100101 (fib).

Given a set of numbers in decimal base, your task is to write them in the Fibonaccimal base.

輸入說明:

The first line of input contains a single number N, representing the quantity of numbers that follow (1≤N ≤500). Than follow exactly N lines, each one containing a single positive integer smaller than 100 000 000. These numbers can come in any order.

輸出說明:

You should output a single line for each of the N integers in the input, with the format ‘DEC BASE = FIB BASE (fib)’. DEC BASE is the original number in decimal base and FIB BASE is its representation in Fibonaccimal base. See the sample output for an example.

範例輸入:

10
1
2
3
4
5
6
7
8
9
10

範例輸出:

1 = 1 (fib)
2 = 10 (fib)
3 = 100 (fib)
4 = 101 (fib)
5 = 1000 (fib)
6 = 1001 (fib)
7 = 1010 (fib)
8 = 10000 (fib)
9 = 10001 (fib)
10 = 10010 (fib)

[LarryLuTW]

目前想到的是用 D&C 01001 -> 6 00100 -> 3 加起來 01101 -> 9 01101 可以化成 10001 9 -> 10001

[KyrieSu]

其實這一題我對後面的表示法很沒有想法QQ 一個毫無頭緒的概念

[LarryLuTW]

我剛剛查了一下有關 Fibonacci coding 的資料然後再分析一下 Fibonacci coding 發現好像還是用暴力法最快

上面那個方法看起來雖然有 D&C 但實質上並不會比較快

而且題目說整數最大是一億(10^8) 但其實費氏數列在第 39 項就超過一億了 所以慢慢減下來其實也滿快的 所以應該是用暴力法

1: 1
2: 2
3: 3
4: 5
5: 8
...
35: 14930352
36: 24157817
37: 39088169
38: 63245986
39: 102334155
40: 165580141

[KyrieSu]

目前有大概的完整做法的想法，先計算出n到費氏數列的哪一個位置。 Ex : n = 10 = (8+0+0+2+0)，這邊大概是用_queue_儲存 0 or 1，然後費氏數列部分大概是用_un_map_加速，所以輸出為10010。

[LarryLuTW]

用 queue 存 0 or 1 似乎沒有什麼好處 如果直接用 string 存呢 輸出就可以直接輸出 string

不太懂怎麼用 umap 加速 是先算好然後存在 umap 裡面嗎

[KyrieSu]

我有想過用string，但因為我想說我從最高位元往下跑，也就是說有相減的地方存1，沒相減的地方存0，最後利用queue的特性『先進先出』剛好可以按照高低位元輸出，然後un_map是因為我要存值跟費氏數列第幾項

[LarryLuTW]

喔喔懂你意思 這樣也不錯 不過存費氏數列第幾項應該用陣列存就可以了 開個 40 格不難

然後你說 umap 存值是要存已經計算過的值嗎

[KyrieSu]

恩恩 對!!! 對耶XD 想到一個index對映一個value，就不知不覺想到map去了XD

最後應該是array就可以實做了!!!

[LarryLuTW]

嗯嗯 然後還有一個小小地方可以加速 就是從高位元跑到低位元的時候 不會有連續兩個 1 的

所以如果目前這個位元是 1 就可以直接把下一個放 0 然後再繼續往後面看

[KyrieSu]

OK 明天實做!

[LarryLuTW]

我覺得不用實作也沒關係 因為好像沒什麼特別技巧 就高到低掃下來而已 不過如果有空還是可以做做看 我在幫你看看 code

4 這題你有想到了嗎

[KyrieSu]

我實做完成了!!

for(int i=index;i>=1;i--) {
        if(x>=dp[i]){
            x-=dp[i];
            data.push(1);
        }
        else
            data.push(0);
}  //這是我一開始版本

我想說用不到dp[0]=0，所以我把條件開i>0(i.e: i>=1)，可是這時候大家最後面都會多一個0 ! WTF!!

後來我改成：

for(int i=index;i>1;i--) {
        if(x>=dp[i]){
            x-=dp[i];
            data.push(1);
        }
        else
            data.push(0);
}  //這是我提交的版本

這樣會變成後面輸出都是對的，但會漏 1 = 1 (fib)，我看來是在for-loop完全沒有進去，導致我的queue為空，所以沒有輸出。

[LarryLuTW]

嗯嗯滿不錯的 不過有寫地方可以再簡化一下

int getindex(int x){
    int i;
    for(i=0;i<max;i++){
        if(dp[i] > x)
            break;    // break 後 return (i-1), 可以直接 return (i-1) 就好了
        else if(dp[i]==x)
            return i;
        else
            continue;  // 不用 continue, 上面都沒 return 就會自己 continue 了
    }
    return i-1;
}

改完之後長這樣

int getindex(int x){
    for(int i=0;i<max;i++){
        if(dp[i] > x)
            return i-1;
        if(dp[i]==x)
            return i;
    }
}

或者是用 while

int getindex(int x){
    int i = 0;
    while(dp[i] < x)    // 不用設定 i<max, 反正一定跑不到
        i++;            // 跑完這邊 dp[i] 一定 >= x
    return dp[i] == x ? i : i-1;  // 判斷是 > 還是 =
}

[KyrieSu]

哈哈 我單純只是想要湊if- else if -else XDD

OK 我已經修改了！

[KyrieSu]

我有更新版本來簡化邏輯，這版本沒有special case 。 自己都覺得頗漂亮 哈哈哈