3

プロパティを持つ有理数を見つけるためのプログラムを書かなければなりません。プロパティをチェックするコードを書きましたが、今ではすべての有理数をチェックする方法がわかりません。で試してみました

float rat;
for (int i=1 ; i ; ++i) {
  for (int j=1 ; j ; ++j) {
    rat = (float)i/(float)j;
    if goodRat(rat) then return rat;
  }
}

しかし、それは決して終わりません！そして、それはあまりにも多くを逃します。だから私はこれを試しました

float rat;
while {
  int i = random(1000) + 1;
  int j = random(1000) + 1;
  rat = (float)i/(float)j;
  if goodRat(rat) 
      return rat;
}

しかし、これはたまにしか機能しません。どうすればこれを解決できますか？

4

3 に答える 3

10

有理数は可算です。つまり、整数と1対1で対応させることができます。そうすれば、あなたはあなたの解決策を手に入れるでしょう。

1対1の対応をする代わりに、理論的根拠をウォークスルーする簡単な方法は次のとおりです。

（可算）無限×（可算）無限行列Qを作成して、Q_(i,j) = i/jここでiとjの範囲がから1になるようにしinfinityます。マトリックスは次のようになります。

 1  1/2 1/3 1/4 1/5 . . .
2/1 2/2 2/3 2/4 2/5 . . .
3/1 3/2 3/3 3/4 3/5 . . . 
4/1 4/2 4/3 4/4 4/5 . . .
5/1 5/2 5/3 5/4 5/5 . . .
 .   .   .   .   .
 .   .   .   .   .
 .   .   .   .   .

もちろん、繰り返しはたくさんありますが（対角線全体が1です！）、速度よりも単純にするために使用します。

あなたがやろうとしているのは、無限の列を歩くことです。そのため、たくさんの数字を見逃してしまいます。代わりに、有限である反対角線に沿って歩く必要があります。つまり、次の順序で要素を取得します

 1  3  6 10 15  . 
 2  5  9 14  .  .
 4  8 13  .  .  .
 7 12  .  .  .
11  .  .  .
 .  .  .
 .  .
 .

だからあなたは得るでしょう1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4, ...。r/sさらに、ステップで遭遇することを知っている(r+s)(r+s-1)/2 + sので、任意の有理数は有限時間で遭遇します。

これをコーディングする1つの方法はi、行インデックス（外側のforループ）jと列インデックス（内側forループ）にすることです。次に、からのi範囲になりますが、からの1範囲になります。infinityj1i

goodRat関数にかなりの時間がかかる場合は、最初に互いに素であるかどうかをテストすることでこれを高速化できます。そうでない場合はスキップしますi。j

于 2011-06-16T01:55:51.773 に答える
4

スターンブロコットツリーは、繰り返しなしですべての有理数を体系的に生成する1つの方法です。https://math.stackexchange.com/questions/7643/produce-an-explicit-bijection-between-rationals-and-naturalsで他の人を参照してください。

于 2011-06-16T01:55:04.117 に答える
0

まず、最初の試みについて：

float rat;
for (int i=1 ; i ; ++i) {
    // the loop for the first won't be reached
  for (int j=1 ; j ; ++j) {
  // this loop will never end, it will either loop for ever or return something like (floag)1/(float)j
    rat = (float)i/(float)j;
    if goodRat(rat) then return rat;
  }
}

私のアドバイスは、あなたの目的を明確にすることです、そして多分あなたはhttp://en.wikipedia.org/wiki/Stern-Brocot_treeを参照することができます

于 2011-06-16T02:03:42.060 に答える