Aizu Online Judge（AOJ）が提供している「プログラミング入門」（ITP1）の7_B問題をC++とPython で解いてみました。
ITP1 のトピック7では、再び構造化プログラムについて学びます。「繰り返し処理や配列を組み合わせることで、構造化プログラミングの理解を深めます。」とあります。この学習コースを通じて、Python に慣れていきたいと考えています。
問題（7_B: How many ways?）
問題はリンク先をご覧ください。
多重のループを使って問題を解きます。
解答案
C++ プログラム例（ITP1 7_B）
重複無しの組み合わせを求める問題です。
読み込んだ n を組み合わせる数の上限、x を合計の数として、条件を満たす通り数（ans）を、3重ループを使ってカウントします。素朴ですが、正しい実装です。
#include <iostream>
using namespace std;
int main()
{
int n, x;
while (1) {
cin >> n >> x;
if ((n == 0)&&(x == 0)) {
break;
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
for (int k = j + 1; k <= n; ++k) {
if (i + j + k == x) {
++ans;
}
}
}
}
cout << ans << endl;
}
return 0;
}3重ループを使いましたが、2重ループにすることができます。それは、i と j が決まれば、残りの k は、k = x – (i + j) で求めることができます。あとは、k が条件を満たせば、通り数をカウントします。
#include <iostream>
using namespace std;
int main()
{
int n, x;
while (1) {
cin >> n >> x;
if ((n == 0)&&(x == 0)) {
break;
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
int k = x - (i + j);
if ((j < k)&&(k <= n)) {
++ans;
}
}
}
cout << ans << endl;
}
return 0;
}与えられた条件を使って、多重ループのループ数を1段または2段減らすことは、よく使われる効率化の手法です。
Python プログラム例（ITP1 7_B）
Python も、2重ループを使った C++ 版と同じ構造としました。以下が、Python 版のプログラムです。
while True:
n, x = map(int, input().split())
if n == 0 and x == 0:
break
ans = 0
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
k = x - (i + j)
if j < k <= n:
ans += 1
print(ans)上記プログラムは、すべて AOJ で「AC（Accepted＝正解）」と判定されます。
最後に
今回解いた問題は、ループを1段減らすことができる例としてよく紹介されます。応用範囲が広がると、要求を正しく実現するだけではなく効率的に実装することも求められてきます。
引き続き、ITP1 の問題を紹介していきます。
