文章目录
一、斐波那契数列
今天博主在练习题时碰见了一道有关斐波那契数列的题目，令博主一时无了头绪，后来搞清楚斐波那契数列的性质及有关知识后，现在分享给大家。
我先给不了解斐波那契数列的同学普及一下斐波那契数的概念及有关知识。
斐波那契数列就是
0 1 1 2 3 5 8 13 21 34 … F（n）=F（n-1）+F（n-2）的递推数列
先看一道简单的题目——计算斐波那契数列
题目名称：
计算斐波那契数
题目内容：
递归和非递归分别实现求第n个斐波那契数
例如：
输入：5 输出：5
输入：10， 输出：55
输入：2， 输出：1
实现代码
1.非递归方式
int main(){int n = 0;scanf_s("%d", &n);/*int ret=Fac(n);
printf("%d\n", ret); */int f1 = 0;int f2 = 1;int f3 ;int i = n - 2;while (i){
f3 = f1 + f2;
f1 = f2;
f2 = f3;
i--;}printf("%d\n", f3);return 0;}
2.递归方式
#include <stdio.h>int Fac(int n){if (n == 1)return 0;else if (n == 2 || n == 3)return 1;else
return Fac(n-1) + Fac(n-2);}
int main(){int n = 0;scanf_s("%d", &n);int ret=Fac(n);printf("%d\n", ret);
return 0;}
好了，了解了斐波那契数列的计算方式，我们来正式引入今天的题目
题目
Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, …，在Fibonacci数列中的数我们称为Fibonacci数。
给你一 个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X - 1或者X + 1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。
输入描述：
输入为一个正整数N(1 ≤ N ≤ 1, 000, 000)
输出描述：
输出一个最小的步数变为Fibonacci数
示例：
输入 15
输出 2
#include <stdio.h>#include <math.h>int main(){int n = 0;scanf_s("%d", &n);int f1 = 0;int f2 = 1;int f3 = 0;while (1){f3 = f1 + f2;f1 = f2;
f2 = f3;if (n == f2){printf("%d\n", 0);break;}else if (n < f2){if (abs(f2 - n) < abs(f1 - n)){printf("%d\n", abs(f2 - n));break;}else if (abs(f2 - n) > abs(f1 - n)){printf("%d\n", abs(f1 - n));break;}}}return 0;}
注意：abs()函数时求绝对值的函数，需要引入<math.h>的头文件
写题的步骤
1.先读懂题目,很多小伙伴们因为题目很长，看不懂，因此放弃了该题。
我们来具体分析一下
例如： 我们输入了一个数字 15，他不是斐波那契数
15 在 13和21的中间，我们需要得到的时15变成斐波那契数的最短步数，那么我们就需要将| 21-15 | 和 | 15 -13 |的绝对值进行比较，得到的较小数就是我们的答案。
2.要明确 我们需要找到我们输入这个数字的两边的斐波那契数，然后差的绝对值进行比较。
二、字符串空格替换
这是一道很常见的题目，但是平时我们都没有注意到，例如我在百度的搜索栏中搜索 张三[空格]李四，出现的结果如下。
好了，进入正题。
题目名称：
字符串替换空格：请实现一个函数，把字符串中的每个空格替换成“％20”。
效果
we are happy.
we%20are%20happy.
实现代码
#include <stdio.h>#include <string.h>void blankreplace(char *str, int length){int i = 0;int count = 0;// 计算字符串中存在的空格数for (i = 0; i < length; i++){if (str[i] == ' ')
count++;}//计算加上替换成%20之后新字符串的长度//算出字符串最后的位置int newlen = length + 2 * count;int pos = newlen - 1;//字符串从后向前替换不会覆盖for (i = length-1; i >= 0; i--){if (str[i] != ' '){
str[pos--] = str[i];}else if (str[i] == ' '){
str[pos--] = '0';
str[pos--] = '2';
str[pos--] = '%';}}}int main(){char str[200] = "we are happy";int len = strlen(str);blankreplace(str,len);printf("%s\n", str);return 0;}
注意：我们改变了字符串的长度，所以在原字符串中一定要留有足够的空间还能进行替换。
思考步骤
1.计算字符串中存在的空格数
2.计算加上替换成%20之后新字符串的长度
3.算出字符串最后的位置
4.字符串从后向前替换不会覆盖
好了，本次的分享就到这里，希望大家多多练习，谢谢欣赏~~