這道數(shù)學(xué)題是我偶然間發(fā)現(xiàn)的：

1223330000組合成十位數(shù)，問：共有多少種組合方式可使組合出的十位數(shù)只讀一個零.

這題不需要用到什么高級的數(shù)學(xué)技巧，但是需要大量分類和枚舉，于是，我想到了編程解決這一問題。

語言上我選擇的是Python，另外，我的編程環(huán)境為PyCharm。

接下來，我們進入正文部分。

思路

我的思路是這樣的：

遍歷每一種組合情況，并對每一種情況進行檢查，看是否符合題目中只讀一個零的條件。

那么，這個程序就可以被分為兩個部分：
1.遍歷
2.檢查
那么，我們開始逐步實現(xiàn)這一程序。

第一部分：遍歷

我們需要用十個數(shù)字來組成十位數(shù)，這種情況下我們就要對每一個數(shù)位進行遍歷，我們倒是可以用十個for循環(huán)嵌套在一起來實現(xiàn)，但是這顯然會影響代碼的可讀性和美觀，所以我們選擇另外一種算法——遞歸。

什么是遞歸

如果對遞歸算法有所了解的，可以直接跳過這一部分。
遞歸算法，用一句話來解釋就是：

遞歸：自己調(diào)用自己

專業(yè)一點叫做：

在函數(shù)的定義中使用函數(shù)自身的方法

為了各位讀者更容易理解遞歸，我們來舉一個簡單的例子：

首先，定義一個數(shù)列，，。

接下來，我們編程來實現(xiàn)，輸入，求的值。

由于這是一個首項為0，公差為2的等差數(shù)列，我們可以這樣寫：

n = int(input("Enter n:"))
an = 2 * (n-1)
print(an)

當然，如果用到剛才講到的遞歸，我們就可以這樣寫：

def a(term):
    if term == 1:
        return 0
    elif term >= 2:
        a(term - 1)


n = int(input("Enter n:"))
print(a(n))

這樣寫可能會有些復(fù)雜，但是這一程序很好的體現(xiàn)了遞歸算法，看到這里：

def a(term):
    …
    elif term >= 2:
        a(term - 1)

這就是前面所提到的，”自己調(diào)用自己“。

那么，這一程序是如何運行的呢？

手繪遞歸展示

注意圖中還標有兩個詞：”回推“和”遞推“

用我的方式來解釋這兩個詞就是：

回推：一層一層向下調(diào)用的過程

遞推：一層一層向上返回值的過程

以上，就是我對遞歸算法一個簡單的介紹，如果想對遞歸有更多、更深入的了解，可以前往知乎上查看其他大佬對遞歸的解釋。

用遞歸來實現(xiàn)遍歷

運用遞歸，我們的實現(xiàn)方式就應(yīng)該是這樣：遞歸時，每回推一次，通過for循環(huán)遍歷一個數(shù)位的可能情況，當所有數(shù)位確定完成時，進行下一部分。

與此同時，我們就也確定出了我們的函數(shù)需要的兩個參數(shù)：已確定的數(shù)位（numlist），還未使用的數(shù)字（unused）。

當然，由于這個程序沒有返回值，也就沒有遞推的過程了。

結(jié)合以上的思路，我們的程序會是這樣：

def recu(numlist, unused):
    if len(numlist) < 10:
        # 長度小于十，說明還未組成十位數(shù)
        used = []
        for addnum in unused:
            snumlist = numlist[:]
            sunused = unused[:]
            snumlist.append(addnum)
            sunused.remove(addnum)
            if snumlist[0] != 0:
                recu(snumlist, sunused)
    elif len(numlist) == 10:
        # 長度等于十，說明十位數(shù)已經(jīng)組成，那么檢查是否能夠讀零
        …

當然，我們還需要注意一點，在題目給出的可選數(shù)字中，有大量的重復(fù)數(shù)字，如果我們的遍歷部分就這樣寫，對于同一個數(shù)字組合方式，程序會計算次，也就是說，程序給出答案的時長會多出整整288倍！

那么，我們要做的就是避免重復(fù)計算同一種情況，方法也很簡單，每次遍歷，檢查addnum是否在列表used中，如果返回值為True，將addnum添加到列表used中。

修改后的程序會是這樣：

def recu(numlist, unused):
    if len(numlist) < 10:
        # 長度小于十，說明還未組成十位數(shù)
        used = []
        for addnum in unused:
            if addnum not in used:
                used.append(addnum)
                snumlist = numlist[:]
                sunused = unused[:]
                snumlist.append(addnum)
                sunused.remove(addnum)
                if snumlist[0] != 0:
                    recu(snumlist, sunused)
    elif len(numlist) == 10:
        # 長度等于十，說明十位數(shù)已經(jīng)組成，那么檢查是否能夠讀零
        …

第二部分：檢查

第二部分要做的工作是檢查已組成的十位數(shù)是否符合”只讀一個零“的條件。

并不是每一個數(shù)中的零都會被讀出，那么，我們來梳理一下讀零的規(guī)則：

• 處于每級末尾的零或由零組成的數(shù)串不會被讀出「如：10 2300 3300」
• 處于數(shù)中部全部由零組成的數(shù)級，且前后數(shù)級不全是零的，會讀一個零「如：12 0000 2333」

我們會發(fā)現(xiàn)，以上兩條規(guī)則都是基于數(shù)級的，所以別的先拋開，我們要做的第一件事，就是將組成的十位數(shù)分級。

