打印菱形以及斐波纳契数列的几种解法介绍

1、编写程序，打印*菱形
推出第i行要打印的空白个数及*号个数，用for循环依次打印各行


代码如下:

#include<stdio.h>
//总共要打印2*n-1行，逐行打印
void print1(int n)
{
 int i,j;
 for(i=1;i<=n;i++){//打印1至n行
  for(j=1;j<=n-i;j++)//打印n-i个空格
      printf(" ");
  for(j=1;j<=2*i-1;j++)//打印2*i-1个*号
   printf("*");
     printf("\n");
 }
    for(;i<2*n;i++){//打印n+1至2*n-1行，同(2*n-i)行
  for(j=1;j<=n-(2*n-i);j++)
      printf(" ");
  for(j=1;j<=2*(2*n-i)-1;j++)
   printf("*");
     printf("\n");
 }
}
void main()
{
 int n;//n是菱形边上*号的个数
 printf("enter n:");
 scanf("%d",&n);
 print1(n);
}

2、斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：
1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）.编写程序，输出F(20)的值。

这里给出四种不同的解法，注意递归和改进的递归效率上有很大区别。


代码如下:

#include<stdio.h>
#include<math.h>
#include<time.h>
#define MAX 100
//递归
int f1(int n)
{
 if(n==1 || n==0)
  return 1;
 return f1(n-1)+f1(n-2);
}
//改进版的递归,去除重复计算
int f2(int n)
{
 //保存中间结果的数组
 static result[MAX]={1,1};
 if(n==1 || n==0)
  return 1;
    if(result[n-1] == 0)
  result[n-1]=f2(n-1);
 if(result[n-2] == 0)
  result[n-2]=f2(n-2);
 return result[n-1]+result[n-2];
}
//用数组保存中间结果(来自陈孝杰)
int f3(int n)
{
    int a[MAX],i;
 a[1]=1;
 a[0]=1;
 for(i=2;i<=n;i++)
  a[i]=a[i-1]+a[i-2];
 return a[n];
}
//迭代
int f4(int n)
{
    int i=2,a=1,b=1,sum=1;
 while(i<=n){
       sum=a+b;
    a=b;
    b=sum;
    i++;
 }
 return sum;
}
void main()
{
 long start,end;
 start=clock();
 printf("f(40)==%d\n",f1(40));
 end=clock();
    printf("用时：%d ms\n",end-start);
 start=clock();
 printf("f(40)==%d\n",f2(40));
 end=clock();
    printf("用时：%d ms\n",end-start);
 start=clock();
 printf("f(20)==%d\n",f3(20));
 end=clock();
    printf("用时：%d ms\n",end-start);
 start=clock();
 printf("f(20)==%d\n",f4(20));
 end=clock();
    printf("用时：%d ms\n",end-start);
}

运行结果：

赞 (0)

