Question

韓信是漢高祖劉邦手下的大將,他英勇善戰(zhàn),智謀超群,為建立漢朝立下了汗馬功勞.據(jù)說他在點兵的時候,為了保證軍事機密,不讓敵人知道自己部隊的實力,采用下述點兵方法：先令士兵從1～3報數(shù),結(jié)果最后一個士兵報2；再令士兵從1～5報數(shù),結(jié)果最后一個士兵報3；又令士兵從1～7報數(shù),結(jié)果最后一個士兵報4.這樣,韓信很快就算出了自己部隊士兵的總數(shù).請設(shè)計一個算法,求出士兵至少有多少人.

Answer 1

解析：第一步：首先確定最小的除以3余2的正整數(shù)：2；

第二步：依次加3就得到所有除以3余2的正整數(shù)：

2,5,8,11,14,17,20,23,26,29,32,35,38,41,44,47,50,53,56,…；

第三步：在上列數(shù)中確定第一個除以5余3的正整數(shù)：8；

第四步：然后依次加上15,得到8,23,38,53,…不難看出,這些數(shù)既滿足除以3余2,又滿足除以5余3；

第五步：在第四步得到的一列數(shù)中找出滿足除以7余4的最小數(shù)53,這就是我們要求的數(shù).