實現(xiàn)方式不難，我們先準備一個二維列表splitnum，用于存放被分級的十位數(shù)。

splitnum = [[], [], []]

然后，for循環(huán)遍歷numlist，將每一個數(shù)字存放在最前面一個尚未存滿的數(shù)級中（存滿，即數(shù)級中已有四個數(shù)字）。

我的代碼如下，需要注意的是，我的這種方式分解出來的數(shù)字是倒序的，在之后的程序，不要忽略這一點，當然，你也可以使分解數(shù)字正續(xù)排列，可以遍歷index，甚至可以這樣寫：splitnum = [[numlist[0], …], …]:

for i in range(0, len(numlist)):
    for grade in splitnum:
        if len(grade) < 4:
            grade.append(numlist.pop())
            break

結(jié)合讀零規(guī)則的第一條，即”處于每級末尾的零或由零組成的數(shù)串不會被讀出“，我們首先去掉處于每級末尾的零：

for grade in splitnum:
    while True:
        if grade[0] == 0 and len(grade) > 0:
            del grade[0]
       else:
            break

注意這里的if grade[0] == 0 and len(grade) > 0，在檢測第一項為0的同時，也保證不把整個數(shù)級刪空，這可以避免IndexError，同時，也因為整個數(shù)級均由零構(gòu)成，可能會讀零。

做完以上工作后，剩下的處于數(shù)中的0數(shù)串就全部都會被讀出了，所以，我們將三個數(shù)級連接起來，再檢查里面有幾個由零組成的數(shù)串即可：

for grade in splitnum:
    # 將每一級連接起來
    for num in grade:
        check.append(num)
while True:
    if check[0] == 0:
        del check[0]
    else:
        break
# 將連在一起的零變?yōu)閱为毜囊粋€零
zero = False
idx = 0
oldcheck = check[:]
for num in oldcheck:
    if num == 0:
        if zero:
            del check[idx]
            idx -= 1
        if not zero:
            zero = True
        else:
            zero = False
    idx += 1
    if check.count(0) == 1:
        result += 1

完工

至此，我們程序的主要部分就已全部編寫完成了，加以整理，即可編寫出完整的程序！

最后附上帶有注釋的完整代碼：

# -*- coding: utf-8 -*-
"""
題目：
1223330000組合成十位數(shù)，問：共有多少種組合方式可使組合出的十位數(shù)只讀一個零.
"""


def recu(numlist, unused):
    if len(numlist) < 10:
        # 長度小于十，說明還未組成十位數(shù)
        used = []
        for addnum in unused:
            if addnum not in used:
                used.append(addnum)
                snumlist = numlist[:]
                sunused = unused[:]
                snumlist.append(addnum)
                sunused.remove(addnum)
                if snumlist[0] != 0:
                    recu(snumlist, sunused)
    elif len(numlist) == 10:
        # 長度等于十，說明十位數(shù)已經(jīng)組成，那么檢查是否能夠讀零
        print(numlist, end='    ')
        global result
        # 首先按級進行分割
        splitnum = [[], [], []]
        for i in range(0, len(numlist)):
            for grade in splitnum:
                if len(grade) < 4:
                    grade.append(numlist.pop())
                    break
        # 對每一級進行檢查，看是否讀零
        check = []
        for grade in splitnum:
            # 末尾的零不會讀出，所以去掉末尾的零
            while True:
                if grade[0] == 0 and len(grade) > 1:
                    del grade[0]
                else:
                    break
            # 將每一級連接起來
            for num in grade:
                check.append(num)
        while True:
            if check[0] == 0:
                del check[0]
            else:
                break
        # 將連在一起的零變?yōu)閱为毜囊粋€零
        zero = False
        idx = 0
        oldcheck = check[:]
        for num in oldcheck:
            if num == 0:
                if zero:
                    del check[idx]
                    idx -= 1
                if not zero:
                    zero = True
            else:
                zero = False
            idx += 1
        print("check:", check, end="    ")
        if check.count(0) == 1:
            result += 1
            print("PASS")
        else:
            print("NOT PASS")
    else:
        print("Error")


if __name__ == "__main__":
    alternative = [1, 2, 2, 3, 3, 3, 0, 0, 0, 0]
    result = 0
    recu([], alternative)
    print(result)

運行結(jié)果：

…
[3, 0, 0, 0, 0, 3, 2, 3, 1, 2]    check: [2, 1, 3, 2, 3, 0, 3]    PASS
[3, 0, 0, 0, 0, 3, 2, 3, 2, 1]    check: [1, 2, 3, 2, 3, 0, 3]    PASS
[3, 0, 0, 0, 0, 3, 3, 1, 2, 2]    check: [2, 2, 1, 3, 3, 0, 3]    PASS
[3, 0, 0, 0, 0, 3, 3, 2, 1, 2]    check: [2, 1, 2, 3, 3, 0, 3]    PASS
[3, 0, 0, 0, 0, 3, 3, 2, 2, 1]    check: [1, 2, 2, 3, 3, 0, 3]    PASS
2460

Process finished with exit code 0

所以，我們得出了這道題目的答案——2460。

在我的博客上查看本文

這是我第一次發(fā)表這種文章，內(nèi)容質(zhì)量和文筆都還有改進的空間，還請大家多多鼓勵，如果有建議的話，歡迎在評論區(qū)留言！