本人大二，最近开始自学算法，在此记录自己学习过程中接触的习题。与君共勉。
水平有限，目前涉及的题目都比较水。
题目分布为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++, 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
", 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
",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个物品的重量和价值分别存储于数组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:
");
scanf("%d",&n); // 输入物品个数
printf("please input tw:");
scanf("%f",&tw); // 输入背包的限制重量
/*输入各个物品的重量*/
for(i=0;i<n;i++)
{
printf("please input the weight of w[%d]:
",i);
scanf("%f",&w[i]);
}
/*输入各个物品的价值*/
for(i=0;i<n;i++)
{
printf("please input the value of v[%d]:
",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:
",maxv); // 输出放入背包的物品的最大价值
printf("the selection is:
");
/*输出物品的选择方式*/
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
**********************************/