昨天下午同事給我出了一到題目:
一筐雞蛋,1個1個拿,拿完;2個2個拿,剩余1個誓篱;3個3個拿糠亩,拿完垂寥;4個4個拿,剩余1個;5個5個拿,剩余1個浑厚;6個6個拿诬乞,剩余3個票堵;7個7個拿军俊,拿完矗蕊;8個8個拿,剩余1個卿操;9個9拿窥摄,拿完崭放。請問雞蛋最少多少個币砂?
最簡答的做法就是循環(huán)掌桩,代碼如下
x=range(1,1000)
s=filter(lambda x:x %2==1 and x%3==0
and x%4==1 and x%5==1
and x%6==3 and x%7==0
and x%9==0 and x%5==1
and x%8==1 x%9==1,x)
print s
這樣寫矢门,憋說你學過編程=龈浮腥椒!
好了候衍,其實這是一種很經典的題目笼蛛,中國剩余定理,不了解的可以看一下基礎數論中歐幾里得算法蛉鹿,擴展歐幾里得算法
# -*- coding: utf-8 -*-
__author__='fanyiting'
import datetime
#求乘法逆元
def ext_euclid(a,b):
if not b:
return a,1,0
else:
g,x,y=ext_euclid(b,a%b)
return g,y,x-y*(a/b)
#中國剩余定理滨砍,要求m兩兩互素
def cal(t,m,a):
starttime=datetime.datetime.now()
M=1
result=0
for i in m:
M=M*i
for i in range(t):
Mi=M/m[i]
G,X,Y=ext_euclid(Mi,m[i])
result=(result+Mi*X*a[i])%M
stoptime=datetime.datetime.now()
print 'run time {}'.format((stoptime-starttime))
return result
sum=cal(4,[5,7,8,9],[1,0,1,0])
print sum