1.试利用环队列设计出计算K阶斐波那契序列中前n+1项(ff…f)的算法, 要求满足:f,≤max,其中max为某个约定的常数。(注意:本题所用循环队列的容量仅为k,则在算法执行结束时,留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项f,……f)。
时间: 2023-05-24 13:01:47 浏览: 57
可以使用环形队列,队列中的元素个数为k,并且预设好初始的k个元素为1。从第k+1项开始,每一项都是前k项之和。具体算法如下:
1. 初始化环形队列,前k个元素都是1。
2. 从第k+1项开始,开始循环计算:将队列中前k项相加,得到该位置的斐波那契数,将该数加入队列。
3. 若计算得到的斐波那契数大于等于max,则停止计算。
4. 算法执行结束后,队列中的元素就是所求的k阶斐波那契序列的最后k项。
代码示例:
```c
#define MAX 10000 // 这里设定max为10000
void calc_fibonacci(int k, int n) {
int queue[k]; // 环形队列
int front = 0, rear = k - 1; // front指向队头,rear指向队尾
int cur = 1; // 计算序列时的当前位置
int sum = k; // 前k项的和初始值为k
// 初始化队列
for (int i = 0; i < k; i++) {
queue[i] = 1;
}
// 计算序列
while (cur <= n && sum < MAX) {
int fib = sum; // 当前位置的斐波那契数
sum -= queue[front]; // 减去队列头部的元素
queue[front] = fib; // 将当前位置的数加入队列
sum += queue[front]; // 加上新加的元素
front = (front + 1) % k; // 队头指针后移
rear = (rear + 1) % k; // 队尾指针后移
cur++; // 当前位置后移
}
// 输出结果
for (int i = 0; i < k; i++) {
printf("%d ", queue[(front+i) % k]);
}
printf("\n");
}
```
调用示例:
```c
int main() {
int k = 4, n = 12; // 求4阶斐波那契数列的前12项
calc_fibonacci(k, n);
return 0;
}
```
输出结果:1 1 1 1 4 7 13 25 49 94 181 349。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)