S - 2.02.多重ループ Editorial

Time Limit: 0 msec / Memory Limit: 0 KB

前のページ | 次のページ

キーポイント

  • ループ構文の中にさらにループ構文があるものを多重ループと呼ぶ
  • 多重ループを一度に抜けたい場合は、フラグ変数を用意してそれぞれのループを抜けるようにする必要がある

多重ループ

ループの中でループすることもできます。

Copy
  1. int main() {
  2.   for (int i = 0; i < 3; i++) {
  3.     for (int j = 0; j < 3; j++) {
  4.       cout << "i:" << i << ", j:" << j << endl;
  5.     }
  6.   }
  7. }
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

このように、ループの内側にループがある物のことを二重ループと言います。
当然三重ループや四重ループもあります。それらをまとめて多重ループと呼びます。

Copy
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.   for (int i = 0; i < 2; i++) {
  6.     for (int j = 0; j < 2; j++) {
  7.       for (int k = 0; k < 2; k++) {
  8.         cout << "i:" << i << ", j:" << j << ", k:" << k << endl;
  9.       }
  10.     }
  11.   }
  12. }
#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型の変数に入れます。

Copy
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.   vector<int> A(3), B(3);
  6.   for (int i = 0; i < 3; i++) {
  7.     cin >> A.at(i);
  8.   }
  9.   for (int i = 0; i < 3; i++) {
  10.     cin >> B.at(i);
  11.   }
  12.  
  13.   // 答えを保持する変数
  14.   bool answer = false;
  15.  
  16.   // ここにプログラムを追記
  17.  
  18.   if (answer) {
  19.     cout << "YES" << endl;
  20.   }
  21.   else {
  22.     cout << "NO" << endl;
  23.   }
  24. }
#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

まず、ループを使わないで書いてみます。

Copy
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.   vector<int> A(3), B(3);
  6.   for (int i = 0; i < 3; i++) {
  7.     cin >> A.at(i);
  8.   }
  9.   for (int i = 0; i < 3; i++) {
  10.     cin >> B.at(i);
  11.   }
  12.  
  13.   // 答えを保持する変数
  14.   bool answer = false;
  15.  
  16.   if (A.at(0) == B.at(0) || A.at(0) == B.at(1) || A.at(0) == B.at(2) ||
  17.      A.at(1) == B.at(0) || A.at(1) == B.at(1) || A.at(1) == B.at(2) ||
  18.      A.at(2) == B.at(0) || A.at(2) == B.at(1) || A.at(2) == B.at(2)) {
  19.     answer = true;
  20.   }
  21.  
  22.   if (answer) {
  23.     cout << "YES" << endl;
  24.   }
  25.   else {
  26.     cout << "NO" << endl;
  27.   }
  28. }
#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に着目してパターン化すると次のような形式になっていることがわかります。

Copy
A.at(i) == B.at(0) || A.at(i) == B.at(1) || A.at(i) == B.at(2)
A.at(i) == B.at(0) || A.at(i) == B.at(1) || A.at(i) == B.at(2)

これをループ化してみます。

Copy
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.   vector<int> A(3), B(3);
  6.   for (int i = 0; i < 3; i++) {
  7.     cin >> A.at(i);
  8.   }
  9.   for (int i = 0; i < 3; i++) {
  10.     cin >> B.at(i);
  11.   }
  12.  
  13.   // 答えを保持する変数
  14.   bool answer = false;
  15.  
  16.   for (int i = 0; i < 3; i++) {
  17.  
  18.     if (A.at(i) == B.at(0) || A.at(i) == B.at(1) || A.at(i) == B.at(2)) {
  19.       answer = true;
  20.     }
  21.  
  22.   }
  23.  
  24.   if (answer) {
  25.     cout << "YES" << endl;
  26.   }
  27.   else {
  28.     cout << "NO" << endl;
  29.   }
  30. }
#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に着目してパターン化します。

Copy
A.at(i) == B.at(j)
A.at(i) == B.at(j)

最終的なプログラムは次のようになります。

Copy
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.   vector<int> A(3), B(3);
  6.   for (int i = 0; i < 3; i++) {
  7.     cin >> A.at(i);
  8.   }
  9.   for (int i = 0; i < 3; i++) {
  10.     cin >> B.at(i);
  11.   }
  12.  
  13.   // 答えを保持する変数
  14.   bool answer = false;
  15.  
  16.   for (int i = 0; i < 3; i++) {
  17.     for (int j = 0; j < 3; j++) {
  18.       if (A.at(i) == B.at(j)) {
  19.         answer = true;
  20.       }
  21.     }
  22.   }
  23.  
  24.   if (answer) {
  25.     cout << "YES" << endl;
  26.   }
  27.   else {
  28.     cout << "NO" << endl;
  29.   }
  30. }
#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によって外側のループを抜けることはできません。

Copy
  for (int i = 0; i < ... ; i++) {  // ループ1
    for (int j = 0; j < ... ; j++) {  // ループ2
      if (/* 条件 */) {
        break;  // (＊)
      }
    }
    // (＊)のbreakでループ2を抜けてここに来る
  }
  // (＊)のbreakでループ1を抜けてここに来ることはできない
  for (int i = 0; i < ... ; i++) {  // ループ1
    for (int j = 0; j < ... ; j++) {  // ループ2
      if (/* 条件 */) {
        break;  // (＊)
      }
    }
    // (＊)のbreakでループ2を抜けてここに来る
  }
  // (＊)のbreakでループ1を抜けてここに来ることはできない

多重ループを抜けるときは、ループを抜けるかどうかを持つ変数(フラグ変数)を用意して、フラグ変数の値に応じてループを抜けるように書きます。

処理の大まかな流れは次の通りです。

Copy
  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でここに来る
  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でここに来る

例

クリックしてサンプルプログラムを開く

Copy
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.   int sum = 0;
  6.   bool finished = false;
  7.  
  8.   for (int i = 0; i < 10 ; i++) {
  9.     for (int j = 0; j < 10 ; j++) {
  10.  
  11.       sum += i * j;
  12.  
  13.       if (sum > 1000) {
  14.         cout << i << ", " << j << endl;
  15.         finished = true;
  16.         break;
  17.       }
  18.     }
  19.  
  20.     if (finished) {
  21.       break;
  22.     }
  23.   }
  24.  
  25.   cout << sum << endl;
  26. }
#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を使って一気に抜けるという方法もあります。

Copy
void func( /* 処理に必要な変数 */ ) {
  for (int i = 0; i < ... ; i++) {
    for (int j = 0; j < ... ; j++) {

      /* 処理 */

      if (/* 2重ループを抜ける条件 */) {
        return;  // 関数のreturnはループに関係なく抜けることができる
      }
    }
  }
}

int main() {
  func();
}
void func( /* 処理に必要な変数 */ ) {
  for (int i = 0; i < ... ; i++) {
    for (int j = 0; j < ... ; j++) {

      /* 処理 */

      if (/* 2重ループを抜ける条件 */) {
        return;  // 関数のreturnはループに関係なく抜けることができる
      }
    }
  }
}

int main() {
  func();
}

この方法ではループ内の処理を行なうために必要な変数を引数で渡す必要があり、 余計な処理が必要になることがあるので、基本的にはフラグ変数を用意する方針で処理するようにしましょう。

例

クリックしてサンプルプログラムを開く

Copy
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void func() {
  5.   int sum = 0;
  6.   for (int i = 0; i < 10 ; i++) {
  7.     for (int j = 0; j < 10 ; j++) {
  8.  
  9.       sum += i * j;
  10.  
  11.       if (sum > 1000) {
  12.         cout << i << ", " << j << endl;
  13.         cout << sum << endl;
  14.         return;
  15.       }
  16.     }
  17.   }
  18. }
  19. int main() {
  20.   func();
  21. }
#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の中の添字ミスがあります。
次のプログラムのどこにミスがあるか考えてみてください。

Copy
for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; i++) {
    cout << "i: " << i << ", j: " << j << endl;
  }
}
for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; i++) {
    cout << "i: " << i << ", j: " << j << endl;
  }
}

正解は内側のループの更新処理の部分です。j++とするべきところをi++としてしまっています。

Copy
  for (int j = 0; j < 3; i++) {
  for (int j = 0; j < 3; i++) {

正しくは

Copy
  for (int j = 0; j < 3; j++) {
  for (int j = 0; j < 3; j++) {

添字のミスは発生しやすく、ミスをした時も発見しにくい(コンパイルエラーにならない)ので、気をつけましょう。

多重ループ中のカウンタ変数の名前はi, j, k, l...としていくのが一般的なのでここでもそうしています。しかし、「iとjは形が似ていて間違えやすい」「名前から意図が伝わりにくい」という意見もあります。
もしカウンタ変数に明確な意味がある場合は、i, j, k, l...にこだわらず、自由に名前を付けるのも良いでしょう。

問題

リンク先の問題を解いてください。

EX17.果物屋さんでお買い物

前のページ | 次のページ

2025-04-05 (Sat)
02:11:58 +00:00