k阶斐波那契序列问题

Question

f(0)=0,f(1)=0,...f(k-2)=0,f(k-1)=1;f(n)=f(n-1)+f(n-2)+........+f(n-k),n=k,k+1,....
请用java编写出算法

Answer 1

我记得这个数列第1项应该是1吧，不过我是按照你的要求写的，你看下吧：
public class TestApplet{
public static int returnSum(int i){
int sum = 0;

if (i<0)
return -1;
else if (i == 2)
sum = 1;
else if(i>2)
sum = returnSum(i-1) +returnSum(i-2);

return sum; }

public static void main(String args[]){
for (int i=0; i<10; i++)
System.out.println(returnSum(i));
} 
}
输出：
0
0
1
1
2
3
5
8
13
21

Answer 2

小猴子手太快了，刚想抢分来着，就被你抢了沙发～递归算法：public class Fibonacci {
public static int fib(int n) {
                if (n < 2) {
                   return n;
                }
                else {
   return fib(n-1)+fib(n-2);
                }
} 
}
循环算法：public class FibonacciIterative {
public static int fib(int n) {
                int prev1=0, prev2=1;
                for(int i=0; i<n; i++) {
                    int savePrev1 = prev1;
                    prev1 = prev2;
                    prev2 = savePrev1 + prev2;
                }
                return prev1;
}
}

Answer 3

大家 忽略了 一点 
不仅仅是 f(0)和f(1)为0  
这要看K
0~k-2都是 0  k-1为1
这样再用递归的方式求出k  之后是k+1这样算法需要改下

Answer 4

很感谢你发代码上来，但是请看题，你发的哪个是最简单的斐波那契数列（f（n）=f(n-1)+f(n-2)），我这个可比你那个复杂多了，而且我要声明我知道他是递归，请不要再说“这是最简单的递归”这种幼稚的回答
在此谢谢大家，请高手给出正解，我会一直关注

Answer 5

没人给解决吗
f(n)=f(n-1)+f(n-2)+........+f(n-k),n=k,k+1,.... 这个方法#3也没有实现啊
自己顶下  希望高手给解决

Answer 6

本来不想说气话的，看到楼主的语气，实在气不过，想说两句：1.最近csdn很多问问题的同学/同志，一上来就就丢个莫名其妙不知所云的标题，正文丢一段代码或者数学表达式，然后就什么说明都没有了，让网友去猜啊？连稍微描述一下疑问的一点时间都不愿意花，怎么能够期待大家踊跃的回答呢？2.另外8楼的回复实在是不够礼貌，既然是来论坛问问题的，谦虚谦让一点不行么，那语气给人一种盛气凌人的感觉以上说的是近期csdn的一种普遍现状，并不是特指楼主，请不要见怪！实在是气不过，发几句牢骚！

Answer 7

只写主程序sum = new int[n + 1];
f = new int[n + 1];for (int i = 0; i < k - 1; ++i) f[i] = sum[i] = 0;
f[k - 1] = sum[k - 1] = 1;for (int i = k; i <= n; ++i) {
  f[i] = sum[i - 1] - (i - k - 1 < 0 ? 0 : sum[i - k - 1]);
  sum[i] = sum[i - 1] + f[i];
}

Answer 8

首先向大家致歉，可能是我没说明白，具体题目是这样的：
f(0)=0,f(1)=0,...f(k-2)=0,f(k-1)=1;f(n)=f(n-1)+f(n-2)+........+f(n-k),n=k,k+1,....，
试编写求k阶斐波那契序列的第m项值得函数算法，k和m均以值调用的形式在函数参数表中出现（貌似和我一开始给的差不多啊，呵呵）
关注中！！！！！！！

Answer 9

阶斐波那契序列，求F(N)时使用递归的执行效率极其低下，几乎可以作为递归效率低的一个典型。
正确的做法是采用非递归算法。只是这个题目比较特殊，可以用简单的循环实现。#4楼中的循环算法不错。
如果想求出所有的值，可以如下大概的主体：if (n < 2) return 0;
int f = new int[n + 1];
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; ++ i)
{
    f[i] = f[i-2] + f[i - 1];
}
return f[n];

