2018-11-06

平成30年度秋期FE午後のアルゴリズム問題をC++で実装&AOJ109のSmart Calculatorで動作確認

こんにちは、ゆでがきと申します。
今回は、先日行われた基本情報技術者試験で出題された擬似言語をC++で書き換えたものを紹介していこうと思います。またそのコードが本当に正しいものなのかをAOJの問題計算機 | Aizu Online Judgeで確認していこうと思います。

そもそも問題のコードがなにをやっているか理解できなかった方は

daeudaeu.com

この方が丁寧に解説していらっしゃるので、こちらを先に見ることをおすすめします。

実装したコード

gistea4de8b4da6d5d30fa35ebf38afdc93c

はい。そのまま実装しただけです。
ひとつ訂正しておくと、38行目のコメントにある"計算優先度の一番高い値を示す"は
"計算優先度の一番高い値の位置を示す"です。

AOJの問題で確認

さて、一番の重要事項である「本当にこのコードは正しいの？」を計算機 | Aizu Online Judgeで確認していきましょう。

この問題は最初に、数式の入力個数であるNが渡されます。その後に数式が入力されるので、その答えを出力しろ。という問題です。

ひとつ気になることといえば、数式が入力される際、末尾に'='がついていることです。ご安心ください。今回のアルゴリズムでは、数字,'+' , '-' , '×' , '÷' , '(' , ')' のみカウントして計算するものになっているのできちんと解を出力することができます。

AOJはいろいろな入力ケースを用意していて、少しでも違う動作をするような箇所があったらAC*1は出ないようになっているので、無事にACを出すことができたら、コードが正しいことの証明になります。

では提出していきましょう。

実装したコード(AOJ109用)

gisted7117f4af65a6547404ffd200005cce

先程のコードに、Nの入力受けとN回ループするfor文を実装しただけです。

果たして結果は…？

f:id:yudegaki:20181111220109p:plain

はい、ACいただきました。

まとめ

この記事を書くきっかけになったのが、私自身がH30秋の基本情報を受験してこの問題を見たときに「このアルゴリズムAOJの例の問題に使えるんじゃないか？」と思ったことでした。実際に試してみて、うまく行ったのでこういう形で今回アウトプットしてみました。
本当に大切なアルゴリズムの解説部分ですが、他の方がわかりやすい解説を書いていたので、サボってしまいました(こら)
次回また記事を書くことがあったら挑戦してみようと思います。

クソ記事に付き合ってくださった皆様、ありがとうございました。

*1:Acceptedのこと。競技プロ界隈では”正しい”解を出せたよ、的な意味で使われている

2018-08-05

C++のString型個人的まとめ

基本的に<string>をincludeしないと使えないよ!!!!!!!!!!!
あと"using namespace std;"もね♡
それじゃ、まとめていくよ

編集する文字列の名前をmojiとするよ

・文字列の抜き取り
　　str=moji.substr(位置,長さ);

・文字列の反転
　　<algorithm>をincludeして
　　reverse( moji.begin(), moji.end() );

・文字列の連結
　　moji=(str1+str2);

・文字列の削除
　　・末端の文字を消す場合
　　　moji.pop_back();
　　・任意の場所一箇所を消す場合
　　　moji.erase(moji.begin()+ここに配列番号);
　　・範囲を指定して消す場合
　　　moji.erase(moji.begin()+範囲の最初の番号,moji.begin()+範囲の最後の番号);

・文字列の長さ
　　　moji.length();

・文字列の初期化
　　　moji.clear();

2018-07-27

個人的な置き場

リダイレクトのチェック(htmlのみ)*追記　普通にf12でできました

EXIF確認君 - 画像情報解析ツール

シーザー暗号復号化

SHA1とかのハッシュ値を戻すよ

CTFに使用するツール類まとめ - ソースコード置き場

ftpコマンドについて詳しくまとめました【Linuxコマンド集】

2018-07-13

aoj-0004 Simultaneous Equation

はい、どうもyudegakiです。

atcoderのc問を埋めるとか言っていたのにすぐに違うサイトに浮気してしまいました。

だって難しいんだもん。解説が(ry

まあ自分の実力不足であるのは確かなので力をつけていくことにします(まあ今回の問題も重要な部分は先輩にアドバイスをもらいましたが)

ということで本題に入りましょう。

今回の問題はこちらSimultaneous Equation | Aizu Online Judge

なんか数字を与えるからxとyを出せ。ってことですね。

まあここまではただの数学だから簡単なんだけど、問題はここ→”xとyを小数点第4位を四捨五入して、小数点第3位までで出力せよ”... 　は？こんなの簡単じゃんという方はお帰りください。私はこの処理をするコードが思いつかなかったのだ...(敗北)

簡潔に結論から言うと、int(1000 * x + 2 * (1000 * x - int(1000 * x))) / 1000.0 です。

まあ、何をやっているかというと2*(1000*x-int(1000*x))で四捨五入で繰り上げする箇所の処理。*1そこに1000倍したxを足してint型でキャストする。これで小数点第3桁までの数字を小数点より上(?)に配置して、int型キャストで下3桁以下の数字を処す。最後に1000で割って、あら不思議、四捨五入の完成よ☆

というわけで解説は以上。　四捨五入の書き方を学べてよかったです。ではまた逢う日まで。(最後にソースコードを貼っておわりにします)

#include<iostream>

#include<stdio.h>

using namespace std;

int main() {

double a, b, c, d, e, f, x, y;

while (cin >> a >> b >> c >> d >> e >> f) {

x = (b*f - e * c) / (b*d - a * e);

y = (a*f - d * c) / (a*e - b * d);

x = int(1000 * x + 2 * (1000 * x - int(1000 * x))) / 1000.0;

y = int(1000 * y + 2 * (1000 * y - int(1000 * y))) / 1000.0;

printf("%.3lf %.3lf\n", x, y);