科目Bの配列の逆順・回転問題の解き方｜入れ替える位置を表で追う

a[n − i + 1] って、結局どこを指しているの？ 毎回指で数えてしまう。

科目Bの問題で、配列を逆順に並べ替えるコードを見たとき、添字の式で手が止まったことはありませんか？

逆順なら最初と最後を入れ替えればいい。頭では分かっているのに、式になった途端に自信がなくなる人は多いのではないでしょうか。

大丈夫です。逆順や回転の問題で必要なのは、入れ替える2つの位置を1回ずつ表に書き出すことと、ループがどこで止まるかを確かめることだけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、新しい順に並んだ一覧を古い順に並べ直したり、担当者を1人ずつずらして当番表を作ったりする処理を何度も書いています。

当番表の処理では、ずらす向きを逆にしてしまい、全員が同じ人の名前になるバグを出しかけたことがあります。気づけたのは、3人分だけの小さな配列で、1回ごとの中身を紙に書き出したからでした。

この記事では、配列の逆順と回転の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中でこうした問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

逆順・回転の問題は何を聞いているのか¶

最初に、逆順と回転がそれぞれ何をする処理なのかを短く押さえておきましょう。どちらも配列の中身を並べ替えるだけで、値そのものは増えも減りもしません。

逆順は、配列の並びを後ろから前へひっくり返す処理です。{3, 8, 5, 1, 9} を逆順にすると {9, 1, 5, 8, 3} になります。

回転は、要素を同じ向きに1つずつずらし、端からあふれた要素を反対側の端へ回す処理です。左へ1つ回転すると、{3, 8, 5, 1, 9} は {8, 5, 1, 9, 3} になります。

科目Bで問われる形¶

試験の擬似言語でこの2つが出るときは、処理の名前よりも、コードの1行1行がどう動くかが問われます。どんな形で聞かれやすいのかを、表に整理しました。

どの形でも、中心にあるのは入れ替える位置とループの回数です。この2つを1回ごとに表へ書ければ、問われ方が変わっても同じ手順で解けます。

挿入・削除の問題との違い¶

配列の要素をずらす処理は、挿入や削除の問題にも出てきます。ただし、挿入や削除では要素の数が変わったり、空いた場所に新しい値が入ったりします。

逆順と回転では、要素の数も値の組み合わせも変わりません。変わるのは並び順だけ、という点を意識しておくと、答えを確かめるときの手がかりになります。

要素をずらして空きを作る処理の書き方そのものは、こちらの記事で詳しく扱っています。

【関連記事】擬似言語の配列への挿入と削除がわからない人へ｜要素をずらす処理の読み方を解説

まず目を付ける場所¶

逆順と回転の違いがつかめたら、次はコードのどこから読むかを決めます。この種の問題では、目を付ける場所が3つあります。

ひとつ目はループの終わりの値、ふたつ目は添字の式、みっつ目は一時変数に値を逃がしている行です。この3か所が分かれば、コード全体が逆順なのか回転なのかがほぼ決まります。

ループの終わりは半分か、全部か¶

逆順のコードでは、ループが配列の長さの半分で止まるのが基本です。5個の配列なら2回、6個の配列なら3回入れ替えれば、全体がひっくり返ります。

なぜ半分なのでしょうか？ 1回の入れ替えで前と後ろの2つが同時に正しい位置へ移るので、全体の半分の回数で足りるからです。

一方、回転のコードでは、ループはほぼ配列の長さぶん回ります。1つずつ隣へずらすので、端から端まで全部の要素に触る必要があるからです。

添字の式は両端で確かめる¶

逆順でよく出るのが、a[i] と a[n − i + 1] を入れ替える形です。n − i + 1 という式は、前から i 番目に対応する、後ろから i 番目の位置を表しています。

式だけ見ても分かりにくいので、両端の値を入れてみましょう。i が 1 なら n − 1 + 1 で n、つまり最後の要素です。

