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

  • 日期:03-10
  • 点击:(1250)


HNUCM 2018 《算法分析与设计》练习2问题解决

前言:

递归主题:

1,找到递归结束条件

2,找到递归方程

A:判断素数

问题含义:

直接给出一个数,然后让你判断它是否是素数

问题解决:

这是一个大问题。

B:对称矩阵

问题含义:

n维矩阵,判断它是否是对称矩阵

问题解决:

没什么好说的,只要判断一个[I][j]==一个[j][i]到

C:矩阵对角线和

问题含义:

n是矩阵,求它的主对角线和它的辅助对角线的和

问题解决:

这个问题根本没有坑。即使长的也没有凹坑

直接求和:

主对角线:i=j

辅助对角线:i j=n-1(从0开始)

D:字符统计

问题含义:

给出一个字符串,判断大写字母、小写字母、阿拉伯数字和空格的数量

问题解决:

递归地遍历它

E:递归求和

问题含义:

即可。找出下列序列的前n项:

s=1-1/2 1/3-1/4 1/5-1/6.

问题含义:

Find递归结束条件

f: Fibonacci number

问题含义:

多组输入,每组输入被赋予n

find第n个Fibonacci number(只输出最后六位数字)

问题解决:

如果这个问题被递归地暴力使用,它肯定会结束(超时)

那么它必须被保存在数组中,空间被交换为时间

G:蜂巢

问题含义:

遍历蜂巢;对于多组数据,给定起点和终点,找出走多少路

问题解决:

H:数字之和

问题含义:

给一个正整数n,找出每个数字之和

问题解决:

学习递归,用递归来写,直接从每一位向前推, 找出递归结束条件:当n只剩下一位时

I:饲养兔子

问题含义:

有人收养一只兔子,成熟期为1天,找出n天有多少只兔子

问题解决:

也找出递归结束条件。

J:XP stairs

问题含义:

J:XP jump stairs,可以一次跳一级,一次跳两级,一次跳三级。

询问有多少个方案可以跳到第n层。

问题解决:

然后找到递归结束条件和递归方程