平成30年度秋期FE午後のアルゴリズム問題をC++で実装&AOJ109のSmart Calculatorで動作確認
こんにちは、ゆでがきと申します。
今回は、先日行われた基本情報技術者試験で出題された擬似言語をC++で書き換えたものを紹介していこうと思います。またそのコードが本当に正しいものなのかをAOJの問題計算機 | Aizu Online Judgeで確認していこうと思います。
そもそも問題のコードがなにをやっているか理解できなかった方は
この方が丁寧に解説していらっしゃるので、こちらを先に見ることをおすすめします。
実装したコード
gistea4de8b4da6d5d30fa35ebf38afdc93c
はい。そのまま実装しただけです。
ひとつ訂正しておくと、38行目のコメントにある"計算優先度の一番高い値を示す"は
"計算優先度の一番高い値の位置を示す"です。
AOJの問題で確認
さて、一番の重要事項である「本当にこのコードは正しいの？」を計算機 | Aizu Online Judgeで確認していきましょう。
この問題は最初に、数式の入力個数であるNが渡されます。その後に数式が入力されるので、その答えを出力しろ。という問題です。
ひとつ気になることといえば、数式が入力される際、末尾に'='がついていることです。ご安心ください。今回のアルゴリズムでは、数字,'+' , '-' , '×' , '÷' , '(' , ')' のみカウントして計算するものになっているのできちんと解を出力することができます。
AOJはいろいろな入力ケースを用意していて、少しでも違う動作をするような箇所があったらAC*1は出ないようになっているので、無事にACを出すことができたら、コードが正しいことの証明になります。
では提出していきましょう。
実装したコード(AOJ109用)
gisted7117f4af65a6547404ffd200005cce
先程のコードに、Nの入力受けとN回ループするfor文を実装しただけです。
果たして結果は…？
はい、ACいただきました。
まとめ
この記事を書くきっかけになったのが、私自身がH30秋の基本情報を受験してこの問題を見たときに「このアルゴリズムAOJの例の問題に使えるんじゃないか？」と思ったことでした。実際に試してみて、うまく行ったのでこういう形で今回アウトプットしてみました。
本当に大切なアルゴリズムの解説部分ですが、他の方がわかりやすい解説を書いていたので、サボってしまいました(こら)
次回また記事を書くことがあったら挑戦してみようと思います。
クソ記事に付き合ってくださった皆様、ありがとうございました。
*1:Acceptedのこと。競技プロ界隈では”正しい”解を出せたよ、的な意味で使われている
