穷举法—韩信点兵

按从1至 5报数,按从 1至 7报数,按从 1至 11报数,最末一个士兵报的数为 10,按从1至 5报数,按从 1至 7报数,韩信让士兵分别3个3个报数多2人,就是解了三个同余方程

穷举法—神帅韩信点兵,穷举神帅韩信点兵

   神帅韩信点兵。

神帅韩信有一队兵,他想通晓有稍许人,便让士兵排队报数。

按从1至 5报数,最末三个士兵报的数为1;

按从1至6报数,最末三个组长报的数为5;

按从 1至 7报数,最末二个小将报的数为 4;

按从 1至 11报数,最末三个兵士报的数为 10。

您知道神帅韩信至少有微微兵吗?


      2、【算法观念】

设兵数为x,则按题意x应满足下述关系式:x%5 ==1 && x%6==5 &&x %7==4
&& x%11==10

使用穷举法对x从
1开首试验,可获得神帅韩信至少有微微兵。


   
  3、
代码实战:

穷举法,设置标识find

#include<stdio.h>
#include "stdlib.h"  
int main( )
{
int x =1;int find = 0; /*设置找到标志为假*/

  while (!find)
  {
    if (x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10)
       {
        find = 1;
        }
    x++;
  printf(" x = %d\n", x);}
  system("pause");   /*解决快闪问题*/
}

 

运作结果:(运营结果是从1—找到的最小数)

图片 1

4、其余代码:

goto

 1 #include<stdio.h>
 2 #include "stdlib.h"  
 3 int main( )
 4 {
 5   int x ;
 6    for(x=1; ;x++)
 7    {   
 8    if(x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10 )
 9       { printf("最小值是x= %d\n ",x);
10       goto end;
11         }
12      }
13    end:;
14  system("pause"); 
15 }

图片 2

break语句实践代码

 1 #include<stdio.h>
 2 #include "stdlib.h"  
 3 int main( )
 4 {
 5   int x ;
 6    for(x=1; ;x++)
 7    {   
 8    if(x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10 )
 9       { printf("最小值是x= %d\n ",x);
10         break;
11         }
12      }
13 
14  system("pause"); 
15 }

结果一样,不再赘言。

开展:用标记,求多少个解,如5个解

 1 #include<stdio.h>
 2 #include "stdlib.h"  
 3 int main( )
 4 {
 5     int x ;int f=0;
 6    for(x=1; f<5;x++)
 7    {   
 8    if(x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10 )
 9       { printf("满足要求的值是x= %d\n ",x);
10         f++;
11         }
12      }
13 
14  system("pause"); 
15 }

图片 3图片 4

 2017-04-16 21:26:44

 

 

 

by-lwb,转发评释出处 

 

韩信点兵。
神帅韩信有一队兵,他想清楚有几个人,便让战士排队报数。 按从 1 至 5
报数,最末二个精兵报…


穷举法,设置标识find

韩信点兵的旧事我们一定都听别人讲过,神帅韩信让士兵分别3个3个报数多2人,5个5个报数多4人,7个7个报数多6人,通过每一遍报数的余数总括出军事的人数。

图片 5图片 6

运维结果:(运维结果是从1—找到的最小数)

华夏剩余定理

咱俩把这几个算法实行,对于随便的方程组x≡bi
(mod mi)

即:

x≡b1 (mod
m1)

x≡b2 (mod
m2)

x≡b3 (mod m3)

……

x≡bn (mod
mn)

当中m皆以互质的

那便是说大家对此每一个方程,算出一个xi,使得xi满意:xi≡1
(mod mi) 且xi≡0 (mod mj)【j!=i】

也正是说xi是其余m的翻番,而模mi余1

y*(N/mi)≡1
(mod mi)  【N=m1*m2*m3*……mn】用扩张欧几里得算法就足以解出了

那就是说最后的x=(x1*b1+x2*b2+x3*b3+……xn*bn)
mod N   【N=m1*m2*m3*……mn】

【小编懒就先不打代码了= =】

水题:POJ1006

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
using namespace std;
const int maxn=100005,INF=2000000000,P=1000000007;

void exgcd(int a,int b,int& d,int& x,int& y){
    if(!b) {d=a;x=1;y=0;}
    else exgcd(b,a%b,d,y,x),y-=(a/b)*x;
}

int main(){
    int N=21252,A[4],T[4]={0,23,28,33},t,ans=0,cnt=0;
    while(cin>>A[1]>>A[2]>>A[3]>>t){
        if(t==-1) break;
        ans=0;
        cnt++;
        for(int i=1;i<=3;i++){
            int x,y,a=T[i],b=N/T[i],d;
            exgcd(a,b,d,x,y);
            ans=(ans+y*b*A[i])%N;
        }
        ans=((ans-t)%N+N)%N;
        if(!ans) ans+=N;
        printf("Case %d: the next triple peak occurs in %d days.\n",cnt,ans);
    }
    return 0;
}
 1 #include<stdio.h> 2 #include "stdlib.h"   3 int main 4 { 5     int x ;int f=0; 6    for(x=1; f<5;x++) 7    {    8    if(x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10 ) 9       { printf("满足要求的值是x= %d\n ",x);10         f++;11         }12      }13 14  system("pause"); 15 }

图片 7

找叁个数x1,使得它是5和7的翻番,而除3余2,

穷举法,设置标识find

图片 5图片 6

x≡4 (mod 5)

2017-04-1621:26:44

 

x≡6 (mod 7)

设兵数为x,则按题意x应知足下述关系式:x%5
==1 && x%6==5 &&x %7==4 && x%11==10

break语句推行代码

找贰个数x1,使得它是5和3的翻番,而除7余6,

按从1至6报数,最末一个精兵报的数为5;

  1. 标题陈说

下一场四个数加起来,就必将满意那几个规格,况且解周期为3*5*7

by-lwb,转发评释出处

      2、【算法观念】

找四个数x1,使得它是7和3的倍数,而除5余4,

goto

 

事实上,神帅韩信所做的,就是解了多少个同余方程: