【問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本】読書メモ
おっちー(O.S)【問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本】
おっちー(O.S)2章
2.1
N進法から10進法への変換
2進法=>10進法は、「位とその桁の数の掛け算」の合計をすることで変換可能になる。
10進法だと、一の位・十の位・百の位・千の位というふうに桁に位をつける。
2進法でも、
11101だと、以下のような数値になるため、その合計を考える。
16 + 8 + 4 + 0 + 1 = 28
10進法からN進法への変換
10進法から、2進法への変換を考える。
2で商が0になるまで割っていって、その余りを下から読むことでできる。
なぜ余りを下から読むことで変換できるのかは、2進法での未計算部分について考えると良い。
具体例として、10進法の11を考える。2進法にすると1011になる。
この時、1回割った時の商が、5となり、これを2進法で表すと101となる。
2回割った時の商が、2となり、これを2進法で表すと10となる。
3回割った時の商が、1となり、これを2進法で表すと1となる。
10進法を3進法に変換するプログラム
#include <iostream>
#include <string>
using namespace std;
int N;
string Answer = "";
int main() {
cin >> N;
while (N >= 1) {
if (N % 3 == 0) Answer = "0" + Answer;
if (N % 3 == 1) Answer = "1" + Answer;
if (N % 3 == 2) Answer = "2" + Answer;
N = N / 3;
}
cout << Answer << endl; // 出力部分
return 0;
}
3.2 ユークリッドの互除法
ユークリッドの互除法が成り立つ理由がよく理解できなかった。