Algorithm筆記 5 - 一些解題的思考方式

剛做完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最好，因為通常有規律性或是簡化轉化問題的機會！