`
中国小虫
  • 浏览: 12516 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

分治与动态规划------斐波那契数列

    博客分类:
  • C
C 
阅读更多

通过看斐波那契数列来看分治跟动态规划的区别,所耗费的时间动态规划的可以达到O(N)的时间复杂度。

/*//婓波那契----分治//
#include<stdio.h>
int F(int n)
{
    if(n == 1||n == 2)
     {
          return 1;
      }
	return F(n-1) + F(n-2);
}
int main(void)
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		printf("%d\n", F(n));
	}
	return 0;
}

//婓波那契----动态规划//
#include<stdio.h>
int main(void)
{
	long n, *a, i;
	while(scanf("%ld", &n) != EOF)
	{
		a = malloc((n + 1) * sizeof(int));
		a[0] = 0;
		a[1] = 1;
		for(i=2; i<=n; i++)
		{
			a[i] = a[i-1] + a[i-2];
		}
		printf("%d\n", a[n]);
	}
	return 0;
}*/

  

分享到:
评论

相关推荐

    (动态规划-分治法-贪心法-回溯法)算法练习题

    本资源汇集了动态规划、分治法、贪心法、回溯法四种算法的练习题,涵盖了矩阵连乘、最长公共子序列、背包问题、最大子段和、递归与分治法、Fibonacci 数列、全排列问题、棋盘覆盖问题、线性时间选择和循环赛日程表等...

    算法分析 递归与分治策略 动态规划 贪心算法 分支限界法 随机化算法等算法

    例如,著名的斐波那契数列和背包问题都可以用动态规划求解。它通过存储和重用子问题的解,避免了重复计算,提高了效率。 3. **贪心算法**: 贪心算法在每一步选择中都采取在当前状态下最好或最优的选择,以期望...

    算法-动态规划- 动态规划概述(包含源程序).rar

    - 动态规划的应用实例,如斐波那契数列、最长公共子序列、0-1背包问题等 - 动态规划的状态定义和状态转移矩阵 - 记忆化搜索的实现方式和效率分析 - 自底向上和自顶向下的算法设计 - 动态规划与其他算法(如分治、...

    c#精典五大算法 分治,动态规划,回溯法

    C#中的斐波那契数列、背包问题等经典问题都可以用动态规划解决。动态规划的关键在于状态转移方程和最优子结构,通过构造一个表格来保存中间结果,逐步求得最终解。文件Arith02.cs和Arith04.cs可能涉及了动态规划的...

    算法设计 蛮力法 分治法 动态规划 贪心算法 分支限界法 回溯法 近似算法 减制法

    经典的动态规划问题有斐波那契数列、最短路径问题等。动态规划强调最优子结构和无后效性。 4. **贪心算法(Greedy Algorithm)**: 贪心算法在每一步选择中都采取当前状态下最好或最优的选择,希望以此得到全局最...

    分治递归动态规划贪心常用算法实例

    本篇文章将深入探讨三种常用的算法:分治、递归、动态规划以及贪心策略,并通过实例来阐述它们的应用和重要性。 首先,让我们来看分治算法。分治法是一种处理大问题的策略,它将大问题分解为若干个规模较小、相互...

    算法设计-实验一-斐波那契数列.docx

    此外,斐波那契数列的计算还可以使用其他方法,如动态规划或循环,这有助于扩展编程技巧和算法设计能力。递归虽然直观,但可能会导致大量的重复计算,特别是在处理较大数值时效率较低。因此,在实际应用中,可能会...

    java代码实现斐波那契数列输出第n个数

    在实际应用中,斐波那契数列的概念还延伸到了动态规划、分治策略等高级算法,如解决最短路径问题、股票交易问题等。了解并能熟练运用斐波那契数列的计算方式,对于提升Java程序员的技能水平和解决实际问题能力具有...

    暴力、递归与分治、动态规划、贪心算法、回溯经典习题

    暴力、递归与分治、动态规划、贪心算法和回溯是算法设计中常见的几种思路和方法,经典习题是帮助我们更好掌握这些算法思想的重要途径。以下是对这些经典习题的详细说明: 1. 暴力解法习题 暴力解法往往是最直观、最...

    算法设计实验报告之多种方法求解斐波那契数列

    在这个算法设计实验报告中,主要关注的是通过不同的方法求解斐波那契数列,这是一种经典的计算机科学问题。斐波那契数列是由0和1开始,后面的每一项数字是前面两项数字的和,通常表示为F(n)。实验的目标是实现四种...

    动态规划,分治算法,概率算法,模拟退火算法,搜索算法,贪婪算法,网上matlab,遗传算法,组合算法

    经典的动态规划问题有斐波那契数列、背包问题和最长公共子序列等。 2. **分治算法**:分治策略是将一个大问题分解为两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的...

    fibonacci数列生成器

    此外,斐波那契数列还出现在各种数据结构和算法问题中,如动态规划、分治策略等。 在金融领域,斐波那契数列常用于技术分析,如股票市场的价格预测,以及交易图表中的斐波那契回撤和扩展等。而在计算机图形学中,...

    【C++】斐波那契数列应用的一个实例

    【C++】斐波那契数列应用的一个实例。这是关于斐波那契数列的一个例子,用C++语言实现

    斐波那契数列,矩阵连乘法

    通过这种方法,我们不仅能够高效地计算斐波那契数列,还能深入理解矩阵运算和分治策略在算法优化中的应用。这对于学习和理解高级算法以及计算复杂性理论至关重要。同时,这种优化技巧对于解决实际编程问题,如大数据...

    数据结构与算法-五大常用算法总结(分治法,回溯法,分治限界法,贪心算法,动态规划法),算法数据结构

    比如,斐波那契数列、背包问题等都可以用动态规划求解。与分治法和回溯法相比,动态规划更注重最优解的方向,并且不回溯,因此效率更高。 这五大算法在解决问题时各有特点,适用场景也有所不同。了解和掌握这些算法...

    栈与递归--含分治与回溯.zip

    例如,用分治法处理递归问题,如计算斐波那契数列,可以显著提高效率。而回溯法在解决棋盘游戏问题时,如棋类的走法搜索,配合栈可以实现深度优先搜索。 总的来说,“栈与递归--含分治与回溯”这个资料可能涵盖了栈...

    动态规划(算法)-代码

    - **分治与动态规划结合**:一些问题可以通过分治策略预处理,然后用动态规划求解,如快速选择算法中的“三向切分”。 - **贪心与动态规划结合**:在部分满足贪心选择性质的问题中,可以结合贪心策略简化动态规划...

    c语言分治法求众数重数-五大常见算法策略之——递归与分治策略,算法数据结构

    以下我们将探讨几种基于递归和分治策略的算法,包括Fibonacci数列、阶乘计算和小青蛙跳台阶问题。 首先,Fibonacci数列是递归的一个经典例子。递归定义了一个数列,其中每个数是前两个数的和。在C语言中,我们可以...

    Fibonacci数列.zip

    标题"Fibonacci数列.zip"表明这个压缩包包含与斐波那契数列相关的编程题目和解答。斐波那契数列是计算机科学和算法设计中的一个基础概念,它在程序设计竞赛,如“蓝桥杯”这样的VIP题目中经常出现。这个数列的定义...

Global site tag (gtag.js) - Google Analytics