1. 枚举法

枚举法又称暴力算法，是指逐个考查某类事件的所有可能情况，进而得出一般结论的方法。枚举法的思想是将问题所有可能的答案逐个列举，然后根据条件判断此答案是否满足，保留满足的，舍弃不满足的。
枚举法比较直观，算法也很容易理解，但枚举法在实际使用中应该尽量减少变量的个数，以及搜索的空间，这样算法的效率才能提高。

2.百钱买百鸡

我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱买百鸡”问题，该问题的叙述如下：
鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何?
本题的数据规模比较小，利用现代计算机的算法可以直接枚举，由于公鸡、母鸡和小鸡的数量都在0~100只，因此可以直接枚举整个空间。案例代码如下：

for(i=0; i<=100;i++)
   for(j=0;j<=100;j++ )
     for(k=0; k<=100;k+ +)
      if(5* i+3* j+k/3==100 && k%3==0 && i+j+k==100)
      printf("公鸡号2d只，母鸡号2d只,小鸡号2d只\n",i,j,k);

如果本题的已知条件不变，将数据规模变大,。变成“万钱买万鸡”的问题,则请你计算一下总共有多少种买法。
这时需要通过变换以减少搜索的空间。
本题中，有3个变量i,j,k,其实只要任何两个变量的值确定后,另一个变量的值就已经确定了。例如: i=1，j=2，这时k只能等于100-1-2=97才满足要求，所以通过变量之间的关系就可以减少搜索空间。
通过分析可知，,小鸡的变量k不需要搜索整个空间，因为要求k的值必须是3的倍数才能满足条件，这样就可以进一步减少搜空间，于是“万钱买万鸡”的问题可以如下解决。

int count=0;
for(-i=0;i<=10000;i++)
   for(k=0;k<=10000;k=k+3)
   {
    j=10000-i-k;
    1f(j< 0) continue;
    1f(5* i+3* j+k/3==10000)
   count++;
  }
printf("%d", count);

如果本题的规模进一步扩大到“百万钱买百万鸡”，那利用上述算法就会超时，需要进步缩小枚举的规模。
通过题目分析可知，要想用定数量的钱买到同等数量的鸡，小鸡必不可少，（因为只有有小鸡，数量才能达到平衡)，并且是3的倍数。通过分析可知：
三只小鸡 + 一只母鸡=四只鸡，而这四只鸡是四文钱，刚好达到平衡。
六只小鸡+ 一只公鸡=七只鸡，而这四只鸡是七文钱，刚好达到平衡。
也就是说，要想用一定数量的钱买到同等数量的鸡，只有这两种组方式能达到平衡;
三只小鸡 + 一只母鸡........①
六只小鸡 + 一只公鸡.........②
本问题就变成了求4x+7y=1000000这个方程的解空间的数量(x代表①组的数量，y代表②组的数量)。这个方程中，4 是1000000的因子，7是一个质数，很容易地就能得出解空间的规律为：
x                   y
250000      0
249993      4
249986       8
249979      12
249972      16
249965     20 ……
这个解空间，即母鸡组每次减少7组，公鸡组每次增加4组就可以达到平衡，所以程序可以进一步简化为：

int count=0;
for(x= 250000;x>=0;  x=x-7)
count+ + ;
printf("id", count) ;

进一步简化为
printf("ad", 1000000/28+1) ;
这个式子请同学们自己分析和思考一下。
通过本题可以看出，使用枚举法一方面是非常灵活的，另一方面，根据问题的规模需要探索不同的算法，这也是算法竞赛经常考查考生的地方，大家在后面的学习过程中要学会分析问题的规模。
在大多数算法竞赛测试平台上，每秒的操作次数约为1e7,在这个限制下时间复杂度一定的算法存在数据规模的处理上限，具体的时间复杂度和数据规模上限如下表所示。

3. 等差素数数列（2017年试题B）（答案见下期）

【问题描述】
2,3,5,7,11,13,..是素数数列。
7,37,67,97,127.157.这样完全由素数组成的等差数列称为等差素数列。
上述数列的公差为30，长度为6。
2004年。格林与陶哲轩合作证明了存在任意长度的等差素数列。这是数论领域的一项惊人成果!
有了这理论作为基础，请你借助手中的计算机满怀信心地搜索：长度为10的等差素数列，其公差最小值是多少?
注意:需要提交一个整数，不要填写任何多余内容和说明文字。
[参考答案]
210

[提示]
本题是关于素数的题目，所以第一步就是要学会判断素数的算法。常用的素数判断算法有两种：一种是基于素数定义的枚举法，另一种是筛选法。
基于素数定义的枚举法的思想非常简单，要想判断n是否是素数，只需要从2到n-1枚举是否有数能够被n整除即可。该方法不再赘述，这里重点介绍筛选法。
(1)筛选法
筛选法非常适合求一个整数区间中各数是否是素数的情况，并且区间越大，效率越高。筛选法据说是由古希腊的埃拉托斯特尼(Eratosthenes，约公元前274-公元前194年)发明的，,因此又称之为埃拉托斯特尼筛子。
具体做法是：先把N个自然数按次序排列起来，因为1不是质数，也不是合数，所以将1划去，从2开始。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22……N
第二个数2是质数，保留下来，把2后面所有能被2整除的数都划去。
2 3 5 7 9 11 13 15 17 19 21 ……N
这时，2后面第一个没被划去的数是 3,把3留下，再把3后面所有能被3整除的数都划去。
2 3 5 7 11 13 17 19 ……N
3后面第一个没被划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。
这样一直做下去，就会把不超过N的全部合数都筛掉，留下的数就是不超过N的全部质数。
因为希腊人是把数写在涂蜡的板上的，每划去一个数，就在上面记一个小点，寻求质数的工作完毕后，许多的小点就像一个筛子，所以就把埃拉托斯特尼的方法叫作“埃拉托斯特尼筛子”，简称“筛选法”。
(2)程序的思路
当判断出2~N中的所有素数后，下面便可以采用暴力算法进行枚举。目前有3个不确定的变量：N的范围、公差和素数序列的起始值。
N的范围可以设定成一个常量，需要足够大，以便满足要找的序列。
公差和素数序列的起始值分别设定为两个变量，采用枚举法进行两层循环。循环过程中，判断是否有满足长度为10的等差素数列，如果有，则输出其公差，即是公差最小值。

