斐波那契（例题及答案）

练习 1：求斐波那契第 n 项（基础版）
题目：
输入 n，输出斐波那契数列第 n 项。
数列：1 1 2 3 5 8 13……
思路
f(1)=1, f(2)=1
f(n)=f(n-1)+f(n-2)

c
运行

include <stdio.h>

int main() {
int n;
scanf("%d", &n);

if (n == 1 || n == 2) {printf("1");return 0;
}int a = 1, b = 1, c;
for (int i = 3; i <= n; i++) {c = a + b;a = b;b = c;
}
printf("%d", b);
return 0;

}

练习 2：兔子繁衍问题（原题）
题目：
一对兔子，第 3 个月起每月生一对，求总数至少达到 N 对时是第几个月。

c
运行

include <stdio.h>

int main() {
int N;
scanf("%d", &N);

int a = 1, b = 1;
int month = 2;if (N == 1) {printf("1");return 0;
}while (1) {int c = a + b;month++;if (c >= N) {printf("%d", month);break;}a = b;b = c;
}
return 0;

}

练习 3：爬楼梯（经典面试题）
题目：
每次可以爬 1 阶或 2 阶，爬到 n 阶共有多少种方法？
思路
最后一步从 n-1 来 或 从 n-2 来
f(n)=f(n-1)+f(n-2)
f(1)=1, f(2)=2

c
运行

include <stdio.h>

int main() {
int n;
scanf("%d", &n);

if (n == 1) {printf("1");return 0;
}
if (n == 2) {printf("2");return 0;
}int a = 1, b = 2, c;
for (int i = 3; i <= n; i++) {c = a + b;a = b;b = c;
}
printf("%d", b);
return 0;

}

练习 4：斐波那契前 n 项和
题目：
求斐波那契前 n 项的和。
公式
S(n) = f(n+2) − 1

c
运行

include <stdio.h>

int main() {
int n;
scanf("%d", &n);

int a = 1, b = 1;
// 求 f(n+2)
for (int i = 3; i <= n + 2; i++) {int c = a + b;a = b;b = c;
}
printf("%d", b - 1);
return 0;

}

练习 5：求斐波那契最后一位数字
题目：
求第 n 项的个位数。
思路
每次相加后对 10 取模，防止溢出。

c
运行

include <stdio.h>

int main() {
int n;
scanf("%d", &n);

if (n == 1 || n == 2) {printf("1");return 0;
}int a = 1, b = 1, c;
for (int i = 3; i <= n; i++) {c = (a + b) % 10;a = b;b = c;
}
printf("%d", b);
return 0;

}

练习 6：判断斐波那契奇偶
题目：
判断第 n 项是奇数还是偶数。
规律：
每 3 个循环：奇、奇、偶、奇、奇、偶……

c
运行

include <stdio.h>

int main() {
int n;
scanf("%d", &n);

if (n % 3 == 0)printf("偶数");
elseprintf("奇数");return 0;

}