1

整数の配列A[i]（i> 1）は、次のように定義されます。要素A [k]（k> 1）は、A [k-1]より大きい最小の数値であり、その桁の合計は次のようになります。は、数値4 *A[k-1]の桁の合計に等しくなります。

指定された最初の要素A[1]に基づいて、この配列のN番目の数を計算するプログラムを作成する必要があります。

入力：標準入力の1行には、A [1]（1 <= A [1] <= 100）とN（1 <= N <= 10000）の2つの数字が1つのスペースで区切られています。

出力：標準出力には、定義されたシーケンスのN番目の数値である単一の整数A[N]のみが含まれている必要があります。

入力：7 4

出力：79

説明：配列の要素は次のとおりです：7、19、49、79...そして4番目の要素は解です。

与えられた数に対してA[k]がその桁の合計を計算し、問題で述べられているようにA [k-1]より大きい最小の数を見つける別の関数をコーディングしてこれを解決しようとしましたが、成功しませんでした。最初のテストはメモリ制限のために失敗し、2番目のテストは時間制限のために失敗しました、そして今私はこれを解決する方法について考えられる考えがありません。ある友人が再帰を提案しましたが、それを設定する方法がわかりません。

何らかの形で私を助けてくれる人は誰でも書いてください。また、この問題を解決するために再帰/DPを使用することについてのいくつかのアイデアを提案してください。ありがとう。

4

3 に答える 3

1

これは再帰とは関係なく、動的計画法とはほとんど関係ありません。実行可能な最適化を見つけて、十分に高速にする必要があります。ヒントとして、この解決策を理解してください。

http://codepad.org/LkTJEILz

于 2010-03-21T16:10:00.667 に答える
0

かなり再帰的です。

問題の核心は次のとおりです。

digitsum(N) = J を持つ、K より大きい最小の数 N を見つけます。

  • digitsum(K) == J の場合、N = K + 9 が条件を満たすかどうかをテストします。

  • digitsum(K) < J の場合、N は K と 1 の桁だけが異なる可能性があります (digitsum が 9 を超えずに達成できる場合)。

  • それ以外の場合、digitsum(K) <= J の場合、新しい 1 の数字は 9 であり、問​​題は次のように繰り返されます。 *10 + 9".

  • digitsum(K) > J の場合 ???

どの場合でも N <= 4 * K

最初のルールにより 9 -> 18

52 -> 2 番目のルールにより 55

3番目のルールにより99 -> 189、再帰中に最初のルールが使用されます

25 -> 100 には 4 番目のケースが必要です。

他に反例はありますか？

于 2010-03-21T17:34:29.913 に答える
0

これはPythonでの簡単な解決策です。繰り返しのみを使用し、再帰は不要であり、迅速で汚いソリューションであっても非効率的です。

def sumDigits(x):
    sum = 0;
    while(x>0):
        sum += x % 10
        x /= 10
    return sum

def homework(a0, N):
    a = [a0]
    while(len(a) < N):
        nextNum = a[len(a)-1] + 1
        while(sumDigits(nextNum) != sumDigits(4 * a[len(a)-1])):
            nextNum += 1
        a.append(nextNum)
    return a[N-1]

PS。宿題の答えを出すことは本当に想定されていないことはわかっていますが、OPはC ++クラスの紹介にあるようです。おそらくまだpythonを知らないでしょう。うまくいけば、疑似コードのように見えます。また、コードには多くの単純な最適化が欠けているため、そのままでは解決するには遅すぎる可能性があります。

于 2010-03-21T16:54:11.933 に答える