以下為2017年全國(guó) NOIP 提高組復(fù)賽的第1題：

怎么樣，讀完題是不是感覺特別懵。—— 我是誰，我在哪里？

接下來我們來慢慢解析這道讓人摸不著頭腦的競(jìng)賽題。

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

l 假設(shè)，現(xiàn)在人民幣只有兩個(gè)幣種，面值你定

l 對(duì)面值數(shù)字的要求是這兩個(gè)數(shù)字不能有公約數(shù)(除1這個(gè)公約數(shù)外)

例如：2和5

l 問用這兩個(gè)面值的錢，不能湊齊的最大的價(jià)錢是多少

l 當(dāng)然，前提是你有任意多的錢

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

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

整個(gè)過程分兩步：

第一步：借助 python 找規(guī)律劃范圍

1 # 先找出能湊出來的金額

2 def myFunc(a, b): # 輸入a,b兩個(gè)互素的面值

3 c = 1 # 從1開始找出能湊出的金額

4 while True: # 不斷循環(huán)，電腦配置低的，請(qǐng)遠(yuǎn)離，前方危險(xiǎn)

5 for i in range(c):

6 an01 = a * i

7 for j in range(c):

8 an02 = b * j

9 if an01 + an02 == c: # 一旦找到能湊出當(dāng)前金額c的i和j，打印出來

10 # print(c, "=", a, '*', i, '+', b, '*', j)

11 print(c,end=' ')

12 c += 1 # 金額不斷上漲，上不封頂

13

14

15 if __name__ == "__main__":

16 myFunc(3, 5)

結(jié)果為：

如果將面值設(shè)置為 7,5 呢

結(jié)果：

再如果換成 7,9

結(jié)果：

綜上:

l 我們可以發(fā)現(xiàn)，不可組合的面值均集中在靠前的位置，但有多靠前，具體又在哪個(gè)位置呢？

l 我們姑且假定這個(gè)數(shù)字就在 兩數(shù)的乘積 之內(nèi)，而且事實(shí)也是這樣的。大家可以多試幾對(duì)數(shù)字，檢驗(yàn)一下。

第二步：范圍找到后，我們?cè)賮砜紤]用 python 找出范圍內(nèi)的不可組合的金額值：

備注：上面的程序是一個(gè)死循環(huán)，需要手動(dòng)結(jié)束程序，建議不懂操作的小伙伴謹(jǐn)慎運(yùn)行(嘿嘿，你是不是已經(jīng)入坑啦！)。但下面這個(gè)程序就不一樣了，小伙伴們盡管去運(yùn)行吧。

1 # 找出兩數(shù)乘積范圍內(nèi)的可組合數(shù)據(jù)

2 def myFunc(a, b):

3 c = a * b

4 my_list = # 創(chuàng)建存放所有組合出來的金額值

5

6 # 找尋過程--不斷對(duì)比

7 for i in range(0, c):

8 an01 = a * i

9 for j in range(c):

10 an02 = b * j

11 if an01 + an02 <= c: # 只找在乘積范圍內(nèi)的組合，節(jié)省運(yùn)算次數(shù)

12 my_list.append(an01 + an02) # 將符合的金額添加進(jìn)目標(biāo)列表

13 return list(set(sorted(my_list))) # 返回經(jīng)過去重和排序的目標(biāo)列表

14

15

16 # 找到最大的那個(gè)不能組合的金額

17 def getMax(a, b):

18 my_list = myFunc(a, b) # 調(diào)用找可拼湊數(shù)據(jù)函數(shù)得到目標(biāo)列表

19 my_list.sort(reverse=True) # 將目標(biāo)列表反序排列

20

21 # 判斷目標(biāo)列表是否連續(xù)，并輸出斷點(diǎn)數(shù)中的最大值

22 y = my_list[0] + 1 # 創(chuàng)建對(duì)比參數(shù)

23 for x in my_list:

24 if x + 1 != y:

25 print(x, y)

26 break

27 y = x

28 return y - 1 # 返回最大斷點(diǎn)值

29

30

31 if __name__ == "__main__":

32 print(getMax(16, 27))

結(jié)果為：

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

c = a * b - a - b

( 其中的a 和 b 為你輸入的兩個(gè)互為素?cái)?shù)的幣種面值，c為它們不能組合的金額 )

大家可以多試幾組數(shù)據(jù)，驗(yàn)證一下。

而且我要悄悄告訴你的就是，這個(gè)公式可是一個(gè)牛哄哄的定理，名字叫：賽瓦維斯特定理

賽瓦維斯特定理:

已知a,b為大于1的正整數(shù)，(a,b)=1,則使不定方程 ax+by=c 無負(fù)整數(shù)解的最大整數(shù)c=ab?a?b

其中的 (a,b) 表示a和b的最大公約數(shù)

怎么樣，通過兩個(gè)程序，我們就很容易的解決了這個(gè)看起來不那么友好的競(jìng)賽題。

此時(shí)，是不是覺得 python 很酷呢！

筆者會(huì)不定時(shí)的更新一些跟python相關(guān)又和數(shù)學(xué)相關(guān)的一些有趣的程序，喜歡就關(guān)注我吧。

總結(jié)

以上是生活随笔為你收集整理的python竞赛题解答_【一点资讯】用python解NOIP竞赛题 www.yidianzixun.com的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。