本人大二，最近开始自学算法，在此记录自己学习过程中接触的习题。与君共勉。

水平有限，目前涉及的题目都比较水。

题目分布为5+1.  5为自己学习的5道水题。 1为从网上找到的比较有水平的相关题目。

 

一步步学算法(算法题解)---4

穷举法。

 

穷举算法是程序设计中使用得最为普遍、大家必须熟练掌握和正确运用的一种算法。它利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案。

    用穷举算法解决问题，通常可以从两个方面进行分析：

    一、问题所涉及的情况：问题所涉及的情况有哪些，情况的种数可不可以确定。把它描述出来。

    二、答案需要满足的条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。把这些条件描述出来。

1.勾股数

问题描述:

 

编写一个程序,求出100之内所有勾股数。 

 

问题分析:

 

可设置I为一斜边(0〈=i〈100〉,j,m为直角边(j,k〈i〉,用两重循环求出所有满足条件的i,j值时m的值,并对m进行判断,判断m是否是一个小于斜边i的完全平方数。若满足该条件,则记数变量n加1 

#include 
    
     #include 
     
      int main(){    int i, j, k, n = 1;        for (i=1; i<100; i++)    {        for (j=1; j
     
    

 

2.亲密数

问题描述:

 

求出10000以内的亲密数.亲密数:如果A的因子和为B,B的因子和为A,则A与B为亲密数.

正整整A的因子:能整除A的所有正整数(除A本身)。如12的因子为:1,2,3,4,5,6. 

 

问题分析:

无非就是遍历。查找1000以内满足条件的所有亲密数。本题用一函数来计算所求数的因子和,可降低其复杂度。

 

#include 
    
     int fsum(int a){    int i, sum = 1;    for (i=2; i<=a/2; i++)        if(a%i==0)            sum += i;    return sum;}int main(){    int a, b, c;    for (a=1; a<=10000; a++)    {        b = fsum(a);        c = fsum(b);        if ( a==c && b!=a)            printf("%8d,%8d\n", a, b);    }    return 0;}/********************************** 打印结果： 220,     284 284,     220 1184,    1210 1210,    1184 2620,    2924 2924,    2620 5020,    5564 5564,    5020 6232,    6368 6368,    6232 **********************************/
    

 

 

3。四方定理

问题描述:

 

编程验证"四方定理":任意一个自然数都能由四个数的平方和来表示. 

 

问题分析:

 

这类问题最主要的是考虑循环变量的起始与终止取值.这个程序中使用了四个循环,其实只须三个循环就能解决这个问题,大家不妨试一试. 

 

#include "math.h"#include "stdlib.h"void check_(int i){    int arr_[4];  //用来纪录4个数    int t;    t = i;      for (arr_[0]=sqrt(t); arr_[0]>=sqrt(t/2); arr_[0]--)    {        t -= arr_[0] * arr_[0];        for (arr_[1]=sqrt(t); arr_[1]>=sqrt(t)/2; arr_[1]--)        {            t -= arr_[1] * arr_[1];            for (arr_[2]=sqrt(t); arr_[2]>=sqrt(t)/2; arr_[2]++)            {                t -= arr_[2] * arr_[2];                for (arr_[3]=sqrt(t); arr_[3]>=sqrt(t)/2; arr_[3]++)                    if (arr_[0]*arr_[0]+arr_[1]*arr_[1]+arr_[2]*arr_[2]+arr_[3]*arr_[3]==i)                    {                        printf("%5d %5d %5d %5d",arr_[0],arr_[1],arr_[2],arr_[3]);                        exit(0);                    }            }        }    }    printf("无解!");}int main(){    int n;    printf("请输入一个整数:");    scanf("%d",&n);     check_(n);    return 0;}/********************************** 打印结果： 请输入一个整数:12 3     1     1     1 **********************************/

 

 

 

4。双百问题

 

问题描述:

 

王大娘要用100元钱买100头小牲畜,不多不少要求“双百”。若小牛每头10元,羊羔每只3元,小兔每只0.5 元。请你替她算算应该怎样买法? 

 

问题分析:

 

 

用变量i,j分别表示牛,羊的头数,则买牛需I*10元,买羊需i*3元,这时可算出剩下的钱以及剩下的钱所能买小兔的头数,根据三种小牲畜的总头数即可求得解。 

#include "stdlib.h"int main(){    int i, j, k, m;    for (i=0; i<=10; i++)        for (j=0; j<=(100-i*10)/3; j++)            if ((i+j+(100-i*10-j*3)*2) == 100)                printf("%d %d %d\n",i,j,(100-i*10-j*3)*2);    return 0;}/********************************** 打印结果： 0 20 80 5 1 94 **********************************/

 

 

 

5.连续和数。

问题描述:

 

请找出十三个连续的自然数,个个都是合数。 

 

问题分析:

所谓“合数”,就是非素数,下面的解法是用flag作为是否是合数的标志,count用来计数。

 

#include "stdlib.h"#include 
        
         int main(){    int count = 0, i = 9, j , flag;    do    {        flag = 0;        for (j=3; j<=sqrt(i); j++)            if (i%j==0)                flag=1;           if (flag==0)            count = 1;        else            count += 2;            i += 2;    }while (count<13);        for (j=i-13; j
        

 

6*使用穷举法解决0—1背包问题

问题描述：

有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

问题分析：

 

设n个物品的重量和价值分别于数组w[ ]和v[ ]中，限制重量为tw.考虑一个n元组（x0，x1，…，xn-1），其中xi=0 表示第i个物品没有选取，而xi=1则表示第i个物品被选取。用枚举法解决背包问题，需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有的n元组，就可以得到问题的解。

    显然，每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为0～2n-1.因此，如果把0～2n-1分别转化为相应的二进制数，则可以得到我们所需要的2n个n元组。

 

#include 
        
         #include 
         
          #define MAX 100                      // 限定最多物品数/*将n化为二进制形式，结果存放到数组b中*/void conversion(int n,int b[MAX]){    int i;    for(i=0;i
          
           maxv))        {            for (j=0;j