Answer 10

public static void main(String[] args) {
System.out.println(compute(9));
} private static long compute(int i) {
if (i == 0 || i == 1) {
return i;
} else {
return compute(i - 1) + compute(i - 2);
}
}

Answer 11

楼主一定要非递归的么？递归的话是比较简单，不过当M增大时，效率是急剧下降的。
先给你递归的吧，非递归的还得研究一下：public class KLevelFibo {

public static int get(int k, int m) {
if (m < k-1) return 0;
else if (m == k-1) return 1;
else {
int result = 0;
for (int i = m-k; i < m; i++)
result += get(k, i);
return result;
}
} public static void main(String[] args) {
System.out.println(KLevelFibo.get(3, 10));
}}

Answer 12

结贴的时候会给你的，我也是很friendly的人，交个朋友吗，积分是次要的

Answer 13

下面是非递归的版本：
public static int get(int k, int m) {
if (m < k-1) return 0;
else if (m == k-1) return 1;
else {
int[] prevs = new int[m+1];
prevs[k-1] = 1;

for (int i = k; i < m+1; i++) {
int cur = 0;
for (int j = i-k; j < i; j++)
cur += prevs[j];
prevs[i] = cur;
}
return prevs[m];
}
}

Answer 14

今天结贴突然来了灵感。。f(0)=0,f(1)=0,...f(k-2)=0,f(k-1)=1;f(n)=f(n-1)+f(n-2)+........+f(n-k),n=k,k+1,....， 
试编写求k阶斐波那契序列的第m项值得函数算法，k和m均以值调用的形式在函数参数表中出现
分析：可分为3个阶段:
1.0<=m<=k-2 f(m)=0;
2.m=k-1 f(m)=1;
3.m>k-1 用数学归纳法解f(n)=f(n-1)+f(n-2)+........+f(n-k),n=k,k+1,....，
当n=k时 f(m)=f（k）=1；
当n=k+1是 f（m）=f(k+1)=f(k)+f(k-1)+0=f(m-1)+f(m-2)
........
可以看出我们可以把f(n)=f(n-1)+f(n-2)+........+f(n-k),n=k,k+1,....， 看成是首项f（k）=1，f（k+1）=2，第m项 f（m）=f（m-1）+f（m-2），
于是可以用我们常见的k阶斐波那契序列求m项来求解
代码：
package file;import java.util.Scanner;public class structer {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
int m = sc.nextInt();
int f[]=new int[10];
if(m>=0&&m<=k-2){
for(int i:f){
i=0;}
}
if(m==k-1){
f[m]=1;
}
else{
for(m=k;m<f.length;m++){
f[k]=1;
f[k+1]=2;
f[m]=f[m-1]+f[m-2];
}
}
for(int j:f ){
System.out.println(j);
}
}
}
结贴时间延长，以上代码供大家讨论。。

Answer 15

直接算吧
public class Test {    public static void main(String[] args) {       
        long n = fibonacci(40);
        System.out.println("F(40) = " + n);
    }
   
    public static long fibonacci(int month) {
        if(month < 1) {
            return 0;
        }
        double sqrt5 = Math.sqrt(5);
        double a = Math.pow((1 + sqrt5) / 2, month);
        double b = Math.pow((1 - sqrt5) / 2, month);
        double r = (sqrt5 / 5) * (a - b);
        return Math.round(r);
    }
} 

Answer 16

楼主有意思啊，这个规律都找到了，我也是一开始想到了简单的递归Fibonacci数列解决，发现有些不对劲，一直愁眉不展，多谢~

Answer 17

不好意思，楼主你错了，你只是归纳到，n=k+1，继续就不成立，因为
n=k+2,f(m)=f(k+2)=f(k+1)+f(k)+f(k-1)；等于三项...还是失望了