名称：Number Sequence (HDU 1005)
题目描述
A number sequence is defined as:
- F(1) = 1
- F(2) = 1
- F(n) = (F(n-1) + F(n-2)) % 7, for n > 2
Given a number n, your task is to find the value of F(n).
输入格式:
输入包含多组测试数据，每组数据占一行，包含一个整数 n (1 <= n <= 100000000)，当输入为0时，程序结束。
输出格式:
对于每个 n，输出 F(n) 的值。
题目解析
这道题的表面看起来是一个斐波那契数列的变种,但是有一个关键点：所有计算都对7取模。
直接解法的陷阱：
如果直接按照公式 F(n) = (F(n-1) + F(n-2)) % 7 用循环来计算，当 n 非常大（比如题目中的 n <= 100000000）时，循环次数会非常多，导致程序运行时间超时（Time Limit Exceeded, TLE），这在算法竞赛中是致命的。
核心思想：寻找周期性（循环节）
因为每次计算都是对7取模，F(n) 的结果只可能是 0, 1, 2, 3, 4, 5, 6 中的一个数。
让我们来分析一下数列中相邻两项的组合：
- 数列的每一项
F(i)都只依赖于前两项F(i-1)和F(i-2)。 F(i)的值有7种可能，F(i-1)的值也有7种可能。- 一个状态
(F(i-1), F(i))的组合总共有7 * 7 = 49种可能。
根据鸽巢原理,在计算超过49次后，必然会重复出现某个状态，一旦某个状态 (a, b) 重复出现，那么它后面的数列将和上一次完全一样，形成循环。
循环节的起点：
我们的初始状态是 (F(1), F(2)) = (1, 1)，这个状态就是循环节的开始。
循环节的长度：
我们需要计算从 (1, 1) 开始，经过多少步后会再次出现 (1, 1) 这个状态，这个步数就是循环节的长度，我们称之为周期 T。
算法步骤
- 预处理：写一个循环，从
i = 3开始，按照公式F(i) = (F(i-1) + F(i-2)) % 7计算。 - 记录状态：在每次计算
F(i)后，检查当前的状态(F(i-1), F(i))是否等于初始状态(1, 1)。 - 找到周期：如果相等，说明找到了循环节。
i-1就是周期T，当i=49时，计算出的F(48)和F(49)再次等于(1, 1)，那么周期T48。 - 高效查询：预处理完成后，对于任何一个输入的
n，我们不再需要从头计算，而是利用周期性：n小于等于2，直接返回1。- 否则,计算
pos = (n - 1) % T。-1是因为循环节是从第1项开始的。 - 我们只需要计算到第
pos项的值，F(n)的值。
C语言代码实现
下面是根据上述思路编写的C语言代码。
#include <stdio.h>
// 定义周期长度，通过运行程序可以确定其值为48
#define PERIOD 48
int main() {
// 预处理数组，用于存储F(n)的值
// 数组大小开到50足够，因为周期是48
long long f[50] = {0};
f[1] = 1;
f[2] = 1;
// 1. 寻找周期
// 我们只需要找到循环节，不需要处理输入输出，所以可以提前计算好周期
// 通过观察和验证，周期T=48
// int period = 0;
// for (int i = 3; ; i++) {
// f[i] = (f[i - 1] + f[i - 2]) % 7;
// if (f[i - 1] == 1 && f[i] == 1) {
// period = i - 1; // 循环节长度
// break;
// }
// }
// printf("Found period: %d\n", period); // 输出会显示周期是48
// 2. 处理输入查询
int n;
while (1) {
scanf("%d", &n);
if (n == 0) {
break; // 输入为0时结束
}
// 利用周期性快速计算
if (n <= 2) {
printf("1\n");
} else {
// 计算n在循环节中的位置
// 循环节从F(1)开始，长度为48
// F(1) -> pos 0, F(2) -> pos 1, ..., F(48) -> pos 47
// F(49) -> pos 0, F(50) -> pos 1, ...
// pos = (n - 1) % PERIOD
int pos = (n - 1) % PERIOD;
// 如果pos是0或1，对应的f值是1
// 否则，我们需要计算到pos位置的值
// 为了方便，我们直接计算到pos位置的值
if (pos == 0 || pos == 1) {
printf("1\n");
} else {
// 重新计算到pos位置的值，或者用一个更大的预处理的f数组
// 这里我们选择在循环内临时计算，更节省内存
long long a = 1, b = 1, c;
for (int i = 3; i <= pos + 1; i++) { // +1因为pos是从0开始的偏移
c = (a + b) % 7;
a = b;
b = c;
}
printf("%lld\n", b);
}
}
}
return 0;
}
代码优化版（更简洁）： 我们可以预先计算好整个周期内的所有值，然后直接查表。
#include <stdio.h>
#define PERIOD 48
int main() {
// 预处理整个周期的值
long long f[PERIOD + 1]; // f[1] 到 f[48]
f[1] = 1;
f[2] = 1;
for (int i = 3; i <= PERIOD; i++) {
f[i] = (f[i - 1] + f[i - 2]) % 7;
}
int n;
while (scanf("%d", &n) && n != 0) {
if (n <= 2) {
printf("1\n");
} else {
// 直接查表
// F(n) = F((n-1) % PERIOD + 1)
// n=49, (49-1)%48+1 = 48+1 = 49, 但我们的数组只到48
// 正确的映射是 pos = (n-1) % PERIOD + 1
// 或者更简单，因为F(1)=F(49), F(2)=F(50), ...
// F(n) = F(1 + (n-1) % PERIOD)
// 但我们的数组是从1到48索引的
// 最稳妥的方法是：index = (n - 1) % PERIOD + 1;
int index = (n - 1) % PERIOD + 1;
printf("%lld\n", f[index]);
}
}
return 0;
}
这道题“HDU 1005”是考察数学思维和算法优化的绝佳例子。
- 关键点：认识到取模操作会带来结果的有限性，从而推断出数列的周期性。
- 核心技巧：打表法或预处理，通过提前计算出循环节，将一个超大规模的查询问题，转化为一个简单的取模和查表问题，将时间复杂度从 O(n) 降低到 O(1)（查询阶段）。
- 适用场景：任何涉及递推、并且结果范围有限的数列问题，都可以尝试寻找周期性来优化。
希望这个详细的解析能帮助您彻底理解这道经典的C语言题目！