i が 2 なら n − 1 で、後ろから2番目になります。最初と最後の2か所で式が正しい位置を指していれば、間も同じ規則で動くと考えて大丈夫です。

添字そのものの数え方に不安がある場合は、こちらの記事で先に整理しておくと読みやすくなります。

【関連記事】科目Bの配列問題の解き方｜添字を表にして追う方法

一時変数は値の避難場所¶

3つ目に探すのが、tmp や first のような一時変数です。2つの値を入れ替えるときや、端からあふれる値を取っておくときに使われます。

a[i] ← a[j] と書いた瞬間に、もとの a[i] の値は消えてしまいます。そこで、上書きする前に tmp へ逃がしておき、最後に tmp を反対側へ入れるわけです。

一時変数に何を入れているかを見れば、どの値が上書きから守られているのかが分かります。逆順なら毎回の入れ替えで、回転ならループの前後で1回ずつ使うのが典型です。

例題：逆順と左回転のコード¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次の2つの手続は、整数型の配列 a を受け取り、その中身を書き換えます。配列の添字は1から始まるものとします。

○reverse(整数型の配列: a)
  整数型: n ← a の要素数
  整数型: i, tmp
  for (i を 1 から n ÷ 2 の商 まで 1 ずつ増やす)
    tmp ← a[i]
    a[i] ← a[n − i + 1]
    a[n − i + 1] ← tmp
  endfor

○rotateLeft(整数型の配列: a)
  整数型: n ← a の要素数
  整数型: i
  整数型: first ← a[1]
  for (i を 1 から n − 1 まで 1 ずつ増やす)
    a[i] ← a[i + 1]
  endfor
  a[n] ← first

reverse は、前から i 番目と後ろから i 番目を入れ替える処理を、配列の半分の回数だけ繰り返します。rotateLeft は、先頭を first に取っておき、残りを1つずつ左へずらしてから、空いた最後に first を入れます。

では、a が {3, 8, 5, 1, 9} のとき、それぞれを呼び出したあとの中身はどうなるでしょうか？

トレース表で入れ替える位置を追う¶

頭の中だけで入れ替えを繰り返すと、どこまで入れ替えたのかがすぐに分からなくなります。そこで、ループ1回ごとに、入れ替える2つの位置と、終わったあとの配列をトレース表に書きます。

ポイントは、値ではなく位置の列を作ることです。どの添字とどの添字が組になっているかが見えると、式の意味が自然に分かってきます。

まず reverse から追います。n は 5 なので、ループの終わりは 5 ÷ 2 の商で 2 です。

2回でループを抜けて、a は {9, 1, 5, 8, 3} になります。真ん中の3番目の 5 は、自分自身と入れ替える必要がないので、一度も触られません。

要素数が偶数のときも確かめておきましょう。6個なら 6 ÷ 2 の商で3回入れ替え、1と6、2と5、3と4の組がちょうど使い切られます。

左回転は1つずつ追い越さないように追う¶

次に rotateLeft を追います。最初に first へ 3 を取っておき、そのあとループで1つずつ左へずらします。

途中で同じ値が2つ並ぶ瞬間がありますが、これは正常です。右隣の値で上書きしたあと、次の回でその右隣がさらに右の値で上書きされるので、最後には重複が消えます。

最終的な a は {8, 5, 1, 9, 3} です。先頭にあった 3 が、first のおかげで最後に回り込んでいることが確かめられます。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

右回転はループの向きが逆になる¶

右へ1つ回転させるときは、最後の要素を取っておき、後ろから前へ向かってずらします。i を n から 2 まで1ずつ減らしながら、a[i] ← a[i − 1] を繰り返し、最後に a[1] へ取っておいた値を入れます。

ここで、前から順にずらしてしまうとどうなるでしょうか？ a[2] ← a[1] で 3 が入り、次の a[3] ← a[2] でもまた 3 が入り、2番目以降がすべて 3 で埋まってしまいます。

冒頭でお話しした当番表のバグが、まさにこれでした。ずらす向きと、ループが進む向きを逆にする。これが、値を追い越さずにずらすための決まりです。

