寒光博客

韩信点兵
初始题目 紫书2.1 升级 学习中国剩余定理 简单理解 暴力求解 最小值 #include <stdio...
扫描右侧二维码阅读全文
27
2019/07

韩信点兵

初始题目

紫书2.1
升级 学习中国剩余定理

简单理解

暴力求解 最小值

#include <stdio.h>

int main()
{
    int i,a,b,c,cas=0;
    while(scanf("%d%d%d",&a,&b,&c)==3)
    {
        cas++;
        for(i=10;i<=100;i++)
        {
            if(i%3==a&&i%5==b&&i%7==c)
                {
                    printf("Case %d: %d\n",cas,i);
                    break;
                }
        }
        if(i==101)
            printf("Case %d:No answer\n",cas);
    }
    return 0;
}

数论

   传说西汉大将韩信,由于比较年轻,开始他的部下对他不很佩服。有一次阅兵时,韩信要求士兵分三路纵队,结果末尾多2人,改成五路纵队,结果末尾多3人,再改成七路纵队,结果又余下2人,后来下级军官向他报告共有士兵2395人,韩信立即笑笑说不对(因2395除以3余数是1,不是2),由于已经知道士兵总人数在2300~2400之间,所以韩信根据23,128,233,------,每相邻两数的间隔是105(3、5、7的最小公倍数),便立即说出实际人数应是2333人(因2333=128+20χ105+105,它除以3余2,除以5余3,除以7余2)。这样使下级军官十分敬佩,这就是韩信点兵的故事。 
 韩信点兵问题简化:已知 n%3=2,  n%5=3,  n%7=2,  求n。 
因为n%3=2, n%5=3, n%7=2 且 3,5,7互质 (互质可以直接得到这三个数的最小公倍数)

令x= n%3=2 , y= n%5=3 ,z= n%7=2
      使5×7×a被3除余1,有35×2=70,即a=2; 
       使3×7×b被5除余1,用21×1=21,即b=1; 
       使3×5×c被7除余1,用15×1=15,即c=1。 

那么n =(70×x+21×y+15×z)%lcm(3,5,7) = 23 这是n的最小解

 而韩信已知士兵人数在2300~2400之间,所以只需要n+i×lcm(3,5,7)就得到了2333,此时i=22

参考文献

[1] https://blog.csdn.net/lyy289065406/article/details/6648551

本文作者:Author:     文章标题:韩信点兵
本文地址:https://dxoca.cn/Algorithm/198.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:July 31st, 2019 at 12:15 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment