【python】ジュニア数学オリンピックの問題を力づくで解いてみる(2016年度 – 問8)


問題

各桁の数字に1個もダブりがない37の倍数のうち最大値を答えよ。


僕の感想

解放が全く頭に浮かばん…。

総当たりしよう…。←

よし、プログラム書くぞ!←


実際のプログラム

文字通り総当たりして見たら、ものすごく遅かったです。笑

不安になりすぎて途中でPrintはさみました。笑

まあ、そりゃそうですよね。

欲しいのって配列の一番最後なので、それまでの計算ってぶっちゃけ無駄じゃないですか?

力づくにもほどがありました…。

ちなみに各桁にダブりがない最大値は「9876543210」になるので、必然的に解はそれ以下の数字になると思っています。

MAX_POSSIBLE_NUM = 9876543210
GIVEN_NUM = 37

valid_num = []
num = 0;

while num * GIVEN_NUM <= MAX_POSSIBLE_NUM:
    result = num * GIVEN_NUM
    str_result = str(result)

    if str_result.count("0") == 1 & str_result.count("1") == 1 & str_result.count("2") == 1 & str_result.count("3") == 1 & str_result.count("4") == 1 & str_result.count("5") == 1 & str_result.count("6") == 1 & str_result.count("7") == 1 & str_result.count("8") == 1 & str_result.count("9") == 1:
        valid_num.append(result)

    print(str_result)
    num = num + 1

print("------- Answer -------")
print(valid_num[-1])

せめて、もう少しまともな回答にするために、後ろから数字を探すことにしました。

9876543210以下が解になるため、9876543210/37した数字を起点にそれ以下の37の倍数の中から各桁にダブりのない数字を探していき、最初に見つかった数字を解とする作戦です。

依然、パワープレイですが、まだマシだと思います。

MAX_POSSIBLE_NUM = 9876543210
GIVEN_NUM = 37

num = MAX_POSSIBLE_NUM / GIVEN_NUM;

while num < 0:
    result = num * GIVEN_NUM
    str_result = str(result)

    if str_result.count("0") == 1 & str_result.count("1") == 1 & str_result.count("2") == 1 & str_result.count("3") == 1 & str_result.count("4") == 1 & str_result.count("5") == 1 & str_result.count("6") == 1 & str_result.count("7") == 1 & str_result.count("8") == 1 & str_result.count("9") == 1:
        print("------- Answer -------")
        print(str_result)
        break

    num = num - 1

こちらはサクッと実行が終わりまして「9876435012」とのことでした。正誤は不明ですが、プログラムが言うのだから間違いないと思っています。


まとめ

このように少し頭を使えばあとは力づくで解を導けるのがプログラミングの便利なところだと思っています。

もちろん、母数となるデータが増えたり、計算のロジックが複雑になればなるほど、数学的素養が必要になり、より効率のよりロジックを組んでいく必要があるのですが、解放が思いつかない時にコンピューターの計算力を拝借できると便利ではないでしょうか?

ちなみにもっと良い解法をご存知の方がいらっしゃいましたら、是非コメント欄で教えてください…。


最後まで読んでいただきありがとうございます。もしこの記事を気に入って頂けたようであればシェアをお願い致します。非常に励みになります。


コメントを残す