关于“韩信点兵”的程序优化问题
本帖最后由 CtrlCV工程師 于 2021-9-6 22:33 编辑我在信息技术书上碰到了一个“韩信点兵”问题，原题如下（无图，纯手打）：
民间流传着“韩信点兵”的故事。韩信带1500名士兵打仗，战死四五百人，剩下的士兵排队：站3人一排，多出2人；站5人一排，多出4人；站7人一排，多出6人。韩信马上说出人数：1049。请编写计算机程序验证结果。
于是我编了个的python程序，如下：for i in range(1000,1101):
if i%3==2 and i%5==4 and i%7==6:
print('共有',i,'个士兵。')
# 上为程序本体，下为输出结果。
共有 1049 个士兵。我觉得得我编的程序运算量有点大，对于同一个数要进行4次运算和3次判断，不符python简约的编程思想。
所以我希望广大的鱼友们可以集思广益，想想有什么程序优化的方法。
本帖最后由 傻眼貓咪 于 2021-9-6 22:45 编辑
def check(num):
return (num%3 == 2) and (num%5 == 4) and (num%7 == 6)
# 1500 死 400 = 1100，1500 死 500 = 1000
# 區間：1000 ~ 1100
for i in range(1000, 1101):
if check(i):
print(i)
1049 根据题意，可知人数+1为3，5，7的倍数，即105的倍数，则1001（人数+1）除105并向上取整，是105的倍数，这个数*105再-1，就是答案。
import math
x = 3 * 5 * 7
n = math.ceil(1001 / x) * x -1
print('共有%d个士兵。'%n) a=1000
while a<1101:
if a%3 == 2:
a += 3
else:
a +=1
if a % 5 == 4 and a % 7 == 6:
print(a)
break
这是我能想到最快的方法了 本帖最后由 傻眼貓咪 于 2021-9-6 23:01 编辑
def lcm(x, y):
if x > y:
greater = x
else:
greater = y
while(True):
if((greater % x == 0) and (greater % y == 0)):
res = greater
break
greater += 1
return res
x = 3
y = 5
z = 7
key = lcm(lcm(x, y), z)
res = key-1
while res < 1000:
res += key
print(res)
代碼簡化：
import math
def lcm(a, b):
return abs(a*b) // math.gcd(a, b)
key = lcm(lcm(3, 5), 7)
res = key-1
while res < 1000:
res += key
print(res) 冬雪雪冬 发表于 2021-9-6 22:50
根据题意，可知人数+1为3，5，7的倍数，即105的倍数，则1001（人数+1）除105并向上取整，是105的倍数，这个 ...
假設題目是 3, 6, 7 呢？
以你的代碼得倍數 126
正確倍數是 42 傻眼貓咪 发表于 2021-9-6 23:04
假設題目是 3, 6, 7 呢？
以你的代碼得倍數 126
正確倍數是 42
这里是公倍数，由于3，5，7互质，所以为3*5*7=105
而3，6，7的最小公倍数是42 冬雪雪冬 发表于 2021-9-6 22:50
根据题意，可知人数+1为3，5，7的倍数，即105的倍数，则1001（人数+1）除105并向上取整，是105的倍数，这个 ...
果然从数学上去优化算法是最快的,大佬也太顶了吧 本帖最后由 CtrlCV工程師 于 2021-9-7 22:22 编辑
冬雪雪冬 发表于 2021-9-6 22:50
根据题意，可知人数+1为3，5，7的倍数，即105的倍数，则1001（人数+1）除105并向上取整，是105的倍数，这个 ...
这程序，对人对机器都友好。我只能说，兄弟nb{:10_275:}。 傻眼貓咪 发表于 2021-9-6 22:44
这其实跟我的差不多，对机器都不大友好 伏惜寒 发表于 2021-9-6 22:57
a=1000
while a
如果if后面是“a%7==6”的话会更好些，因为枚举算法要尽可能缩短枚举范围吗。不过怎么样都比我好 本帖最后由 CtrlCV工程師 于 2021-9-7 22:26 编辑
傻眼貓咪 发表于 2021-9-6 22:58
代碼簡化：
我差不多懂你的意思了函数lcm()是求最大公约数的，然后差不多是数学方法。不过你的第2个程序的第3行代码我看不懂。为什么3，5，7三个数我怎么代算出来都是1（我的python版本比较低，不能直接验证，都是口算的）。解释一下ok？ abs() 取絕對值
gcd() 取最大公因數
a和b最小公倍數 = (a乘b的絕對值) 除 大公因數 傻眼貓咪 发表于 2021-9-7 22:30
abs() 取絕對值
gcd() 取最大公因數
哦，所以整条式是返回这两个数的最大公约数吗？ CtrlCV工程師 发表于 2021-9-7 22:33
哦，所以整条式是返回这两个数的最大公约数吗？
整條式返回最小公因數（LCM - Least Common Multiple）
這題剛好取 3，5 和 7 作為範例，所以像樓上的所說，3個互乘就是最小公因數（我當然知道，要我一行代碼解決也沒有問題）但是主要是想讓樓主明白，為什麼要用最小公因數？因為真正外面面試官挑戰的是你真正明白題目，而不是走直徑，所以我才故意寫多一些讓人明白 傻眼貓咪 发表于 2021-9-7 22:39
整條式返回最小公因數（LCM - Least Common Multiple）
這題剛好取 3，5 和 7 作為範例，所以像樓上的所 ...
我知道要算最小公倍数，只是刚才我想的是最小公倍数，却打成了最大公因数{:10_277:}{:10_284:}。
其实我后天或者大后天就要就要去学生会IT部面试了{:10_266:}（既然我看信息技术书，那您就应该知道我是学生吧）。您真的很有学校老师的那种用心良苦。而且您也提醒了我：要好好准备面试。谢谢，谢谢{:10_275:}
页:
[1]