专栏首页WindCoderk 阶斐波那契序列的第 m 项值的函数算法—C语言

k 阶斐波那契序列的第 m 项值的函数算法—C语言

/***************************************************
作业要求:
		求 k 阶斐波那契序列的第 m 项值的函数算法

完成日期:
		2013年9月3日
***************************************************/
#include <stdio.h>

// 函数原型
int fibnocci_1(int m, int k);
int fibnocci_2(int m, int k);
int fibnocci_3(int m, int k);

// main函数
int main(void)
{
	// 求3阶fibnocci数列第8项的值
	// 0 0 1 1 2 4 7 13 24 ……
	printf("%dn", fibnocci_1(8, 3));
	printf("%dn", fibnocci_2(8, 3));
	printf("%dn", fibnocci_3(8, 3));

	return 0;
}

/****************************************************
函数功能:
		求k阶fibnocci数列的第m项值
算法思想:
		(1) 根据m和k的值,先返回特殊情况下的值;
		(2) 首先初始化前k项值;
		(3) 按照公式求第k+1项至第m项的值。
函数参数:
		int		m		待求fibnocci数列项数
		int		k		fibnocci数列的阶数
返回值:
		返回k阶fibnocci数列第m项的值
时间复杂度:
		O(m * k):双重循环(外层为m-k,内层为k)
空间复杂度:
		O(m):	开辟的辅助存储空间总共有m+3个(f、i、j、result)
*****************************************************/
int fibnocci_1(int m, int k)
{
	int i, j, result;
	int *f;				// 辅助数组空间
	// 特殊情况
	if (m < k-1)
	{
		return 0;
	}
	else if (m == k-1 || m == k)
	{
		return 1;
	}

	// 一般情况

	// 动态内存分配辅助空间
	f = (int *) malloc(sizeof(int) * (m+1));

	// 初始化前k项的值
	for (i = 0; i < k-1; ++i)
	{
		f[i] = 0;
	}
	f[k-1] = f[k] = 1;

	// 求第m项值
	for (i = k+1; i <= m; ++i)
	{
		f[i] = 0;
		for (j = 1; j <= k; ++j)
		{
			f[i] += f[i - j];
		}
	}
	result = f[m];

	// 释放辅助空间
	free(f);

	return result;
}

/****************************************************
函数功能:
		求k阶fibnocci数列的第m项值
算法思想:
		(1) 根据m和k的值,先返回特殊情况下的值;
		(2) 首先初始化前k项值;
		(3) 按照公式求第k+1项至第m项的值(借助数学运算简化求解)。
函数参数:
		int		m		待求fibnocci数列项数
		int		k		fibnocci数列的阶数
返回值:
		返回k阶fibnocci数列第m项的值
时间复杂度:
		O(m):	计算第m项时,借助数学公式取消内层循环
空间复杂度:
		O(m):	开辟的辅助存储空间总共有m+3个(f、i、j、result)
*****************************************************/
int fibnocci_2(int m, int k)
{
	int i, j, result;
	int *f;				// 辅助数组空间
	// 特殊情况
	if (m < k-1)
	{
		return 0;
	}
	else if (m == k-1 || m == k)
	{
		return 1;
	}

	// 一般情况

	// 动态内存分配辅助空间
	f = (int *) malloc(sizeof(int) * (m+1));

	// 初始化前k项的值
	for (i = 0; i < k-1; ++i)
	{
		f[i] = 0;
	}
	f[k-1] = f[k] = 1;

	// 求第m项值
	for (i = k+1; i <= m; ++i)
	{
		// 按照数学公式计算
		f[i] = 2 * f[i - 1] - f[i - k - 1];
	}
	result = f[m];

	// 释放辅助空间
	free(f);

	return result;
}

/****************************************************
函数功能:
		求k阶fibnocci数列的第m项值
算法思想:
		递归求解。
函数参数:
		int		m		待求fibnocci数列项数
		int		k		fibnocci数列的阶数
返回值:
		返回k阶fibnocci数列第m项的值
时间复杂度:
		O(k^m):	由递归式:f(m) = k * f(m-1),
		则f(m) = k * k * f(m-2),以此类推可得,
		f(m) = k^m
空间复杂度:
		O(m * k):	每一次递归调用过程中需要求得其前k项的值,
		共需递归调用m次,故总共的辅助空间约为 m * k个。
*****************************************************/
int fibnocci_3(int m, int k)
{
	int i, result = 0;
	if (m < k - 1)
	{
		return 0;
	}
	else if (m == k - 1 || m == k)
	{
		return 1;
	}
	else
	{
		for (i = 1; i <= k; ++i)
		{
			result += fibnocci_3(m - i, k);
		}
		return result;
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数组计算

    汐楓
  • 求最大公约数

    汐楓
  • 数组版通讯录-C++

    汐楓
  • 数据结构第四次实验 矩阵快速转置与矩阵加法

    用户2965768
  • 对数据操作封装的一点心得

    在对数据进行操作时,可能需要读写name,于是我们写了一个接口,这个接口会实时更新缓存

    王亚昌
  • 【Miscalculation UVALive - 6833 】【模拟】

    题目讲的是给你一个串,里面是加法、乘法混合运算(个人赛中误看成是加减乘除混合运算),有两种算法,一种是乘法优先运算,另一种是依次从左向右运算(不管它是否乘在前还...

    _DIY
  • URAL 2040 Palindromes and Super Abilities 2(回文树)

    Palindromes and Super Abilities 2 Time Limit: 1MS Memory Limit: 102400KB ...

    ShenduCC
  • Data Structure_Visualization

    选择排序很简单,遍历所有元素,查看一下他们的之后最小的元素和当前元素交换即可。模板函数使用上面的swing模板。为了更清楚显示出排序的过程,可以用不同颜色代表排...

    西红柿炒鸡蛋
  • leetcode 88 Merge Sorted Array

    Given two sorted integer arrays nums1 and nums2, merge nums2 intonums1 as one so...

    用户1539362
  • 8寒假专辑:五、循环结构​

    int *fun(int *a , int *b) 这里是函数声明的写法,注意数组就是指针

    用户6755376

扫码关注云+社区

领取腾讯云代金券