24-6：分治法-階乘

Chinglin-K

目錄：Dice 程式教學-Python完整版
上一篇：24-5：貪心法-最少紙幣兌換

題目

分治法：
將大問題不斷切割成兩個或多個小問題，這樣的過程稱作「Divide」，當切割到最後的小問題，
若簡單到可以直接解決，就直接使用程式解決，根據問題的需求決定是否要將小問題的解合併或組合成大問題的解，
這樣的過程稱作「Conquer」，這是一種演算法解題策略，屬於由上而下(top-down)的解題策略。

分治法練習：
使用者輸入一數字 n，需顯示從 1-n 的所有階乘值(建議使用遞迴函數)。
解題想法：
本題可以使用分而治之(Divide and Conquer)解題策略。
Step1：Divide
自訂函式f(n)用於計算n階乘，f(n)與f(n-1)的關係為「f(n)=nf(n-1)」，大問題f(n)可以切割成小問題f(n-1)，一直切割到f(1)為止，f(1)答案就是1。
Step2：Conquer
利用「f(n)=nf(n-1)」，將f(n-1)的結果乘以n就可以獲得f(n)的結果。

輸入範例:
6
輸出範例:
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720

程式碼









def factorial(n):
    if(n==1):
        return 1
    else:
        return n*factorial(n-1)

n=int(input())
for i in range(n):
    print(f'{i+1}!={factorial(i+1)}')