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

￡神魔★判官ぃ 2022-10-21 11:45 117阅读 0赞

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

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

**题目分布为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 <stdio.h>
    #include <math.h>
    
    int main()
    {
        int i, j, k, n = 1;
        
        for (i=1; i<100; i++)
        {
            for (j=1; j<i; j++)
            {
                k = sqrt(i*i-j*j);
                if ((k*k == i*i-j*j) && (k <= j))
                {
                    printf("%d : %d,%d,%d\n", n++, i, j, k);
                }
            }
        }
        return 0;
    }
    
    /**********************************
     打印结果：
     1 : 5,4,3
     2 : 10,8,6
     3 : 13,12,5
     4 : 15,12,9
     5 : 17,15,8
     。。。。。。。。。。。。。
     
     **********************************/

# 2.亲密数 #

问题描述:

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

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

问题分析:

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

#include <stdio.h>
    
    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 <math.h>
    
    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<i;j++)
            printf("%d ",j);
        
        return 0;
    }
    /**********************************
     打印结果：
    114 115 116 117 118 119 120 121 122 123 124 125 126 
     **********************************/

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

**问题描述：**

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

**问题分析：**

**设n个物品的重量和价值分别[存储][Link 1]于数组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 <stdio.h>
    #include <math.h>
    
    #define MAX 100                      // 限定最多物品数
    /*将n化为二进制形式，结果存放到数组b中*/
    void conversion(int n,int b[MAX])
    {
        int i;
        for(i=0;i<MAX;i++)
        {
            b[i] = n%2;
            n = n/2;
            if(n==0)break;
        }
        
    }
    
    int main()
    {
        int i,j,n,b[MAX],temp[MAX];
        float tw,maxv,w[MAX],v[MAX],temp_w,temp_v;
        printf("please input n:\n");
        scanf("%d",&n);   // 输入物品个数
        printf("please input tw:");
        scanf("%f",&tw);    // 输入背包的限制重量
        /*输入各个物品的重量*/
        for(i=0;i<n;i++)
        {
            printf("please input the weight of w[%d]:\n",i);
            scanf("%f",&w[i]);
        }
        /*输入各个物品的价值*/
        for(i=0;i<n;i++)
        {
            printf("please input the value of v[%d]:\n",i);
            scanf("%f",&v[i]);
        }
        maxv = 0;
        /*穷举2n个可能的选择，找出物品的最佳选择*/
        for (i=0;i<pow(2,n);i++)
        {
            for (j=0;j<n;j++)
            {
                b[j] = 0;
            }
            conversion(i,b);
            temp_v = 0;
            temp_w = 0;
            for (j=0;j<n;j++)
            {
                if (b[j]==1)
                {
                    temp_w = temp_w+w[j];
                    temp_v = temp_v + v[j];
                }
            }
            /*试探当前选择是否是最优选择，如果是就保存下来*/
            if ((temp_w < tw)&&(temp_v>maxv))
            {
                for (j=0;j<n;j++)
                {
                    temp[j] = 0;
                }
                maxv = temp_v;
                for (j=0;j<n;j++)
                {
                    temp[j] = b[j];
                }
            }
        }
        printf("the max values is %f:\n",maxv); // 输出放入背包的物品的最大价值
        printf("the selection is:\n");
        /*输出物品的选择方式*/
        for (j=0;j<n;j++)
        {
            
            printf("%d   ",temp[j]);
        }
        
        return 0;
    }
    /**********************************
     打印结果：
     please input n:
     3
     please input tw:100
     please input the weight of w[0]:
     30
     please input the weight of w[1]:
     80
     please input the weight of w[2]:
     60
     please input the value of v[0]:
     20
     please input the value of v[1]:
     70
     please input the value of v[2]:
     60
     the max values is 80.000000:
     the selection is:
     1   0   1
     **********************************/

[Link 1]: http://www.storworld.com/