Динамическое программирование Фибоначчи

Мне нужно сделать Фибоначчи с динамическим массивом dp. Если значение не установлено, имеется Double.NEGATIVE_INFINITY. Проблема в том, что результат неверный, и я не знаю, почему.

общедоступный статический двойной член DP (int n) {

    if (dp[n]!= Double.NEGATIVE_INFINITY){     
        return  dp[n];
    }
    if(n<c){
        dp[n] =  n;
    }else if( n%2 == 0) {
            dp[n] = a*memberDP(n-1)+memberDP(n-c);
    }else{
            dp[n] = b*memberDP(n-1)+memberDP(n-c);

        }
    return dp[n];
    }

public static void initDP(int maxn){
        dp = new double [maxn];
        for ( int i = 0;i<dp.length;i++){
        dp[i]= Double.NEGATIVE_INFINITY;
        }


}

Результат :

    c = 4;
    a = 1.5;
    b = 2.5;
    initDP(50);
    for ( int i = 0; i < 50; i++ ){
        System.out.println(i + ":\t" + memberDP(i));


    0: 0.0
    1:  1.0

    2:  2.0
    3:  -1.0
    4:  -0.5
    5:  2.25
    6:  2.375
    7:  -1.6875
    8:  -0.28125
    9:  2.515625
    10: 2.0859375
    11: -1.32421875
    12: 0.529296875
    13: 1.8212890625
    14: 1.40771484375
    15: -0.174560546875
    16: 1.5594482421875
    17: 0.62799072265625
    18: 0.767425537109375
    19: 1.1757354736328125
    20: 2.3915939331054688
    21: -0.4283714294433594
    22: 0.5331783294677734
    23: 2.125004768371582
    24: 2.7591357231140137
    25: -0.8463895320892334
    26: 0.8554204702377319
    27: 2.3314254879951477
    28: 2.650748699903488
    29: -0.46995387971401215
    30: 1.6264946684241295
    31: 1.8375013656914234
    32: 2.286298168823123
    33: 0.483345584012568
    34: 2.5625197417102754
    35: 1.0050382979679853
    36: 1.990903030964546
    37: 1.5670682262280025
    38: 3.355640637309989
    39: 0.3130827123095514
    40: 2.0366922946923296
    41: 2.337294489963824
    42: 3.8190244472552877
    43: 0.12718007106468576
    44: 2.528064596560853
    45: 2.5549921489748613
    46: 3.9596682945269777
    47: 0.548230449297364
    48: 3.3773378229209072
    49: 2.270999383066524
    */

java dynamic
person user3578012    schedule 12.05.2014    source источник
comment
Для какого ввода вы получаете неправильный результат? Какой результат вы получите и каким он должен быть? Пожалуйста, не заставляйте нас гадать.   -  person Dawood ibn Kareem    schedule 12.05.2014
comment
Я предполагаю, что у вас есть a=1, b=1 и c=2, чтобы получить из этого числа Фибоначчи.   -  person Dawood ibn Kareem    schedule 12.05.2014
comment
Фибоначчи — это последовательность целых чисел. Почему вы используете двойной?   -  person slim    schedule 12.05.2014
comment
@slim Они не являются целыми числами, если a и b не являются целыми числами. Это какое-то причудливое обобщение Фибоначчи.   -  person Dawood ibn Kareem    schedule 12.05.2014
comment
Действительно странно. Я бы беспокоился о n%2 == 0 для парного разряда.   -  person slim    schedule 12.05.2014
comment
@slim кажется, что n на самом деле целое число, dp[n] и a, b могут быть нецелыми   -  person Ordous    schedule 12.05.2014
comment
Как вам удалось превратить -1.0 в dp[3]? Если n=3 и c=4 должно получиться dp[3]=3.0   -  person Absurd-Mind    schedule 12.05.2014
comment
вау, я вижу свою ошибку, извините, все в порядке, у меня все в порядке. Спасибо всем за помощь :)   -  person user3578012    schedule 12.05.2014

Ответы (1)


arrow_upward
0
arrow_downward

Не зная точного определения вашего «Фибоначчи», можно подозревать, что часть - c неверна. После его удаления я получаю «значимые» результаты.

dp[n] = a * memberDP(n - 1) + memberDP(n - 2); // - 2 instead of - c

а также

dp[n] = b * memberDP(n - 1) + memberDP(n - 2); // - 2 instead of - c

Результаты:

0:  0.0
1:  1.0
2:  2.0
3:  3.0
4:  6.5
5:  19.25
6:  35.375
7:  107.6875
8:  196.90625
9:  599.953125
10: 1096.8359375
11: 3342.04296875
12: 6109.900390625
13: 18616.7939453125
14: 34035.09130859375
15: 103704.52221679688
16: 189591.87463378906
17: 577684.2088012695
18: 1056118.1878356934
19: 3217979.678390503
20: 5883087.705421448
person Absurd-Mind    schedule 12.05.2014
comment
Спасибо :) я был слишком слеп, чтобы увидеть правильный ответ ^^ - person user3578012; 12.05.2014