4

2 から 10 の数字で構成される任意の数字行を使用できます。そして、この行から等比級数を取得する必要があります。

例: 与えられた番号の行: 125 5 625I have to get answer 5. 行:128 8 512私は答えを得る必要があります4.

手伝って頂けますか？私はプログラムを求めているのではなく、ヒントだけを求めています。それを自分で理解し、自分でコードを書きたいのですが、くそー、私は一日中考えていて、これを理解できませんでした。

ありがとうございました。

プログラム全体を書かないでください!

みんな、あなたはそれを理解していません、私は単純に分割することはできません. 私は実際に等比級数を取得し、すべての数字を表示する必要があります。行では128 8 512、すべての数字は次のようになります。8 32 128 512

4

5 に答える 5

4

セスの答えは正しいものです。人々がそれに問題を抱えているように見えるため、なぜ答えが得られるのかを詳しく説明するために、この答えをここに残しておきます128 8 512。4

等比数列の要素は、 は探している数 (も必ず 1 より大きい)、は定数、任意の数の形式c*b^nで記述できます。bbcn

したがって、最善の策は、最小の数から始めて、それを因数分解しc*b^n、それをフォームに書き込むためのすべての可能な解決策を調べてから、それをb残りの数に使用することです。機能する最大の結果を返します。

だからあなたの例のために：

125 5 625

5 から始めます。5 は素数なので、次の 1 つの方法でのみ記述できます5 = 1*5^1。したがって、あなたbは 5 です。行が実際に幾何学的であることがわかっていると仮定すると、ここで停止できます。それが幾何学的かどうかを判断する必要がある場合はb、残りの数値でテストします。

128 8 512

8複数の方法で書くことができます: 8 = 1*8^1, 8 = 2*2^2, 8 = 2*4^1, 8 = 4*2^1. したがって、 には 3 つの可能な値がbあり、 にはいくつかの異なるオプションがありますc。最初に最大のものを試してください。8動作しません。試してみてください4。できます！128 = 2*4^3と512 = 2*4^4。そうbです。4_ c_2

3 15 375

これは、最初の数が素数であるが ではないため、少し意地悪bですc。したがって、最初のb-candidate が残りの数値で機能しない場合は、次に小さい数値を見て分解する必要があることを確認する必要があります。したがって、ここでは 15 を分解します: 15 = 15*?^0(縮退ケース) 15 = 3*5^1, 15 = 5*3^1, 15 = 1*15^1. 答えは 5 で、3 = 3*5^0です。

于 2010-09-29T18:15:55.513 に答える
2

編集：これは今正しいはずだと思います。

このアルゴリズムは、因数分解に依存せず、ユークリッド アルゴリズムとその変形にのみ依存します。これにより、因数分解を使用するソリューションよりも数学的に洗練されたものになりますが、はるかに高速になります。ユークリッド アルゴリズムと対数を理解していれば、数学は問題にならないはずです。

(1) 数字のセットをソートします。の形式の番号がありますab^{n1} < .. < ab^{nk}。

例：(3 * 2, 3*2^5, 3*2^7, 3*2^13)

(2) ソート済みリストの (n+1) 番目の要素の n 番目の要素を (n) 番目の要素で割った新しいリストを作成します。あなたは今持っていb^{n2 - n1}, b^{n3 - n2}, ..., b^{nk - n(k-1)}ます。

(続き) 例:(2^4, 2^2, 2^6)

定義します (これをプログラムしないでください -- プログラムがどのように動作するかを説明するためだけに、プログラムが不明であるd_i = n_(i+1) - n_iため、プログラムしたくてもできませんでした)。n_i

(続き) 例:d_1 = 4, d_2 = 2, d_3 = 6

(a = 3, b = 2)この例の問題では、またはを自由に選択できることに注意してください(a = 3/2, b = 4)。要点は、ステップ (2) からリスト内のすべてのエントリを分割する「実数」の任意の累乗がb正解です。したがってb、すべてを割る任意の累乗d_i(この場合は 4、2、および 6 を割る任意の累乗) に累乗できるということになります。問題は、私たちがどちらbも知らないことd_iです。しかし、 を にすれば、m = gcd(d_1, ... d_(k-1))を見つけることができますb^m。これで十分です。

注: と が与えられるb^iと、以下を使用してb^j見つけることができます。b^gcd(i, j)

log(b^i) / log(b^j) = (i log b) / (j log b) = i/j

これにより、ユークリッド アルゴリズムの修正版を使用して を見つけることができますb^gcd(i, j)。「アクション」はすべて指数にあります。加算は乗算に、乗算はべき乗に、(結果として)商は対数に置き換えられました。

import math
def power_remainder(a, b):
    q = int(math.log(a) / math.log(b))
    return a / (b ** q)        

def power_gcd(a, b):
    while b != 1:
    a, b = b, power_remainder(a, b)
    return a

(3) 元の集合のすべての要素は のべき乗だけ異なるためr = b^gcd(d_1, ..., d_(k-1))、それらはすべて、cr^n必要に応じて の形式です。ただし、c整数ではない場合があります。問題がある場合はお知らせください。

于 2010-09-29T18:41:48.847 に答える
0

最も簡単な方法は、数を因数分解して、それらに共通する最大数を見つけることです。ただし、因数分解は指数関数的に複雑なため、行に大きな数が含まれていると機能しなくなる可能性があることに注意してください。

于 2010-09-29T18:14:03.143 に答える
0

あなたが知りたいのは、連続するすべての数の最大公約数を知ることです。

1 つの方法は、行の小さい方の数ですべて割り切れるかどうかを確認することです。

そうでない場合は、行の小さい方の数字の半分を試してください。

次に、それらをすべて割る数が見つかるか、除数が 1 になるまで、下に移動し続けます。

于 2010-09-29T18:15:10.317 に答える
0

Seth の回答128 8 2048は正しくありません。たとえば (2*4^x) などの行を 解決しないソリューションを適用すると、次のようになります。 8 128 2048=> 16 16=> GCD = 16

解がこの結果の要因であることは事実ですが、それを因数分解して、正しい答えを 1 つずつ確認する必要があります。この場合、16, 8, 4, 24 つのすべてが一致するまで、逆の順序で解の要因を確認する必要があります。状況、契約条項。

于 2010-09-29T22:00:03.393 に答える