赞
踩
在中国数学史上流传着一个“韩信点兵”的故事:韩信是汉高祖刘邦手下的大将,他英勇善战,智谋超群,为汉朝建立了卓越功劳,据说韩信的数学水平也非常高超,他在点兵的时候,为了知道有多少个兵,同时又能保住军事机密,便让士兵排队报数:
按从1至5报数,记下最末一个士兵报的数为1;
再按从1至6报数,记下最末一个士兵报的数为5;
再按1至7报数,记下最末一个报的数为4;
最后按1至11报数,最末一个士兵报的数为10;
你知道韩信的排队中至少有多少个兵吗?
1.设计要点:
设兵数为x,则x满足下述不定方程组:
x=5y+1 mod(x,5)=1
x=6z+5 mod(x,6)=5
x=7u+4 mod(x,7)=4
x=11v+10 mod(x,11)=10
其中y,z,u,v都是正整数,试求满足以上不定方程组的最小正整数x;
应用枚举可以得到至少的兵数,x从1开始递增1取值当然可以,但不必要,事实上枚举次数可联系问题的具体实际大大缩减;
(1)、注意到x除11余10,于是可设置x从21开始,以步长11递增,此时,只要判别前三个条件即可;
(2)、由以上第2、4两方程知x+1为11的倍数,也为6的倍数,而11与6互素,因而x+1必为66的倍数,于是取x=65开始,以步长66递增,此时,只要判别x%5=1与x%7=4两个条件即可;
这样可算得满足条件的最小整数x即可点兵的数量;
2.程序设计:
#include<stdio.h>
int main()
{
long x=65;
while(1)
{
x=x+66;
if(x%5==1 && x%7==4)
{
printf("至少有兵: %ld个",x);
break;
}
}
}
3.程序运行结果:
至少有兵: 2111个
4.一般情形的韩信点兵:
上述点兵是报4遍数,一般化为报n遍数,第i次从1至p(i)报数时,最末一名士兵报数为r(i),这里i=1,2,……,n;
(1)、设计要点;
如果r(i)=p(i),这在报数过程中是可能的,为统一处理,此时需要归零r(i)=0;
(2)、程序设计;
#include<stdio.h> int main() { long n,t,i,x,p[20],r[20]; printf("按1至p报数,最末一人报数为r\n"); printf("报数n轮,请输入n:"); scanf("%ld",&n); for(i=1;i<=n;i++) /*输入n轮报数的数据*/ { printf("第%ld轮,请输入p,r:",i); scanf("%ld,%ld",&p[i],&r[i]); if(r[i]==p[i]) r[i]=0; } x=r[n]; while(1) { x=x+p[n]; /*人数x为若干个p[n]加r[n]*/ t=0; for(i=1;i<=n-1;i++) if(x%p[i]!=r[i]) /*检测x满足其他n-1轮报数*/ { t=1; break; } if(t==0) { printf("至少有%ld个兵\n",x); break; } } }
(3)、程序运行示例及其注意事项:
按1至p报数,最末一人报数为r
报数n轮,请输入n:5
第1轮,请输入p,r:3,1
第2轮,请输入p,r:5,2
第3轮,请输入p,r:7,5
第4轮,请输入p,r:11,9
第5轮,请输入p,r:13,10
至少有2077个兵
以上求解的不定方程组,满足上述不定方程组的正整数解有无穷多组,程序输出的只有满足条件的最小正整数解;
例如,以上示例数据,2077+3*5*7*11*13=17092 也是一个解;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。