基本情報技術者試験（FE）を攻略しよう『アルゴリズム対策』

　今回は、基本情報技術者試験（以下、FE）の午後で必須のテーマである、データ構造及びアルゴリズム（以下、アルゴリズムという）がテーマの問題に対する攻略法について解説します。解説に入る前にひとつ情報処理技術者試験に関するトピックスを紹介します。

トピックス：情報セキュリティに関する出題の強化について

　先日（2013年10月29日）、IPAから「iパス（ITパスポート試験）をはじめとする情報処理技術者試験の出題構成の見直しについて」とのプレス発表があり、情報セキュリティに関するリテラシー向上などを目的として、ITパスポートを始めとする全試験区分で、情報セキュリティ分野の出題が強化・拡充されると告知されました。

　FEでは、午前問題において情報セキュリティ分野の出題数が高くなるとともに、同分野の午後問題が選択から必須に変更されました。今後FEを受験するときは午後試験において同分野の問題を必ず解かなければならず、苦手だから選ばないということはできません。情報セキュリティ分野の知識を十分に高めなければ合格は難しくなると予想されるので、過去問題や参考書で十分に学習しましょう。

アルゴリズム対策、4つの要点

　今回の攻略は、情報セキュリティ分野と同じく、FE午後試験で必須のアルゴリズムの問題（問8）の解き方について解説します。重要なことは次の4点です。

　①アルゴリズムの説明文とプログラムの内容を比較し、問題文を精読してアルゴリズムの目的を把握する
　②プログラムに入力されるデータと、プログラムが出力するデータを確認する
　③問題文、表、図の内容をチェックする（引数、配列の添字の開始、データ型）
　④処理内容から空欄の見当をつけられるようにする

　①については、アルゴリズムの問題を解くときに重要なことのひとつは、『問題を解く』ことではなく『問題文を読む』ことです。得点を取れない人は、アルゴリズムの説明文を正確に読み取れていないので、そのアルゴリズムがどのような入力データを受け取り、どのような処理を行って、どのような結果を出力しているかを確認せず、ただ漫然と問題を解いてしまっているのです。問題文を冒頭から設問文の直前まで確認することで、出題されているアルゴリズムが何をしようとしており、どのようなデータ構造（特に、配列やリストは重要）を操作しているのかを、正確に読み取ることが重要です。また、問題文や図表の中で重要と思われる箇所には下線を引くなどして、見直せるようにしましょう。

　②については、プログラムに入力されるデータと、プログラムが出力するデータを、プログラムの引数を示す表などから確認することが重要です。プログラムが出力するデータは、そのプログラムがアルゴリズムに従って処理を実行した結果です。入力された値と出力された値とを比較し、プログラム中で入力が適切に変換され、出力されているかどうかを確認することが重要です。

　③については、表や図の内容を入念にチェックしましょう。②で説明した入力データや出力データは、プログラムの引数として表に示されています。図にはアルゴリズムの処理内容が示されたり、プログラムで扱う配列やリストなどの具体例が記述されたりしています。これらはいずれもアルゴリズムを理解する上で重要であるとともに、後述するトレースを行うときにも使えます。また、問題文中に「配列の添字は1から始まる」などという指定がある場合、それを見落とさないようにします。配列の添字が0から始まるか1から始まるかで、正解が変わるからです。

　④は、①～③ができるようになった後で重要になります。たとえば、2つの変数A、Bの内容を入れ替えるとき、作業用の変数Workを用いて、次のようにすることがあります。

・Work←A
・A←B　（※）
・B←Work

　この3つの代入文は、2つの変数の内容を入れ替えるときに必ず用いられます。入替え処理があるプログラムでは、この3つの代入文で（※）が空欄になっていたら、必ず「A←B」が入るので、空欄の前後の文を見ただけで正解がすぐにわかります。

　他にも、アルゴリズムの問題では、配列の各要素を順に参照する繰返し処理中で、添字を指定する変数の値を1加算する処理が必ずあるなどの、「定番」としての処理があります。アルゴリズムの問題を数多く解き、さまざまなアルゴリズムに慣れていくことで定番処理のパターンを覚えて、短い時間で効率的に解けるようにしなければなりません。

アルゴリズムの問題攻略のコツは
『トレース』と『空欄をあえて無視する』

　アルゴリズムの問題を効率的に解くには、『トレース』と『空欄をあえて無視する』ことが重要です。プログラムの空欄を無理に埋めようとする前に、その空欄では何もしていないと仮定し、その前後の命令をトレースしてみることで、空欄に入る字句を特定しやすくなります。ただし、限られた試験時間中にプログラム全体を完全にトレースするのは難しいので、④で説明した定番処理のパターンから正解を特定することも忘れないでください。

　例として、平成25年度春期FEの午後問8の本文とプログラムの一部を示します。【】や下線は筆者が追加したものです。下線を引いている箇所は重要な記述です。アルゴリズムの概要や、プログラム中で使用する変数や配列の説明をしている箇所には、必ず下線を引いてください。

