java - C语言算法题-韩信点兵 求解?
本文介绍了java - C语言算法题-韩信点兵 求解?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
问 题
完全不知道怎么下手??
解决方案
这个。。。不知道怎么说才好。。。
设共有 n 个人,三人一排,五人一排,七人一排,看最后一排剩下 a, b, c 人
不就是
n % 3 = a
n % 5 = b
n % 7 = c
下面不就很简单了么?
方法 1: 暴力
n 从 10 到 100 都试一下。这个不用我说了吧
方法 2: 数学方法(解同余式-初等数经)
例题:
n % 3 = 2
n % 5 = 4
可以转化成什么呢?
设 n / 3 = x 余 2, n / 5 = y 余 4
==> 3x + 2 = 5y + 4
==> 3x = 5y + 2
x,y 在 自然数的最小解是 x = 4, y = 2
==> n 最小是 12
3 和 5 的最小公倍数 = 15
所以 n % 15 == 12
三个的话,先算两个,再算第三个。
这篇关于java - C语言算法题-韩信点兵 求解?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文