HNUCM 2018级《算法分析与设计》练习二题解

一时失言乱红尘 2023-07-08 02:38 37阅读 0赞

# HNUCM 2018级《算法分析与设计》练习二题解 #

**前言：**  
递归专题：  
1、找递归结束条件  
2、找递归方程

--------------------

## [A：判断素数][A] ##

--------------------

**题意：**  
直接给定一个数，然后要你判断它是不是素数

**题解：**  
完全就是个大水题。。。。

--------------------

## [B：对称矩阵][B] ##

--------------------

**题意：**  
n维矩阵，判断它是不是对称矩阵

**题解：**  
也没啥说的，只要判断a\[i\]\[j\]==a\[j\]\[i\]即可

--------------------

## [C：矩阵对角求和][C] ##

--------------------

**题意：**  
n为矩阵，求它的主对角线和它的副对角线的和

**题解：**  
这题完全没坑点，就连long long都没设坑

直接求和即可：  
主对角线：i=j  
副对角线：i+j=n-1（以0开始记）

--------------------

## [D：字符统计][D] ##

--------------------

**题意：**  
给一个字符串，判断大写字母、小写字母、阿拉伯数字和空格的个数

**题解：**  
直接遍历一下即可

--------------------

## [E：递归求和][E] ##

--------------------

**题意：**  
用递归，求以下数列的前n项：  
s=1-1/2+1/3-1/4+1/5-1/6+…

**题意：**  
找到递归结束条件

if(n==1)
    	return 1;
    else
    	return f(n-1)+1.0/n;

--------------------

## [F：斐波那契数][F] ##

--------------------

**题意：**  
多组输入，每组输入给定n  
求第n个斐波拉契数（只输出最后六位）

**题解：**  
这题如果用暴力递归的话，肯定会tle（超时）  
于是就必须用数组存了，以空间换时间

--------------------

## [G：蜂房][G] ##

--------------------

**题意：**  
走蜂房；多组数据，给定起点和终点，求有多少种走法

**题解：**

if(n==1)
    	return 1;
    else if(n==2)
    	return 2;
    else
    	return f(n-1)+f(n-2);

--------------------

## [H：数字求和][H] ##

--------------------

**题意：**  
给出一个正整数n，求其每位数的和

**题解：**  
学递归，就用递归写，直接从个位一直往前推即可，找好递归结束条件：n只剩一位数的时候

if(n/10==0)
    	return n;
    else
    	return f(n/10)+n%10;

--------------------

## [I：养兔子][I] ##

--------------------

**题意：**  
某人收养一只兔子，成熟期为1天，求第n天有多少只兔子

**题解：**  
同样找递归结束条件。

if(n==1)
    	return 1;
    else
    	return f(n-1)*2;

--------------------

## [J：XP的楼梯][J_XP] ##

--------------------

**题意：**  
xp跳楼梯，可以一次跳一级、一次跳两级、一次跳三级。  
问跳到第n级有多少种方案

**题解：**  
需要注意的是，xp的起始位置是第一级  
于是找递归结束条件和递归方程

if(n==1)
    	return 1;
    else if(n==2)
    	return 1;
    else if(n==3)
    	return 2;
    else
    	return f(n-1)+f(n-2)+f(n-3);

[A]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1071&pid=0
[B]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1071&pid=1
[C]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1071&pid=2
[D]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1071&pid=3
[E]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1071&pid=4
[F]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1071&pid=5
[G]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1071&pid=6
[H]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1071&pid=7
[I]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1071&pid=8
[J_XP]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1071&pid=9