　このプログラムの空欄a、bを埋めるために、まず空欄を無視してトレースしてみます。【A】でKが2、【B】でTが1になります。K＞0かつTが対象行数（3）以下なので【C】内の処理を行います。購入[2].品番（111）は対象[1].品番（222）と異なるので、【D】から【F】以降に進みます。

　【F】では購入[2].品番が対象[1].品番より小さいので、空欄aを実行します。空欄aで何もしていないと仮定すると、Kの値が2のままで【C】に戻ります。Kの値が0にならない限りは【C】の条件が成立し続けるので、繰返しが終了しなくなり、購入[2]の次のレコードの参照もできません。

　この点から、空欄aではKの値を変更していると推定できます。「購入[]中のptrは、レコードを品番の昇順にたどるポインタであり、次に大きい品番をもつレコードが格納されている要素の添字が入っている」と説明されています。購入[2]のptr（1）をKに代入することで、購入[2]の次に大きい品番をもつレコードである購入[1]を参照できます。空欄aには“K←購入[K].ptr”が入り、Kを1にしてから【C】に戻ります。

　K＞0かつTが対象行数（3）以下なので【C】内の処理を行います。購入[1].品番（222）は対象[1].品番（222）と等しいので、【D】から【E】以降に進みます。対象[1]の特売対象の商品（品番＝222）が購入されていたので、【E】では対象[1].数量に購入[1].数量を設定しています。空欄aでは購入[1]のptr（4）をKに代入します。空欄bで何もしないと仮定すると、ここで【C】に戻るのでTの値がそのままになり、以降の処理でも対象[1].数量が参照され続けます。対象[1]のレコードに数量を設定する処理は終わったので、次の特売対象の商品のレコードを参照するために、空欄bでTの値を変更する必要があります。対象[]は購入[]のようなリスト構造にはなっていないので、単純にTの値に1加算することで次の特売対象の商品のレコードを参照できます。空欄bには“T←T＋1”が入ります。

　以上のようにして、プログラムの空欄を確実に埋めることが合格への道です。また、平成22年秋期午後問8など、プログラムに空欄がなく、代わりにプログラムの処理結果がどのようになるかを解答させる問題もあります。この種の問題ではプログラムをトレースすることで正解できるので、過去試験や模擬試験のアルゴリズムの問題を何度も解き、トレースの練習をしましょう。

【関連書籍紹介】

『基本情報技術者試験』の対策にはこの教科書と問題集！

かんたん合格 基本情報技術者教科書 平成26年度

IT初心者でも「わかる言葉」で「出るトコだけ」をやさしく解説。

本書は「解説に使われている言葉がわからない」「結局どこが出題されるのかがわからない」「最短で合格したい」といった受験者の声にお応えし、専門用語をできる限り易しい言葉に置き換えて解説しています。また、出題頻度の高いテーマに絞っているため、幅広い出題範囲を短期間で学習できます。さらに、インプレス情報処理試験シリーズでは受験者応援キャンペーンを実施中！内容もボリュームも従来のままに応援価格によるご提供と、購入者限定特典として全文の電子版(PDF)と、スマホで学べる単語帳アプリ「でる語句200」を無料でダウンロードいただけます。

徹底攻略 基本情報技術者教科書 平成25年度秋期・平成26年度春期

これ一冊で合格に必要な知識が身に付く！

人気講師が試験を徹底分析し、これ一冊で確実に合格ラインの実力が身に付くよう構成。学習のポイントを測注で補足しているので、効率良く学習を進められます。巻頭には試験直前に理解度を確認できる穴埋め問題、巻末には重要問題を集めた模擬問題を掲載。最後の総仕上げに最適です。また、インプレス情報処理試験シリーズでは受験者応援キャンペーンを実施中！内容もボリュームも従来のままに応援価格によるご提供と、購入者限定特典として全文の電子版（PDF）と、スマホで学べる単語帳アプリ「でる語句200」を無料でダウンロードいただけます。

かんたん合格 基本情報技術者過去問題集 平成26年度春期

これ一冊で合格力が付く！解き方に加えて受かるカギを解説。

過去問から類似問題が多く出題される基本情報技術者試験では、過去問題に触れておくことが必須。しかし、ただ問題を解くだけで合格力は身に付きません。本書では、各問題の解き方に関する解説だけではなく、覚えるべきポイントや攻略法を「午前のカギ」「午後のカギ」欄に掲載。過去問題集でありながら、これ一冊で確実に合格ラインの実力が身に付くよう構成しています。現在キャンペーン実施中につき、購入者限定2特典（スマホで学べる単語帳アプリ「でる語句200」＆本書全文の電子版PDF）を付けて、応援価格によりご提供します。

徹底攻略ポケット 基本情報技術者試験 午前対策

プロが出題をズバリ予想！ 基本情報技術試験午前の出題傾向を徹底分析した厳選300問。

情報処理技術者試験の基本情報技術者試験の午前対策本です。試験問題を見続けているプロ講師の著者だからできる、出題傾向を徹底分析。過去問題の中から今後試験に出そうな類似問題を300問厳選しました。本書に収録した問題を理解し解けるようになれば、午前試験の合格に必要な60%は確実に取れるように構成しています。試験までに時間のない方、教科書だけの勉強に不安な方は、本書を活用すると、合格に一歩近づけます。