实验二 枚举与递推

1．由0到4五个数字，组成5位数，每个数字用一次，但十位和百位不能为3（当然万位不能为0），输出所有可能的五位数。
#include<stdio.h>
int main()
{
int a,b,c,d,e,n=0,h;
for(a=0;a<=4;++a)
{
for(b=0;b<=4;++b)
{
for(c=0;c<=4;++c)
{
for(d=0;d<=4;++d)
{
for(e=1;e<=4;++e)
{
if(ab||bc||cd||de||b3||c3||ac||ad||ae||bd||be||ce)
h=h+1;
else
{
printf("%d%d%d%d%d\n",e,d,c,b,a);
n=n+1;
}
}
}
}
}
}
printf(“一共有%d种可能\n”,n);
}

2．最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。
例如, 当（a1,a2,a3,a4 ,a5,a6) = （-2,11,-4,13,-5,-2）时，最大子段和为: a2+a3+a4=20
输入格式:
第一行输入整数个数n（1≤n≤10000），再依次输入n个整数。
输出格式:
输出第一行为最大子段和，第二行为子段第一个数和最后一个数在整个序列中的位序。
输入样例1:
6
-2 11 -4 13 -5 -2
输出样例1:
20
2 4
#include<stdio.h>
#define N 101
int main()
{
int n,i,j,k,d[N],maxsum=0,sum=0,a=0,b=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&d[i]);
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
sum=0;
for(k=i;k<=j;k++)
{
sum+=d[k];
}
if(sum>maxsum)
{
maxsum=sum;
a=i;
b=j;
}
}
}
printf("%d\n",maxsum);
printf("%d %d\n",a,b);
return 0;
}

3．有两队选手每队5人进行一对一的比赛，甲队为A、B、C、D、E，乙队为J、K、L、M、N，经过抽签决定比赛对手名单。规定A不和J比赛， M不和D及E比赛。列出所有可能的比赛名单。
#include<stdio.h>
int main()
{
int j=0,k=0,l=0,m=0,n=0;
for(j=1;j<=5;j++)
{
for(k=1;k<=5;k++)
{
for(l=1;l<=5;l++)
{
for(m=1;m<=5;m++)
{
for(n=1;n<=5;n++)
{
if(j!=k&&j!=l&&j!=m&&j!=n&&k!=l&&k!=m&&k!=n&&l!=m&&l!=n&&m!=n&&j!=1&&m!=4&&m!=5)
{
switch(j)
{
case 1: printf("A vs J ");break; //A=1,B=2,C=3,D=4,E=5
case 2: printf("B vs J ");break;
case 3: printf("C vs J ");break;
case 4: printf("D vs J ");break;
case 5: printf("F vs J ");break;
}
switch(k)
{
case 1: printf("A vs K ");break;
case 2: printf("B vs K ");break;
case 3: printf("C vs K ");break;
case 4: printf("D vs K ");break;
case 5: printf("F vs K ");break;
}
switch(l)
{
case 1: printf("A vs L ");break;
case 2: printf("B vs L ");break;
case 3: printf("C vs L ");break;
case 4: printf("D vs L ");break;
case 5: printf("F vs L ");break;
}
switch(m)
{
case 1: printf("A vs M ");break;
case 2: printf("B vs M ");break;
case 3: printf("C vs M ");break;
case 4: printf("D vs M ");break;
case 5: printf("F vs M ");break;
}
switch(n)
{
case 1: printf(“A vs N\n”);break;
case 2: printf(“B vs N\n”);break;
case 3: printf(“C vs N\n”);break;
case 4: printf(“D vs N\n”);break;
case 5: printf(“F vs N\n”);break;
}
}
}
}
}
}
}
}

4．教材58页习题算法设计题第（1）小题。
有5个海盗，相约进行一次帆船比赛。比赛中天气发生突变,他们被冲散了。恰巧，他们都先后经过途中的一个无名的荒岛，并且每个人都信心满满，觉得自己是第一个经过该岛的人。
第一个人在沙滩上发现了一堆金币。他把金币分成5等份。发现刚好少了一个金币。他就从自己口袋拿出一个金币补充进去，然后把属于自己的那份拿走.
第二个到达的人也看到了金币，他也和第一个人一样，把所有金币5等分，发现刚好缺少一个金币，于是自己补进去一个，拿走了属于自己的那份。
第三人，第四人，第五人的情况一模一样。
等他们到了目的地，都说自己的情况，才恍然大悟，一起去荒岛找金币，然而再也没有找到荒岛。他们都惋惜地说：岛上还有一千多枚金币呢！
请推算荒岛上最初有多少金币？
#include<stdio.h>
int main()
{
int x,flag,i,j;
for(i=1000;i<2000;i++)
{
flag=1;
x=i;
for(j=1;j<=5;j++)
{
if(x%4!=0)
flag=0;
x=(x+x/4)-1;
}
if(flag&&(x+1)%5==0)
printf("%d\n",x);
}
return 0;
}

5．教材59页习题算法设计题第（2）小题。
任意给定一个正整数N，如果是偶数，执行：N/2；如果是奇数，执行：N*3+1。生成的新的数字再执行同样的动作，循环往复。通过观察发现，这个数字会一会儿上升到很高，一会儿又降落下来。就这样起起落落的，但最终必会落到“1”，这有点像小冰雹粒子在冰雹云中翻滚增长的样子。比如N=9：9，28，14，7，22，11，34，17，52，26，13，40，20，10，5，16，8，4，2，1
可以看到，N=9时，这个“小冰雹”最高冲到了52这个高度。
输入格式：一个正整数N(N<1000000)
输出格式：一个正整数，表示不大于N的数字，经过冰雹数变换过程中，最高冲到了多少。
例如，输入：
10
程序应该输出：
52
再例如，输入：
100
程序应该输出：
9232
#include<stdio.h>
int main()
{
int max=0,b,n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
b=i;
while(b!=1)
{
if(b%2==0)
b/=2;
else
b=b*3+1;
if(b>=max)
max=b;
}
}
printf("%d\n",max);
return 0;
}