杭电OJ第11页2040~2044算法题（C语言）

亦凉 2023-10-06 16:01 37阅读 0赞

#### 目录 ####

*  2040.亲和数
 *  2041.超级楼梯
 *  2042.不容易系列之二
 *  2043.密码
 *  2044.一只小蜜蜂...

## 2040.亲和数 ##

Problem Description
    古希腊数学家毕达哥拉斯在自然数研究中发现，220的所有真约数(即不是自身的约数)之和为：
    1+2+4+5+10+11+20+22+44+55+110＝284。
    而284的所有真约数为1、2、4、71、142，加起来恰好为220。人们对这样的数感到很惊奇，并称之
    为亲和数。一般地讲，如果两个数中任何一个数都是另一个数的真约数之和，则这两个数就是亲和
    数。
    你的任务就编写一个程序，判断给定的两个数是否是亲和数
    Input
    输入数据第一行包含一个数M，接下有M行，每行一个实例,包含两个整数A,B； 其中 0 <= A,B <= 
    600000 ;
    Output
    对于每个测试实例，如果A和B是亲和数的话输出YES，否则输出NO。
    Sample Input
    2
    220 284
    100 200
    Sample Output
    YES
    NO

分析：在求一个整数的真约数之和时，注意不要将整数本身加入其中即可。

#include <stdio.h>
    
    //求一个整数的所有真约数之和 
    int SumOfTrueDivisor(int n){
        
    	int i,sum=0;
    	for(i=1;i<=n/2;i++){
        
    		if(n%i==0){
        
    			sum+=i;
    		}
    	}
    	return sum;
    }
    
    void AffinityNum(){
        
    	int n,sum1,sum2,i,A,B;
    	scanf("%d",&n);
    	while(n--){
        
    		scanf("%d%d",&A,&B);
    		if(A<0 || A>600000 || B<0 || B>600000){
        
    			printf("A、B的取值范围为[0,600000]之间的整数！\n");
    			continue;
    		}
    		sum1=SumOfTrueDivisor(A);
    		sum2=SumOfTrueDivisor(B);
    		if(sum1==B && sum2==A){
        
    			printf("YES\n");
    		}else{
        
    			printf("NO\n");
    		}
    	}
    }

## 2041.超级楼梯 ##

Problem Description
    有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走
    法？
    Input
    输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数
    M（1<=M<=40）,表示楼梯的级数。
    Output
    对于每个测试实例，请输出不同走法的数量
    Sample Input
    2
    2
    3
    Sample Output
    1
    2

分析：设floor\[i\]为走上第i级阶梯的走法，那么由题可知floor\[1\]=0（第1级阶梯为起点，不用走，所以其值为0），floor\[2\]=1，floor\[3\]=2，floor\[4\]=3，floor\[5\]=5，…，**由此可以找出递推式floor\[i\]=floor\[i-1\]+floor\[i-2\]**。  
具体推理过程如下：假设现在按要求floor\[i\]（i>=3），通过分析可知通过一次跨楼梯到达第i级阶梯的方法有2种：  
（1）在第i-1级阶梯上跨一级  
（2）在第i-2级阶梯上跨二级  
由前面的设定已知floor\[i-1\]为走上第i-1级阶梯的走法，floor\[i-2\]为走上第i-2级阶梯的走法，所以走上第i级阶梯的走法等于走上第i-1级阶梯的走法与走上第i-2级阶梯的走法之和，即floor\[i\]=floor\[i-1\]+floor\[i-2\]。

#include <stdio.h>
    
    void SuperLadder(){
        
    	int n,m,i;
    	//floor[i]为走上第i级阶梯的走法
    	int floor[41];
    	floor[1]=0;
    	floor[2]=1;
    	floor[3]=2;
    	for(i=4;i<=40;i++){
        
    		floor[i]=floor[i-1]+floor[i-2];
    	}
    	scanf("%d",&n);
    	while(n--){
        
    		scanf("%d",&m);
    		if(m<=0 || m>40){
        
    			printf("楼梯的级数的取值范围应为[1,40]之间的整数!\n");
    			continue;
    		}
    		printf("%d\n",floor[m]);
    	}
    }

