题目1 斐波那契数列

题目描述

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39

代码

递归方法:

非递归方法:

题目2 青蛙跳台阶

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

题目解析

对于这种问题我们可以这样分析。在第一次跳台阶的时候,它可以选择跳1个台阶,也可以选择跳两个台阶。对于它要跳n个台阶来说(设为f(n)),假如第一次跳了1个台阶,那么第二次跳就是f(n-1)的问题;假如第一次跳了2个台阶,那么第二次就是f(n-2)的问题。对于第二次跳也是如此,就是分别是f(n-2)和f(n-3)(对于第一次跳了1阶的情况下)、f(n-3)和f(n-4)(对于第一次跳了2阶的情况下),依次类推下去,成为一个递归。特别的,当n=1的时候,只有一种跳法(只跳一阶),当n=2的时候,有两种跳法(跳1阶跳两次,跳2阶跳一次)。实际上这就是一个斐波那契数列。

代码

题目3 变态跳台阶

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目解析

当一个青蛙跳上n级台阶有以下的情况:

n情况数情况
11(1)
22(1,1),(2)
34(1,1,1),(1,2),(2,1),(3)
48(1,1,1,1),(1,2,1),(1,1,2),(2,1,1),(2,2),(1,3),(3,1),(4)
………………
n2*f(n-1)(1)

通过尝试,可以发现规律,当n>1的时候,f(n)=2*f(n-1)。

代码

题目4 矩形覆盖

题目描述

我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

题目解析

对于这种问题,我们还是需要进行分析。

n情况数情况(括号中1为竖着,2为横着)
11(1)
22(1,1),(2,2)

当n=3的时候,我们发现,若固定了第三块砖的放置方式,那么前两块砖有两种放置方式(f(2));若固定了第二块和第三块的放置方式,则前一块砖有一种放置方式(f(1))。以此类推,可以得出f(n)=f(n-1)+f(n-2),当n>2的时候。

代码

题目5 二进制中1的个数

题目描述

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

题目解析

思路很简单,利用与的特性:1&1=1,0&1=0就可以进行判断。

代码

题目6 调整数组,使奇数位于偶数前面

题目描述

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

题目解析

其实这个可以借助于类似于冒泡法的思想,不过这样的复杂度有O(n2),并且空间复杂度也较高。因此可以使用下面的方法。借鉴了插入排序。

代码