黑马程序员技术交流社区

标题: 求斐波那契数列 算法原理，要能让我懂的。先谢谢了 [打印本页]
作者: app297    时间: 2014-3-8 00:05
标题: 求斐波那契数列 算法原理，要能让我懂的。先谢谢了
求斐波那契数列第n项，n<30
斐波那契数列前10项为 1,1,2,3,5,8,13,21,34,55

这个东西。一直没有搞明白到底用代码怎么体现。 有会的哥们么？ 给我解释下。 看百度 都是介绍一大堆。但是还是不会
作者: chen_x    时间: 2014-3-8 00:33
斐波那契数列的数学递推公式就是：F(0)=F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2时)
java实现就是按此公式从进行递归，递归到n=0和n=1时F(n)值是明确的，从而终止递归，代码如下：
public class Fibonacci {
       
        public static void main(String[] args) {
                for(int i=1;i<=30;i++){
                        System.out.println("斐波那契数列第"+i+"项值是"+Fibo(i-1));
                }

        }
    public static int Fibo(int n){
            if(n==0||n==1){
                    return 1;
            }else{
                    return Fibo(n-1)+Fibo(n-2);
            }
    }
}
可以看出来代码基本就是按照Fibonacci数列递推公式来的，关于递归，是先依次向下拆分为若干子式，直到子式已有明确取值，然后再从下往上逐步得到各个子式的值及最终值, 比如，F(4)=F(3)+F(2),而F(2)=F(1)+F(0)=1+1=2, F(3)=F(2)+F(1)=2+1=3, 这样F(4)=F(3)+F(2)=5.
作者: 榨菜    时间: 2014-3-8 00:39
下面是这个的公式         ------------所以得要用到递归
        0                 (n=0时)
f(n)= 1                 (n=1时)
        f(n-1)+f(n-2)  (n = 2,3,4,..)

下面是代码
  1. public static void main(String[] args) {
  2.                
  3.                 for(int i = 0; i<= 10 ;i++){
  4.                         //打印前10次的数
  5.                         System.out.print(math(i) +"  ");
  6.                 }

  8.         }
  9.         
  10.         //根据公式写的
  11.         public static int math(int n){
  12.                 if(n==0){              //递归最重要的就是一定要有个结束点，不能一直递归下去
  13.                         return 0;
  14.                 }else if(n== 1){       //递归最重要的就是一定要有个结束点，不能一直递归下去
  15.                         return 1;     
  16.                 }else{
  17.                         return math(n-1)+math(n-2);
  18.                 }
  19.                
  20.                
  21.         }
复制代码

结果：0  1  1  2  3  5  8  13  21  34  55  



作者: syw02014    时间: 2014-3-8 10:18
  1. import java.util.*;
  2. class Fibonacci
  3. {
  4.         public static void Fibonacci_NRecursion(int number)
  5.         {               
  6.                 long current = 1;        //当前数字               
  7.                 long next = 1;                //下一个数字               
  8.                 System.out.print(current+" "+next);               
  9.                 for (int i=0; i <number-2; i++)
  10.                 {                       
  11.                         long sum = current + next;        //两个数的和                       
  12.                         System.out.print(" "+sum);                       
  13.                         current = next;                       
  14.                         next = sum;               
  15.                 }       
  16.         }
  17.         public static int Fibonacci_Recursion(int n)
  18.         {
  19.                 if(n<=1)
  20.                         return 1;
  21.                 return Fibonacci_Recursion(n-1)+Fibonacci_Recursion(n-2);
  22.         }
  23.        
  24.         public static void main(String[] args)
  25.         {
  26.                 System.out.println("输入斐波那契数列的项数n：");
  27.         Scanner in = new Scanner(System.in);   
  28.         int n=in.nextInt();

  30.         System.out.print("     递归：");
  31.                 for(int i =0; i <n; i++)
  32.                         System.out.print(Fibonacci_Recursion(i)+" ");
  33.                
  34.                 System.out.print("\n非递归：");
  35.                 Fibonacci_NRecursion(n);

  37.         }
  38. }
  39.        
复制代码
作者: 观决    时间: 2014-3-8 10:38
在上课 没得编译环境  就给个核心代码吧   你是原理不懂还是代码不懂  原理不懂就要自己去查资料了解

因为是前30个 我看在c++中每超出int型 就用的int型

int [] a=new int[30];  //先定义一个数组，
a[0]=0;            //数组的前几项
a[1]=1;
a[2]=1;
a[3]=2;

for(int i=4;i<30;i++)      //根据规律开始前两项的和是后一项
{
   a[i]=a[i-1]+a[i-2];        //将前30个存入数组中，
}

for(int i=1;i<30;i++)     //依次输出每个的结果
{
System.out.print(a[i]+",");
}

用c++编写的结果是这样的

QQ截图20140308103746.png (82.45 KB, 下载次数: 8)

QQ截图20140308103746.png
作者: 战狼    时间: 2014-3-8 14:17
裴波拉契数列用的是递归的方法，方法如下：

图像 013.png (17.31 KB, 下载次数: 13)

裴波拉契数列

裴波拉契数列
作者: chaos    时间: 2014-3-8 15:14
/**
         *.求斐波那契数列第n项，n<30
     *斐波那契数列前10项为 1,1,2,3,5,8,13,21,34,55
公式为f（n）=f（n-1）+f（n-2）
         */

import java.util.Scanner;

public class Test3 {
       
        public static void main(String[] args) {
                System.out.print("请输入想得到的项数：");
                Scanner r = new Scanner(System.in);
                int a = 0;
                boolean b =true;
                //判断输入的数是不是小于30的正整数
                while(b){
                        if(!r.hasNextInt()){
                                System.out.println("请输入一个小于30的正整数！");
                            r = new Scanner(System.in);
                            continue;
                        }
                        a = r.nextInt();
                        if((0>=a)||(a>=30)){
                                System.out.println("请输入一个小于30的正整数！");
                            r = new Scanner(System.in);
                            continue;
                        }
                        b=false;
                }
                //输出结果
                System.out.print(new Test3().fibonacciSequence(a));
        }
//斐波那契数列的公式
        private int fibonacciSequence(int n){
                if(n==1||n==2){
                        return 1;
                }else{
                        return fibonacciSequence(n-1)+fibonacciSequence(n-2);
                }
        }

}




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2