## 2042.不容易系列之二 ##

Problem Description
    你活的不容易，我活的不容易，他活的也不容易。不过，如果你看了下面的故事，就会知道，有位老
    汉比你还不容易。
    
    重庆市郊黄泥板村的徐老汉（大号徐东海，简称XDH）这两年辛辛苦苦养了不少羊，到了今年夏天，
    由于众所周知的高温干旱，实在没办法解决牲畜的饮水问题，就决定把这些羊都赶到集市去卖。从黄
    泥板村到交易地点要经过N个收费站，按说这收费站和徐老汉没什么关系，但是事实却令徐老汉欲哭无泪：
    
    （镜头回放）
    
    近景：老汉，一群羊
    远景：公路，收费站
    
    ......
    
    收费员（彬彬有礼+职业微笑）：“老同志，请交过路费！”
    
    徐老汉（愕然，反应迟钝状）：“锅，锅，锅，锅-炉-费？我家不烧锅炉呀？”
    
    收费员（职业微笑依然）：“老同志，我说的是过-路-费，就是你的羊要过这个路口必须交费，understand?”
    
    徐老汉（近镜头10秒，嘴巴张开）：“我-我-我知道汽车过路要收费，这羊也要收费呀？”
    
    收费员（居高临下+不解状）：“老同志，你怎么就不明白呢，那么我问你，汽车几个轮子？”
    
    徐老汉（稍放松）：“这个我知道，今天在家里我孙子还问我这个问题，4个！”
    
    收费员（生气，站起）：“嘿！老头，你还骂人不带脏字，既然知道汽车四个轮子，难道就不知道这羊
    有几条腿吗？！”
    
    徐老汉（尴尬，依然不解状）：“也，也，也是4个呀，这有关系吗？”
    
    收费员（生气，站起）：“怎么没关系！我们头说了，只要是4条腿的都要收费！”
    
    ......
    
    (画外音)
    
    由于徐老汉没钱，收费员就将他的羊拿走一半，看到老汉泪水涟涟，犹豫了一下，又还给老汉一只。
    巧合的是，后面每过一个收费站，都是拿走当时羊的一半，然后退还一只，等到老汉到达市场，就只
    剩下3只羊了。
    你,当代有良知的青年，能帮忙算一下老汉最初有多少只羊吗？
    Input
    输入数据第一行是一个整数N，下面由N行组成，每行包含一个整数a(0<a<=30),表示收费站的数
    量。
    Output
    对于每个测试实例，请输出最初的羊的数量,每个测试实例的输出占一行。
    Sample Input
    2
    1
    2
    Sample Output
    4
    6

分析：设sheep\[i\]表示经过i个加油站后羊的数量，则有题可知sheep\[0\]=最初的羊的数量，sheep\[a\]=3，并且从题目中可以得到相应的递推式：sheep\[i-1\]=(sheep\[i\]-1)\*2

#include <stdio.h>
    
    void SheepNum(){
        
    	int n,a,res;
    	scanf("%d",&n);
    	while(n--){
        
    		res=3;
    		//a表示收费站的数量
    		scanf("%d",&a);
    		if(a<=0 || a>30){
        
    			printf("a的取值范围为(0,30]之间的整数!\n");
    			continue;
    		}
    		while(a--){
        
    			res-=1;
    			res*=2;
    		}
    		printf("%d\n",res);
    	}
    }

## 2043.密码 ##

Problem Description
    网上流传一句话:"常在网上飘啊，哪能不挨刀啊～"。其实要想能安安心心地上网其实也不难，学点
    安全知识就可以。
    首先，我们就要设置一个安全的密码。那什么样的密码才叫安全的呢？一般来说一个比较安全的密码
    至少应该满足下面两个条件：
    (1).密码长度大于等于8，且不要超过16。
    (2).密码中的字符应该来自下面“字符类别”中四组中的至少三组。
    这四个字符类别分别为：
    1.大写字母：A,B,C...Z;
    2.小写字母：a,b,c...z;
    3.数字：0,1,2...9;
    4.特殊符号：~,!,@,#,$,%,^;
    给你一个密码，你的任务就是判断它是不是一个安全的密码。
    Input
    输入数据第一行包含一个数M，接下有M行，每行一个密码（长度最大可能为50），密码仅包括上面的
    四类字符。
    Output
    对于每个测试实例，判断这个密码是不是一个安全的密码，是的话输出YES，否则输出NO。
    Sample Input
    3
    a1b2c3d4
    Linle@ACM
    ^~^@^@!%
    Sample Output
    NO
    YES
    NO

