Aizu Online Judge（AOJ）が提供している「プログラミング入門」（ITP1）の5_D問題をC++とPython で解いてみました。
ITP1 のトピック5では、構造化プログラムについて学びます。「制御構造や文を組み合わせる構造化プログラミングの基礎を身に付けます。」とあります。この学習コースを通じて、Python に慣れていきたいと考えています。
問題（5_D: Structured Programming）
問題はリンク先をご覧ください。
AOJ ITP1 5_D問題:Structured Programming
分かりにくいコードを分かりやすく書き直す問題です。
構造化プログラミングとは
最初に、書き換える元のプログラムを提示します。
void call(int n){
int i = 1;
CHECK_NUM:
int x = i;
if ( x % 3 == 0 ){
cout << " " << i;
goto END_CHECK_NUM;
}
INCLUDE3:
if ( x % 10 == 3 ){
cout << " " << i;
goto END_CHECK_NUM;
}
x /= 10;
if ( x ) goto INCLUDE3;
END_CHECK_NUM:
if ( ++i <= n ) goto CHECK_NUM;
cout << endl;
}読みにくいプログラムだと感じると思います。読みにくい理由は、goto で制御の流れが前後に飛ぶためです。
この問題のタイトルにもなっている「構造化プログラミング（Structured Programming）」とは、プログラムを書くときに以下を意識します。
- プログラムは以下の3つの構成要素から成る。
- 連続（sequence）ー 順番に実行される文の並び
- 選択（selection）ー 文が選択的に実行される
- 反復（iteration）ー 文のグループが複数回実行される
- プログラムは、一つの入り口、一つの出口を持つ制御構造を採用する。
別の言い方をすれば、goto などの制御構造を採用しない、となります。
解答案
元のプログラムを読みやすいプログラムに変換します。
前提として、このプログラムは以下を実行することが読み取れているとします。実はこの意図を読み取るのが難しいのですが、頭の中で繰り返し、プログラムをシミュレーションしてください。
- 1 から与えられた n までの値に対して、以下の操作を行う。
- その数が3で割り切れるなら、1個の空白に続きその数を出力する。次の数を調べる。
- その数が3を含むなら、1個の空白に続きその数を出力する。次の数を調べる。
- 最後に改行を出力する。
C++ プログラム例（ITP1 5_D）
call 関数の goto 文を繰り返し文に変換します。if の条件を再利用するため、while 文に変更しました。ただし、条件式でインクリメントを行うのは分かりにくいため、変数 i のインクリメントは、ループ本体の末尾に置きました。
この書き換えにより goto 文を無くすことができました。多少、読みやすくなったでしょうか。
#include <iostream>
using namespace std;
void call(int n)
{
int i = 1;
while (i <= n) {
if (i % 3 == 0) {
cout << " " << i;
} else {
int x = i;
while (x > 0) {
if (x % 10 == 3) {
cout << " " << i;
break;
} else {
x /= 10;
}
}
}
++i;
}
cout << endl;
}
int main()
{
int n;
cin >> n;
call(n);
return 0;
}この問題の繰り返しは、ループ変数がはっきりしています。そのため、while 文よりも for 文を使ったほうが分かりやすいと思います。以下は、for 文を使ったプログラムです。
#include <iostream>
using namespace std;
void call(int n)
{
for (int i = 1; i <= n; ++i) {
if (i % 3 == 0) {
cout << " " << i;
} else {
int x = i;
while (x > 0) {
if (x % 10 == 3) {
cout << " " << i;
break;
} else {
x /= 10;
}
}
}
}
cout << endl;
}
int main()
{
int n;
cin >> n;
call(n);
return 0;
}指定した数が3を含むか判定する関数 include3 を分けました。C++ 版としては、これを最終版とします。読みやすく改造しやすいプログラムになりました。
#include <iostream>
using namespace std;
bool include3(int n)
{
bool result = false;
while (n > 0) {
if (n % 10 == 3) {
result = true;
break;
} else {
n /= 10;
}
}
return result;
}
void call(int n)
{
for (int i = 1; i <= n; ++i) {
if ((i % 3 == 0)||(include3(i))) {
cout << " " << i;
}
}
cout << endl;
}
int main()
{
int n;
cin >> n;
call(n);
return 0;
}Python プログラム例（ITP1 5_C）
Python は、指定した数が3を含むか簡単に判定できます（文字列に変換して、”3″ の個数をカウントする）。そのため、call 関数だけでプログラムしました。
冒頭で提示したプログラムと比較すると、非常に読みやすく書けていることが分かります。
def call(n):
for i in range(1, n + 1):
if i % 3 == 0 or str(i).count("3") >= 1:
print(f" {i}", end="")
print("")
call(int(input()))上記プログラムは、すべて AOJ で「AC（Accepted＝正解）」と判定されます。
最後に
いつもの問題と違い、与えられたプログラムを分かりやすく書き換える、という問題でした。現実のソフトウェア開発では、最初からコーディングする場合よりも、元にあるプログラムを修正する場合の方が多くなります。
そのため、プログラムは、書くよりも読む頻度の方が多くなります。趣味のプログラミングだとしても、分かりやすく書くことを心掛けています。
引き続き、ITP1 の問題を紹介していきます。
