任意の数の行を含む等比数列

StackOverflow https://stackoverflow.com/questions/3824530

  •  26-09-2019
  •  | 
  •  

質問

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

例えば：指定された番号の行: 125 5 625 答えを得なければなりません 5. 。行： 128 8 512 答えを得なければなりません 4.

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

ありがとう。

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

皆さん、わかっていないでしょう、単純に割り算をすることはできません。実際には等比数列を取得し、すべての数値を表示する必要があります。で 128 8 512 行すべての数値は次のようになります。 8 32 128 512

役に立ちましたか？

解決

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

等比数列の要素は次の形式で書くことができます。 c*b^n どこ b は探している番号です (b 必ず 1 より大きくなります)、 c は定数であり、 n は任意の数値です。

したがって、最善の策は、最小の数値から始めて因数分解し、それを次の形式で記述するための可能なすべての解決策を検討することです。 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, 、それでうまくいきます。

他のヒント

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

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

(1) 数値の集合を並べ替えます。次の形式の番号があります ab^{n1} < .. < ab^{nk}.

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

（２）ソートされたリストの（ｎ＋１）番目の要素のｎ番目の要素を（ｎ）番目で割った新しいリストを形成する。あなたは今持っています 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). 。肝心なのは「本物」の力です b ステップ (2) のリスト内のすべてのエントリを分割するのが正解です。したがって、上げることができます 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 整数でなくてもよい。これに問題がある場合はお知らせください。

最も簡単なアプローチは、数値を因数分解して、共通する最大の数値を見つけることです。ただし、因数分解は指数関数的な複雑さがあるため、行に大きな数値が含まれる場合は機能しなくなる可能性があることに注意してください。

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

1 つの方法は、行内の小さい方の数値ですべてを除算できるかどうかを確認することです。

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

次に、すべてを割る数が見つかるか、約数が 1 に等しくなるまで下に進み続けます。

セスの答え は正しくありません。その解決策を適用しても解決しません 128 8 2048 たとえば行 (2*4^x) の場合、次のようになります。8 128 2048 => 16 16 => GCD = 16

確かに、解がこの結果の因数であることは事実ですが、それを因数分解して何が正しい答えであるかを 1 つずつ確認する必要があります。この場合、解の因数を逆の順序で確認する必要があります。 16, 8, 4, 2 4 がすべての条件に一致するまで続けます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top