黑马程序员技术交流社区
标题:
一个菲波那契数列的题
[打印本页]
作者:
崔自成
时间:
2013-4-15 18:02
标题:
一个菲波那契数列的题
该数列的规律是 从第3个数开始,每个数都是前两个数的和, 1,1,2,3,5,8,13,21,34..........
有道题是要求写个方法接受一个int类型的参数,返回参数指定的个数的菲波那契数列, 如参数是 5 ,那就返回 1,1,2,3,5
一开始我以为很简单,后来发现真的不会....求解。
作者:
乘鱼飞
时间:
2013-4-15 18:33
本帖最后由 乘鱼飞 于 2013-4-15 18:36 编辑
普通方法:
import java.util.*;
public class Test {
public static void main(String[] args) {
int a=1,b=1,f;
System.out.print("请输入一个整数:");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.print(n+"的斐波那契级数为");
System.out.print("1"+" "+"1");
for(int i=3;i<=n;i++)
{
f=b;
b=a+b;
a=f;
System.out.print(" "+b);
}
}
}
递归方法:
import java.util.*;
public class Test {
public static long fib(int n)
{
if(n==1||n==2)
return 1;
else
return fib(n-1)+fib(n-2);
}
public static void main(String[] args) {
System.out.print("请输入一个整数:");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.print(n+"的斐波那契级数为");
for(int i=1;i<=n;i++)
{
System.out.print(" "+fib(i));
}
}
}
输出结果:
请输入一个整数:5
5的斐波那契级数为 1 1 2 3 5
希望对你有所启发
作者:
王大斌
时间:
2013-4-15 18:56
解这类问题,首先一定要分析其数学模型,这也是程序设计的基础
这个题使用的是递归的思想。
F0=1,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)
这是数学模型。建议集中学习递归。
作者:
lipingan0520
时间:
2013-4-15 19:02
import java.util.*; //记得导包,不然不能从键盘接收一个数值
class Qbl
{
public static long fib(int n)
{
if (n <= 1)
return n;
else
return fib(n-1) + fib(n-2); //递归调用,实现菲波那契数列
}
}
class QblDemo
{
public static void main(String[] args)
{
System.out.print("请输入一个整数:");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=1;i<=n;i++)
{
System.out.print(Qbl.fib(i)+"\t"); //输出
}
}
}
复制代码
作者:
杜成龙
时间:
2013-4-16 09:22
<DIV class=blockcode>
<BLOCKQUOTE>import java.util.*;
class FibDemo
{
public static void main(String[] args)
{
System.out.print("请输入一个整数:");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.print(n+"的斐波那契级数为");
int x=1,y=1,f;
for (int i=1;i<=n ;i++ )
{
if(i==1)
System.out.print(1+" ");
else if(i==2)
System.out.print(1+" ");
else
{
f=y;
y=x+y;
x=f;
System.out.print(y+" ");
}
}
}
}
复制代码
希望能对你有所帮助~~
作者:
钟逊
时间:
2013-4-16 11:29
用递归的思路的确简单,也容易理解,但是效率很低,稍加分析你就会发现每个递归分支都重复计算了很多次f(0)和f(1)。
其实还有一种比较简单的思路:建一个数组arr[],arr[0] = 1,arr[1] = 1,然后对于n>=2, arr[n] = arr[n-1] + arr[n-2]
这个递推公式不难得到,由于减少了大量的重复计算,运算效率高,计算结果得到了存储,以后调结果也方便,算法也很容易理解,供参考。
作者:
黄玉昆
时间:
2013-4-16 12:35
如果问题未解决,请继续追问,如果没有问题了,请将帖子分类 改为“已解决”,谢谢
作者:
先小涛
时间:
2013-4-17 01:11
虽然楼上都给出了答案,但都是直接打印结果,而不是返回一个int[]数组,如以下代码
public class Demo {
public static void main(String[] args) {
int[] arr = fib(14);
for(int i:arr) //遍历数组,打印所有数组中的值
System.out.print(i+" ");
}
//方法接受一个int类型的参数,返回参数指定的个数的菲波那契数列(int[])
public static int[] fib(int n){
int[] fibs = new int[n];
if(n==1)
fibs[0] = 1;
else{
fibs[1] = fibs[0] = 1;
for(int i=2; i<n; i++){
fibs[i] = fibs[i-1] + fibs[i-2];
}
}
return fibs;
}
}
复制代码
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2