快捷導(dǎo)航

C語言新手練習(xí)題之求第n個(gè)斐波那契數(shù)

更新時(shí)間：2022年11月10日 11:23:37 作者：輕輕敲醒沉睡的心靈d(?д??)

斐波那契數(shù)列這一個(gè)大一上C語言就有的問題大家應(yīng)該都不陌生,下面這篇文章主要給大家介紹了關(guān)于C語言新手練習(xí)題之求第n個(gè)斐波那契數(shù)的相關(guān)資料,文中通過圖文以及實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下

前言

在C語言中，分別用遞歸和非遞歸兩種方法實(shí)現(xiàn)求第n個(gè)斐波那契數(shù)

一、思路

首先分析一下關(guān)于斐波那契數(shù)列的原理：

第一個(gè)和第二個(gè)數(shù)都是1，之后的每個(gè)數(shù)都是前兩個(gè)數(shù)之和，即：

1，1，2，3，5，8，……

1.非遞歸

用到了循環(huán)相關(guān)的知識(shí)，

當(dāng)n>2的時(shí)候進(jìn)入循環(huán)，將前兩個(gè)數(shù)相加得到第三個(gè)數(shù)；

當(dāng)n<=2的時(shí)候跳出循環(huán)。

2.遞歸

觀察斐波那契數(shù)列可以得到一個(gè)公式：

$gif.latex?f%28n%29%3D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%201%20%26%20n%20%3D%201%2C2%20%26%20%5C%5C%20f%28n-1%29%20+%20f%28n-2%29%26n%3E2%20%26%20%5Cend%7Bmatrix%7D%5Cright.$

根據(jù)這個(gè)公式就能進(jìn)行遞歸。當(dāng)n>2的時(shí)候進(jìn)行遞歸，當(dāng)n = 1或n = 2時(shí)返回1。

二、源代碼以及運(yùn)行截圖

為了方便大家的交流和學(xué)習(xí)，我將程序源代碼和運(yùn)行截圖放置在下方。

非遞歸：

源代碼：

#include<stdio.h>
//遞歸和非遞歸分別實(shí)現(xiàn)求第n個(gè)斐波那契數(shù)
//非遞歸
int main()
{
	int i = 1;
	int j = 1;
	int temp = 0;
	int n = 0;
	int fib = 0;
	scanf("%d", &n);
	while (n > 0)
	{
		if (n > 2)
		{
			temp = j;
			j = i + j;
			i = temp;
		}
		else 
			fib = j;
		n--;
	}
	printf("%d", fib);
	return 0;
}

運(yùn)行截圖：

遞歸：

源代碼：

//遞歸
int Fib(int n)
{
	if (n > 2)
	{
		return Fib(n - 1) + Fib(n - 2);
	}
	else 
	{
		return 1;
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	while (1)
	{
		if (n <= 0)
		{
			printf("輸入錯(cuò)誤請重新輸入:>");
		}
		else
		{
			printf("%d\n", Fib(n));
			break;
		}
	}
	return 0;
}

運(yùn)行截圖：