k個まとめて回転する書き方¶

科目Bでは、1つではなく k 個まとめて回転させるコードが出ることもあります。よく使われるのが、新しい配列 b を用意して、余りの計算で行き先を決める書き方です。

右へ k 個回転するなら、a[i] の行き先は ((i − 1 + k) mod n) + 1 番目になります。1を引いてから余りを取り、最後に1を足すのは、1始まりの添字を0始まりに直して計算し、また戻すためです。

i が 5、k が 2、n が 5 なら、(4 + 2) mod 5 + 1 で 2 番目に行きます。後ろからあふれた要素が前へ回り込む様子を、余りが表しているわけです。

間違いやすい選択肢の見分け方¶

逆順と回転の問題では、式やループの範囲を少しだけ変えた選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

よくある誤りを表にまとめました。

この中でも、特によく狙われるのがループの範囲と相手の位置の式です。順番に見ていきましょう。

ループの範囲は全部回して試す¶

逆順のループを n まで回す選択肢は、一見すると丁寧に全部入れ替えているように見えます。ところが実際には、前半で1回ひっくり返したあと、後半でもう1回ひっくり返して元に戻ってしまいます。

確かめるには、要素数3くらいの小さな配列で全部回してみるのがいちばんです。{1, 2, 3} なら、1回目で {3, 2, 1}、2回目は真ん中同士で変化なし、3回目で {1, 2, 3} に戻ります。

答えが元の配列と同じになる選択肢を見つけたら、ループの範囲を疑ってください。逆順を求める問題で、何も変わらない結果が正解になることはまずありません。

ループの回数そのものを数えるのが苦手な場合は、こちらの記事が参考になります。

【関連記事】科目Bの繰返し問題が解けない人へ｜ループ回数を追うコツ

相手の位置は i が 1 のときで決める¶

相手の位置の式が n − i なのか、n − i + 1 なのか。選択肢で迷ったら、i に 1 を入れてみてください。

最初の要素の相手は、必ず最後の要素です。i が 1 のときに n になる式が正解で、n − 1 になる式は1つずれています。

擬似言語の配列は1から数えるのが基本ですが、問題によっては0から数えることもあります。0始まりなら相手の位置は n − i − 1 のような形に変わるので、問題文の冒頭で添字の始まりを必ず確かめておきましょう。

回転は端の値の行方を見る¶

回転の選択肢で迷ったときは、端にあった値がどこへ行くかだけを追うと速く判断できます。左回転なら先頭の値が最後に、右回転なら最後の値が先頭に来ていれば正解です。

その値が途中で消えていたり、2つに増えていたりしたら、一時変数の使い方かずらす向きのどちらかが間違っています。要素の数と値の組み合わせが変わらない、という性質がここで役に立ちます。

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。値を上書きしながら進む処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数や配列の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの回で予想とずれたのかがすぐに分かります。

試すときは、まず正しい reverse を動かし、そのあとループの終わりを n に書き換えて動かしてみてください。配列が一度ひっくり返ってから元に戻る様子を見ると、半分で止める理由が体で分かります。

回転も同じように、右回転を前から回す誤ったコードを一度動かしてみるのがおすすめです。先頭の値が配列全体に広がっていく様子は、一度見ると忘れません。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、配列の中身が1行ごとに変わっていく様子を確かめてみてください。

まとめ¶

科目Bの逆順・回転の問題は、特別なアルゴリズムの知識を問うものではありません。入れ替える2つの位置を1回ずつ表に書き、ループがどこで止まるかを確かめれば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、要素数が3から5個の小さな配列で十分です。何度か表を書くうちに、n − i + 1 を見ただけで後ろから i 番目だと分かるようになります。

答えが出たら、要素の数と値の組み合わせが変わっていないかを確かめる。この一手間を習慣にしておけば、本番でも自分の答えに自信を持てます。次に逆順や回転の問題に出会ったら、まずは入れ替える位置の表を書くところから始めてみてください。