4.上期答案——杨辉三角

[解析]
本题主要考查杨辉三角的相关知识，通过观察可以得出杨辉三角的基本性质:每个数均等于它上方两数之和。
可以采用递推的方式从上到下计算出杨辉三角中每个元素的数值，边计算边比较，见参考程序一和参考程序二
但该段程序代码要求N的范围只能在20000以内，无法达到1000000。要想解决该题，必须对杨辉三角进行分析。其实，杨辉三角的规律还可以利用数学的方式表示出来，即杨辉三角中每个数的值为组合数cn m,其中,m代表行数，n代表列数，如下图1所示。

图1 组合数 根据组合数的性质：前一半数和后一半数是对称数，即Ci n= Cn-i n，所以每行只需要考虑前一半数即可。

图2一半组合数 从图中可以得出以下结论：（1）任意一个正整数N在杨辉三角中肯定会出现，并且出现的次序是按照从上到下的斜行出现，即如图2所示，6出现两次，第3斜行比第2斜行出现的早。（2）按照最头方向推列，.每斜行的数据起始位为Ci n，存在n=2i的关系，即C1 2，C2 4，C3 6。（3）这里需要估算数据计算终止的边界范围，利用器或计算器或者编程实现都可以，确定C17 34=2333606220>109,s所以i最大从16开始。（4）由于每个行的数据都是通增的，因此可以可以用二分查找法快速逼近要查找的数据。具体算法见参考程序3 参考程序1

#include <iostream>
#include <math.h>
using namespace std;
int a[20000][20000];
int main()
{
 int n;
 cout<<"input n：";
 cin>>n;
 if(n==1)
 {cout<<1<<endl;
 return 0;
 }
 else
 {
 a[0][0]=1;
 int num=1; //位序 
 for(int i=1;i<20000;i++)
  for(int j=0;j<=i;j++)
  {
   if(j==0)
    a[i][j]=1; //每一行的第1列是1 }
   else
       a[i][j]=a[i-1][j-1]+a[i-1][j];
   num++;// 位序加1  
      if(a[i][j]==n)  
      {
       cout<<num<<endl;
       return 0;
   }
  }
 }
}

参考程序2——申茂生答案

#include <iostream>
using namespace std;
int main()
{
 int n,i=1,j=1;//i为第几个数，j为第几行 
 int num[1000]={};
 cin>>n; 
 while(true)
 {
  if(i==j*(j+1)/2||i==(j*(j+1)/2-j+1))//判断该数是否为每行的头或尾 
   num[i]=1;
  else
   num[i]=num[i-j]+num[i-j+1];
  if(num[i]==n)
   break;
  if(i==j*(j+1)/2)
   j++;
  i++;
 }
 cout<<i;
}

参考程序3：

#include <iostream>
#include <math.h>
using namespace std;
typedef long long LL;
int n;
LL combi(int a,int b)//从a中取b个数的组合 
{
 LL res=1;
 for(int i=a,j=1;j<=b;i--,j++) 
 {
  res=res*i/j;
  if(res>n)  return res;  
 }
 return res; 
 } 
 bool check(int k)
 {
  LL le=k*2,ri=n;
  while(le<ri)
  {
   LL mid=(le+ri)/2;
   if(combi(mid,k)>=n) ri=mid;
   else le=mid+1;
   
  }
  if(combi(ri,k)!=n) return false;
  cout<<ri*(ri+1)/2+k+1;
  return true;
  } 
int main()
{
 cout<<"input n:";
 cin>>n;
 for(int k=16;k>=1;k--)
 if(check(k))
  break;
 return 0;
}

5.猴子选大王

 参考程序——申茂生答案

#include <iostream>
using namespace std;
int main()
{
 int n,m,i=0,j=1,k=0;//j为当前猴子的报数，k为出局的猴子数 
  cin>>n>>m;
 while (m!=0&&n!=0)
 {
 
  int *monkey=new int[n];
 for(int i=0;i<n;i++)
    monkey[i]=1;//未出局的猴子为1 
 while(k<n-1)//当出局的猴子达到n-1只时停止 
 {
   if(monkey[i])//若当前猴子未出局 
  {
   if(j==m)//若当前猴子报的数为m 
   {
    monkey[i]=0;//该猴子出局 
    j=1;//从一开始报数 
    k++;//出局的猴子数+1 
   }
   else
    j++;
  }
  i++;
  if(i==n)
   i=0;
 }
 for(int i=0;i<n;i++)//找到未出局的猴子 
 {
  if(monkey[i])
  {
   cout<<i+1;//输出编号 
   break;
  }
 }
 }

---

添加 家长论坛微信