第22回【Python】お金の支払い、二重ループ：活用編 三角形の探索

現在取り組んでいるのは、paiza ラーニング問題集「二重ループメニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 22 回目です。

自信をもってコレだ、と書いたプログラムで特殊データでテストを実施するとエラーが発生しています。それに合わせて修正したら、通常のデータでエラーを吐きました。何に対してガッカリすればいいのかわからずに、なんかガッカリしています。

それでは、今日も頑張ってみようと思います。

お金の支払い

paiza国では、1 円と X 円と Y 円の 3 種類の硬貨しかありません。ちょうど Z 円を支払うとき、支払う硬貨の枚数が最小になるように支払ったときの硬貨の枚数を求めてください。ただし、支払う各硬貨の枚数に制限は無いものとします。

こんな国嫌だなぁ。例えば、1 円硬貨と 100 円硬貨と 1000 円硬貨しかなくて、999 円ちょうどを支払おうとすると、100 円硬貨を 9 枚と 1 円硬貨を 99 枚用意しなければいけないんですね。財布が重くなりそうな国で嫌だなぁ。

Python
X,Y,Z = map(int, input().split())

ans = Z

for x in range(Z // X + 1):
    for y in range(Z // Y + 1):
        if x * X + y * Y <= Z:
            one = Z - x * X - y * Y
            if x + y + one < ans:
                ans = x + y + one
print(ans)

最初にやっちゃった誤り。

Python (誤）
X,Y,Z = map(int,input().split())
cnt = 0
cnt += Z // Y
Z %= Y
cnt += Z // X
Z %= X
cnt += Z
print(cnt)

硬貨の最小枚数を求める問題であれば、これで良いのだけれど、それって、5 と 10 の倍数で考えられた硬貨が存在するからできることなんですね。

ダメな例として挙げていただいていますが、1 円硬貨と 7 円硬貨と 16 円硬貨で 21 円の支払いをする場合。

16 円硬貨と 1 円硬貨では、それぞれ 1 枚と 5 枚が必要で、合計 6 枚。
7 円硬貨であれば、3 枚で支払うことが可能。

誤りのプログラムだと、6 枚って数字が出力されちゃいます。

VBA
S = Split(Cells(1, 1), " ")
x = Val(S(0))
y = Val(S(1))
Z = Val(S(2))
ans = Z
For i = 0 To Int(Z / x)
    For j = 0 To Int(Z / y)
        If x * i + y * j <= Z Then
            one = Z - x * i - y * j
            If i + j + one < ans Then
                ans = i + j + one
            End If
        End If
    Next
Next
Debug.Print ans

切り捨てを INT 関数を使ってやっています。Python でいうところのスラッシュ 2 つ（//）と同じです。rounddown とか余計なことをしなくて良いのでスッキリしていて個人的に好き。

二重ループ：活用編 三角形の探索

整数 N が与えられるので、三角形の三辺の長さの和が N であり、全ての辺の長さが整数であるような直角三角形が存在するかどうかを判定してください。なお、直角三角形の斜辺 a と他の二辺 b , c の間には次のような三平方の定理が成り立ちます。

a ^ 2 = b ^ 2 + c ^ 2

・ ヒント
三辺の長さの和が N であるような全ての三角形の三辺 a , b , c の組み合わせのうち、三平方の定理を満たすものが 1 つでもあれば “YES" , それ以外の場合は “NO" が答えとなります。全ての三辺の場合を全列挙することができれば三平方の定理を満たすかの判定をすることで答えを求めることができます。

N の条件が 3 <= N <= 1000 なので、全通り試すことで求められそう。

Python
N = int(input())
flg = False
for a in range(1,N):
    for b in range(1,N-a):
        c = N - a - b
        if a**2 == b**2 + c**2:
            flg = True
            break
    if flg:
        break
if flg:
    print("YES")
else:
    print("NO")

「三平方の定理を満たすものが 1 つでもあれば」という条件なので、見つかった時点で for 文を抜ける。一番わかりやすいフラグを利用した。最近は、次のような抜け方を模索したりしている。

Python (別解)
N = int(input())
for a in range(1,N):
    for b in range(1,N-a):
        c = N - a - b
        if a**2 == b**2 + c**2:
            print("YES")
            break
    else:
        continue
    break
else:
    print("NO")

なんか美しくて好き。しかし、Python に慣れていない人からは、よくわからないと言われてしまう。

VBA
N = Cells(1, 1)
For A = 1 To N
    For B = 1 To N - A
        c = N - A - B
        If A ^ 2 = B ^ 2 + c ^ 2 Then
            flg = True
            Exit For
        End If
    Next
    If flg Then Exit For
Next
If flg Then
    Debug.Print "YES"
Else
    Debug.Print "NO"
End If

条件 N を 999 にしてみると、少し動きがもったりした気がした。

最後に

「ループメニュー 1」「ループメニュー 2」ときて「二重ループメニュー」と 3 つめのメニューを終えることができました。元々ループは嫌いじゃないので、というか、コンピューターを利用した総当たり戦で答えを探るのは面白いと思っているので、楽しくやってこれました。

スパコンで素数を探すのだって、やっていることは結局同じ。

次は「配列メニュー」に挑戦してみよう。

引き続き、お付き合いよろしくお願いいたします！

Pythonpaiza,学習,Python

Posted by LeoSaki