番号を生成する方法の数を確認

Question

私はFibonacci digits onlyを与えている、私はKフィボナッチ数を使用して番号を生成する方法の数を見つける必要があります。

制約例：

1<=K<=10 
1<=N<=10^9 

：

N=14 and K=3 

2つの方法があります。

：ここ

(8,5,1) and (8,3,3) 

は私の再帰的なソリューションです。

public static void num_gen(int i ,long val ,int used){ 

     if(used==0){ 

      if(val==n) ans++; 
      return ; 
     } 

     if(i==Fib.length) return ; 

     for(int j=0;j<=used;j++){ 

      long x = j*Fib[i]; 
      if(x+val<=n){ 
       num_gen(i+1,x+val, used-j); 
      } 
     } 

} 

このソリューションは、NとK = 10の大きな値に対してタイムアウトします。より複雑なアルゴリズムを私に提供できますか？

Answer 1

これは、指数がフィボナッチ数である乗算多項式として表すことができます。因子の

数結果が指数に等しいN.結果多項式のメンバーの係数K.

ある

例：3から番号7を構成するいくつかの方法は何 これらの3つの数字のそれぞれは1,2または3

可能な番号（X + X 2 +x³）³=x⁹+3x⁸+6x⁷+7x⁶+6x⁵+3x⁴+x³

結果多項式のx7メンバーの係数なので、結果は6です。

Answer 2

私はあなたに別の言語で動作するソリューションを提供したいと思います。私はそれをJavaに翻訳する過程で学ぶのに役立つことを願っています。再帰が必要ではないと私は思っているので、あなたが作業中の再帰的な解決策を修正する手助けをする方法は不明だからです。フィボナッチ数のプリセット配列も必要ありません。

これはPerlであり、それがために働い：

$ perl fibber.pl 3 14 
8,5,1 
8,3,3 
2 matches 

しかし、私は、それは完全に正しいです保証することはできません。

#!/usr/bin/perl 
use bigint; 
use List::Util qw(sum); 

my ($digits, $goal) = @ARGV; 
if (!($digits > 0) || !($goal > 0)) { 
    die "Missing 2 arguments: the number count to sum, the value they sum to."; 
} 

sub fib { 
    my ($a, $b) = @_; 
    return sub { 
     if (0 == scalar @_) { 
      (my $r, $a, $b) = ($a, $b, $a+$b); 
      return $r; 
     } else { 
      ($a, $b) = @_; 
      (my $r, $a, $b) = ($b, $a+$b, $a+$b+$b); 
      return $r; 
     } 
    } 
} 

my @f = (0) x $digits; 
    @f = map {fib(1,2)} @f; 
my @d = map {$_->()} @f; 
my $count = 0; 
while ($d[0] < $goal) { 
    if ($goal == sum @d) { 
     $count++; 
     print(join(",", @d)."\n"); 
    } 
    my ($i, $a, $b) = (0, $d[$i], $f[$i]->()); 
    $d[$i] = $b; 
    while ($goal <= $d[$i]) { 
     $i++; 
     if ($i == $digits) { 
      print "$count matches\n"; 
      exit 0; 
     } 
     ($a, $b) = ($d[$i], $f[$i]->()); 
     $d[$i] = $b; 
    } 
    while ($i > 0) { 
     $i--; 
     $d[$i] = $f[$i]->($a, $b); 
    } 
}