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

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

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

前言

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

一、思路

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

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

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

1.非遞歸

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

當n>2的時候進入循環(huán)，將前兩個數(shù)相加得到第三個數(shù)；

當n<=2的時候跳出循環(huán)。

2.遞歸

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

$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ù)這個公式就能進行遞歸。當n>2的時候進行遞歸，當n = 1或n = 2時返回1。

二、源代碼以及運行截圖

為了方便大家的交流和學習，我將程序源代碼和運行截圖放置在下方。

非遞歸：

源代碼：

#include<stdio.h>
//遞歸和非遞歸分別實現(xiàn)求第n個斐波那契數(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;
}

運行截圖：

遞歸：

源代碼：

//遞歸
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("輸入錯誤請重新輸入:>");
		}
		else
		{
			printf("%d\n", Fib(n));
			break;
		}
	}
	return 0;
}

運行截圖：