2019年2月17日日曜日

cpp - 数学の問題(最小公倍数)

Modern C++チャレンジ ―C++17プログラミング力を鍛える100問 (Marius Bancila(著)、島 敏博(監修)、黒川 利明(翻訳)、オライリージャパン)の1章(数学の問題)、問題3(最小公倍数)の解答を求めてみる。

コード

```#include <iostream>

size_t lcm1(size_t a, size_t b)
{
size_t al = a;
size_t bl = b;

while (al != bl)
{
if (al < bl)
{
al += a;
}
else
{
bl += b;
}
}
return al;
}

size_t gcd(size_t q, size_t r)
{
if (r == 0)
{
return q;
}
return gcd(r, q % r);
}

size_t lcm2(size_t a, size_t b)
{
return a * b / gcd(a, b);
}

int main()
{
for (size_t i = 5; i < 10; i++)
{
for (size_t j = 5; j < 10; j++)
{
std::cout << "lcm(" << i << "," << j << ") = "
<< lcm1(i, j) << ", " << lcm2(i, j) << std::endl;
}
}
for (size_t i = 50; i < 55; i++)
{
for (size_t j = 100; j < 105; j++)
{
std::cout << "lcm(" << i << "," << j << ") = "
<< lcm1(i, j) << ", " << lcm2(i, j) << std::endl;
}
}
}```

```Active code page: 65001

C:\Users\...>cl sample3.cpp && sample3.exe
Microsoft(R) C/C++ Optimizing Compiler Version 19.16.27027.1 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

sample3.cpp
C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\include\xlocale(319): warning C4530: C++ 例外処理を使っていますが、アンワインド セマンティクスは有効にはなりません。/EHsc を指定してください。
Microsoft (R) Incremental Linker Version 14.16.27027.1
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:sample3.exe
sample3.obj
lcm(5,5) = 5, 5
lcm(5,6) = 30, 30
lcm(5,7) = 35, 35
lcm(5,8) = 40, 40
lcm(5,9) = 45, 45
lcm(6,5) = 30, 30
lcm(6,6) = 6, 6
lcm(6,7) = 42, 42
lcm(6,8) = 24, 24
lcm(6,9) = 18, 18
lcm(7,5) = 35, 35
lcm(7,6) = 42, 42
lcm(7,7) = 7, 7
lcm(7,8) = 56, 56
lcm(7,9) = 63, 63
lcm(8,5) = 40, 40
lcm(8,6) = 24, 24
lcm(8,7) = 56, 56
lcm(8,8) = 8, 8
lcm(8,9) = 72, 72
lcm(9,5) = 45, 45
lcm(9,6) = 18, 18
lcm(9,7) = 63, 63
lcm(9,8) = 72, 72
lcm(9,9) = 9, 9
lcm(50,100) = 100, 100
lcm(50,101) = 5050, 5050
lcm(50,102) = 2550, 2550
lcm(50,103) = 5150, 5150
lcm(50,104) = 2600, 2600
lcm(51,100) = 5100, 5100
lcm(51,101) = 5151, 5151
lcm(51,102) = 102, 102
lcm(51,103) = 5253, 5253
lcm(51,104) = 5304, 5304
lcm(52,100) = 1300, 1300
lcm(52,101) = 5252, 5252
lcm(52,102) = 2652, 2652
lcm(52,103) = 5356, 5356
lcm(52,104) = 104, 104
lcm(53,100) = 5300, 5300
lcm(53,101) = 5353, 5353
lcm(53,102) = 5406, 5406
lcm(53,103) = 5459, 5459
lcm(53,104) = 5512, 5512
lcm(54,100) = 2700, 2700
lcm(54,101) = 5454, 5454
lcm(54,102) = 918, 918
lcm(54,103) = 5562, 5562
lcm(54,104) = 2808, 2808

C:\Users\...>
```

whileループで小さい方に足していって等しくなるまで続ける単純なアルゴリズムを利用した関数と、問題2で定義した最大公約数を求める関数(ユークリッド互除法)を利用した関数を定義してみた。2つの関数の結果を比較で検算。