3

プロジェクトオイラーでは、問題により、調和数列から20項の収束値を見つけるプログラムを作成するように求められます。

1/111, 1/222, 1/333, 1/444, 1/555, 1/666, 1/777, 1/888, 1/999, 1/1000, 1/1110, 1/1111, 1/1112, 1/1113, 1/1114, 1/1115, 1/1116, 1/1117, 1/1118, and 1/1119

問題を解決するために自分でプログラムを書きたいのですが、Calc IIを扱っていなかったので、発散/収束について調べなければなりませんでした。すべての説明は、式で表すことができるシリーズを扱っています。このシリーズは、私が知る限り、できません。

したがって、問題は次のとおりです。

この級数を表す式はありますか、それとも式なしでこの級数の収束を見つける方法はありますか？

4

3 に答える 3

9

誰かがブルートフォース攻撃を検討する場合に備えて：

ここでは、ほとんどの多数のプロジェクトオイラーの問題と同様に、力ずくのアプローチは妥当な時間内に終了しません。

コンピューターが1秒あたり109個の数値を処理できると仮定します（実際には、処理できる数ははるかに少なくなります）。10 nまでの有効な項を合計するにn > 9は、約10n-9秒かかります。

小数点以下10桁までの合計を決めるには、どこまで行かなければなりませんか？

すべてのより大きな有効な項の合計が10-10未満になるのに十分な距離です。10 12で十分でしょうか？いいえ。次の千の数字を考えてみてください

1001001001001

その中の無効な番号は

1001001001110
1001001001111
1001001001112
...
1001001001119
1001001001222
1001001001333
1001001001444
...
1001001001999
1001001002000

それらは19であるため、981の有効な数値があり、対応する合計は981/1001001002000より大きく、9 *10-10より大きくなります。これらの線に沿ってもう少し推論すると、10 15よりはるかに高いブルートフォースが必要になることがわかります。実際、残りの有効な用語の合計が10 -10未満になる前に、102000を超える必要があります。

宇宙の初めに始まったブルートフォースは、まだ信頼できる答えの近くにさえありません。

于 2012-01-26T23:37:01.663 に答える
0

問題を注意深く読むと、実際には数式があることに気付くでしょう。扱っているシーケンスは調和級数であり、3つ以上の等しい連続した数字を持つ項が削除されています。ここでの強引なアプローチは、必要な精度に達するまで指定されたものを省略して、調和級数のすべての項を合計することです。そのクラスを持つRubyは、そのRationalための非常に優れた候補のようです。

于 2012-01-26T20:53:04.590 に答える
0

この問題に対する素朴でブルートフォースのアプローチは、問題の説明に記載されている制限によって除外されていない場合、シリーズの分母を反復処理し、分母の逆数を全体の合計に追加するループを作成することです。

アウトラインは次のようになります。

for i in (1..1200)
  if is_valid(i) then
    sum += 1.0 / i
  end
end

def is_valid(_i)
  # implement the check here. hint: use modulo operator ;-)
end
于 2012-01-26T20:59:32.727 に答える