剛做完Algorithmic Toolbox這門課的第一個assignment，還真的被跟Pisano period相關的某一題難住了，
有點出乎意料之外，趕快趁熱把一些經驗談寫下來，希望之後用得到：
(以下的題目，Java grader要求在1.5秒內要pass所有的test）
計算小的Fibonacci Number
第一題沒啥特別，就是要讓我們知道
不要根據題目的數學定義直接轉換成code，因為這可能是最沒效率的事，
見我筆記2。這邊可以用簡單的dynamic programming來解決問題，由於grader只要求能在時間內完成Fib(45)的數就可以，所以沒什麼問題。
找出較大的Fibonacci數中的個位數字 (最大到Fib(10^7))
這一題其實就要引入一個觀念：
轉化與簡化題目。由於
計算fibonacci數字是O(n^2) runtime，所以我們不可能直接去計算Fib(10^7)，然後將之除以10來找個位數字。但是因為我們只關心個位數字，所以只要計算每個Fib(n)的個位數字就好，十位數字以上的我們不關心，這樣就可以避免大數字的計算，但實際asymtotic time我也不確定，我猜是O(n)。
一樣用簡單的dynamic programming來計算Fib(n):
private static int calc_fib_mod10(int n) {
int[] F = new int[n+2];
F[0] = 0;
F[1] = 1;
for (int i = 2; i <= n; i++)
F[i] = (F[i-2] + F[i-1])%10;
return F[n];
}
計算兩數最大公因數GCD (a,b 兩數分別最大到2*10^9)
這題也只是讓你練習
筆記2中講的概念：先利用數學關係把題目簡化過一遍，這樣大大省略計算時間。O(log(a*b))
計算兩數最小公倍數LCM (a, b 兩數分別最大到2*10^9)
最小公倍數可以簡化成 a*b/GCD(a,b)，因為
a = GCD(a,b) * x
b = GCD(a,b) * y
LCM(a,b) = GCD(a,b) * x * y = (a * b) / GCD(a,b)
所以asymptotic runtime應該和GCD(a,b)一樣為 O(log(a*b))
計算大Fibonacci數 Fib(n) 除以m的餘數 (1≤𝑛≤1018,2≤𝑚≤105)
這一題就是我卡關的題目，主要是沒意識到要把計算限縮在餘數就好，因為這個input 已經太大了，沒把計算限縮在餘數的話，即便利用題目中提示的Pisano period簡化計算，也絕對跑不動。
這題其實就是用了上面幾題帶來的解題觀念！綜合應用之～
/*1 <= n <= 10^18 < Long.MAX2 <= m <= 10^5
(a + b) % m === (a % m + b % m) % m */
private static long getFibonacciHugePisano(long n, long m) {
if (n <= 1)
return n;
long beforePrevious = 0;
long previous = 1;
long a = -1;
long current = -1;
for (long i = 2; i <= n; i++) {
current = (beforePrevious + previous) % m;
if (a == 0 && current == 1) {
long period = (i + 1) - 2;
long reductionN = n % period;
return getFibonacciHugePisano(reductionN, m);
}
else {
a = current;
beforePrevious = previous;
previous = current;
}
}
return current;
}
計算Fibonacci數字連加的和的個位數字 (0 ≤ 𝑛 ≤ 1014)
這應該有兩種做法，第一種（我沒嘗試的）就是把計算限縮在個位數來算Fib(0) + Fib(1) + ... + Fib(n)的和，但我懷疑是否能通過grader的1.5秒時間限制？這感覺上是O(n^2)。
第二種就是找看這個數列有無規則？還真的有，原來SumFib(n)的個位數隨著n變大，每60次會循環一次，所以只要找出這60個數字，之後用查表法就超快：
private static final int PERIOD = 60;
private static int[] LastDigitOfFibSums = new int[] {
0, 1, 2, 4, 7, 2, 0, 3, 4, 8, 3, 2, 6,
9, 6, 6, 3, 0, 4, 5, 0, 6, 7, 4, 2, 7,
0, 8, 9, 8, 8, 7, 6, 4, 1, 6, 8, 5, 4,
0, 5, 6, 2, 9, 2, 2, 5, 8, 4, 3, 8, 2,
1, 4, 6, 1, 8, 0, 9, 0};
private static int getFibonacciSumLastDigit(long n) {
return LastDigitOfFibSums[(int)(n % PERIOD)];
}
這題的啟示就是，執行觀察各種input的結果，是否有可能有規律性，一但有規律性就非常容易解決問題。
上一題的Pisano period無法有一個modulo m 的 P(m)的函數，只能在loop裡面找重複的時機，當然就沒有這一題執行快了。不考慮 n % Period的話，O(1)。
找出Fibonacci數列中部分和 𝐹𝑚 + 𝐹𝑚+1 + · · · + 𝐹𝑛 的個位數字 (0 ≤ 𝑚 ≤ 𝑛 ≤ 1018)
這一題乍看之下，跟上一題很像，但可惜其output沒有規律性。不過跟上一題還是有關係，因為它可以寫成上一題的式子：
(F(3) + F(4) + F(5) + F(6) + F(7)) % 10
= (F0 + F1 + F2 + .. + F7 - (F0 + F1 + F2)) % 10
= (SumFib(7) - SumFib(2)) % 10
要能跟
getFibonacciSumLastDigit扯上關係，必須要證明
SumFib(7)%10 - SumFib(2)%10 == getFibonacciSumLastDigit(7) - getFibonacciSumLastDigit(2)
的確是可以，以下：
if x > y,
(x - y)% 10 == (x%10 - y%10), if x%10 >= y%10
(x - y)% 10 == x%10 - y%10 + 10, if x%10 < y%10
所以我們可以簡單地用上一題的output來實作本題：
private static long getFibonacciPartialSumLastDigit(long from, long to) {
int x = getFibonacciSumLastDigit(to);
int y = getFibonacciSumLastDigit(from-1);
if (x >= y)
return x - y;
else return x - y +10;
}
結論
如果一個問題能以數學來model最好，因為通常有規律性或是簡化轉化問題的機會！