分析：

#include <stdio.h>
    #include <string.h>
    
    void Password(){
        
    	char psw[50];
    	int i,M,length;
    	int flag1,flag2,flag3,flag4,flag;
    	scanf("%d",&M);
    	while(M--){
        
    		scanf("%s",psw);
    		length=strlen(psw);
    		if(length<8 || length>16){
        
    			printf("NO\n");
    			continue;
    		}
    		flag1=flag2=flag3=flag4=0;
    		for(i=0;i<length;i++){
        
    			if(psw[i]>=65 && psw[i]<=90){
        
    				//A~Z的ASCII值为65~90
    				flag1=1; 
    			}else if(psw[i]>=97 && psw[i]<=122){
        
    				//a~z的ASCII值为97~122
    				flag2=1; 
    			}else if(psw[i]>=48 && psw[i]<=57){
        
    				//0~9的ASCII值为97~122
    				flag3=1; 
    			}else if(psw[i]=='~'  ||  psw[i]=='!'  ||  
    					 psw[i]=='@'  ||  psw[i]=='#'  ||  
    					 psw[i]=='$'  ||  psw[i]=='%'  ||  
    					 psw[i]=='^'){
        
    				//~,!,@,#,$,%,^
    				flag4=1;
    			}
    		}
    		flag=flag1+flag2+flag3+flag4;
    		if(flag>=3){
        
    			printf("YES\n");
    		}else{
        
    			printf("NO\n");
    		}
    	}
    }

## 2044.一只小蜜蜂… ##

Problem Description
    有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b
    的可能路线数。其中，蜂房的结构如下所示。
    Input
    输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和
    b(0<a<b<50)。
    Output
    对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。
    Sample Input
    2
    1 2
    3 6
    Sample Output
    1
    3

![在这里插入图片描述][20210111151921512.jpg]  
分析：此题与2041超级楼梯比较类似，有着相同的递归式。设hive\[i\]为从蜂房1到蜂房i的可能路线数(i>1)，并且hive\[1\]=0，hive\[2\]=1，hive\[3\]=2，hive\[4\]=3，hive\[5\]=5…，由此可以找出递推式hive\[i\]=hive\[i-1\]+hive\[i-2\]，具体推导过程可参考2041超级楼梯；仔细观察蜂房的结构可知，**求蜜蜂从蜂房a爬到蜂房b的可能路线数可以转换为求蜜蜂从蜂房1爬到蜂房b-a的可能路线数，即等于hive\[b-a\]**。

#include <stdio.h>
    
    void Honeybee(){
        
    	int hive[50];
    	int i,n,a,b;
    	hive[1]=1;
    	hive[2]=2;
    	for(i=3;i<50;i++){
        
    		hive[i]=hive[i-1]+hive[i-2];
    	}
    	while(scanf("%d",&n)!=EOF){
        
    		while(n--){
        
    			scanf("%d%d",&a,&b);
    			if(a<=0 || a>=50 || b<=0 || b>=50){
        
    				printf("0<a<b<50，且均为整数！\n");
    				continue;
    			}
    			//若a>b，则交换a、b的值 
    			if(a>b){
        
    				a=a+b;
    				b=a-b;
    				a=a-b;
    			}
    			printf("%d\n",hive[b-a]);
    		}
    	}
    }

[杭电OJ第11页2045~2049算法题（C语言）][OJ_11_2045_2049_C]

[20210111151921512.jpg]: https://img-blog.csdnimg.cn/20210111151921512.jpg
[OJ_11_2045_2049_C]: https://blog.csdn.net/weixin_43004044/article/details/112505506