2023年4月から基本情報技術者試験の内容がアルゴリズムまみれに
基本情報技術者試験が2023年4月から大幅に変わります。主に旧・午後試験(新・科目B試験)の内容変更が著しく、以下のサンプル問題の冒頭に記載されておりますが8割が「アルゴリズムとプログラミング」2割が「情報セキュリティ」という構成になります。それ以外の分野は消滅してしまいました。アルゴリズム試験と言ってもいいぐらいの内容になります・・・!
・情報元 : IPA 独立行政法人 情報処理推進機構情報処理技術者試験における出題範囲・シラバス等の変更内容の公表について
基本情報技術者試験科目B試験のサンプル問題
アルゴリズムはこれまでの試験では100点中20点配点でしたから、苦手な方の中には「最悪アルゴが0点でも他で合格ライン(60点以上)超えればいい」そんな風に割り切ってしまう方もいました。
2023年4月以降、出題割合が8割アルゴリズムになるわけですから、もうその手も使えません。
アルゴリズム対策には疑似言語の実装が有効
私が数年前に基本情報の勉強をした際のアルゴリズム対策ですが、過去問のアルゴリズムを疑似言語のロジック通りにC言語でとにかくコード化(実装)しました。実装さえしてしまえば動くのはもちろん、デバッグ機能を使って1行ずつステップ実行しながら値がどのように変化するのか追うのも楽です。
これはどんなプログラミング言語でも実現可能です。しかし、コーディング能力がまだ無い方には難しいことでしょう。基本情報技術者試験は「IT従事者向け試験」とIPAは位置づけているものの、就職・転職対策として非エンジニアの方が挑戦することも多いのが実情です。
コードが書けないなら誰かに疑似言語を実装してもらい、コピペして動かしてみるのも有りでしょう。ただ、動かすための環境構築が曲者です。もっとも最近はAWSのCloud9のようにブラウザ上で動作する開発環境もありますが、登録に要クレジットカードだったりと万人が気軽にとはいきません。
GAS(google Apps Script)なら誰でもすぐ動かせる
Googleのアカウントを作るだけで、ブラウザからスプレッドシートというExcelのパクリ・・・コホン!!便利な表計算ソフトが使えたり色々できるのですが、ExcelにVBAというプログラミング機能がついているように、スプレッドシートにもGASというプログラミング機能が備わっています。
つまり、環境構築不要でブラウザさえあればプログラミングができるわけです。
GASはまんまJavaScriptの文法です。基本情報のアルゴリズムで使われる疑似言語をJavaScriptの文法で書けば良いわけで・・・素晴らしいことにブラウザ上でデバッグまですべて完結します。
「だから俺はコードがまだ書けないっちゅーの!」というアナタ、上達のためには自力で書けるようになるのが理想ではありますが、まずはコピペすればええんですよ。
冒頭でリンクを貼った科目B試験のサンプル問題のアルゴリズム、5問すべてこの記事の後半にGASで実装したコードを公開してます。
GASの操作法(プログラムの実行やデバッグについて)は私のYouTube動画(12月上旬公開予定)でも触れますが、普通に検索で調べても良いと思います。この後紹介するコードをコピペで利用される方で心の優しい方は私の動画も見て、高評価を押してくれると私もちょっと報われます、オナシャス・・・!
【重要】実装内容に関する補足と注意
・原則として // から始まるコメントはサンプル問題の文章です。その次の行に対応するコードを記述しています。例外として /* */ に挟まれたコメントは独自に付け加えたものです。
・サンプル問題では配列の添え字が1から始まるのに対し、GASの配列は0から始まります。そのため配列にアクセスする際は +1 または -1 するなどして差異を埋めています。
・関数化された処理のみが実装されており、呼び出し元がサンプル問題では省略されている出題に関しては、こちらで文章の仕様を読み解き、独自に実装することで実行可能な状態にしてあります。
・バグを見つけた方はこのブログでもYouTubeでもどちらでもいいのでご連絡いただけると幸いです。
・自由に使っていただいて構いませんが「俺が書いたコードだ!」のように権利を主張するのはおやめください。知的財産権では解法(アルゴリズム)は保護されませんが、ソースコードは別です。
・解答の穴埋め個所も実装しています。正解をまだ知りたくない方は要注意。
ここから先は実装したGASコードです!レッツコピペ!
問1の実装
ボーナス問題。”より小さい”と”以下”の違いに気を付ければOK。
/* 問1(GoogleAppsScriptによる実装)*/
// ○整数型: fee(整数型: age)
function fee(age) {
// 整数型: ret
let ret
// if (age が 3 以下)
if (age <= 3) {
// ret ← 100
ret = 100;
// elseif (【age が 9 以下】)
} else if (age <= 9) {
// ret ← 300
ret = 300;
// else
} else {
// ret ← 500
ret = 500;
// endif
}
// return ret
return ret;
}
/* 動作確認用(スプレッドシートに移動するとポップアップが出ます) */
function fe01() {
let ui = SpreadsheetApp.getUi();
let res = ui.prompt('年齢を入力してください ※整数値', ui.ButtonSet.OK);
let age = parseInt(res.getResponseText());
console.log(fee(age));
}
問2の実装
逆順ソートアルゴリズム。値の大小比較を行わないのでまだ易しい。
/* 問2(GoogleAppsScriptによる実装) */
/* GASの配列は0から始まるため一部読み替えています */
/* 動作確認兼用 */
function fe02() {
// 整数型の配列: array ← {1, 2, 3, 4, 5}
let array = [1, 2, 3, 4, 5];
// 整数型: right, left
let right, left;
// 整数型: tmp
let tmp;
// for (left を 1 から (arrayの要素数 ÷ 2 の商) まで 1 ずつ増やす)
for (left = 1; left <= (array.length / 2); left++) {
// right ← 【array の要素数 - left + 1】
right = array.length - left + 1;
// tmp ← array[right]
tmp = array[right - 1];
// array[right] ← array[left]
array[right - 1] = array[left - 1];
// 【array[left]】 ← tmp
array[left - 1] = tmp;
// endfor
}
/* 結果確認用 */
console.log(array)
}
問3の実装
単方向連結リスト作成アルゴリズム。少し複雑かもしれませんが要は電車ごっこです。
/* 問3(GoogleAppsScriptによる実装)*/
// 大域: ListElement: listHead ← 未定義の値
var listHead = null;
// ○append(文字型: qVal)
function append(qVal) {
// ListElement: prev, curr
let prev, curr;
// curr ← ListElement(qVal)
curr = new ListElement(qVal);
// if (listHead が 【未定義】)
if (listHead == null) {
// listHead ← curr
listHead = curr;
// else
} else {
// prev ← listHead
prev = listHead;
// while (prev.next が 未定義でない)
while (prev.next != null) {
// prev ← prev.next
prev = prev.next;
// endwhile
}
// prev.next ← 【curr】
prev.next = curr;
// endif
}
}
/* ListElementクラス定義 */
class ListElement {
constructor(qVal) {
this.val = qVal;
this.next = null;
}
}
/* 動作確認用 */
function fe03() {
append('a');
append('b');
append('c');
console.log(listHead);
}
問4の実装
この辺りから難解に。データ変換アルゴリズムの一端といったところでしょうか・・・。
/* 問4(GoogleAppsScriptによる実装) */
/* GASの配列は0から始まるため一部読み替えています */
// ○整数型配列の配列: transformSparseMatrix(整数型の二次元配列: matrix)
function transformSparseMatrix(matrix) {
// 整数型: i, j
let i, j;
// 整数型配列の配列: sparseMatrix
let sparseMatrix;
// sparseMatrix ← {{}, {}, {}} /* 要素数0の配列を三つ要素にもつ配列 */
sparseMatrix = [[], [], []];
// for (i を 1 から matrixの行数 まで 1 ずつ増やす)
for (i = 0; i < matrix.length; i++) {
// for (j を 1 から matrixの列数 まで 1 ずつ増やす)
for (j = 0; j < matrix[i].length; j++) {
// if (matrix[i, j] が 0 でない)
if (matrix[i][j] != 0) {
// sparseMatrix[1]の末尾 に iの値 を追加する
sparseMatrix[0].push(i + 1);
// sparseMatrix[2]の末尾 に jの値 を追加する
sparseMatrix[1].push(j + 1);
// sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加する
sparseMatrix[2].push(matrix[i][j]);
// endif
}
// endfor
}
// endfor
}
// return sparseMatrix
return sparseMatrix;
}
/* 動作確認用 */
function fe04() {
let matrix = transformSparseMatrix([[3, 0, 0, 0, 0], [0, 2, 2, 0, 0], [0, 0, 0, 1, 3], [0, 0, 0, 2, 0], [0, 0, 0, 0, 1]]);
console.log(matrix);
}
問5の実装
こちらも問4に引き続き難解。文章パターン解析の一端といったところか。
/* 問5(GoogleAppsScriptによる実装)*/
/* Wordsクラス定義) */
class Words {
constructor(args) {
this.EnglishWords = args;
this.engLen = this.EnglishWords.length;
}
/* 英単語群中の文字列 str の出現回数を返す */
freq(str) {
let cnt = 0;
let tmp;
for (let i = 0; i < engLen; i++) {
tmp = this.EnglishWords[i].split(str);
cnt = cnt + tmp.length - 1;
}
return cnt;
}
/* 英単語群の中で,文字列 str で終わる英単語の数を返す */
freqE(str) {
let cnt = 0;
for (let i = 0; i < engLen; i++) {
if (this.EnglishWords[i].endsWith(str)) {
cnt++;
}
}
return cnt;
}
}
// 大域: Words: words /* 英単語群が格納されている */
var words = new Words(["importance", "inflation", "information", "innovation"]);
// /* c1の次にc2が出現する割合を返す */
// ○実数型: prob(文字型: c1, 文字型: c2)
function prob(c1, c2) {
// 文字列型: s1 ← c1の1文字だけから成る文字列
let s1 = c1;
// 文字列型: s2 ← c2の1文字だけから成る文字列
let s2 = c2;
// if (words.freq(s1 + s2) が 0 より大きい)
if (words.freq(s1 + s2) > 0) {
// return (回答:ウ) words.freq(s1 + s2) ÷ (words.freq(s1) - words.freqE(s1))
return words.freq(s1 + s2) / (words.freq(s1) - words.freqE(s1));
// else
} else {
// return 0
return 0;
//endif
}
}
/* 動作確認用 */
function fe05() {
let ui = SpreadsheetApp.getUi();
let res1 = ui.prompt("c1を入力してください ※英小文字1字", ui.ButtonSet.OK);
let c1 = res1.getResponseText();
let res2 = ui.prompt("c2を入力してください ※英小文字1字", ui.ButtonSet.OK);
let c2 = res2.getResponseText();
let prm = prob(c1, c2);
console.log(prm);
}
YouTubeで上記コードの動かし方を解説しています
5:50~辺りからがコードの動かし方です。
あとがき
今回はJavaScriptの文法でコーディング可能なGASを使って基本情報の科目Bサンプル問題を実装してみましたが、私はGASなんて普段触らないし、JavaScriptも触りません。Excelで設計書作って、ビジネスメールを送って、TeraTermでサーバにログインしてコマンドを打鍵する日々を送るタイプのSEです。とはいえサーバ上にはシェルスクリプトが配置されておりプログラマ的思考(論理的思考)は必須です。
結局、SEは全部やらなアカン。
基本情報技術者試験のアルゴリズム対策はまさに論理的思考を鍛えるのにうってつけです。科目Bのサンプル問題に限らず、これまでの過去問(午後試験)のアルゴリズムも実装してみてください。
コメント