/ 
Time Limit: 0 msec / Memory Limit: 0 KiB
キーポイント
- ループ構文の中にさらにループ構文があるものを多重ループと呼ぶ
- 多重ループを一度に抜けたい場合は、フラグ変数を用意してそれぞれのループを抜けるようにする必要がある
多重ループ
ループの中でループすることもできます。
int main() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cout << "i:" << i << ", j:" << j << endl;
}
}
}
実行結果
i:0, j:0 i:0, j:1 i:0, j:2 i:1, j:0 i:1, j:1 i:1, j:2 i:2, j:0 i:2, j:1 i:2, j:2
このように、ループの内側にループがある物のことを二重ループと言います。
当然三重ループや四重ループもあります。それらをまとめて多重ループと呼びます。
#include <bits/stdc++.h>
using namespace std;
int main() {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
cout << "i:" << i << ", j:" << j << ", k:" << k << endl;
}
}
}
}
実行結果
i:0, j:0, k:0 i:0, j:0, k:1 i:0, j:1, k:0 i:0, j:1, k:1 i:1, j:0, k:0 i:1, j:0, k:1 i:1, j:1, k:0 i:1, j:1, k:1
二重ループを使って次の問題を問いてみましょう。
例題「3要素の2つの配列A, Bに同じ要素が含まれているかどうか判定する」
次のプログラムをベースに説明していきます。
今回は「存在するかどうか」のYES/NOを判定する問題なので、答えはbool型の変数に入れます。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> A(3), B(3);
for (int i = 0; i < 3; i++) {
cin >> A.at(i);
}
for (int i = 0; i < 3; i++) {
cin >> B.at(i);
}
// 答えを保持する変数
bool answer = false;
// ここにプログラムを追記
if (answer) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
「全てのAとBの要素の組み合わせを見て、一致しているものがあるかを調べる」という方針で解くことにしましょう。
入力
1 3 2 4 5 3
実行結果
YES
まず、ループを使わないで書いてみます。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> A(3), B(3);
for (int i = 0; i < 3; i++) {
cin >> A.at(i);
}
for (int i = 0; i < 3; i++) {
cin >> B.at(i);
}
// 答えを保持する変数
bool answer = false;
if (A.at(0) == B.at(0) || A.at(0) == B.at(1) || A.at(0) == B.at(2) ||
A.at(1) == B.at(0) || A.at(1) == B.at(1) || A.at(1) == B.at(2) ||
A.at(2) == B.at(0) || A.at(2) == B.at(1) || A.at(2) == B.at(2)) {
answer = true;
}
if (answer) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
Aに着目してパターン化すると次のような形式になっていることがわかります。
A.at(i) == B.at(0) || A.at(i) == B.at(1) || A.at(i) == B.at(2)
これをループ化してみます。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> A(3), B(3);
for (int i = 0; i < 3; i++) {
cin >> A.at(i);
}
for (int i = 0; i < 3; i++) {
cin >> B.at(i);
}
// 答えを保持する変数
bool answer = false;
for (int i = 0; i < 3; i++) {
if (A.at(i) == B.at(0) || A.at(i) == B.at(1) || A.at(i) == B.at(2)) {
answer = true;
}
}
if (answer) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
次はBに着目してパターン化します。
A.at(i) == B.at(j)
最終的なプログラムは次のようになります。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> A(3), B(3);
for (int i = 0; i < 3; i++) {
cin >> A.at(i);
}
for (int i = 0; i < 3; i++) {
cin >> B.at(i);
}
// 答えを保持する変数
bool answer = false;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (A.at(i) == B.at(j)) {
answer = true;
}
}
}
if (answer) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
このプログラムの添字の動きを追ってみましょう。
慣れてきたらループ処理を一つ一つ追っていくことはほとんど無くなりますが、慣れないうちは添字がどのように動くのかをイメージすることが大切です。
多重ループのbreak/continue
for文やwhile文にはbreak/continueという命令がありました。多重ループはループ文の中にループ文を入れた物なので、
通常のfor文と同様にbreak/continue命令を使うことができます。
多重ループでbreak命令を使うと1段階ループを抜けることができます。
内側のループの中でbreakすると内側のループを抜けることができますが、このbreakによって外側のループを抜けることはできません。
for (int i = 0; i < ... ; i++) { // ループ1
for (int j = 0; j < ... ; j++) { // ループ2
if (/* 条件 */) {
break; // (＊)
}
}
// (＊)のbreakでループ2を抜けてここに来る
}
// (＊)のbreakでループ1を抜けてここに来ることはできない
多重ループを抜けるときは、ループを抜けるかどうかを持つ変数(フラグ変数)を用意して、フラグ変数の値に応じてループを抜けるように書きます。
処理の大まかな流れは次の通りです。
bool finished = false; // 外側のループを抜ける条件を満たしているかどうか(フラグ変数)
for (int i = 0; i < ... ; i++) {
for (int j = 0; j < ... ; j++) {
/* 処理 */
if (/* 2重ループを抜ける条件 */) {
finished = true;
break; // (＊)
// finishをtrueにしてからbreakすることで、
// 内側のループを抜けたすぐ後に外側のループも抜けることができる
}
}
// (＊)のbreakでここに来る
if (finished) {
break; // (＊＊)
}
}
// (＊＊)のbreakでここに来る
例
クリックしてサンプルプログラムを開く
#include <bits/stdc++.h>
using namespace std;
int main() {
int sum = 0;
bool finished = false;
for (int i = 0; i < 10 ; i++) {
for (int j = 0; j < 10 ; j++) {
sum += i * j;
if (sum > 1000) {
cout << i << ", " << j << endl;
finished = true;
break;
}
}
if (finished) {
break;
}
}
cout << sum << endl;
}
実行結果
7, 4 1015
他の方法
多重ループの部分を関数化し、関数の内部で使えるreturnを使って一気に抜けるという方法もあります。
void func( /* 処理に必要な変数 */ ) {
for (int i = 0; i < ... ; i++) {
for (int j = 0; j < ... ; j++) {
/* 処理 */
if (/* 2重ループを抜ける条件 */) {
return; // 関数のreturnはループに関係なく抜けることができる
}
}
}
}
int main() {
func();
}
この方法ではループ内の処理を行なうために必要な変数を引数で渡す必要があり、 余計な処理が必要になることがあるので、基本的にはフラグ変数を用意する方針で処理するようにしましょう。
例
クリックしてサンプルプログラムを開く
#include <bits/stdc++.h>
using namespace std;
void func() {
int sum = 0;
for (int i = 0; i < 10 ; i++) {
for (int j = 0; j < 10 ; j++) {
sum += i * j;
if (sum > 1000) {
cout << i << ", " << j << endl;
cout << sum << endl;
return;
}
}
}
}
int main() {
func();
}
実行結果
7, 4 1015
注意点
添え字のミス
多重ループを書いているときによくあるミスにforの中の添字ミスがあります。
次のプログラムのどこにミスがあるか考えてみてください。
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; i++) {
cout << "i: " << i << ", j: " << j << endl;
}
}
正解は内側のループの更新処理の部分です。j++とするべきところをi++としてしまっています。
for (int j = 0; j < 3; i++) {
正しくは
for (int j = 0; j < 3; j++) {
添字のミスは発生しやすく、ミスをした時も発見しにくい(コンパイルエラーにならない)ので、気をつけましょう。
多重ループ中のカウンタ変数の名前はi, j, k, l...としていくのが一般的なのでここでもそうしています。しかし、「iとjは形が似ていて間違えやすい」「名前から意図が伝わりにくい」という意見もあります。
もしカウンタ変数に明確な意味がある場合は、i, j, k, l...にこだわらず、自由に名前を付けるのも良いでしょう。
問題
リンク先の問題を解いてください。