用斐波那契数列来认识算法

爱被打了一巴掌 2023-09-26 15:31 75阅读 0赞

[14天阅读挑战赛][14]  
*努力是为了不平庸~  
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~*

### 算法知识点 ###

> 打开算法之门
> 
> 百度百科的定义：（请自觉跳过）
> 
> （**别看，看就是不懂，不看还好，一看之会更迷糊**）
> 
> 算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰[指令][Link 1]，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的[输入][Link 2]，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用[空间复杂度][Link 3]与[时间复杂度][Link 4]来衡量。
> 
> 算法中的指令描述的是一个[计算][Link 5]，当其[运行][Link 6]时能从一个初始状态和（可能为空的）初始输入开始，经过一系列**有限**而清晰定义的状态，最终产生**输出**并**停止**于一个终态。一个状态到另一个状态的转移不一定是确定的。[随机化算法][Link 7]在内的一些算法，包含了一些随机[输入][Link 8]。
> 
> 形式化算法的概念部分源自尝试解决[希尔伯特][Link 9]提出的[判定问题][Link 10]，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括[库尔特·哥德尔][Link 11]、Jacques Herbrand和[斯蒂芬·科尔·克莱尼][Link 12]分别于1930年、1934年和1935年提出的[递归函数][Link 13]，[阿隆佐·邱奇][Link 14]于1936年提出的[λ演算][Link 15]，1936年Emil Leon Post的Formulation 1和[艾伦·图灵][Link 16]1937年提出的[图灵机][Link 17]。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。

### 算法题目来源 ###

> 自编

### 算法题目描述 ###

> 斐波那契数列：
> 
> 1、1、2、3、5、8、13、21、34、55......
> 
> 求第n个数是多少？（题目保证在整形数据范围内,n>0）
> 
> 提示：从第3个数开始，这个数都等于前两个数的和，例如：
> 
> 第3个：2=1+1；
> 
> 第4个：3=2+1；
> 
> ……

### 做题思路 ###

> 一个一个的算呗，还能咋办…………
> 
> 又不是数学，还要自己找规律。

### 模板代码 ###

>     //  代码1：递归
>     
>     int Fun(int n){       
>     	if (n == 1 || n == 2)
>     		return 1;
>     	else
>     		return Fibon1(n - 1) + Fibon1(n - 2);
>     }
>     int main(){
>     	int n;
>     	scanf("%d", &n);
>     	printf("%d", Fun(n));
>     	return 0;
>     }

>     //数组
>     
>     int Fun(int n){
>     	int i=3,list[1000000];
>     	list[1]=list[2]=1;
>         if(n >= 3){
>     	    while (i <= n){
>                 list[i] = list[i - 2] + list[i - 1];
>     		    i++;
>     		}
>         }
>     	return list[i];
>     }

>     //啥都不用
>     
>     int Fun(int n){
>     	int num1 = 1;
>     	int num2 = 1;
>     	int tmp = 0;
>     	int i = 0;
>     	if (n < 3)
>     		return 1;
>     	else
>     		for (i = 0; i>n-3; i++){
>     			tmp = num1 + num2;
>     			num1 = num2;
>     			num2 = tmp;
>     		}
>     	return tmp;
>     }

### 相关算法题型题目总结 ###

> 光看代码就知道谁好谁坏了吧
> 
> 递归：从n迭代到1，再从1算到n去，麻烦啰嗦复杂浪费时间
> 
> 数组：看看那数组开多大了，占了多少内存，还没到整型的上限呢，n一大，咋办，凉凉
> 
> 啥不用：哎，巧了，啥麻烦没有。

### 读书笔记 ###

> 啥叫算法，就这，就是这个问题最好的算法，连之一都不带有的

[14]: https://marketing.csdn.net/p/bb9f9e25975dba9f9b87f5272afded16
[Link 1]: https://baike.baidu.com/item/%E6%8C%87%E4%BB%A4/3225201?fromModule=lemma_inlink
[Link 2]: https://baike.baidu.com/item/%E8%BE%93%E5%85%A5/32696?fromModule=lemma_inlink
[Link 3]: https://baike.baidu.com/item/%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/9664257?fromModule=lemma_inlink
[Link 4]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/1894057?fromModule=lemma_inlink
[Link 5]: https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97/81857?fromModule=lemma_inlink
[Link 6]: https://baike.baidu.com/item/%E8%BF%90%E8%A1%8C?fromModule=lemma_inlink
[Link 7]: https://baike.baidu.com/item/%E9%9A%8F%E6%9C%BA%E5%8C%96%E7%AE%97%E6%B3%95/6233182?fromModule=lemma_inlink
[Link 8]: https://baike.baidu.com/item/%E8%BE%93%E5%85%A5/5481954?fromModule=lemma_inlink
[Link 9]: https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9/172452?fromModule=lemma_inlink
[Link 10]: https://baike.baidu.com/item/%E5%88%A4%E5%AE%9A%E9%97%AE%E9%A2%98?fromModule=lemma_inlink
[Link 11]: https://baike.baidu.com/item/%E5%BA%93%E5%B0%94%E7%89%B9%C2%B7%E5%93%A5%E5%BE%B7%E5%B0%94/10781768?fromModule=lemma_inlink
[Link 12]: https://baike.baidu.com/item/%E6%96%AF%E8%92%82%E8%8A%AC%C2%B7%E7%A7%91%E5%B0%94%C2%B7%E5%85%8B%E8%8E%B1%E5%B0%BC/2094842?fromModule=lemma_inlink
[Link 13]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92%E5%87%BD%E6%95%B0/5634537?fromModule=lemma_inlink
[Link 14]: https://baike.baidu.com/item/%E9%98%BF%E9%9A%86%E4%BD%90%C2%B7%E9%82%B1%E5%A5%87?fromModule=lemma_inlink
[Link 15]: https://baike.baidu.com/item/%CE%BB%E6%BC%94%E7%AE%97?fromModule=lemma_inlink
[Link 16]: https://baike.baidu.com/item/%E8%89%BE%E4%BC%A6%C2%B7%E5%9B%BE%E7%81%B5?fromModule=lemma_inlink
[Link 17]: https://baike.baidu.com/item/%E5%9B%BE%E7%81%B5%E6%9C%BA/2112989?fromModule=lemma_inlink