自然数 n を素因数分解する関数 factorization を定義してください。返り値はスライス [ ]*Pow で、構造体 Pow{p q} は pq を表します。
type Pow struct {
p, q int
}
func factorization(n int) []*Pow
factorization(24) => [(2, 3) (3, 1)] factorization(12345678) => [(2, 1) (3, 2) (47, 1) (14593, 1)] factorization(123456789) => [(3, 2) (3607, 1) (3803, 1)] factorization(1234567890) => [(2, 1) (3, 2) (5, 1) (3607, 1) (3803, 1)] factorization(1111111111) => [(11, 1) (41, 1) (271, 1) (9091, 1)]
自然数 n の約数の個数を求める関数 divisorNum を定義してください。
func divisorNum(n int) int
divisorNum(24) => 8 divisorNum(12345678) => 24 divisorNum(123456789) => 12 divisorNum(1234567890) => 48 divisorNum(1111111111) => 16
自然数 n の約数の合計値を求める関数 divisorSum を定義してください。
func divisorSum(n int) int
divisorSum(24) => 60 divisorSum(12345678) => 27319968 divisorSum(123456789) => 178422816 divisorSum(1234567890) => 3211610688 divisorSum(1111111111) => 1246404096
自然数 n の約数をスライスに格納して返す関数 divisor を定義してください。
func divisor(n int) []int
divisor(24) => [1 2 3 4 6 8 12 24] divisor(12345678) => [1 2 3 6 9 18 47 94 141 282 423 846 14593 29186 43779 87558 131337 262674 685871 1371742 2057613 4115226 6172839 12345678] divisor(123456789) => [1 3 9 3607 3803 10821 11409 32463 34227 13717421 41152263 123456789] divisor(1234567890) => [1 2 3 5 6 9 10 15 18 30 45 90 3607 3803 7214 7606 10821 11409 18035 19015 21642 22818 32463 34227 36070 38030 54105 57045 64926 68454 108210 114090 162315 171135 324630 342270 13717421 27434842 41152263 68587105 82304526 123456789 137174210 205761315 246913578 411522630 617283945 1234567890] divisor(1111111111) => [1 11 41 271 451 2981 9091 11111 100001 122221 372731 2463661 4100041 27100271 101010101 1111111111]
完全数 - Wikipedia によると、『完全数（かんぜんすう，perfect number）とは、その数自身を除く約数の和が、その数自身と等しい自然数のことである。』 とのことです。自然数 n 以下の完全数を求める関数 perfectNumber を定義してください。
func perfectNumber(n int)
perfectNumber(10000) => (画面に出力) 6 28 496 8128
友愛数 - Wikipedia によると、『友愛数（ゆうあいすう）とは、異なる2つの自然数の組で、自分自身を除いた約数の和が、互いに他方と等しくなるような数をいう。』 とのことです。自然数 n 以下の友愛数を求める関数 yuuaiNumber を定義してください。
func yuuaiNumber(n int)
yuuaiNumber(100000) => (画面に出力) 220 284 1184 1210 2620 2924 5020 5564 6232 6368 10744 10856 12285 14595 17296 18416 63020 76084 66928 66992 67095 71145 69615 87633 79750 88730
Go 言語のパッケージ math/big には多倍長整数 Int が定義されています。Int を使って階乗 (fact), フィボナッチ数列 (fibo)、整数の累乗 (power) を求める関数を定義してください。
func fact(n int64) *big.Int func fibo(n int64) *big.Int func power(x, y int64) *big.Int
fact(10) => 3628800 fact(30) => 265252859812191058636308480000000 fact(50) => 30414093201713378043612608166064768844377641568960512000000000000 fibo(100) => 354224848179261915075 fibo(150) => 9969216677189303386214405760200 fibo(200) => 280571172992510140037611932413038677189525 power(2, 100) => 12676506002282294014967032053765 power(3, 100) => 15377520732011331036461129765621272702107522001 power(5, 100) => 7888609052210118054117285652827862296732064351090230047702789306640625
分数を小数に直すことを考えます。1 / 2, 1 / 5, 1 / 8, 1 / 10 などは 0.5, 0.2, 0.125, 0.1 のように途中で割り切れて、有限な桁で表すことができます。これを「有限小数」といいます。ところが、1 / 3, 1 / 6, 1 / 7 は、次のように有限な桁では表すことができません。
1 / 3 = 0.333333 ... 1 / 6 = 0.166666 ... 1 / 7 = 0.142857142857142857 ...
1 / 3 は 3 を無限に繰り返し、1 / 6 は 0.1 のあと 6 を無限に繰り返し、1 / 7 は数列 142857 を無限に繰り返します。このような少数を「循環小数 (repeating decimal)」といい、繰り返される数字の列を「循環節」といいます。分数を小数に直すと、有限小数か循環小数のどちらかになります。
循環小数は次のように循環節の始めと終わりを点で示します。
.
1 / 3 = 0.3
.
1 / 6 = 0.16
. .
1 / 7 = 0.142857
このほかに、循環節に下線を引いたり、カッコで囲む表記法もあります。
それでは問題です。分数 (p / q) を循環小数に変換する関数 repdec を定義してください。
func repdec(p, q int) ([]int, []int)
返り値は 2 つのスライスで、先頭のスライスが冒頭の小数部分を、次のスライスが循環節の部分を表します。途中で割り切れる場合は循環節を [0] とします。
repdec(1, 2) => [0 5] [0] repdec(1, 3) => [0] [3] repdec(1, 6) => [0 1] [6] repdec(1, 7) => [0] [1 4 2 8 5 7] repdec(1, 9) => [0] [1] repdec(1, 11) => [0] [0 9] repdec(355, 113) => [3] [1 4 1 5 9 2 9 2 0 3 5 3 9 8 2 3 0 0 8 8 4 9 5 5 7 5 2 2 1 2 3 8 9 3 8 0 5 3 0 9 7 3 4 5 1 3 2 7 4 3 3 6 2 8 3 1 8 5 8 4 0 7 0 7 9 6 4 6 0 1 7 6 9 9 1 1 5 0 4 4 2 4 7 7 8 7 6 1 0 6 1 9 4 6 9 0 2 6 5 4 8 6 7 2 5 6 6 3 7 1 6 8]
循環小数から分数を求める関数 fromRepdec を定義してください。
func fromRepdec(xs, ys []int) (int, int)
スライス xs が冒頭の小数部分を、スライス ys が循環節の部分を表します。
fromRepdec([]int{0, 5}, []int{0}) => 1 2
fromRepdec([]int{0}, []int{3}) => 1 3
fromRepdec([]int{0, 1}, []int{6}) => 1 6
fromRepdec([]int{0}, []int{1,4,2,8,5,7}) => 1 7
fromRepdec([]int{0}, []int{1}) => 1 9
fromRepdec([]int{0}, []int{0,9}) => 1 11
パズル「小町分数」を解くプログラムを作ってください。
下図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。3 つの分数を足すと 1 / N になる配置を求めてください。
A D G 1
--- + --- + --- = ---
B C E F H I N
ex) 3 / 27 + 6 / 54 + 9 / 81 = 1 / 3
3 / 54 + 6 / 72 + 9 / 81 = 1 / 4
図 : 小町分数
このパズルの元ネタは N = 1 の場合で、参考文献 [1] に掲載されています。
リスト : 素因数分解
// Pow の定義
type Pow struct {
p, q int
}
// Pow の生成
func newPow(p, q int) *Pow {
a := new(Pow)
a.p, a.q = p, q
return a
}
// Stringer の定義
func (p *Pow) String() string {
return fmt.Sprintf("(%d, %d)", p.p, p.q)
}
// m で割り切れる回数を求める
func factorSub(n, m int) (int, int) {
i := 0
for ; n % m == 0; n /= m {
i++
}
return i, n
}
// 素因数分解
func factorization(n int) []*Pow {
a := make([]*Pow, 0)
c, m := factorSub(n, 2)
if c > 0 {
a = append(a, newPow(2, c))
}
for i := 3; m >= i * i; i += 2 {
c, m = factorSub(m, i)
if c > 0 {
a = append(a, newPow(i, c))
}
}
if m > 1 {
a = append(a, newPow(m, 1))
}
return a
}
素因数分解は素数 2, 3, 5, ... で順番に割り算していけばいいのですが、いちいち素数を求めるのは大変なので、2 と 3 以上の奇数列で割り算していきます。関数 factorSub は n を m で割り算します。このとき、m で割り切れる回数を求めます。factorSub は m で割った回数と商を多値で返します。
次に、factorSub を呼び出して n を 2 で割り算します。それから、for ループで奇数列を生成します。変数 i は 3 で初期化します。a は結果を格納するスライスです。√m < i になったら for ループを終了します。そうでなければ、factorSub を呼び出して m を i で割り算します。奇数列には素数ではないものがありますが、その前に小さな素数で素因数分解されているので、n がその値で割り切れることはありません。
n の素因数分解ができると、約数の個数を求めるのは簡単です。n = pa * qb * rc とすると、約数の個数は (a + 1) * (b + 1) * (c + 1) になります。たとえば、12 は 22 * 31 になるので、約数の個数は 3 * 2 = 6 になります。実際、12 の約数は 1, 2, 3, 4, 6, 12 の 6 個です。
プログラムは次のようになります。
リスト : 約数の個数
func divisorNum(n int) int {
a := 1
for _, x := range factorization(n) {
a *= x.q + 1
}
return a
}
divisorNum は for ループでスライスの要素を順番に取り出し、x.q + 1 を a に掛け算していくだけです。
n の素因数分解ができると、約数の合計値を求めるのは簡単です。n の素因数分解が pa だった場合、その約数の合計値は次の式で求めることができます。
σ(p, a) = pa + pa-1 + ... + p2 + p + 1
たとえば、8 の素因数分解は 23 になり、素数の合計値は 8 + 4 + 2 + 1 = 15 になります。
pa の約数の合計値を σ(p, a) で表すことにします。n = pa * qb * rc の場合、n の約数の合計値は σ(p, a) * σ(q, b) * σ(r, c) になります。たとえば、12 は 22 * 3 に素因数分解できますが、その合計値は (4 + 2 + 1) * (3 + 1) = 28 となります。12 の約数は 1, 2, 3, 4, 6, 12 なので、その合計値は確かに 28 になります。
プログラムは次のようになります。
リスト : 約数の合計値
// 累乗の計算
func power(x, y int) int {
if y == 0 {
return 1
} else if y == 1 {
return x
} else {
z := power(x, y / 2)
if y % 2 == 0 {
return z * z
} else {
return z * z * x
}
}
}
// σ(p, n) の計算
func divSumSub(p, n int) int {
a := 0
for ; n > 0; n-- {
a += power(p, n)
}
return a + 1
}
// 約数の和
func divisorSum(n int) int {
a := 1
for _, x := range factorization(n) {
a *= divSumSub(x.p, x.q)
}
return a
}
関数 divSumSub は σ(p, n) を計算します。あとは for ループで divSumSub の返り値を累積変数 a に掛け算していくだけです。
p が素数の場合、pa の約数は次のように簡単に求めることができます。
pa, pa-1, ... p2, p, 1
n の素因数分解が pa * qb だったとすると、その約数は次のようになります。
(pa, pa-1, ... p2, p, 1) * qb,
(pa, pa-1, ... p2, p, 1) * qb-1,
.....
(pa, pa-1, ... p2, p, 1) * q2,
(pa, pa-1, ... p2, p, 1) * q,
(pa, pa-1, ... p2, p, 1) * 1
たとえば、12 の約数は 24 = (1, 2, 4) と 3 = (1, 3) から、(1, 2, 4) * 1 と (1, 2, 4) * 3 のすべての要素 (1, 2, 4, 3, 6, 12) になります。
プログラムは次のようになります。
リスト : 約数をすべて求める
// 単純挿入ソート
func insertSort(ary []int) []int {
for i := 1; i < len(ary); i++ {
tmp := ary[i]
j := i - 1
for ; j >= 0 && tmp < ary[j]; j-- {
ary[j + 1] = ary[j]
}
ary[j + 1] = tmp
}
return ary
}
// pn の約数を求める
func divisorSub(p, q int) []int {
a := make([]int, q + 1)
for i := 0; i <= q; i++ {
a[i] = power(p, i)
}
return a
}
// 互いの要素を掛け算する
func product(xs, ys []int) []int {
a := make([]int, len(xs) * len(ys))
k := 0
for _, x := range xs {
for _, y := range ys {
a[k] = x * y
k++
}
}
return a
}
//
func divisor(n int) []int {
xs := factorization(n)
ys := divisorSub(xs[0].p, xs[0].q)
for i := 1; i < len(xs); i++ {
ys = product(divisorSub(xs[i].p, xs[i].q), ys)
}
return insertSort(ys)
}
関数 divisorSub は pn の約数をスライスに格納して返します。関数 product は 2 つのスライス xs、ys の要素を掛け合わせたものをスライスに格納して返します。あとは for ループで素因数分解した結果を順番に取り出し、Pow{p q} を divisorSub でスライスに変換して、それを product で累積変数 ys のスライスと掛け合わせていくだけです。
リスト : 完全数
func perfectNumber(n int) {
for x := 2; x <= n; x++ {
if divisorSum(x) - x == x {
fmt.Println(x)
}
}
}
完全数を求める perfectNumber は簡単です。x の約数の合計値を divisorSum で求め、その値から x を引いた値が x と等しければ完全数です。Println で x を表示します。
リスト : 友愛数
func yuuaiNumber(n int) {
for x := 2; x <= n; x++ {
m := divisorSum(x) - x
if x < m && x == divisorSum(m) - m {
fmt.Println(x, m)
}
}
}
友愛数を求める yuuaiNumber も簡単です。divisorSum で x の約数の合計値を求め、その値から x を引いた値を変数 m にセットします。m の約数の合計値から m を引いた値が x と等しければ、x と m は友愛数です。Println で x と m を表示します。同じ組を表示しないようにするため、x < m を条件に入れています。
パッケージ big の関数 (メソッド) を使うと、多倍長整数の計算は簡単にできます。Int を生成する関数と四則演算のメソッドを以下に示します。
関数 NewInt は整数 (int64) を多倍長整数に変換します。メソッド Int64 は多倍長整数を整数 (int64) に変換します。Add, Sub, Mul, Div は加減乗除を行うメソッドで、引数 x と y の演算結果をレシーバ z に代入し、その z を返します。
単純な代入を行うメソッドも用意されています。
Set は引数 x の値をレシーバ z に代入します。SetInt64 は引数 x を多倍長整数に変換して、その値をレシーバ z に代入します。どちらの関数も z を返します。
階乗の計算は次のようになります。
リスト : 階乗
// 再帰
func fact0(n int64) *big.Int {
if n == 0 {
return big.NewInt(1)
} else {
x := big.NewInt(n)
return x.Mul(x, fact0(n - 1))
}
}
// 繰り返し
func fact(n int64) *big.Int {
a := big.NewInt(1)
for ; n > 0; n-- {
a.Mul(a, big.NewInt(n))
}
return a
}
関数 fact0 は再帰定義で、fact は繰り返しでプログラムしています。階乗の定義そのままなので、とくに難しいところはないと思います。
次はフィボナッチ関数を作ります。
リスト : フィボナッチ関数
// 再帰
func fibo0(n int64) *big.Int {
if n < 2 {
return big.NewInt(n)
} else {
a := fibo0(n - 1)
return a.Add(a, fibo0(n - 2))
}
}
// 繰り返し
func fibo(n int64) *big.Int {
a := big.NewInt(0)
b := big.NewInt(1)
c := big.NewInt(0)
for ; n > 0; n-- {
c.Set(a)
a.Set(b)
b.Add(b, c)
}
return a
}
関数 fibo0 は再帰定義で、fibo は繰り返しでプログラムしています。fibo は定義そのままなので、難しいところはないでしょう。ただし、fibo0 は二重再帰なので実行時間はとても遅くなります。大きな値は計算しないでくださいね。fibo は 変数 c を用意して、Set で a の値を c に保存します。そして、a.Set(b) で a の値を b に書き換えて、b.add(b, c) で b に a + b の値を代入します。これを繰り返すことでフィボナッチ数列を求めることができます。
リスト : 累乗
func power(x, y int64) *big.Int {
switch {
case y == 0: return big.NewInt(1)
case y == 1: return big.NewInt(x)
default:
z := power(x, y / 2)
z.Mul(z, z) // z *= z
if y % 2 == 0 {
return z
} else {
return z.Mul(z, big.NewInt(x))
}
}
}
関数 power は再帰定義でプログラムしています。これも難しいところはないと思います。
分数を循環小数に直すのは簡単です。筆算と同じように計算していくだけです。次の図を見てください。
0 1 4 2 8 5 7
----------------
7 ) 1
0
-----
1 0 <-- 余り 1
7
-------
3 0
2 8
-------
2 0
1 4
-------
6 0
5 6
-------
4 0
3 5
-------
5 0
4 9
-----
1 <-- 余り 1
7 で割った余り 1 が 2 回現れていますね。これから先は同じ数列を繰り返すことがわかります。7 の剰余は 0 から 6 まであり、剰余が 0 の場合は割り切れるので循環小数にはなりません。現れる余りの数が限られているので、割り切れなければ循環することになるわけです。また、このことから循環節の長さは分母の値よりも小さいことがわかります。
リスト : 循環小数を求める
// n と等しい要素の位置を求める
func position(n int, xs []int) int {
for i, x := range xs {
if n == x {
return i
}
}
return -1
}
// 循環小数を求める
func repdec(m, n int) ([]int, []int) {
xs := make([]int, 0)
ys := make([]int, 0)
for {
p := m / n
q := m % n
if q == 0 {
return append(ys, p), []int{0}
} else {
n := position(q, xs)
if n >= 0 {
return ys[:n+1], append(ys[n+1:], p)
} else {
xs = append(xs, q)
ys = append(ys, p)
m = q * 10
}
}
}
}
関数 repdec(m, n) は m / n を循環小数に変換します。返り値は 2 つのスライスで、先頭のスライスが冒頭の小数部分を、次のスライスが循環節の部分を表します。途中で割り切れる場合は循環節を [0] とします。これ以降、冒頭の小数部分を有限小数部分と記述することにします。
変数 xs が余りを格納するスライス、変数 ys が商を格納するスライスです。最初に m と n の商と余りを計算して、変数 p と q にセットします。q が 0 ならば割り切れたので有限小数です。append で ys に p を追加し、それと [ ]int{0} を多値で返します。
割り切れない場合、余り q が xs にあるか関数 position でチェックします。同じ値を見つけた場合、ys を n + 1 の位置で 2 つに分けます。先頭部分が有限小数部分で、後半部分に p を追加したものが循環節になります。同じ値が見つからない場合は、p, q を xs, ys に追加して、m の値を q * 10 に書き換えて処理を繰り返します。
循環小数を分数に直すことも簡単にできます。循環小数 - Wikipedia によると、有限小数部分を a、循環節の小数表記を b、節の長さを n とすると、循環小数 x は次の式で表すことができる、とのことです。
1 1 1
x = a + b * (1 + ------ + ------- + ------- + ...)
10^n 10^2n 10^3n
10^n
= a + b * ----------
10^n - 1
ここで、カッコの中は初項 1, 公比 1 / (10^n) の無限等比級数になるので、その和は次の公式より求めることができます。
∞ a Σ arn = ----- (ただし |r| < 1) n=0 1 - r
簡単な例を示しましょう。
. .
0.142857 =
10^6
0.142857 * -------- = 142857 / 999999 = 1 / 7
10^6 - 1
.
0.16 =
10 1 6 10 15
0.1 + 0.06 * ---- = -- + --- * -- = ----- = 1 / 6
9 10 100 9 90
プログラムを作る場合、次のように考えると簡単です。
有限小数部分を表すリストを xs とすると
有限小数部分 = p / q
ただし p = xs を整数に変換
q = 10 ^ (len(xs) - 1)
循環節を表すリストを ys とすると
循環節 = p' / q'
ただし p' = ys を整数に変換
q' = (10 ^ len(ys)) - 1
p p' p * q' + p'
循環小数 = --- + -------- = -------------
q q * q' q * q'
冒頭の有限小数部分を分数に変換するのは簡単ですね。先頭が整数部分になるので、小数部分の桁はリスト xs の長さ - 1 になります。循環節だけを分数に変換する場合、たとえば 1 / 7 の循環節は [1,4,2,8,5,7] になりますが、分子 p' は 0.142857 * 10^6 = 142857 となるので、循環節を表すリストを整数に変換するだけでよいことがわかります。有限小数部分がある場合は、その桁数だけ循環節の部分を右シフトすればよいので、p' / q' に 1 / q を掛けるだけです。
リスト : 循環小数を分数に直す
// スライスを多倍長整数に変換する
func toNum(xs []int) *big.Int {
a := big.NewInt(0)
b := big.NewInt(10)
c := big.NewInt(0)
for _, x := range xs {
a.Mul(a, b)
c.SetInt64(int64(x))
a.Add(a, c)
}
return a
}
func fromRepdec(xs, ys []int) (int64, int64) {
x := big.NewInt(1)
p1 := toNum(xs)
q1 := power(10, int64(len(xs) - 1))
p2 := toNum(ys)
q2 := power(10, int64(len(ys)))
q2.Sub(q2, x) // q2 = q2 - 1
q1.Mul(q1, q2) // q1 = q1 * q2
q2.Mul(q2, p1)
q2.Add(q2, p2) // q2 = q2 * p1 + p2
x.GCD(nil, nil, q1, q2)
q1.Div(q1, x)
q2.Div(q2, x)
return q2.Int64(), q1.Int64()
}
アルゴリズムをそのままプログラムしただけですが、多倍長整数 Int を使って計算していることに注意してください。power は問題 27 で作成した累乗を求める関数、GCD は 2 つの多倍長整数の最大公約数を求めるメソッドです。
分数の計算はパッケージ math/big の構造体 Rat を使って行うことができますが、ここでは Go 言語のお勉強ということで、あえて分数を表す構造体 Ratio を作ることにします。最初に構造体 Ratio を定義します。
リスト : 分数の定義
// Ratio の定義
type Ratio struct {
p, q int
}
// 最大公約数を求める
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a % b)
}
// 絶対値を返す
func abs(n int) int {
if n < 0 {
return -n
}
return n
}
// Ratio の生成
func newRatio(p, q int) *Ratio {
r := new(Ratio)
if q < 0 {
p, q = -p, -q
}
a := gcd(abs(p), q)
r.p, r.q = p / a, q / a
return r
}
// Stringer の定義
func (r *Ratio) String() string {
return fmt.Sprintf("%d/%d", r.p, r.q)
}
Ratio のフィールド変数 p が分子で、q が分母を表します。p, q の型は int としましたが、パッケージ math/big の構造体 Rat は分子と分母を多倍長整数 Int で表しています。今回のパズルであれば、p, q の型は int でもかまいません。Ratio を生成するとき、gcd で最大公約数を求めて約分することに注意してください。それから、有理数の符号は分子に付けるので、分母 q が負の場合は p と q の符号を反転します。
次は四則演算を行うメソッドを定義します。
リスト：有理数の四則演算
// 加算
func (a *Ratio) addr(b *Ratio) *Ratio {
p := a.p * b.q + b.p * a.q
q := a.q * b.q
return newRatio(p, q)
}
// 減算
func (a *Ratio) subr(b *Ratio) *Ratio {
p := a.p * b.q - b.p * a.q
q := a.q * b.q
return newRatio(p, q)
}
// 乗算
func (a *Ratio) mulr(b *Ratio) *Ratio {
return newRatio(a.p * b.p, a.q * b.q)
}
// 除算
func (a *Ratio) divr(b *Ratio) *Ratio {
return newRatio(a.p * b.q, a.q * b.p)
}
有理数 (分数) の四則演算をそのままプログラムしただけなので、とくに難しいところはないと思います。
最後にパズルを解く関数 solver を作ります。
リスト : 小町分数
// n と等しい要素が xs にあるか
func member(n int, xs []int) bool {
for _, x := range xs {
if n == x { return true }
}
return false
}
func permSub(f func([]int), n, m int, xs []int) {
if len(xs) == m {
f(xs)
} else {
for i := 1; i <= n; i++ {
if !member(i, xs) {
permSub(f, n, m, append(xs, i))
}
}
}
}
// 順列の生成
func permutation(f func([]int), n, m int) {
permSub(f, n, m, make([]int, 0, m))
}
// 順列 [a, b, c, d, e, f, g, h, i]
func check(xs []int) {
if xs[0] < xs[3] && xs[3] < xs[6] {
x := newRatio(xs[0], xs[1] * 10 + xs[2])
y := newRatio(xs[3], xs[4] * 10 + xs[5])
z := newRatio(xs[6], xs[7] * 10 + xs[8])
a := x.addr(y).addr(z)
if a.p == 1 {
fmt.Printf("%d/%d%d + %d/%d%d + %d/%d%d = 1/%d\n",
xs[0], xs[1], xs[2],
xs[3], xs[4], xs[5],
xs[6], xs[7], xs[8], a.q)
}
}
}
func solver(){
permutation(check, 9, 9)
}
単純な生成検定法です。重複解を排除するため、xs[0] < xs[3] < xs[6] の条件を付けています。また、順列を生成するとき、このチェックを入れることで枝刈りと同じ効果を得ることができます。興味のある方は試してみてください。実行結果は次のようになります。
1/24 + 3/56 + 7/98 = 1/6 1/26 + 5/39 + 7/84 = 1/4 1/32 + 5/96 + 7/84 = 1/6 1/38 + 2/95 + 4/76 = 1/10 1/48 + 5/32 + 7/96 = 1/4 1/56 + 3/72 + 9/84 = 1/6 1/96 + 5/32 + 7/84 = 1/4 1/96 + 5/48 + 7/32 = 1/3 2/18 + 5/63 + 7/49 = 1/3 2/19 + 4/57 + 6/38 = 1/3 3/27 + 6/54 + 9/81 = 1/3 3/48 + 5/16 + 9/72 = 1/2 3/54 + 6/72 + 9/81 = 1/4 5/34 + 7/68 + 9/12 = 1/1
//
// yagp03.go : Yet Another Golang Probolems
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import (
"fmt"
"math/big"
)
//
// P21
//
// Pow の定義
type Pow struct {
p, q int
}
// Pow の生成
func newPow(p, q int) *Pow {
a := new(Pow)
a.p, a.q = p, q
return a
}
// Stringer の定義
func (p *Pow) String() string {
return fmt.Sprintf("(%d, %d)", p.p, p.q)
}
// m で割り切れる回数を求める
func factorSub(n, m int) (int, int) {
i := int(0)
for ; n % m == 0; n /= m {
i++
}
return i, n
}
// 素因数分解
func factorization(n int) []*Pow {
a := make([]*Pow, 0)
c, m := factorSub(n, 2)
if c > 0 {
a = append(a, newPow(2, c))
}
for i := int(3); m >= i * i; i += 2 {
c, m = factorSub(m, i)
if c > 0 {
a = append(a, newPow(i, c))
}
}
if m > 1 {
a = append(a, newPow(m, 1))
}
return a
}
// P22
func divisorNum(n int) int {
a := int(1)
for _, x := range factorization(n) {
a *= x.q + 1
}
return a
}
//
// P23
//
// 累乗の計算
func pow(x, y int) int {
if y == 0 {
return 1
} else if y == 1 {
return x
} else {
z := pow(x, y / 2)
if y % 2 == 0 {
return z * z
} else {
return z * z * x
}
}
}
// σ(p, n) の計算
func divSumSub(p, n int) int {
a := int(0)
for ; n > 0; n-- {
a += pow(p, n)
}
return a + 1
}
// 約数の和
func divisorSum(n int) int {
a := int(1)
for _, x := range factorization(n) {
a *= divSumSub(x.p, x.q)
}
return a
}
//
// P24
//
// 単純挿入ソート
func insertSort(ary []int) []int {
for i := 1; i < len(ary); i++ {
tmp := ary[i]
j := i - 1
for ; j >= 0 && tmp < ary[j]; j-- {
ary[j + 1] = ary[j]
}
ary[j + 1] = tmp
}
return ary
}
// pn の約数を求める
func divisorSub(p, q int) []int {
a := make([]int, q + 1)
for i := int(0); i <= q; i++ {
a[i] = pow(p, i)
}
return a
}
// 互いの要素を掛け算する
func product(xs, ys []int) []int {
a := make([]int, len(xs) * len(ys))
k := 0
for _, x := range xs {
for _, y := range ys {
a[k] = x * y
k++
}
}
return a
}
//
func divisor(n int) []int {
xs := factorization(n)
ys := divisorSub(xs[0].p, xs[0].q)
for i := 1; i < len(xs); i++ {
ys = product(divisorSub(xs[i].p, xs[i].q), ys)
}
return insertSort(ys)
}
// P25
func perfectNumber(n int) {
for x := int(2); x <= n; x++ {
if divisorSum(x) - x == x {
fmt.Println(x)
}
}
}
// P26
func yuuaiNumber(n int) {
for x := int(2); x <= n; x++ {
m := divisorSum(x) - x
if x < m && x == divisorSum(m) - m {
fmt.Println(x, m)
}
}
}
//
// P27
//
// 再帰
func fact0(n int64) *big.Int {
if n == 0 {
return big.NewInt(1)
} else {
x := big.NewInt(n)
return x.Mul(x, fact0(n - 1))
}
}
// 繰り返し
func fact(n int64) *big.Int {
a := big.NewInt(1)
for ; n > 0; n-- {
a.Mul(a, big.NewInt(n))
}
return a
}
// 再帰
func fibo0(n int64) *big.Int {
if n < 2 {
return big.NewInt(n)
} else {
a := fibo0(n - 1)
return a.Add(a, fibo0(n - 2))
}
}
// 繰り返し
func fibo(n int64) *big.Int {
a := big.NewInt(0)
b := big.NewInt(1)
c := big.NewInt(0)
for ; n > 0; n-- {
c.Set(a)
a.Set(b)
b.Add(b, c)
}
return a
}
// 再帰
func power(x, y int64) *big.Int {
switch {
case y == 0: return big.NewInt(1)
case y == 1: return big.NewInt(x)
default:
z := power(x, y / 2)
z.Mul(z, z) // z *= z
if y % 2 == 0 {
return z
} else {
return z.Mul(z, big.NewInt(x))
}
}
}
//
// P28
//
// n と等しい要素の位置を求める
func position(n int, xs []int) int {
for i, x := range xs {
if n == x {
return i
}
}
return -1
}
// 循環小数を求める
func repdec(m, n int) ([]int, []int) {
xs := make([]int, 0)
ys := make([]int, 0)
for {
p := m / n
q := m % n
if q == 0 {
return append(ys, p), []int{0}
} else {
n := position(q, xs)
if n >= 0 {
return ys[:n+1], append(ys[n+1:], p)
} else {
xs = append(xs, q)
ys = append(ys, p)
m = q * 10
}
}
}
}
//
// P29
//
// スライスを多倍長整数に変換する
func toNum(xs []int) *big.Int {
a := big.NewInt(0)
b := big.NewInt(10)
c := big.NewInt(0)
for _, x := range xs {
a.Mul(a, b)
c.SetInt64(int64(x))
a.Add(a, c)
}
return a
}
func fromRepdec(xs, ys []int) (int64, int64) {
x := big.NewInt(1)
p1 := toNum(xs)
q1 := power(10, int64(len(xs) - 1))
p2 := toNum(ys)
q2 := power(10, int64(len(ys)))
q2.Sub(q2, x) // q2 = q2 - 1
q1.Mul(q1, q2) // q1 = q1 * q2
q2.Mul(q2, p1)
q2.Add(q2, p2) // q2 = q2 * p1 + p2
x.GCD(nil, nil, q1, q2)
q1.Div(q1, x)
q2.Div(q2, x)
return q2.Int64(), q1.Int64()
}
//
// P30
//
// Ratio の定義
type Ratio struct {
p, q int
}
// 最大公約数を求める
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a % b)
}
// 絶対値を返す
func abs(n int) int {
if n < 0 {
return -n
}
return n
}
// Ratio の生成
func newRatio(p, q int) *Ratio {
r := new(Ratio)
if q < 0 {
p, q = -p, -q
}
a := gcd(abs(p), q)
r.p, r.q = p / a, q / a
return r
}
// Stringer の定義
func (r *Ratio) String() string {
return fmt.Sprintf("%d/%d", r.p, r.q)
}
// 加算
func (a *Ratio) addr(b *Ratio) *Ratio {
p := a.p * b.q + b.p * a.q
q := a.q * b.q
return newRatio(p, q)
}
// 減算
func (a *Ratio) subr(b *Ratio) *Ratio {
p := a.p * b.q - b.p * a.q
q := a.q * b.q
return newRatio(p, q)
}
// 乗算
func (a *Ratio) mulr(b *Ratio) *Ratio {
return newRatio(a.p * b.p, a.q * b.q)
}
// 除算
func (a *Ratio) divr(b *Ratio) *Ratio {
return newRatio(a.p * b.q, a.q * b.p)
}
// n と等しい要素が xs にあるか
func member(n int, xs []int) bool {
for _, x := range xs {
if n == x { return true }
}
return false
}
func permSub(f func([]int), n, m int, xs []int) {
if len(xs) == m {
f(xs)
} else {
for i := 1; i <= n; i++ {
if !member(i, xs) {
permSub(f, n, m, append(xs, i))
}
}
}
}
// 順列の生成
func permutation(f func([]int), n, m int) {
permSub(f, n, m, make([]int, 0, m))
}
// 順列 [a, b, c, d, e, f, g, h, i]
// 順列 [a, b, c, d, e, f, g, h, i]
func check(xs []int) {
if xs[0] < xs[3] && xs[3] < xs[6] {
x := newRatio(xs[0], xs[1] * 10 + xs[2])
y := newRatio(xs[3], xs[4] * 10 + xs[5])
z := newRatio(xs[6], xs[7] * 10 + xs[8])
a := x.addr(y).addr(z)
if a.p == 1 {
fmt.Printf("%d/%d%d + %d/%d%d + %d/%d%d = 1/%d\n",
xs[0], xs[1], xs[2],
xs[3], xs[4], xs[5],
xs[6], xs[7], xs[8], a.q)
}
}
}
func solver(){
permutation(check, 9, 9)
}
// 簡単なテスト
func main() {
fmt.Println("----- P21 -----")
fmt.Println(factorization(24))
fmt.Println(factorization(12345678))
fmt.Println(factorization(123456789))
fmt.Println(factorization(1234567890))
fmt.Println(factorization(1111111111))
fmt.Println("----- P22 -----")
fmt.Println(divisorNum(24))
fmt.Println(divisorNum(12345678))
fmt.Println(divisorNum(123456789))
fmt.Println(divisorNum(1234567890))
fmt.Println(divisorNum(1111111111))
fmt.Println("----- P23 -----")
fmt.Println(divisorSum(24))
fmt.Println(divisorSum(12345678))
fmt.Println(divisorSum(123456789))
fmt.Println(divisorSum(1234567890))
fmt.Println(divisorSum(1111111111))
fmt.Println("----- P24 -----")
fmt.Println(divisor(24))
fmt.Println(divisor(12345678))
fmt.Println(divisor(123456789))
fmt.Println(divisor(1234567890))
fmt.Println(divisor(1111111111))
fmt.Println("----- P25 -----")
perfectNumber(10000)
fmt.Println("----- P26 -----")
yuuaiNumber(100000)
fmt.Println("----- P27 -----")
fmt.Println(fact(10))
fmt.Println(fact(30))
fmt.Println(fact(50))
fmt.Println(fibo(100))
fmt.Println(fibo(101))
fmt.Println(fibo(150))
fmt.Println(fibo(151))
fmt.Println(fibo(200))
fmt.Println(fibo(201))
fmt.Println(power(2, 100))
fmt.Println(power(3, 100))
fmt.Println(power(5, 100))
fmt.Println("----- P28 -----")
fmt.Println(repdec(1, 2))
fmt.Println(repdec(1, 3))
fmt.Println(repdec(1, 6))
fmt.Println(repdec(1, 7))
fmt.Println(repdec(1, 9))
fmt.Println(repdec(1, 11))
fmt.Println(repdec(355, 113))
fmt.Println("----- P29 -----")
fmt.Println(fromRepdec([]int{0, 5}, []int{0}))
fmt.Println(fromRepdec([]int{0}, []int{3}))
fmt.Println(fromRepdec([]int{0, 1}, []int{6}))
fmt.Println(fromRepdec([]int{0}, []int{1,4,2,8,5,7}))
fmt.Println(fromRepdec([]int{0}, []int{1}))
fmt.Println(fromRepdec([]int{0}, []int{0,9}))
fmt.Println("----- P30 -----")
solver()
}
$ go run yagp03.go ----- P21 ----- [(2, 3) (3, 1)] [(2, 1) (3, 2) (47, 1) (14593, 1)] [(3, 2) (3607, 1) (3803, 1)] [(2, 1) (3, 2) (5, 1) (3607, 1) (3803, 1)] [(11, 1) (41, 1) (271, 1) (9091, 1)] ----- P22 ----- 8 24 12 48 16 ----- P23 ----- 60 27319968 178422816 3211610688 1246404096 ----- P24 ----- [1 2 3 4 6 8 12 24] [1 2 3 6 9 18 47 94 141 282 423 846 14593 29186 43779 87558 131337 262674 685871 1371742 2057613 4115226 6172839 12345678] [1 3 9 3607 3803 10821 11409 32463 34227 13717421 41152263 123456789] [1 2 3 5 6 9 10 15 18 30 45 90 3607 3803 7214 7606 10821 11409 18035 19015 21642 22818 32463 34227 36070 38030 54105 57045 64926 68454 108210 114090 162315 171135 324630 342270 13717421 27434842 41152263 68587105 82304526 123456789 137174210 205761315 246913578 411522630 617283945 1234567890] [1 11 41 271 451 2981 9091 11111 100001 122221 372731 2463661 4100041 27100271 101010101 1111111111] ----- P25 ----- 6 28 496 8128 ----- P26 ----- 220 284 1184 1210 2620 2924 5020 5564 6232 6368 10744 10856 12285 14595 17296 18416 63020 76084 66928 66992 67095 71145 69615 87633 79750 88730 ----- P27 ----- 3628800 265252859812191058636308480000000 30414093201713378043612608166064768844377641568960512000000000000 354224848179261915075 573147844013817084101 9969216677189303386214405760200 16130531424904581415797907386349 280571172992510140037611932413038677189525 453973694165307953197296969697410619233826 1267650600228229401496703205376 515377520732011331036461129765621272702107522001 7888609052210118054117285652827862296732064351090230047702789306640625 ----- P28 ----- [0 5] [0] [0] [3] [0 1] [6] [0] [1 4 2 8 5 7] [0] [1] [0] [0 9] [3] [1 4 1 5 9 2 9 2 0 3 5 3 9 8 2 3 0 0 8 8 4 9 5 5 7 5 2 2 1 2 3 8 9 3 8 0 5 3 0 9 7 3 4 5 1 3 2 7 4 3 3 6 2 8 3 1 8 5 8 4 0 7 0 7 9 6 4 6 0 1 7 6 9 9 1 1 5 0 4 4 2 4 7 7 8 7 6 1 0 6 1 9 4 6 9 0 2 6 5 4 8 6 7 2 5 6 6 3 7 1 6 8] ----- P29 ----- 1 2 1 3 1 6 1 7 1 9 1 11 ----- P30 ----- 1/24 + 3/56 + 7/98 = 1/6 1/26 + 5/39 + 7/84 = 1/4 1/32 + 5/96 + 7/84 = 1/6 1/38 + 2/95 + 4/76 = 1/10 1/48 + 5/32 + 7/96 = 1/4 1/56 + 3/72 + 9/84 = 1/6 1/96 + 5/32 + 7/84 = 1/4 1/96 + 5/48 + 7/32 = 1/3 2/18 + 5/63 + 7/49 = 1/3 2/19 + 4/57 + 6/38 = 1/3 3/27 + 6/54 + 9/81 = 1/3 3/48 + 5/16 + 9/72 = 1/2 3/54 + 6/72 + 9/81 = 1/4 5/34 + 7/68 + 9/12 = 1/1