穷举法思想

在算法课程中，我们接触的第一个算法，也是相对简单的算法就是穷举法。其实穷举法的思想是，我们在解决问题时，先确定问题域，通过测试每一个情况，直到我们找到我们想要的答案。

如求解1到100之间的素数，我们通过穷举法，一个数，一个数的判断该数是否是素数，代码如下：

#include <stdio.h>

/*判断n是否是素数，是返回1；不是返回0*/
int isPrime(int n)
{
  int i;
  for(i=2;i<n;i++)
  {
    if(n%i == 0)
    {
      return 0;
    }
  }
  return 1;
}

getPrime(int low, int high)
{
  int i;
  for (i=low;i<=high;i++)
  {
    if(isPrime(i))
    {
      printf("%d ",i);
    }
  }
  printf("\n");
}

int main(int argc,char* argv[])
{
  int low,high;
  printf("please input the domain for searching prime\n");
  printf("low limitation:");
  scanf("%d",&low);
  printf("high limitation:");
  scanf("%d",&high);
  printf("The whole primes in this domain are\n");
  getPrime(low,high);
  return 0;
}

执行结果：

peng@ubuntu:~/src/test/c/suanfa/miaoqu$ ./3.3

please input the domain for searching prime

low limitation:1

high limitation:100

The whole primes in this domain are

1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

又如：TOM一共有5本新书，要借给A,B,C三个人，每个人只能借1本，则TOM可以有多少种不同的借书方法。

我们可以通过穷举，所有的借书情况，然后找出我们需要的（每个人只能借一本），因此这种方法，也是通过穷举法实现的，代码如下：

#include <stdio.h>

/*计算TOM可以有多少种不同的借书方法*/
int main(int argc, char* argv[])
{
  int i,j,k;
  printf("There are different methods for TOM to distribute his book to A,B,C\n");
  for(i=1;i<=5;i++)
    for(j=1;j<=5;j++)
      for(k=1;k<=5;k++)
     if(i != j && j != k && k != i)
     {
     printf("(%d,%d,%d) ",i,j,k);
         }
  printf("\n");
  return 0;
}

执行结果如下：

There are different methods for TOM to distribute his book to A,B,C

(1,2,3) (1,2,4) (1,2,5) (1,3,2) (1,3,4) (1,3,5) (1,4,2) (1,4,3) (1,4,5) (1,5,2) (1,5,3) (1,5,4) (2,1,3) (2,1,4) (2,1,5) (2,3,1) (2,3,4) (2,3,5) (2,4,1) (2,4,3) (2,4,5) (2,5,1) (2,5,3) (2,5,4) (3,1,2) (3,1,4) (3,1,5) (3,2,1) (3,2,4) (3,2,5) (3,4,1) (3,4,2) (3,4,5) (3,5,1) (3,5,2) (3,5,4) (4,1,2) (4,1,3) (4,1,5) (4,2,1) (4,2,3) (4,2,5) (4,3,1) (4,3,2) (4,3,5) (4,5,1) (4,5,2) (4,5,3) (5,1,2) (5,1,3) (5,1,4) (5,2,1) (5,2,3) (5,2,4) (5,3,1) (5,3,2) (5,3,4) (5,4,1) (5,4,2) (5,4,3)