4

私は自分自身を自己学習するために、プログラミングの練習のためにプロジェクトオイラーの質問をしています。私は、質問を数学的に行う方法と、プログラムで行う方法を完全によく知っています。

しかし、私はそれを行うためにいくつかの非常識なコードを考え出す必要があります。100個のネストされたループとPythonは、このエラーを陽気に発生させます。おそらく当然のことながら、100レベルのインデントで発生します。

IndentationError: too many levels of indentation



tally = 0
ceiling = 100
for integer_1 in range(0, 100, 1):
    for integer_2 in range(0, 100 - integer_1, 2):
        for integer_3 in range(0, 100 - integer_1 - integer_2, 3):
            for integer_4 ....
                for integer_5 ....
                    etc.
                        etc.
                            all the way to integer_100

私は解決策をグーグルで調べましたが、この問題は非常にまれであり、この主題に関する文献はほとんどなく、この他のスタックオーバーフローの質問（Python IndentationError：インデントのレベルが多すぎます）を見つけることができましたが、私の質問。

私の質問は-私の解決策を取り、いくつかの回避策を見つけるか、それが機能する方法でそれをリファクタリングする方法はありますか？私は本当に困惑しています。

編集：

nneonneoの答えのおかげで、私は質問を解決することができました。私のコードは、コードを適切にリファクタリングする方法を探している人々の将来の参照のためにここにあります。

from time import time
t = time()
count_rec_dict = {}

# for finding ways to sum to 100
def count_rec(cursum, level):
    global count_rec_dict

    # 99 is the last integer that we could be using,
    # so prevent the algorithm from going further. 
    if level == 99:
        if cursum == 100:
            return 1
        else:
            return 0

    res = 0

    for i in xrange(0, 101-cursum, level+1):

        # fetch branch value from the dictionary
        if (cursum+i, level+1) in count_rec_dict:
            res += count_rec_dict[(cursum+i, level+1)]

        # add branch value to the dictionary
        else:
            count_rec_dict[(cursum+i, level+1)] = count_rec(cursum+i, level+1)
            res += count_rec_dict[(cursum+i, level+1)]        

    return res}

print count_rec(0, 0)
print time() - t

これは私のコンピューターでは驚くべき0.041秒で実行されます。おお！！！！！今日は新しいことを学びました！

4

4 に答える 4

5

この種の操作を必要としない問題には、まったく異なる解決策があると確信していますが、再帰的な解決策はうまくいくはずです。

def count_rec(cursum, level):
    if level == 100:
        return 1
    res = 0
    for i in xrange(0, 100-cursum, level+1):
        res += count_rec(cursum+i, level+1)
    return res

print count_rec(0, 0)

興味深いことに、この関数をメモ化すると、実際には妥当な実行時間が得られます（これが動的計画法の力です）。楽しむ！

于 2012-09-26T00:08:30.050 に答える
1

インデントエラーを回避する1つの方法は、ループを別々の関数に配置し、各関数を1レベルだけネストすることです。

または、再帰を使用して、範囲を狭くし、ネストレベルを高くして、関数を何度も呼び出すこともできます。

そうは言っても、どのようにコーディングしても、アルゴリズムの実行時間は非常に長くなります。より良いアルゴリズムが必要です:-)

于 2012-09-26T00:12:34.493 に答える
1

アルゴリズムを正確に使用してこれを行うには（次の各数値を必要な合計に収まる可能性のある数値に制限する）、実際には再帰が必要ですが、真のブルートフォース方式はワンライナーにすることができます。

sum(sum(i) == 100 for i in itertools.product(xrange(100), repeat=100))

当然、これはアルゴリズムの実際のリファクタリングよりもかなり遅くなります（実際、コメントで述べられているように、それは手に負えないことがわかります）。

于 2012-09-26T00:36:50.567 に答える
0

最も効果的な解決策は、算術演算のアイデアに基づいています。最大値とステップのリスト、および現在の値のリストがあります。これらの100個の変数を更新するたびに、次のようにします。

inc_index = -1
currentvalue[inc_index] += stepval[inc_index]
# I use >= rather than > here to replicate range()s behaviour that range(0,100) generates numbers from 0 to 99.
while currentvalue[inc_index] >= maxval[inc_index]:
    currentvalue[inc_index] = 0
    inc_index -= 1
    currentvalue[inc_index] += stepval[inc_index]
# now regenerate maxes for all subordinate indices
while inc_index < -1:
    maxval[inc_index + 1] = 100 - sum (currentvalue[:inc_index])
    inc_index += 1

IndexErrorが発生すると、ループが終了します（実行する「桁数」が不足します）。

于 2012-09-26T01:29:26.740 に答える