以下為2017年全國 NOIP 提高組復賽的第1題：

image.png

image.png

????--------------------------------------- 問題展示完畢 -----------------------------------------

怎么樣菜秦，讀完題是不是感覺特別懵舶掖。—— 我是誰眨攘，我在哪里？

接下來我們來慢慢解析這道讓人摸不著頭腦的競賽題共螺。

一、首先翻譯一下題的意思：

• 假設璃谨，現(xiàn)在人民幣只有兩個幣種鲤妥，面值你定
• 對面值數(shù)字的要求是這兩個數(shù)字不能有公約數(shù)（除1這個公約數(shù)外）
  ?? 例如：2和5
• 問用這兩個面值的錢拱雏，不能湊齊的最大的價錢是多少
• 當然，前提是你有任意多的錢

是不是稍微要清晰一些了呢铸抑。

二、那我們接下來用python寫一個程序來完成這道題：

整個過程分兩步：
第一步：借助 python 找規(guī)律劃范圍

# 先找出能湊出來的金額
def myFunc(a, b):  # 輸入a,b 兩個互素的面值
    c = 1  # 從1開始找出能湊出的金額
    while True:  # 不斷循環(huán)蒲赂，電腦配置低的，請遠離滥嘴，前方危險
        for i in range(c):
            an01 = a * i
            for j in range(c):
                an02 = b * j
                if an01 + an02 == c:  # 一旦找到能湊出當前金額c的i和j，打印出來
                    print(c, "=", a, '*', i, '+', b, '*', j)
        c += 1  # 金額不斷上漲若皱，上不封頂


if __name__ == "__main__":
    myFunc(3, 5)

結果：

image.png

如果將面值設置為7,5

結果：

image.png

結果：

image.png

綜上:

我們可以發(fā)現(xiàn)走触，不可組合的面值均集中在靠前的位置，但有多靠前敛腌，具體又在哪個位置呢惫皱？
我們姑且假定這個數(shù)字就在 兩數(shù)的乘積 之內像樊，而且事實也是這樣的逸吵。大家可以多試幾對數(shù)字，檢驗一下足绅。

二、范圍找到后氢妈，我們再來考慮用 python 找出范圍內的不可組合的金額值：

??備注：上面的程序是一個死循環(huán)段多，需要手動結束程序，建議不懂操作的小伙伴謹慎運行进苍，但下面這個程序就不一樣了，小伙伴們盡管去運行吧觉啊。

  # 找出兩數(shù)乘積范圍內的可組合數(shù)據(jù)
def myFunc(a, b):
    c = a * b
    my_list = []  # 創(chuàng)建存放所有組合出來的金額值
    
    # 找尋過程 -- 不斷對比
    for i in range(0, c):
        an01 = a * i
        for j in range(c):
            an02 = b * j
            if an01 + an02 <= c:  # 只找在乘積范圍內的組合杠人，節(jié)省運算次數(shù)
                my_list.append(an01 + an02)  # 將符合的金額添加進目標列表
    return list(set(sorted(my_list)))  # 返回經過去重和排序的目標列表


# 找到最大的那個不能組合的金額
def getMax(a, b):
    my_list = myFunc(a, b)  # 調用找可拼湊數(shù)據(jù)函數(shù)得到目標列表
    my_list.sort(reverse=True)  # 將目標列表反序排列

    # 判斷目標列表是否連續(xù)宋下，并輸出斷點數(shù)中的最大值
    y = my_list[0] + 1  # 創(chuàng)建對比參數(shù)
    for x in my_list:
        if x + 1 != y:
            print(x, y)
            break
        y = x
    return y - 1  # 返回最大斷點值


if __name__ == "__main__":
    print(getMax(16, 27))

結果為：

image.png

不知道大家有沒有發(fā)現(xiàn)一個問題辑莫，這個最大不可組合數(shù)據(jù)似乎有一定的規(guī)律，規(guī)律為：

c = a * b - a - b
( 其中的a 和 b 為你輸入的兩個互為素數(shù)的幣種面值各吨，c為它們不能組合的金額 )
大家可以多試幾組數(shù)據(jù)，驗證一下伺帘。

怎么樣，通過兩個程序伪嫁，我們就很容易的解決了這個看起來不那么友好的競賽題偶垮。
此時张咳，是不是覺得 python 很酷呢似舵！
?
?

筆者會不定時的更新一些跟python相關又和數(shù)學相關的一些有趣的程序，喜歡就關注我吧龙助。

?

特別警示：本文為作者原創(chuàng)作品蛛芥，禁止不經過本人同意就將其轉載用于商業(yè)用途，否則將予以追究仅淑。
處于學習分享轉載請附上出處鏈接，謝謝涯竟！