計算が終わりません。

Question

質問内容

書いたコードの計算が終わりません。
何が問題なのでしょうか？
どうぞよろしくお願い致します。

A, B, X = map(int,input().split())

def N_prices(n):
    return(A*n + B*(len(str(n))))

if X <= N_prices(0):
    print('0')

if N_prices(10**9) <= X:
    print('109')

for i in range(1, 10**9):
    if N_prices(i) <=X and X<=N_prices(i+1):
        print(str(i))

環境

python3.7.3, jupyter notebook

Answer 1

for i in range(1, 10**9):
    if N_prices(i) <=X and X<=N_prices(i+1):
        print(str(i))

10**9、つまり上記のコード1000000000回繰り返してるので非常に時間が掛かってると思います。

Comments

[SHS]

こちらはある問題を問いているのですが、10**9と書かれていたので、その数字は変えられないです。

[ChaosRepainter]

そういう時は何らかのアルゴリズムを使って高速化しますね。

[SHS]

なるほど、ではこの問題はそれを使えるのかが肝かもしれないですね

[ChaosRepainter]

その問題についてよく考えれば計算しなくても良いnの値が見つかるはず。
その法則を見つければ何とかなる。

[SHS]

なるほど、もう少し問題を簡単に解けないか考えてみます。

Answer 2

ループ回数を少なくして、何回のときにどれくらいの時間かかるか確かめてみてはいかがですか？
for i in range(1, 10**6)
くらいが待てる限界かと思います。

Comments

[SHS]

かしこまりました、そこから検討してみます。

[SHS]

仰る通り、10**6でしてみました。ですが結果は出るものの計算が終わっていないようでしたのでコードを確認したところ、printしたあとにbreakを書いておりませんでした。breakを書いたら動きが良くなりました。ご指摘いただき、ありがとうございました????‍♀️

Answer 3

10^9回も計算しようとしていますからねえ、一回やるのに1us要するとして1000秒くらいはかかってもおかしくはありません。

かんたんにざっくり見積る方法。

$ python -m timeit '(12345*10111213 + 67890*(len(str(10111213))))'
1000000 loops, best of 3: 0.295 usec per loop

Comments

[SHS]

usについてうかがってもよろしいでしょうか？

[hayataka2049]

マイクロ秒

[SHS]

すみません

[hayataka2049]

謝る必要はないですよ。こちらこそ雑なコメントですみません。

[SHS]

温かいコメントありがとうございます