[已解决]关于“韩信点兵”的程序优化问题

CtrlCV工程師

我在信息技术书上碰到了一个“韩信点兵”问题，原题如下（无图，纯手打）：

民间流传着“韩信点兵”的故事。韩信带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:50:15

根据题意，可知人数+1为3，5，7的倍数，即105的倍数，则1001（人数+1）除105并向上取整，是105的倍数，这个数*105再-1，就是答案。

1. import math
   
2. x = 3 * 5 * 7
   
3. n = math.ceil(1001 / x) * x -1
   
4. print('共有%d个士兵。'%n)

复制代码

跳转到最佳答案楼层

傻眼貓咪

1. def check(num):
   
2.     return (num%3 == 2) and (num%5 == 4) and (num%7 == 6)
   
3. 
   
4. # 1500 死 400 = 1100，1500 死 500 = 1000
   
5. # 區間：1000 ~ 1100
   
6. for i in range(1000, 1101):
   
7.     if check(i):
   
8.         print(i)

复制代码

1. 1049

复制代码

冬雪雪冬

根据题意，可知人数+1为3，5，7的倍数，即105的倍数，则1001（人数+1）除105并向上取整，是105的倍数，这个数*105再-1，就是答案。

1. import math
   
2. x = 3 * 5 * 7
   
3. n = math.ceil(1001 / x) * x -1
   
4. 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
这是我能想到最快的方法了

傻眼貓咪

1. def lcm(x, y):
   
2.    if x > y:
   
3.        greater = x
   
4.    else:
   
5.        greater = y
   
6.    while(True):
   
7.        if((greater % x == 0) and (greater % y == 0)):
   
8.            res = greater
   
9.            break
   
10.        greater += 1
    
11.    return res
    
12. 
    
13. x = 3
    
14. y = 5
    
15. z = 7
    
16. 
    
17. key = lcm(lcm(x, y), z)
    
18. res = key-1
    
19. 
    
20. while res < 1000:
    
21.     res += key
    
22. 
    
23. print(res)

复制代码

代碼簡化：

1. import math
   
2. def lcm(a, b):
   
3.     return abs(a*b) // math.gcd(a, b)
   
4. 
   
5. key = lcm(lcm(3, 5), 7)
   
6. res = key-1
   
7. while res < 1000:
   
8.     res += key
   
9. 
   
10. 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

白two

冬雪雪冬 发表于 2021-9-6 22:50
根据题意，可知人数+1为3，5，7的倍数，即105的倍数，则1001（人数+1）除105并向上取整，是105的倍数，这个 ...

果然从数学上去优化算法是最快的,大佬也太顶了吧

CtrlCV工程師

冬雪雪冬 发表于 2021-9-6 22:50
根据题意，可知人数+1为3，5，7的倍数，即105的倍数，则1001（人数+1）除105并向上取整，是105的倍数，这个 ...

这程序，对人对机器都友好。我只能说，兄弟nb。

CtrlCV工程師

傻眼貓咪 发表于 2021-9-6 22:44

这其实跟我的差不多，对机器都不大友好

CtrlCV工程師

伏惜寒 发表于 2021-9-6 22:57
a=1000
while a

如果if后面是“a%7==6”的话会更好些，因为枚举算法要尽可能缩短枚举范围吗。不过怎么样都比我好

CtrlCV工程師

傻眼貓咪 发表于 2021-9-6 22:58
代碼簡化：

我差不多懂你的意思了函数lcm()是求最大公约数的，然后差不多是数学方法。不过你的第2个程序的第3行代码我看不懂。为什么3，5，7三个数我怎么代算出来都是1（我的python版本比较低，不能直接验证，都是口算的）。解释一下ok？

傻眼貓咪

abs() 取絕對值
gcd() 取最大公因數

a和b最小公倍數 = (a乘b的絕對值) 除 大公因數

CtrlCV工程師

傻眼貓咪 发表于 2021-9-7 22:30
abs() 取絕對值
gcd() 取最大公因數

哦，所以整条式是返回这两个数的最大公约数吗？

傻眼貓咪

CtrlCV工程師 发表于 2021-9-7 22:33
哦，所以整条式是返回这两个数的最大公约数吗？

整條式返回最小公因數（LCM - Least Common Multiple）
這題剛好取 3，5 和 7 作為範例，所以像樓上的所說，3個互乘就是最小公因數（我當然知道，要我一行代碼解決也沒有問題）但是主要是想讓樓主明白，為什麼要用最小公因數？因為真正外面面試官挑戰的是你真正明白題目，而不是走直徑，所以我才故意寫多一些讓人明白

CtrlCV工程師

傻眼貓咪 发表于 2021-9-7 22:39
整條式返回最小公因數（LCM - Least Common Multiple）
這題剛好取 3，5 和 7 作為範例，所以像樓上的所 ...

我知道要算最小公倍数，只是刚才我想的是最小公倍数，却打成了最大公因数。
其实我后天或者大后天就要就要去学生会IT部面试了（既然我看信息技术书，那您就应该知道我是学生吧）。您真的很有学校老师的那种用心良苦。而且您也提醒了我：要好好准备面试。谢谢，谢谢