---
title: 24-6：分治法-階乘
lang: zh-tw
tags: DICE Python
---

24-6：分治法-階乘
===

> [name=Chinglin-K]

---

目錄：[Dice 程式教學-Python完整版](https://hackmd.io/@Chinglin-K/Dice-menu)
上一篇：[24-5：貪心法-最少紙幣兌換](https://hackmd.io/@Chinglin-K/Dice-24-5)

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

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

---

## 輸出

---

目錄：[Dice 程式教學-Python完整版](https://hackmd.io/@Chinglin-K/Dice-menu)
上一篇：[24-5：貪心法-最少紙幣兌換](https://hackmd.io/@Chinglin-K/Dice-24-5)

---

:::info

「盡多少本分，得多少本事」😊
:::

---

{%hackmd i1nMRrZcTFmTvoF897K9zg %}