镜缘浮影 小人本住在 苏州的城外 家里有屋又有田 生活乐无边

那些年我们一起忘掉的C (三).斐波那契数列

2016-11-21
wilmosfang
c
原文地址 http://soft.dog/2016/11/21/c-basic-03/

前言

数组与函数递归调用是C语言中很重要的组成部分


概要


求斐波那契数列的前20项之和

斐波那契数列是这样一种数列,它的头两个元素是1,从第三个开始,后面的每一个元素值都是它之前两个元素之和,如:

1,1,2,3, 5, 8, 13,21……

要求出这个数列的前20项之和

代码注解

使用递归

#include <stdio.h>

int feb(int n) //定义一个叫feb的函数,它接收一个整型数,返回一个整型数作为结果
{
	int v; //定义一个整型变量存放结果
	if(n==1 || n==2) v=1; //当n为1或2时,结果为1 
	else v=feb(n-1)+feb(n-2); //其它情况下结果为前两个值之和(限于这个具体情景,没有考虑负值的情况,也没对负数进行检查)
	return v; //使用v值进行返回
	//return ( n==1 || n==2 )?1:feb(n-1)+feb(n-2); //其实上面那么多可以使用这一条语句进行表达,st1?st2:st3 代表如果 st1为真,就求解st2作为整个表达式的值,否则求解st3作为整个表达式的值
}

void main()
{
	int sum=0,i; //定义两个变量,sum用来存放累加结果,i用来进行遍历
	for (i=1;i<21;i++) sum+=feb(i); // i会逐1遍历[1,20]范围里的所有整数,feb(i)会根据i值产生这个位置的结果值,然后结果会累加到sum中
	printf("%d\n",sum);
}

使用数组

#include <stdio.h>

void main()
{
	int sum=0,i,n[20]={1,1}; //定义两个整型变量和一个长度为20的整型数组,sum用来存放累加结果赋初值0,i用来进行遍历,n[20]用来存放这个长度为20的斐波那契数列,并将前两个元素的初值赋为1
	sum=n[0]+n[1]; //将数列的前两个元素累加到sum中,数组元素是以0下标作为第一个元素的,一直到n-1下标所代表的最后一个元素,所以0和1分别代表第一个和第二个元素
	for (i=2;i<20;i++) //i会逐一遍历[2,19]范围里的每个整数,如果作为下标,就在指示第3个到第20个元素
	{
		n[i]=n[i-1]+n[i-2];//从第3个开始,后面每个元素值都是前两之和
		sum+=n[i]; // 然后将结果顺便累加到sum中
	}	
	printf("%d\n",sum);
}

两种实现方式的区别是什么呢

使用数组会消耗更多存储空间,但比较快;使用递归函数会消耗更多CPU时间,但比较省存储空间

一个是在拿空间换时间,一个是在拿时间换空间

思路

想获取斐波那契数列的前20项之和,可以先将这个数列进行构建,存储,然后遍历相加

也可以实现出一个斐波那契函数,进行遍历累加

基础知识点

  • 函数的定义
  • 函数的递归调用
  • 数组的定义与赋值
原文地址 http://soft.dog/2016/11/21/c-basic-03/

评论