0

私はかなり複雑なディオファントス方程式を解く必要がある数論の問題に取り組んでいます。この式をf(r1, r2, ..., rk)としましょう。方程式内の変数の数は、それ自体変数です。これは、私がプログラミングでつまずいているところです。

署名が次のようになる Java メソッドを書きたいと思います。

int[] getExponents( int n, int k, int max );

ここで、引数kは、ディオファントス方程式f(r1, ... , rk)の引数の数に等しくなります。

このメソッドは、0 < r1 < r2 < ... < rk < maxとなるr1, ..., rkのすべての組み合わせに対して f(r1, ... , rk)を評価する必要があります。ここで、maxはメソッドで指定された引数です。サイン。

n = f(r1, ... , rk) となるrが見つかった場合、 r1, ... , rkを整数配列として返します。(値nは、メソッド シグネチャで指定されます。)

このメソッドは再帰を使用すると思われます。残念ながら、私のプログラミング スキルや忍耐力では、それを見つけることができません。

私のためにそのような方法を概説できる人に感謝します。

4

2 に答える 2

1

f(int r[])が方程式を評価する関数のシグネチャであると仮定すると、基本的な関数は次のようになります。

  int[] getExponents( int n, int k, int max ){
    int[] result = new int[k];
    for(int i=0; i<k; i++)
      result[i]=i+1;
    do{
      if(f(result)==n)
        return result;
    }while(updateExponents(result,max));          
    return null;
  }

次に、とboolean updateExponents(result,max)の間の整数のシーケンスを増やして反復処理する関数が必要です。このようなもの：0max

  private boolean updateExponents(int[] result, int max) {
    int k = result.length;
    for(int i=k-1; i>=0; i--){
      if(result[i]< max-(k-i))
      {
        result[i]++;
        for(int j=i+1; j<k; k++)
          result[j]=result[j-1]+1;
        return true;
      }
    }
    return false;
  }

免責事項: このコードにはおそらくバグが含まれています。テストも実行もしていませんが、少なくとも出発点としては適切です。

于 2013-10-01T20:50:57.133 に答える
0

再帰の扱いについては、次のように考えます。(これはディオファントス方程式に限ったことではありません。これは、そのような整数のシーケンスをすべて見つける必要がある他のケースでも機能します。)

k問題は、0 < r1 < r2 < ... < rk < max となる整数 rのすべてのシーケンスを見つけることです。

さて、r1を選ぶことから始めましょう。可能性は 1、2、...、max - 1(実際には の前で停止できますmax - 1。ループを通過して、それぞれを試します。

ごとに、それを新しい問題に減らしました: r1 [固定] < r2 < r3 < ... < rk < max となる整数 r2、r3、...、rkr1のすべてのシーケンスを見つけます。k-1これは元の問題とよく似ていますか？さて、あなたの再帰があります。唯一の違いは、下限が 0 以外のものであることです。そのため、再帰ルーチンには下限パラメーター (最初に呼び出されたときに 0 になります) と、最初に呼び出されたときにパラメーターが必要になりますk。kその後、、、k-1などk-2。

あとは、底に落ちたときに何をすべきかを考えなければなりません。が 1 の場合k、再帰ルーチンを再度呼び出す必要はありません。集めたすべての数字で何かをする必要があるだけです。そのため、整数の配列を維持する必要があります。この配列は最初は空です。しかし、再帰の最初のレベルで整数が見つかったら、配列r1に追加します。r1次に、2 番目のレベルを追加する必要があります r2配列に; つまり、再帰メソッドには、これまでに見つかった整数の配列を保持するパラメーターが必要になります。メソッドの各呼び出しは、「これまでに見つかった整数」の配列を取得し、それ自体を再帰的に呼び出すときに新しい整数を追加してその配列を使用します。最下位レベルに到達すると、整数の完全な配列が得られ、ディオファントス方程式をテストして、整数でやりたいことを何でも行うことができます。

うまくいけば、それがあなたを始めさせるでしょう。

于 2013-10-01T20:53:05.633 に答える