首页 > 代码库 > ACM试题 - 韩信点兵

ACM试题 - 韩信点兵

1. ACM试题题源:http://acm.nyist.net/JudgeOnline/problem.php?pid=34

关于韩信点兵:淮安民间传说着一则故事——“韩信点兵”,其次有成语“韩信点兵,多多益善”。韩信带1500名兵士打仗,战死四五百人,站3人一排,多出2人;站5人一排,多出4人;站7人一排,多出6人。韩信马上说出人数:1049。

2. 解题思路

思路一:可以先求出三组数,这三组数分别是分别用3,5,7除总人数在规定范围内所有的可能数值,然后求得这三组数中相同的那个数即可。

例如:一个数除以3余2,除以5余3,除以7余2,求符合条件的最小数。

解:先列出除以3余2的数:2,5,8,11,14,17,20,23,26……。再列出除以5余3的数:3,8,13,18,23,28……。这两列数中,首先出现的公共数是8。3与5的最小公倍数是15。两个条件合并成一个就是8+15×整数,列出这一串数是8,23,38,……,再列出除以7余2的数2,9,16,23,30……。就得出符合题目条件的最小数是23。
事实上,我们已把题目中三个条件合并成一个:被105除余23。
 
具体代码如下:
 1 import java.util.Scanner; 2  3 public class Main { 4  5     public static void main(String[] args){ 6          7         Scanner cin = new Scanner(System.in); 8         int a = cin.nextInt(), b = cin.nextInt(), c = cin.nextInt(); 9         int re = 0;10         for(int i = 9 + a; i < 101; i = i + 3){11             for(int j = 10 + b; j < 101; j = j + 5){12                 for(int k = 7 + c; k < 101; k = k + 7){13                     if(i == j && j == k){14                         re = i;15                         break;16                     }17                 }18             }19         }20         System.out.println(re);21         cin.close();22     }23 }

思路二凡是用3除剩下的余数,将它用70去乘(因为70是5与7的倍数,而又是以3去除余1的数);5除剩下的余数,将它用21去乘(因为21是3与7的倍数,又是以5去除余1的数);7除剩下的余数,将它用15去乘(因为15是3与5的倍数,又是以7去除余1的数),将这些数加起来,若超过105,就减掉105,如果剩下来的数目还是比105大,就再减去105,直到得数比105小为止。这样,所得的数就是原来的数了。

如上个例子:2*70+3*21+2*15 = 233  ,  233-(105*2)=23

代码很简单,我就不写了。

 

3. 参考资料

1. 韩信点兵_百度百科:http://baike.baidu.com/view/30671.htm?fr=aladdin

2. 韩信点兵算法流程图_百度知道:http://zhidao.baidu.com/question/95184845.html?qbl=relate_question_1&word=%BA%AB%D0%C5%B5%E3%B1%F8

ACM试题 - 韩信点兵