目次
はじめに
競技プログラミングの鉄則という本を読み進めています。現在 Javaでコーディングしています。そんな中で、アルゴリズム以外でつまづくことがたくさんあったんですよね。なので、つまづいたポイントのメモと解説を兼ねて、書いていきます。
ちなみに解答例として書かれているコードは私が書いたものです。公式の解答は解答例の下にリンクを貼っているのでそちらから見ていただけると助かります。
問題文
A04 - Binary Representation 1 , https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_dより抜粋
整数 N が 10 進法表記で与えられます。N を 2 進法に変換した値を出力するプログラムを作成してください。
解答例
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
for (int i = 9; i >= 0; i--) {
int wari = (int)Math.pow(2, i);
System.out.print((N / wari) % 2);
}
}
}
公式の解答はこちらから→https://github.com/E869120/kyopro-tessoku/blob/main/codes/java/chap01/answer_A04.java
解説
int wari = (int)Math.pow(2, i);について。
Mathの型はDoubleなので、(int)でこいつはint型として扱ってくださいねーってJVMに伝えています。（JVMとはJava 仮想マシン（Java Virturl Machine）のことでJavaで作ったプログラムとコンピュータの通訳をする。）そうすることで、正常にソースコードをコンパイルすることが出来ます！
そうしなかった場合はDouble型になってしまって計算結果自体もDouble型になってしまいます。なので、結果が正しくならないんですよね。計算は合っているんですけど。例）Int → 1 〇, double → 1.0 ×。
- ビット演算について。
私の解答例では計算でMathを使っていますが、公式の解答例ではビット演算(1 << i)を使っているんですよね。このビット演算っていうのが曲者なんです。何かと申しますと、、データを0,1 が並んだもの（2進数）として計算するってことです。具体的に言うなら、「8」というデータが渡されたら、「1000」で計算するというものです。
じゃあ、Math とビット演算が今回なんで会計しているのかってことなですよね。今回は、どってでも「2の〇乗」を表せるからなんですよ。
Mathの方はMath.pow(2, i)で「2のi乗」です。 ですが、(1 << i)でも「2のi乗」なんですよ。
(1 << i)でも「2のi乗」な理由は、「i」を増やしていったらわかりやすいです。i が１の時は１が左に１ずれて「10」になる。↓↓↓例↓↓↓
- i =1,「10」 →（10進数に変換すると）「2」→2の1乗
- i =2,「100」→（10進数に変換すると）「4 」→2の1乗
- i =3,「1000」→（10進数に変換すると）「8」→2の3乗
- i =4,「10000」→（10進数に変換すると）「16」→2の4乗
そうなんです、ビット演算でもできちゃんです。〇乗が。。公式の解答例ではこっち使っていたので、覚えておいたほうが良いかと。
- 割り算の英語について
ソースコードにwariという変数名を付けています。なんか、ここだけ日本語だったので、英語はなんていうんだろうと疑問に思い調べたので、ここにメモします。
- 割り算 ・・・ division
- 商 ・・・ quotient
- あまり ・・・ remainder
だそうです。覚えたいたら今後も使って行こうか。。
所感
個人的にはいろいろと詰まった問題でした。アルゴリズムっていうよりかは同実装するのかという所で。後は、コードのメカニズムというか、コードの意味とかに詰まっていました。ドキュメントを読むよりも、いろいろと試行錯誤したほうが理解が深ったので、次からもそうしよう！！
