算法分析与设计（实验二）枚举与递推

清疚 2022-12-23 00:53 105阅读 0赞

**一、实验目的：**  
理解枚举法的思想及程序的执行过程；  
理解递推算法的思想；  
能较熟练地编写枚举、递推程序，对给定的问题能设计出相应算法予以解决。  
**二、实验环境：**  
Visual C++  
**三、实验内容：**  
1.由0到4五个数字，组成5位数，每个数字用一次，但十位和百位不能为3（当然万位不能为0），输出所有可能的五位数。

#include<stdio.h>
    int main(){
        
    int a,b,c,d,e;
    int k=0;
    for(a=1;a<=4;a++){
        
    	for(b=0;b<=4;b++){
        
    		for(c=0;c<=4;c++){
        
    			for(d=0;d<=4;d++){
        
    				for(e=0;e<=4;e++){
        
    				if(a==b||b==c||c==d||d==e||c==3||d==3||a==c||a==d||a==e||b==c||b==d||b==e||c==d||c==e||d==e)
    				continue;
    				k++;
    				 printf("%d%d%d%d%d   ",a,b,c,d,e);
    				 if(k%10==0)
    					 printf("\n");
    				}
    			}
    		}
    	}
    }
    return 0;
    }

![在这里插入图片描述][2020112113392374.png_pic_center]  
2. 最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。  
例如, 当（a1,a2,a3,a4 ,a5,a6) = （-2,11,-4,13,-5,-2）时，最大子段和为: a2+a3+a4=20  
输入格式:  
第一行输入整数个数n（1≤n≤10000），再依次输入n个整数。  
输出格式:  
输出第一行为最大子段和，第二行为子段第一个数和最后一个数在整个序列中的位序。

#include<stdio.h>
    int Max(int a[],int n)
    {
        
        int max=0,sum=0,t=0;
    	int start,end;
        for(int i=0;i<n;i++){
        
            if(t+a[i]>a[i])
    		  t=t+a[i];
    		else t=a[i];
    		if(t>max)
    		{
        	max=t;
    		   end=i+1;
    		}
        }
    	for(int j=end-1;j>=0;j--){
        
    	     sum=sum+a[j];
    		 if(sum==max)
    			 start=j+1;
    	}
    	if(max<0)
    		printf("0");
    	else printf("%d\n",max);
    	printf("%d %d\n",start,end);
    return 0;
    }
    int main(){
        
        int n, a[10000];
        scanf("%d",&n);
        for(int i=0;i<n;i++){
        
        scanf("%d",&a[i]);
    	}
        Max(a,n);
        return 0;
    }

![在这里插入图片描述][20201121134010274.png_pic_center]  
3.有两队选手每队5人进行一对一的比赛，甲队为A、B、C、D、E，乙队为J、K、L、M、N，经过抽签决定比赛对手名单。规定A不和J比赛， M不和D及E比赛。列出所有可能的比赛名单。

#include<stdio.h>
    #include<string.h>
    int main(){
        
    	char s1[]={
        'A','B','C','D','E'};
    char s2[]={
        'J','K','L','M','N',}; 
    int i;
    for( i=0;i<5;i++)
    {
        
    if(s2[i]!=s2[0])
    {
        
    printf("%c,%c\n",s1[0],s2[i]); 
    }
    }
    for( i=0;i<5;i++)
    {
        
    
    printf("%c,%c\n",s1[1],s2[i]); 
    }
    for( i=0;i<5;i++)
    {
        
    
    printf("%c,%c\n",s1[2],s2[i]); 
    }
    for( i=0;i<5;i++)
    {
        
    if(s2[i]!=s2[3])
    {
        
    printf("%c,%c\n",s1[3],s2[i]); 
    }
    }
    for( i=0;i<5;i++)
    {
        
    
    if(s2[i]!=s2[3])
    {
        
    printf("%c,%c\n",s1[3],s2[i]); 
    }
    }
    return 0;
    }

![在这里插入图片描述][20201121134050669.png_pic_center]  
4.有5个海盗，相约进行一次帆船比赛。 比赛中天气发生突变，他们被冲散了。 恰巧，他们都先后经过途中的一个无名的荒岛，并且每个人都信心满满，觉得自己是第一个经过该岛的人。  
第一个人在沙滩上发现了一堆金币。他把金币分成5等份。发现刚好少一个金币。他就从自己口袋拿出一个金币补充进去，然后把属于自己的那份拿走。  
第二个到达的人也看到了金币，他也和第一个人一样，把所有金币5等分，发现刚好缺少一个金币，于是自己补进去一个，拿走了属于自己的那份。  
第三，第四，第五人的情况一模一样。  
等他们到了目的地，都说自己的情况，才恍然大悟，一起去荒岛找金币，然而再也没有找到荒岛。他们都惋惜地说：岛上还有一千多枚金币呢！  
请你根据这些信息，推算荒岛上最初有多少金币？

#include<stdio.h>
    
    int main(){
        
    long a;
    for(int i=1000;i<=2000;i++){
        
        a=i;
        for(int j=1;j<=5;j++){
        
            a*=5;
    		if(a%4!=0) break;
    		a/=4;
    		a--;
    		if(j==5)
    			printf("%d\n",a);
    	}
    }
    }

![在这里插入图片描述][20201121134148123.png_pic_center]  
5.任意给定一个正整数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;
    	int 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;
    }

[2020112113392374.png_pic_center]: /images/20221120/a9c47107005244d39c1c846013e57ab1.png
[20201121134010274.png_pic_center]: /images/20221120/4b28fad8c5c742ac90c580126558dad9.png
[20201121134050669.png_pic_center]: /images/20221120/f95c858758ea4fc5ba842ef553af20e6.png
[20201121134148123.png_pic_center]: /images/20221120/aef211b571a14c379433d59d012dd548.png