剛剛在貼吧上看到一個(gè)很簡(jiǎn)單的算法小問(wèn)題瞧预，順便看到了很多人不同的思路仪召。我覺(jué)得很有意思，所以也來(lái)研究一下松蒜。
問(wèn)題如下：
一筐雞蛋：
1個(gè)1個(gè)拿扔茅，正好拿完。
2個(gè)2個(gè)拿秸苗，還剩1個(gè)召娜。
3個(gè)3個(gè)拿，正好拿完惊楼。
4個(gè)4個(gè)拿玖瘸，還剩1個(gè)秸讹。
5個(gè)5個(gè)拿，還差1個(gè)雅倒。
6個(gè)6個(gè)拿璃诀，還剩3個(gè)。
7個(gè)7個(gè)拿蔑匣，正好拿完劣欢。
8個(gè)8個(gè)拿，還剩1個(gè)裁良。
9個(gè)9個(gè)拿凿将，正好拿完。
問(wèn)：筐里最少有幾個(gè)雞蛋价脾？
題目很簡(jiǎn)單牧抵，我們可以直接用暴力窮舉法。這當(dāng)然是最簡(jiǎn)單的辦法侨把， 下面是這種方法的Kotlin代碼犀变。運(yùn)行之后，得到結(jié)果為1449秋柄。
fun answer1() {
var n = 0
while (true) {
if (n % 2 == 1 && n % 4 == 1 && n % 5 == 4 && n % 6 == 3 && n % 7 == 0 && n % 8 == 1 && n % 9 == 0) {
break
}
n++
}
println(n)
}
當(dāng)然暴力窮舉雖然簡(jiǎn)單获枝，但是效率并不是很高，對(duì)于這個(gè)問(wèn)題來(lái)說(shuō)华匾，循環(huán)運(yùn)行了1449次。我們可以分析題目特點(diǎn)机隙，簡(jiǎn)化循環(huán)的運(yùn)行次數(shù)蜘拉。
首先來(lái)看看題目，很明顯第一句是廢話(huà)有鹿，因?yàn)槿魏握麛?shù)都可以被1整除旭旭。然后是第二句，這表明這個(gè)數(shù)是一個(gè)奇數(shù)葱跋。第三句和第九句明顯重復(fù)持寄，可以被9整除，那么必然也可以被3整除来庭，所以只看第九句就可以了蜀备。還有第五句需要注意一下婉弹，因?yàn)檫@里是被5除還差1個(gè)，所以是還剩4個(gè)模庐。我看貼吧里有些人審題不嚴(yán)，導(dǎo)致做了一個(gè)錯(cuò)誤答案油宜。
經(jīng)過(guò)一番分析掂碱，上面的題目就變成了下面這樣的怜姿。
奇數(shù)
能被9整除
除以4余1
除以5余4
除以6余3
能被7整除
除以8余1
注意到7和9互質(zhì)，所以答案必然是63的倍數(shù)疼燥，而且還是個(gè)奇數(shù)沧卢，所以是奇數(shù)倍。所以我們的代碼可以改進(jìn)一下醉者。代碼中的count用于統(tǒng)計(jì)循環(huán)次數(shù)但狭，這次結(jié)果和上次一樣，但是循環(huán)次數(shù)僅為12次湃交，每次要判斷的條件也減少了很多熟空。
fun answer2() {
var n = 63
var count = 0
while (true) {
count++
if (n % 4 == 1 && n % 5 == 4 && n % 6 == 3 && n % 8 == 1) {
break
}
n += 63 * 2
}
println("n=$n,count=$count")
}
當(dāng)然還可以進(jìn)一步優(yōu)化。由于這個(gè)數(shù)除以5余4搞莺，可以想到該數(shù)的個(gè)位數(shù)字不是4就是9息罗，但是由于是奇數(shù)，那么個(gè)位數(shù)必然是9才沧，而且這個(gè)數(shù)是63的倍數(shù)迈喉。而除以4余1和除以8余1這兩個(gè)條件可以簡(jiǎn)化為除以8余1。所以最后代碼就變成了這樣温圆，循環(huán)僅僅循環(huán)了3次挨摸。
fun answer3() {
var n = 63 * 3
var count = 0
while (true) {
count++
if (n % 8 == 1) {
break
}
n += 630
}
println("n=$n,count=$count")
}
我還看到貼吧上有人說(shuō)用同余定理算，但是我比較笨岁歉，沒(méi)理解怎么用同余定理來(lái)計(jì)算得运。不過(guò)以前我倒是遇到過(guò)類(lèi)似的題目，所以最后來(lái)介紹一下锅移。
我遇到的題目類(lèi)似下面這樣：
一個(gè)數(shù)除以2余1熔掺，除以3余2，除以4余3非剃，這個(gè)數(shù)最小是幾置逻？
這個(gè)問(wèn)題倒是有一個(gè)簡(jiǎn)便方法，由于余數(shù)恰好和除數(shù)只差1备绽，所以如果在被除數(shù)上加1券坞，那么它就可以同時(shí)被2、3肺素、4整除恨锚，所以這個(gè)數(shù)最小應(yīng)該是2、3倍靡、4的最小公倍數(shù)再減1眠冈，所以應(yīng)該是23 。
回到我們這道題目來(lái)說(shuō)，由于余數(shù)每次都不一樣蜗顽，所以沒(méi)辦法這么做布卡。不過(guò)我想了想，能不能通過(guò)加一個(gè)數(shù)雇盖，讓余數(shù)都變得相同忿等。由于我數(shù)學(xué)不好，也不懂?dāng)?shù)論這些專(zhuān)業(yè)知識(shí)崔挖，所以直接用代碼模擬一下贸街，發(fā)現(xiàn)確實(shí)可以得到一個(gè)數(shù)，讓答案加上這個(gè)數(shù)以后狸相，所有余數(shù)都相同薛匪。這個(gè)數(shù)是1071，這時(shí)候余數(shù)都是0 脓鹃。Kotlin代碼如下逸尖。
fun cal() {
val numbers = hashMapOf(
2 to 1,
3 to 0,
4 to 1,
5 to 4,
6 to 3,
7 to 0,
8 to 1,
9 to 0)
var n = 0
while (true) {
n++
for (k in numbers.keys) {
val old = numbers[k]
numbers[k] = (old!! + 1) % k
}
val set = numbers.values.toSet()
if (set.size == 1) {
break
}
}
println("這個(gè)數(shù)是:$n")
}
有了這個(gè)數(shù)，我們就可以用上面的方法來(lái)計(jì)算結(jié)果了瘸右。答案加上1071之后娇跟，可以被2-9的所有數(shù)整除，所以2-9的最小公倍數(shù)再減去1071太颤，就是我們要求的答案苞俘。而2-9的最小公倍數(shù)也就是5-9的最小公倍數(shù)，是2520龄章，再減去前面的1071吃谣，正好就是最一開(kāi)始我們得到的答案1449！
如果大家有更好的思路做裙，也可以告訴我岗憋，讓我們互相學(xué)習(xí)，共同進(jìn)步菇用！