相关推荐

  • 斐波那契数列 优化矩阵求法实例

    斐波那契数列 优化矩阵求法实例

    在做编程题目的时候经常会遇到"斐波那契数列"相关的题目,尤其在做OJ中.下面说一些方法: (一)递归 递归是最慢的会发生重复计算,时间复杂度成指数级. 复制代码 代码如下: long long fac(int n){ if(n==1) return 1; else if(n==2)  return 2; else   return fac(n-1)+fac(n-2);} (二)循环 利用临时变量来保存中间的计算过程,加快运算. 复制代码 代码如下: long long fac(int

  • 求斐波那契(Fibonacci)数列通项的七种实现方法

    求斐波那契(Fibonacci)数列通项的七种实现方法

    一:递归实现使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1.二:数组实现空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快.三:vector<int>实现时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源.四:queue<int>实现当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int>一样,但队列太适合这里了,

  • 递归形式与非递归形式的斐波那契数列的用法分析

    复制代码 代码如下: <SPAN style="FONT-SIZE: 32px">采用递归形式和非递归形式实现斐波那契数列</SPAN> 复制代码 代码如下: #include "stdafx.h"#include <iostream>using namespace std;//递归形式的斐波那契数列int fibonacciRecursion(int n){ if (n == 1 || n ==2) {  return 1; }

  • c#斐波那契数列(Fibonacci)(递归,非递归)实现代码

    c#斐波那契数列(Fibonacci)(递归,非递归)实现代码

    //Main 复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Fibonacci{    class Program    {        static void Main(string[] args)        {            Console.WriteLine("Would you like to know which

  • 基于使用递归推算指定位数的斐波那契数列值的解决方法

    昨天面试遇到这样的一道题目:1,1,2,3,5,8,13,21...,请问第30位的值是多少? 代码实现如下: 复制代码 代码如下: //1,1,2,3,5,8,13,21.......第30个是多少?     //使用递归计算指定位数的斐波那契数列值     //Fn=F(n-1)+F(n-2)     public static int GetFibonacciNumber(int index)     {         if(index<0||index==0)throw new Exc

  • 解析分别用递归与循环的方式求斐波那契数列的实现方法

    代码如下: 复制代码 代码如下: public class Fibonacci { public static long recursive(int n) {  if (n <= 0)   return 0;  if (n == 1)   return 1;  return recursive(n - 1) + recursive(n - 2); } public static long loop(int n) {  if (n <= 0)   return 0;  if (n == 1)  

  • 打印菱形以及斐波纳契数列的几种解法介绍

    打印菱形以及斐波纳契数列的几种解法介绍

    1.编写程序,打印*菱形推出第i行要打印的空白个数及*号个数,用for循环依次打印各行 复制代码 代码如下: #include<stdio.h>//总共要打印2*n-1行,逐行打印void print1(int n){ int i,j; for(i=1;i<=n;i++){//打印1至n行  for(j=1;j<=n-i;j++)//打印n-i个空格      printf(" ");  for(j=1;j<=2*i-1;j++)//打印2*i-1个*号 

  • JS实现斐波那契数列的五种方式(小结)

    下面是五种实现斐波那契数列的方法 循环 function fibonacci(n){ var res1 = 1; var res2 = 1; var sum = res2; for(var i = 1;i < n;i ++){ sum = res1 + res2; res1 = res2; res2 = sum; } return sum; } 普通递归 function fibonacci (n) { if ( n <= 1 ) {return 1}; return fibonacci(n

  • C语言中斐波那契数列的三种实现方式(递归、循环、矩阵)

    C语言中斐波那契数列的三种实现方式(递归、循环、矩阵)

    目录 一.递归 二.循环 三.矩阵 <剑指offer>里讲到了一种斐波那契数列的 O(logN) 时间复杂度的实现,觉得挺有意思的,三种方法都记录一下. 一.递归 一般来说递归实现的代码都要比循环要简洁,但是效率不高,比如递归计算斐波那契数列第n个元素. long long Fibonacci_Solution1(unsigned int n) { // printf("%d ", n); if (n <= 0) return 0; if (n == 1) retur

  • C++输出斐波那契数列的两种实现方法

    定义: 斐波那契数列指的是这样一个数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...这个数列从第三项开始,每一项都等于前两项之和. 以输出斐波那契数列的前20项为例: 方法一:比较标准的做法,是借助第三个变量实现的. 复制代码 代码如下: #include<iostream>  using namespace std;int main(){    int f1=0,f2=1,t,n=1;    cout<<"数列第1个

  • C语言求Fibonacci斐波那契数列通项问题的解法总结

    C语言求Fibonacci斐波那契数列通项问题的解法总结

    一:递归实现   使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1. 二:数组实现   空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快. 三:vector<int>实现   时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源. 四:queue<int>实现   当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int&g

  • C#实现斐波那契数列的几种方法整理

    什么是斐波那契数列?经典数学问题之一:斐波那契数列,又称黄金分割数列,指的是这样一个数列:1.1.2.3.5.8.13.21.--想必看到这个数列大家很容易的就推算出来后面好几项的值,那么到底有什么规律,简单说,就是前两项的和是第三项的值,用递归算法计第50位多少. 这个数列从第3项开始,每一项都等于前两项之和. 斐波那契数列:{1,1,2,3,5,8,13,21...} 递归算法,耗时最长的算法,效率很低. public static long CalcA(int n) { if (n <=

  • java实现斐波那契数列的3种方法

    先说说为什么写这个吧,这个完全是由去阿里巴巴面试引起的一次惨目忍睹的血案.去面试的时候,由于面试前天晚上11点钟才到阿里巴巴指定面试城市,找到旅馆住下基本都1点多,加上晚上完全没有睡好,直接导致第二天面试效果很不好(对于那些正在找工作的大虾们不要向小虾一下悲剧,提前做好准备还是很重要滴),面试大概进行了一个多小时(面试结束回去的时候基本走路都快睡着了,悲催!!),面试快结束的时候面试官问的我问题就是关于费波那西数列,当时头脑完全浆糊,只知道要设置三个变量或者用List先初始化,当写到for循环的

  • PHP迭代器实现斐波纳契数列的函数

    复制代码 代码如下: class Fibonacci implements Iterator {     private $previous = 1;     private $current = 0;     private $key = 0; public function current() {         return $this->current;     } public function key() {         return $this->key;     } pub

  • Python/R语言分别实现斐波那契数列的示例详解

    Python/R语言分别实现斐波那契数列的示例详解

    目录 前言 1.年龄计算 1.1 图解问题 1.2 代码解决 1.3 实验小结 2.斐波那契数列 2.1 图解问题 2.2 代码实现 2.3 实验小结 总结 前言 此专栏为python与R语言对比学习的文章:以通俗易懂的小实验,带领大家深入浅出的理解两种语言的基本语法,并用以实际场景!感谢大家的关注,希望对大家有所帮助. “博观而约取,厚积而薄发!”谨以此言,望诸君共勉 本文将前两个小实验整理拼凑再了一起 :分别是“年龄计算”.“斐波那契数列”.具体的项目介绍见下文. 1.年龄计算 有 5 个人

  • python实现斐波那契数列的方法示例

    python实现斐波那契数列的方法示例

    介绍 斐波那契数列,又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下递归的方法定义: F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*) . 1. 元组实现 fibs = [0, 1] for i in range(8): fibs.append(fibs[-2] + fibs[-1]) 这能得到一个在指定范围内的斐波那契数列的列表. 2. 迭代器实现 class Fibs: def __init__

随机推荐