斐波那契数列
f ( n ) = { 1 n = 1 1 n = 2 f ( n − 1 ) + f ( n − 2 ) n > 2 1 , 1 , 2 , 3 , 5 , 8 . . . \begin{aligned} f(n)=\begin{cases}1&n=1\\ 1&n=2\\ f(n-1)+f(n-2)&n\gt2 \end{cases}\\ 1,1,2,3,5,8\quad ... \end{aligned} f(n)=⎩ ⎨ ⎧11f(n−1)+f(n−2)n=1n=2n>21,1,2,3,5,8...
上楼梯问题
一共有 n 个台阶,一次可以上 1 或 2 个台阶,请问有多少种走法?
(1)当 n = 1 n=1 n=1 时, f ( 1 ) = 1 f(1)=1 f(1)=1
(2)当 n = 2 n=2 n=2 时, f ( 1 ) = 2 , 1 + 1 2 f(1)=2,\quad \begin{aligned}1+1\\ 2\end{aligned} f(1)=2,1+12
(3)假设已知 f ( n − 1 ) , f ( n − 2 ) f(n-1),f(n-2) f(n−1),f(n−2),则 f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n−1)+f(n−2)
到达第n级楼梯的方式可以从第n-1级楼梯一步走上来,也可以从第n-2级楼梯两步走上来
int f(int n){
if(n<3)return n;
return f(n-1)+f(n-2);
}
// 优化
vector<int> v;
int f(int n){
if(n<3)return n;
if (v.size() >= (n-2)) {
return v.at(n-3);
}
v.push_back(f(n-1)+f(n-2));
return v.back();
}
// 非递归
int g(int n){
if(n<3)return n;
queue<int> Q;
Q.push(1);
Q.push(2);
for(int i=0;i<n-2;i++){
int a = Q.front();
Q.pop();
int b=Q.front();
Q.push(a+b);
}return Q.back();
}
hanoi塔
-
把上面 n-1 个盘子移动到 B
-
只有一个盘子时,直接从 A 移到 C
-
把 B 的 n-1 个盘子也移到 C
void move(int n, char a, char c){
printf("%d: %c -> %c\n", n, a, c);
}
void hanoi(int n, char a, char b, char c){
if(n>1){
hanoi(n-1, a, c, b);
move(n, a, c);
hanoi(n-1, b, a, c);
}else{
move(n, a, c);
}
}