窮舉法—韓信點兵

1. 問題描述：

   韓信點兵。

韓信有一隊兵，他想知道有多少人，便讓士兵排隊報數。

按從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—找到的最小數）

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 }

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 }

 2017-04-16 21:26:44

by-lwb,轉載註明出處http://www.cnblogs.com/lwbjyp/p/6719892.html