本サイトAIZU ONLINE JUDGE ITP1_7_B へはこちらから
問題：組み合わせの数
1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。
例えば、1 から 5 までの数から３つを選んでそれらの合計が 9 となる組み合わせは、
- 1 + 3 + 5 = 9
- 2 + 3 + 4 = 9
の２通りがあります。
Input
複数のデータセットが入力として与えられます。各データセットでは、空白で区切られた n、x が 1 行に与えられます。
n、x がともに 0 のとき入力の終わりとします。
Output
各データセットについて、組み合わせの数を１行に出力して下さい。
Sample Input
5 9
0 0Sample Output
2解答例
while True:
n, x = map(int, input().split())
if n == 0 and x == 0:
break
cnt = 0
for i in range(1, n-1):
for j in range(i+1, n):
if j < x - i - j <= n:
cnt += 1
print(cnt)別解
while True:
n, x = map(int, input().split())
if n == 0 and x == 0:
break
cnt = 0
for i in range(1, n+1):
for j in range(i+1, n+1):
for k in range(j+1, n+1):
if i + j + k == x:
cnt += 1
print(cnt)解説
以下のように解いていきます。
while文を使用し、入力処理を行う
ある条件まで入力を続ける場合はwhile文とif文を組み合わせて、入力処理を行います。
# if文の条件式に当てはまるまでループ処理を続ける
while True:
処理
# この条件式に当てはまる場合、break文でループ処理を終了する
if 条件式:
break今回は、whileループ内でmap関数でn、x に2つの整数を設定し、n、x が全て -1の場合にbreak文で処理を終了します。
# 終了条件に当てはまるまで処理を続ける
while True:
# input().split()で複数個の文字列を取得 → int関数に当てはめint型に変換 → n, xに設定
n, x = map(int, input().split())
# n, xともに0の場合にbreak文で処理を終了
if n == 0 and x == 0:
break※サイト内「AIZU ONLINE JUDGE ITP1_1_Cをpythonで解いてみた」の、map関数とはにmap関数の使用方法が書かれておりますのでぜひご覧ください。
組み合わせのパターンの計算と表示
今回は少し数学的な考え方が含まれる問題です。1からnまでの数のなかから重複無しで3つの数を足してxにすることを考えます。例えば1から5までの数から9をつくるとします。このとき、1+3+5と3+5+1は同じ数字の組み合わせなので同一の組み合わせとみなします。このような組み合わせを複数回数えることがないように、「次に選ぶ数は必ず前に選んだ数よりも大きい」というルールのもとで選んでいくことにします。
はじめに外側のfor文で1からn-1までを選びiの設定します、重複が発生しないように内側のfor文ではそれより大きいi+1からnを選びjに設定します。あとは3つ目の数字にあたるx-i-jがjよりも大きくn以下であれば3つの値が指定された範囲内で重複せず、組み合わせを作成できます。
cnt = 0
# 1からn-1までをiに設定
for i in range(1, n-1):
# i+1からnまでをjに設定
for j in range(i+1, n):
# 3つ目の数字(x-i-j)がjより大きいとi,jと重複せず、nより小さいという条件を満たす
if j < x-i-j <= n:
# 条件を満たす場合にカウント
cnt += 1
print(cnt)例である1から5(n)までの数から9(x)をつくる場合のイメージは以下です。
i,j,-
1,2,6 # j(2) < x(9)-i(1)-j(2) <= n(5) が成立しないのでカウントされない
1,3,5 # j(3) < x(9)-i(1)-j(3) <= n(5) が成立するのでカウント
1,4,4 # j(4) < x(9)-i(1)-j(4) <= n(5) が成立しないのでカウントされない
2,3,4 # j(3) < x(9)-i(1)-j(3) <= n(5) が成立するのでカウント
2,4,3 # j(4) < x(9)-i(1)-j(4) <= n(5) が成立しないのでカウントされない
3,4,2 # j(4) < x(9)-i(1)-j(4) <= n(5) が成立しないのでカウントされない
1,3,5と2,3,4の2通りがカウントされる別解について
入力は解答例と同様です。組み合わせのパターンの計算と表示ではfor文を3つ使用し、for文のイテラブルのrange関数の開始値を1ずつずらして設定します。
i,j,kそれぞれの変数に設定された値の合計値がxと同じか比較し、条件を満たす場合にカウントします。
cnt = 0
# 1からn+1までをiに設定
for i in range(1, n+1):
# i+1からn+1までをjに設定
for j in range(i+1, n+1):
# j+1からn+1までをkに設定
for k in range(j+1, n+1):
# 3つの数字がxの場合
if i + j + k == x:
# 条件を満たす場合にカウント
cnt += 1
print(cnt)例である1から5(n)までの数から9(x)をつくる場合のイメージは以下です。
i,j,k
1,2,3 # 合計値が9ではないのでカウントされない
1,2,4 # 合計値が9ではないのでカウントされない
1,2,5 # 合計値が9ではないのでカウントされない
1,3,4 # 合計値が9ではないのでカウントされない
1,3,5 # 合計値が9なのでカウント
1,4,5 # 合計値が9ではないのでカウントされない
2,3,4 # 合計値が9なのでカウント
2,3,5 # 合計値が9ではないのでカウントされない
2,4,5 # 合計値が9ではないのでカウントされない
3,4,5 # 合計値が9ではないのでカウントされない
1,3,5と2,3,4の2通りがカウントされる最後に、もう一度プログラムを確認してみましょう。
# 終了条件に当てはまるまで処理を続ける
while True:
# input().split()で複数個の文字列を取得 → int関数に当てはめint型に変換 → n, xに設定
n, x = map(int, input().split())
# n, xともに0の場合にbreak文で処理を終了
if n == 0 and x == 0:
break
cnt = 0
# 1からn-1までをiに設定
for i in range(1, n-1):
# i+1からnまでをjに設定
for j in range(i+1, n):
# 3つ目の数字(x-i-j)がjより大きいとi,jと重複せず、nより小さいという条件を満たす
if j < x-i-j <= n:
# 条件を満たす場合にカウント
cnt += 1
print(cnt)別解は以下です。
# 終了条件に当てはまるまで処理を続ける
while True:
# input().split()で複数個の文字列を取得 → int関数に当てはめint型に変換 → n, xに設定
n, x = map(int, input().split())
# n, xともに0の場合にbreak文で処理を終了
if n == 0 and x == 0:
break
cnt = 0
# 1からn+1までをiに設定
for i in range(1, n+1):
# i+1からn+1までをjに設定
for j in range(i+1, n+1):
# j+1からn+1までをkに設定
for k in range(j+1, n+1):
# 3つの数字がxの場合
if i + j + k == x:
# 条件を満たす場合にカウント
cnt += 1
print(cnt)
コメント