文档章节

斐波那契数(C/C++,Scheme)

NoMasp
 NoMasp
发布于 2015/09/08 21:45
字数 538
阅读 2
收藏 0

一、背景

斐波那契数的定义:

f0=0

f1=1

fi=fi1+fi2(i>1)

二、分析

我引用两张表,大家一看便懂。

1.递归

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4* 3 2)))) (* 6 (* 5 (* 4 6))) (* 6 (* 5 24)) (* 6 120) 720

2.迭代

(factorial 6)
(factorial 1 1 6)
(factorial 1 2 6)
(factorial 2 3 6)
(factorial 6 4 6)
(factorial 24 5 6)
(factorial 120 6 6)
(factorial 720 7 6)
720

递归的核心在于:不断地回到起点。
迭代的核心在于:不断地更新参数。

在下面的代码中,递归的核心是sum的运算,sum不断的累乘,虽然运算的数值不同,但形式和意义一样。

而迭代的核心是product和counter的不断更新。如上表中,product就是factorial的前2个参数不断的累乘更新成第一个参数;而第二个参数则是counter,其不断的加1来更新自己。

product <- counter * product
counter < - counter + 1

三、代码

C语言版

#include <stdio.h>
#include <stdlib.h>

int factorialRecursive(int n);
int factorialIteration(int product, int counter, int max_count);

int main()
{
    int n;
    printf("Enter an integer: \n");
    scanf("%d",&n);

    printf("%d\n",factorialRecursive(n));
    printf("%d\n",factorialIteration(1,1,n));

    return 0;
}

int factorialRecursive(int n)
{
    int sum=1;
    if(n==1)
        sum*=1;
    else
        sum=n*factorialRecursive(n-1);
    return sum;
}

int factorialIteration(int product, int counter, int max_count)
{
    int sum=1;
    if(counter>max_count)
        sum*=product;
    else
        factorialIteration((counter*product),(counter+1),max_count);
}

C++语言版

#include <iostream>

using namespace std;

int factorialRecursive(int n);
int factorialIteration(int product, int counter, int max_count);

int main()
{
    int n;
    cout<<"Enter an integer:"<<endl;
    cin>>n;
    cout<<factorialRecursive(n)<<endl;
    cout<<factorialIteration(1,1,n)<<endl;

    return 0;
}

int factorialRecursive(int n)
{
    int sum=1;
    if(n==1)
        sum*=1;
    else
        sum=n*factorialRecursive(n-1);
    return sum;
}

int factorialIteration(int product, int counter, int max_count)
{
    int sum=1;
    if(counter>max_count)
        sum*=product;
    else
        factorialIteration((counter*product),(counter+1),max_count);
}

四、进阶

Scheme语言版

(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))
(define (factorial n) (fact-iter 1 1 n))
(define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-counter)))



为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp

版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

本文转载自:http://blog.csdn.net/nomasp/article/details/45343891

NoMasp
粉丝 7
博文 334
码字总数 0
作品 0
镇江
程序员
私信 提问
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
184
0
nodejs多线程,真正的非阻塞(转)

node从他推出至今,充满赞美和饱受诟病的都是其单线程模型,所有的任务都在一个线程中完成(I/O等例外),优势的地方自然是免去了频繁切换线程的开销,以及减少资源互抢的问题等等,但是当n...

KelvinQ
2013/12/26
260
0
面试官问你斐波那契数列的时候不要高兴得太早

前言 假如面试官让你编写求斐波那契数列的代码时,是不是心中暗喜?不就是递归么,早就会了。如果真这么想,那就危险了。 递归求斐波那契数列 递归,在数学与计算机科学中,是指在函数的定义中...

编程珠玑
01/08
0
0
在Node.js中使用C++模块

对程序员来说,确实是我们作为服务端开发的首选语言。的性能优势源于其使用的,使用非阻塞式的,依靠事件驱动。但涉及密集型计算的场景时,不一定能够有很优秀的表现。还好有C++ Addons的机制...

counterxing
2018/10/29
0
0
斐波那契数列的三种C++实现及时间复杂度分析

斐波那契数列定义:F(1)=1, F(2)=1, F(n)=F(n-1) + F(n-2) (n>2) 如何计算斐波那契数 F(n) 及时间复杂度 T(n) 呢? 我参考了一些资料总结了以下3种方法:递归法、顺序法和矩阵乘法,并给出了基...

GarrettLu
2018/12/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

python学习10.04:Python list列表使用技巧及注意事项

前面章节介绍了很多关于 list 列表的操作函数,细心的读者可能会发现,有很多操作函数的功能非常相似。例如,增加元素功能的函数有 append() 和 extend(),删除元素功能的有 clear()、 remo...

太空堡垒185
10分钟前
2
0
新手插画学习的方法?教你如何自学?

插画学习的方法?教你如何自学? 从小喜欢画一些漫画头像随笔画,但是其实没有基础。个人偏好小清新手绘风的插画(如下图),每每看到都希望自己能画出这样的作品。 我其实很想说画这种美术功...

huihuajiaocheng
16分钟前
3
0
面试题

1、实现clone();

gtandsn
27分钟前
3
0
CentOS 7 部署 tesseract-ocr

官方地址 github yum-config-manager --add-repo https://download.opensuse.org/repositories/home:/Alexander_Pozdnyakov/CentOS_7/ 若提示 yum-config-manager: command not found 执行以......

阿白
27分钟前
2
0
JAVA比较器中comparator的使用

一个专用的比较器Comparator Comparator是一个专用的比较器,当一个不支持自比较或者自比较函数不能满足要求时,可写一个比较器来完成两个对象之间大小的比较。Comparator体现了一种策略模式...

daxiongdi
28分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部