問題タブ [diophantine]

一般的なディオファントス方程式を次のようにします: a1*x1 + a2*x2 + .... + am*xm = n 、ここで gcd(a1...am) = 1, (a1....am) >= 0

非負 (x1..xm) 解の数を見つけたいです。誰かがこれで私を助けてくれますか? 詳細な数学的説明またはアルゴリズムは非常に役立ちます。

私はプログラミングとルビーが初めてです。私は特定のディオファントス方程式 (MIT オープンコースウェアの問題から) を扱うコードに取り組んでおり、それを使って何ができるかを調べています。

このコードは、3 つの変数を持つ特定の線形方程式に対して、3 つの配列と、そのうちの 2 つのハッシュを生成します。

コードは次のとおりです。

私が今やろうとしているのは、個々のハッシュペアにアクセスして、それらが正しく並んでいることを確認することですが、

任意の数値に対して nil を返します。何か助けはありますか？また、初心者なので何か良い方法があれば教えていただけると助かります。

MIT Open Courseware Introduction to Computer Science and Programming を独学しています。問題セット 2には、チキン ナゲットの箱 (6、9、または 20) の合計を数えることに基づくディオファントス方程式が含まれます。

アルゴリズムの作成について私が考えた方法は、測定値のサイズ (値) がスティックに記録され、別のピースに転送される、(木工所のような) 仮想測定スティックを作成するようなものでした。

数直線上で使用されていると想像すると、初期値が示され、それらのスポットに印を付けてから、最初に遭遇した印にゼロ点を移動して新しい印を付け、繰り返します。それは、常に前進することです。

、x=0、a=x+6、b=x+9、c=x+20それぞれがリストに追加され、次のようになります[6,9,20]。次にやりたいことはx、リスト内の次に大きい値に切り替えて、リストに追加される他の変数の新しい値を作成することです。の次の値xは で6、他の変数を変更すると、次のようなリストになります[6,9,20,12,15,26]。次に、9などです。

私の最初の問題は、重複とリストの順序が無限ループを引き起こすことでした。リストに戻す一連のリストを作成する行を追加することで、それを修正しました。これはほとんど機能しました。

しかし、ここに問題があります。可能なすべての値でリストを埋めるわけではありません。たとえば、明らかに 6 の倍数である 48 はリストに入れません。

私の推測では、私の問題は、常に編集および/または追加されているリストを繰り返し処理しているという事実と関係があると思います。

私は研究を行い、他の人がこの問題の答えをどのようにコーディングしたかを見たので、使用して割り当てを再設計できるアルゴリズムがあることを知っています。問題の解決策。これまでの私のコードは次のとおりです。

セットのフロベニウス数は、セットの数の gcd が 1 である場合に存在します。すべての要素の gcd が 1 であるような最大 10 個の要素を持つ正の整数のセットが与えられた場合、セットのフロベニウス数をどのように計算できますか? ?

元の問題へのリンクは次のとおりです: https://icpcarchive.ecs.baylor.edu/external/62/6298.pdf シルベスターの公式を使用して、2 つの要素のセットのフロベニウス数を見つけることができます。

問題は次のとおりです。次の式で、x、y、および n は正の整数です。

1/x + 1/y = 1/n

極限 L に対して、F(L) を x < y ≤ L を満たす解の数として定義します。

F(15) = 4 および F(1000) = 1069 であることを確認できます。F(1012) を求めます。

F(15) を見つけることができるかどうかをテストすることにしました

しかし、リストには何も保存されていません。

同様の質問があります: Checking whether a variable is an integer or notですが、質問に対する回答がありません。

つまり、私は最近大きな数と戦っていたので、私の友人は私に Python をインストールするように勧めました。今日開いたので、大きな数を計算して精度を高めることができましたが...この精度をどのように使用するのですか? つまり、うまくいくようなpow(31,123)ことをするとうまくいきますが、数値が整数かどうかを確認したい場合は、次のようになります。

diophantine-equationのいくつかの解を見つける単純なループを書きたかったのですが、非常に大きな数から平方根を取り、それが整数かどうかを確認する必要がありますが、今はピンチです。誰かが私を助けたり、より良い精度を達成するためのアドバイスをくれたりできますか?

例：

例: $ 2x^2 = 1 + y^31 $、x、y は整数です。私のアイデアは、ループを作成することです。ここで、y をインクリメントし (1 から開始)、1 を加算し、2 で割り、平方根を取り、方程式を満たすには整数にする必要があります。これが私がそれを必要とする理由です。

ユーザー入力を整数の形式で受け取るプログラムがあります。それをkと呼びましょう。他に a、b、c の 3 つの数が知られています。私の仕事は、ax + by + cz = k となるすべての正の整数解 {x,y,z} を見つけることです。a、b、および c が組み込まれているオブジェクトに対して呼び出すメソッドを作成しました。x + y + z が既知の整数 p を超えることはできないという追加の制約があります。

これは、k がやや小さい (<100000) 場合に機能しますが、3 桁を超えると、インタープリターは計算を行うときに数秒間フリーズしますが、最終的には想定どおりに動作します。

私の問題は、k が大きい場合、チェックする必要がある組み合わせの量が多すぎて、Python インタープリターで処理できないことです。

したがって、これらのクラッシュを回避する方法は、プログラムがすべてのソリューションを見つけて一度に追加するのではなく、プログラムに各ソリューションを見つけてリストボックスに1つずつ追加することだと考えていました。コンピュータが使用前に RAM に多くの情報を保存するのを避けるため。ただし、 tkinters .insert メソッドがリストボックスに情報を追加する唯一の方法のように見えるため、これを行う方法がわかりません。

どんな助けでも大歓迎です！