このページは M.Hiroi が Go 言語の勉強で作成した簡単なプログラムをまとめたものです。拙作のページ Yet Another Prolog Problems や Yet Another Scheme Problems などの Go 言語バージョンになります。同じような問題が多くなると思いますが、あしからずご了承くださいませ。
整数 n から m までの和、二乗の和、三乗の和を求める関数 sumOfInt, sumOfSquare, sumOfCube を定義してください。
func sumOfInt(n, m int) int func sumOfSquare(n, m int) int func sumOfCube(n, m int) int
素因数分解とは、素数でない整数 (合成数) を素数の積の形に書き表すことです。たとえば、12 は 2 * 2 * 3 と素因数分解することができます。素因数分解を行う関数 primeFactor を定義してください。結果は画面 (標準出力) へ出力するものとします。
func primeFactor(n int)
下図に示すフィボナッチ関数 fibo を定義してください。
func fibo(n int) int
n 個の中から r 個を選ぶ組み合わせの数 \({}_n \mathrm{C}_r\) を求める関数 combNum(n, r) を定義してください。
func combNum(n, r int) int
次の公式を使って平方根の整数部分を求める関数 sqrtInt を定義してください。
式 (1) は、奇数 1 から 2n - 1 の総和は \(n^2\) になることを表しています。式 (2) のように、整数 m の値が \(n^2\) より大きくて \((n + 1)^2\) より小さいのであれば、\(m\) の平方根の整数部分は \(n\) であることがわかります。これは \(m\) から奇数 \(1, 3, 5, \ldots, (2n - 1), (2n + 1)\) を順番に引き算していき、引き算できなくなった時点の \(\frac{2n + 1}{2} = n\) が m の平方根になります。参考文献 [1] によると、この方法を「めのこ平方」と呼ぶそうです。
func sqrtInt(n int) int
sqrtInt(10) => 3 sqrtInt(100) => 10 sqrtInt(1000) => 31 sqrtInt(10000) => 100 sqrtInt(123456789) => 11111
点を多角形の形に並べたとき、その総数を「多角数 (polygonal number)」といいます。三角形に配置したものを三角数、四角形に配置したものを四角数、五角形に配置したものを五角数といいます。三角数、四角数、五角数を下図に示します。
１ ３ ６ 10 15
● ● ● ● ●
●● ●● ●● ●●
●●● ●●● ●●●
●●●● ●●●●
●●●●●
図 : 三角数
|
１ ４ ９ 16 25
● ●● ●●● ●●●● ●●●●●
●● ●●● ●●●● ●●●●●
●●● ●●●● ●●●●●
●●●● ●●●●●
●●●●●
図 : 四角数
|
１ ５ 12 22
● ● ● ●
● ● ● ● ● ●
● ● ● ●
● ● ● ● ● ●
● ● ● ● ●
● ● ●
● ● ● ●
● ● ● ●
● ● ● ●
図 : 五角数
n 番目の p 角数を求める関数 polygonalNum を定義してください。
func polygonalNum(p, n int) int
polygonalNum(3, 1) => 1 polygonalNum(3, 2) => 3 polygonalNum(3, 3) => 6 polygonalNum(4, 1) => 1 polygonalNum(4, 2) => 4 |
polygonalNum(4, 3) => 9 polygonalNum(5, 1) => 1 polygonalNum(5, 2) => 5 polygonalNum(5, 3) => 12 |
配列 (スライス) に格納されている実数 (float64) の平均値と標準偏差を求める関数 meanSD を定義してください。
データを \(x_1, x_2, \ldots , x_N\) とすると、総計量 \(T\) と平均値 \(M\) は次式で求めることができます。
平均値が同じ場合でも、データの特徴が異なる場合があります。たとえば、A = {4, 4, 5, 5, 5, 6, 6, 6, 7, 7} と B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} の平均値は 5.5 になります。A のデータは平均値の近くに集まっていてますが、B のデータはバラバラになっていますね。統計学では、ばらつきの大きさを表すために「分散 (variance)」という値を使います。分散 \(S^2\)の定義を次に示します。
分散の定義からわかるように、平均値から離れたデータが多いほど、分散の値は大きくなります。逆に、平均値に近いデータが多くなると分散は小さな値になります。そして、分散の平方根が「標準偏差 (SD : standard deviation)」になります。標準偏差は、ばらつきの大きさを表すのによく使われています。
リスト : テストデータ (乱数で作成した身長のデータ)
var height []float64 = []float64{
148.7, 149.5, 133.7, 157.9, 154.2, 147.8, 154.6, 159.1, 148.2, 153.1,
138.2, 138.7, 143.5, 153.2, 150.2, 157.3, 145.1, 157.2, 152.3, 148.3,
152.0, 146.0, 151.5, 139.4, 158.8, 147.6, 144.0, 145.8, 155.4, 155.5,
153.6, 138.5, 147.1, 149.6, 160.9, 148.9, 157.5, 155.1, 138.9, 153.0,
153.9, 150.9, 144.4, 160.3, 153.4, 163.0, 150.9, 153.3, 146.6, 153.3,
152.3, 153.3, 142.8, 149.0, 149.4, 156.5, 141.7, 146.2, 151.0, 156.5,
150.8, 141.0, 149.0, 163.2, 144.1, 147.1, 167.9, 155.3, 142.9, 148.7,
164.8, 154.1, 150.4, 154.2, 161.4, 155.0, 146.8, 154.2, 152.7, 149.7,
151.5, 154.5, 156.8, 150.3, 143.2, 149.5, 145.6, 140.4, 136.5, 146.9,
158.9, 144.4, 148.1, 155.5, 152.4, 153.3, 142.3, 155.3, 153.1, 152.3,
}
func meanSD(data []float64) (float64, float64)
meadSD(height) => 150.62699999999998 6.433472701426501
配列 (スライス) の部分列の中から最大値を求める関数 maximum と 最小値を求める関数 minimum を定義してください。maximum と minimum は値とその位置を返すものとします。また、部分列の指定はスライスと同じで、省略することができるものとします。
maximum(buff) // buff[0:len(buff)] の中から最大値を求める maximum(buff, s) // buff[s:len(buff)] の中から最大値を求める maximum(buff, s, e) // buff[s:e] の中から最大値を求める
func maximum(buff []int, args ... int) (int, int) func minimum(buff []int, args ... int) (int, int)
選択ソート (selection sort) は、ソートしていないデータの中から最小値（または最大値）を見つけ、それを先頭のデータと交換する、という手順を繰り返すことでソートを行います。最初は、すべてのデータの中から最小値を探し、それを配列の先頭 buff[0] と交換します。次は、buff[1] 以降のデータの中から最小値を探し、それを buff[1] と交換します。これを繰り返すことでソートすることができます。
[9 5 3 7 6 4 8] 3 と 9 を交換する
+ +
3 [5 9 7 6 4 8] 5 と 4 を交換する
+ +
3 4 [9 7 6 5 8] 9 と 5 を交換する
+ +
3 4 5 [7 6 9 8] 7 と 6 を交換する
+ +
3 4 5 6 [7 9 8] 7 と 7 を交換する
+
3 4 5 6 7 [9 8] 9 と 8 を交換してソート終了
+ +
図 : 選択ソート
配列 (スライス) を選択ソートする関数 selectSort を定義してください。
func selectSort(buff []int) []int
バブルソート (buble sort) は泡がぶくぶくと浮いてくるように、いちばん小さいデータが後ろから前に浮かび上がってくるアルゴリズムです。隣接する 2 つのデータを比較して、順序が逆であれば入れ換えます。これを順番に後ろから前に行っていけば、いちばん小さなデータは頂上に浮かび上がっているというわけです。先頭が決まったならば、残りのデータに対して同じことを行えば、2 番目には残りのデータの中でいちばん小さいものが浮かび上がります。これをデータ数だけ繰り返せばソートが完了します。
9 5 3 7 6 4 8 交換しない
~~~
9 5 3 7 6 4 8 交換する
~~~
9 5 3 7 4 6 8 交換する
~~~
9 5 3 4 7 6 8 交換しない
~~~
9 5 3 4 7 6 8 交換する
~~~
9 3 5 4 7 6 8 交換する
~~~
3 9 5 4 7 6 8 いちばん小さいデータが決定する
+ 残りのデータに対して同様な操作を行う
図 : バブルソート
スライスをバブルソートする関数 bubleSort を定義してください。
func bubleSort(buff []int) []int
まず最初に、単純なループでプログラムを作ってみましょう。
リスト : 整数の和、二乗の和、三乗の和
func sumOfInt(n, m int) int {
a := 0
for ; n <= m; n++ {
a += n
}
return a
}
func sumOfSquare(n, m int) int {
a := 0
for ; n <= m; n++ {
a += n * n
}
return a
}
func sumOfCube(n, m int) int {
a := 0
for ; n <= m; n++ {
a += n * n * n
}
return a
}
簡単なプログラムなので説明は不要ですね。ところで、数列の和を求める公式を使うと、プログラムはもっと簡単になります。
リスト : 別解
func sumOfInt0(n, m int) int {
sum := func(x int) int { return x * (x + 1) / 2}
return sum(m) - sum(n - 1)
}
func sumOfSquare0(n, m int) int {
sum := func(x int) int {
return x * (x + 1) * (2 * x + 1) / 6
}
return sum(m) - sum(n - 1)
}
func sumOfCube0(n, m int) int {
sum := func(x int) int {
return x * x * (x + 1) * (x + 1) / 4
}
return sum(m) - sum(n - 1)
}
公式を匿名関数でプログラムして、それを変数 sum にセットします。あとは sum(m) から sum(n - 1) を引き算すれば解を求めることができます。
リスト : 素因数分解
func primeFactor(n int) {
// 2 で割り算する
for ; n % 2 == 0; n /= 2 {
fmt.Print(2, " ")
}
// 奇数で割り算する
for i := 3; i * i <= n; i += 2 {
for ; n % i == 0; n /= i {
fmt.Print(i, " ")
}
}
if n > 1 {
fmt.Println(n)
}
}
最初に 2 で割り算します。それから、奇数で割り算していきます。割り算するときは、その数で割り切れるあいだは割り算を続けることに注意してください。たとえば、27 を素因数分解すると 3 * 3 * 3 になりますが、3 を一回だけしか割り算しないと、結果は 3 * 9 のように素数ではない数が含まれてしまいます。
簡単な実行例を示します。
primtFactor(12345678) => 2 3 3 47 14593 primtFactor(123456789) => 3 3 3607 3803 primtFactor(1234567890) => 2 3 3 5 3607 3803 primtFactor(1111111111) => 11 41 271 9091
なお、これはとても単純なアルゴリズムなので、大きな整数の素因数分解には適していません。巨大な合成数の素因数分解はとても難しい問題です。興味のある方は素因数分解について調べてみてください。
フィボナッチ関数は再帰呼び出しを使えば簡単にプログラムできます。
リスト : フィボナッチ関数
func fibo(n int) int {
if n < 2 {
return n
} else {
return fibo(n - 1) + fibo(n - 2)
}
}
関数 fibo は自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo の呼び出しをトレースすると下図のようになります。
fibo(5) ┬ fibo(4) ┬ fibo(3) ┬ fibo(2) ┬ fibo(1)
│ │ │ │
│ │ │ └ fibo(0)
│ │ └ fibo(1)
│ └ fibo(2) ┬ fibo(1)
│ │
│ └ fibo(0)
│
└ fibo(3) ┬ fibo(2) ┬ fibo(1)
│ │
│ └ fibo(0)
└ fibo(1)
図 : 関数 fibo のトレース
同じ値を何回も求めているため、関数 fibo の効率はとても悪いのです。この場合、二重再帰を「末尾再帰」に変換すると高速化することができます。そこで累算変数を使って、二重再帰を末尾再帰へ変換してみましょう。プログラムは次のようになります。
リスト : フィボナッチ関数（末尾再帰）
func fiboSub(n, a1, a2 int) int {
if n < 1 {
return a1
} else {
return fiboSub(n - 1, a2, a1 + a2)
}
}
func fiboi(n int) int {
return fiboSub(n, 0, 1)
}
関数 fiboSub の累算変数 a1 と a2 の使い方がポイントです。現在のフィボナッチ数を変数 a1 に、ひとつ先の値を変数 a2 に格納しておきます。あとは a1 と a2 を足し算して、新しいフィボナッチ数を計算すればいいわけです。fiboSub の呼び出しを下図に示します。
fiboSub(5, 0, 1)
fiboSub(4, 1, 1)
fiboSub(3, 1, 2)
fiboSub(2, 2, 3)
fiboSub(1, 3, 5)
fiboSub(0, 5, 8)
=> a1 の値 5 を返す
=> 5
=> 5
=> 5
=> 5
=> 5
図 : 関数 fiboSub の呼び出し
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行することができます。
Go 言語の場合、末尾再帰最適化はサポートされていませんが、末尾再帰を繰り返しに変換することは簡単です。関数 fibo を繰り返しに変換すると次のようになります。
リスト : フィボナッチ関数（繰り返し）
func fibol(n int) int {
a1, a2 := 0, 1
for ; n > 0; n-- {
a1, a2 = a2, a1 + a2
}
return a1
}
このように、末尾再帰は簡単に繰り返しに変換することができます。
組み合わせの数 \({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。
皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。Go 言語の整数 (int, int64 など) は多倍長整数ではないので、この公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。
この式は \({}_n \mathrm{C}_r\) と \({}_n \mathrm{C}_{r-1}\) の関係を表しています。あとは階乗やフィボナッチ関数と同じように、再帰定義を使って簡単にプログラムできます。次のリストを見てください。
リスト : 組み合わせの数を求める
func combNum(n, r int) int {
if n == r || r == 0 {
return 1
} else {
return combNum(n, r - 1) * (n - r + 1) / r
}
}
とても簡単ですね。ところで、M.Hiroi が使用している Go 言語の int は 64 bit なので、このプログラムでも桁あふれする場合があります。どこまで計算できるか試してみましょう。
combNum(32, 16) => 601080390 combNum(34, 17) => 2333606220 combNum(36, 18) => 9075135300 combNum(38, 19) => 35345263800 combNum(40, 20) => 137846528820 combNum(42, 21) => 538257874440 combNum(44, 22) => 2104098963720 combNum(46, 23) => 8233430727600 combNum(48, 24) => 32247603683100 combNum(50, 25) => 126410606437752 combNum(52, 26) => 495918532948104 combNum(54, 27) => 1946939425648112 combNum(56, 28) => 7648690600760440 combNum(58, 29) => 30067266499541040 combNum(60, 30) => 118264581564861424 combNum(62, 31) => -284401161134521734
Go 言語の場合、桁あふれが発生してもランタイムエラーは発生しません。もっと大きな値を計算したい場合はパッケージ math/big を使ってみてください。big には多倍長整数を扱う関数が多数用意されています。
リスト : めのこ平方
func sqrtInt(n int) int {
m := 1
for ; n >= m; m += 2 {
n -= m
}
return m / 2
}
アルゴリズムをそのままプログラムしただけなので、とくに難しいところは無いと思います。この方法はとても簡単ですが、数が大きくなると時間がかかるようになります。そこで、整数を 2 桁ずつ分けて計算していくことにします。次の図を見てください。
整数 6789 を 67 と 89 に分ける 1 + 3 + ... + 15 = 82 < 67 両辺を 100 倍すると 802 < 6700 < 6789 802 = 1 + 3 + ... + 159 (= 2 * 80 - 1) 161 + 163 < (6789 - 6400 = 389) < 161 + 163 + 165
整数 6789 を 67 と 89 に分けます。最初に 67 の平方根を求めます。この場合は 8 になり、82 < 67 を満たします。次に、この式を 100 倍します。すると、802 < 6700 になり、6700 に 89 を足した 6789 も 802 より大きくなります。802 は 1 から 159 までの奇数の総和であることはすぐにわかるので、6789 - 6400 = 389 から奇数 161, 163, ... を順番に引き算していけば 6789 の平方根を求めることができます。
プログラムは次のようになります。
リスト : めのこ平方 (改良版)
func sqrtIntSub(n, m int) int {
for ; n >= m; m += 2 {
n -= m
}
return m / 2
}
func sqrtInt1(n int) int {
if n < 100 {
return sqrtIntSub(n, 1)
} else {
m := 10 * sqrtInt1(n / 100)
return sqrtIntSub(n - m * m, 2 * m + 1)
}
}
sqrtInt1 は n の平方根の整数部分を求めます。n が 100 未満の場合は sqrtIntSub で平方根を求めます。これが再帰呼び出しの停止条件になります。n が 100 以上の場合は、n の下位 2 桁を取り除いた値 (n / 100) の平方根を sqrtInt1 で求め、その値を 10 倍して変数 m にセットします。そして、sqrIntSub で n - m * m から奇数 2 * m + 1, 2 * m + 3 ... を順番に引き算していって n の平方根を求めます。
多角数の点の増分を表に示すと、次のようになります。
n 三角数 四角数 五角数
---+-----------------------------------------------------------
1 | 1 1 1
2 | 3 = 1+2 4 = 1+3 5 = 1+4
3 | 6 = 1+2+3 9 = 1+3+5 12 = 1+4+7
4 | 10 = 1+2+3+4 16 = 1+3+5+7 22 = 1+4+7+10
5 | 15 = 1+2+3+4+5 25 = 1+3+5+7+9 35 = 1+4+7+10+13
6 | 21 = 1+2+3+4+5+6 36 = 1+3+5+7+9+11 51 = 1+4+7+10+13+16
・・・・・・ ・・・・・・・ ・・・・・
n | n(n + 1) / 2 n^2 n(3n - 1) / 2
表を見ればお分かりのように、三角数は公差 1、四角数は公差 2、五角数は公差 3、p 角数は公差 p - 2 の等差数列の和になります。初項を a, 公差を d とすると、等差数列の和 Sn は次式で求めることができます。
a = 1, d = p - 2 を代入して計算すると、多角数 \(P_{p,n}\) は次式で求めることができます。
この式を Go 言語でプログラムすると、次のようになります。
リスト : 多角数 (polygon.go)
func polygonalNum(p, n int) int {
return ((p - 2) * n * n - (p - 4) * n) / 2
}
リスト : 簡単なテスト
for p := 3; p <= 8; p++ {
for i := 1; i <= 20; i++ {
fmt.Print(polygonalNum(p, i), " ")
}
fmt.Println("")
}
それでは実行してみましょう。
1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 1 5 12 22 35 51 70 92 117 145 176 210 247 287 330 376 425 477 532 590 1 6 15 28 45 66 91 120 153 190 231 276 325 378 435 496 561 630 703 780 1 7 18 34 55 81 112 148 189 235 286 342 403 469 540 616 697 783 874 970 1 8 21 40 65 96 133 176 225 280 341 408 481 560 645 736 833 936 1045 1160
p 角数の初項は 1 で、第 2 項は p になります。多角数 - Wikipedia によると、多角数にはいろいろな面白い性質があるようです。
平均値と標準偏差を求めるプログラムは簡単です。次のリストを見てください。
リスト : 平均値と標準偏差
// 合計値を求める
func sum(buff []float64) float64 {
a := 0.0
for _, v := range buff {
a += v
}
return a
}
// 平均値と標準偏差を求める
func meanSD(buff []float64) (float64, float64) {
n := float64(len(buff))
m := sum(buff) / n
s := 0.0
for _, x := range buff {
s += (x - m) * (x - m)
}
return m, math.Sqrt(s / n)
}
プログラムは簡単なので、説明は不要でしょう。
参考文献 [2] によると、データを 1 回通読するだけで平均値と標準偏差 (分散) を求めることができるそうです。参考文献 [2] のプログラムを Go 言語で書き直すと、次のようになります。
リスト : 平均値と標準偏差 (2)
func meanSD2(buff []float64) (float64, float64) {
n := float64(len(buff))
m, s := 0.0, 0.0
for i, x := range buff {
x -= m
m += x / float64(i + 1)
s += float64(i) * x * x / float64(i + 1)
}
s = math.Sqrt(s / n)
return m, s
}
関数 meanSD2 でデータ height の平均値と標準偏差を求めると、次のようになります。
150.62699999999998 6.433472701426506
平均値は 150.63 cm で、標準偏差は 6.43 cm になりました。
リスト : 最大値と最小値
// 引数の取得
func getRange(buff, args []int) (int, int) {
var s, e int
switch len(args) {
case 0: s, e = 0, len(buff)
case 1: s, e = args[0], len(buff)
default: s, e = args[0], args[1]
}
return s, e
}
// 最小値を求める
func minimum(buff []int, args ... int) (int, int) {
s, e := getRange(buff, args)
m := s
for s++ ; s < e; s++ {
if buff[s] < buff[m] {
m = s
}
}
return buff[m], m
}
// 最大値を求める
func maximum(buff []int, args ... int) (int, int) {
s, e := getRange(buff, args)
m := s
for s++ ; s < e; s++ {
if buff[s] > buff[m] {
m = s
}
}
return buff[m], m
}
部分列の範囲指定は minimum, maximum の可変長引数 args で受け取ります。そして、部分列の範囲は関数 getRange で求めます。args の長さが 0 ならば、始点が 0 で終点が len(buff) になり、args の長さが 1 ならば、始点が args[0] で終点が len(buff) になります。それ以外の場合は始点が args[0] で終点が args[1] です。
minimum と maximum は getRange を呼び出して始点と終点を変数 s, e にセットします。そして、始点 s の要素を仮の最小値 (または最大値) として、その位置を変数 m にセットします。あとは、s + 1 から e 未満の範囲で buff[m] と buff[s] を比較して、buff[s] が小さい (または大きい) 場合は m の値を s に更新します。最後に buff[m] と m を返します。
リスト : 選択ソート
func selectSort(buff []int) []int {
k := len(buff)
for i := 0; i < k - 1; i++ {
v, m := minimum(buff, i, k)
buff[i], buff[m] = v, buff[i]
}
return buff
}
選択ソートは関数 minimum を使うと簡単です。データの個数を変数 k にセットします。最初のループで変数 i の値は 0 から k - 1 まで動きます。そして、minimum で buff[i] から buff[k - 1] までの中から最小値を探し、それを buff[i] と交換するだけです。
リスト : バブルソート
func bubleSort(buff []int) []int {
k := len(buff) - 1
for i := 0; i < k; i++ {
for j := k; j > i; j-- {
if buff[j - 1] > buff[j] {
buff[j - 1], buff[j] = buff[j], buff[j - 1]
}
}
}
return buff
}
最初のループで k 回 (データの個数 - 1) だけ繰り返します。2 番目のループで buff の後ろから前に向かって、確定していないデータを比較していき、もしも順番が逆になっていたら交換します。
選択ソートとバブルソートは簡単なアルゴリズムですが、データ数が多くなると時間がかかります。データ数を n とすると実行時間は n の 2 乗に比例します。選択ソートとバブルソートは遅いアルゴリズムなのです。
//
// yagp01.go : Yet Another Golang Problems
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import (
"fmt"
"math"
)
// P01
func sumOfInt(n, m int) int {
a := 0
for ; n <= m; n++ {
a += n
}
return a
}
func sumOfSquare(n, m int) int {
a := 0
for ; n <= m; n++ {
a += n * n
}
return a
}
func sumOfCube(n, m int) int {
a := 0
for ; n <= m; n++ {
a += n * n * n
}
return a
}
func sumOfInt0(n, m int) int {
sum := func(x int) int { return x * (x + 1) / 2}
return sum(m) - sum(n - 1)
}
func sumOfSquare0(n, m int) int {
sum := func(x int) int {
return x * (x + 1) * (2 * x + 1) / 6
}
return sum(m) - sum(n - 1)
}
func sumOfCube0(n, m int) int {
sum := func(x int) int {
return x * x * (x + 1) * (x + 1) / 4
}
return sum(m) - sum(n - 1)
}
// P02
func primeFactor(n int) {
// 2 で割り算する
for ; n % 2 == 0; n /= 2 {
fmt.Print(2, " ")
}
// 奇数で割り算する
for i := 3; i * i <= n; i += 2 {
for ; n % i == 0; n /= i {
fmt.Print(i, " ")
}
}
if n > 1 {
fmt.Println(n)
}
}
// P03
func fibo(n int) int {
if n < 2 {
return n
} else {
return fibo(n - 1) + fibo(n - 2)
}
}
func fiboSub(n, a1, a2 int) int {
if n < 1 {
return a1
} else {
return fiboSub(n - 1, a2, a1 + a2)
}
}
func fiboi(n int) int {
return fiboSub(n, 0, 1)
}
func fibol(n int) int {
a1, a2 := 0, 1
for ; n > 0; n-- {
a1, a2 = a2, a1 + a2
}
return a1
}
// P04
func combNum(n, r int) int {
if n == r || r == 0 {
return 1
} else {
return combNum(n, r - 1) * (n - r + 1) / r
}
}
// P05
func sqrtInt(n int) int {
m := 1
for ; n >= m; m += 2 {
n -= m
}
return m / 2
}
func sqrtIntSub(n, m int) int {
for ; n >= m; m += 2 {
n -= m
}
return m / 2
}
func sqrtInt1(n int) int {
if n < 100 {
return sqrtIntSub(n, 1)
} else {
m := 10 * sqrtInt1(n / 100)
return sqrtIntSub(n - m * m, 2 * m + 1)
}
}
// P06
func polygonalNum(p, n int) int {
return ((p - 2) * n * n - (p - 4) * n) / 2
}
// P07
// 身長のデータ
var height []float64 = []float64{
148.7, 149.5, 133.7, 157.9, 154.2, 147.8, 154.6, 159.1, 148.2, 153.1,
138.2, 138.7, 143.5, 153.2, 150.2, 157.3, 145.1, 157.2, 152.3, 148.3,
152.0, 146.0, 151.5, 139.4, 158.8, 147.6, 144.0, 145.8, 155.4, 155.5,
153.6, 138.5, 147.1, 149.6, 160.9, 148.9, 157.5, 155.1, 138.9, 153.0,
153.9, 150.9, 144.4, 160.3, 153.4, 163.0, 150.9, 153.3, 146.6, 153.3,
152.3, 153.3, 142.8, 149.0, 149.4, 156.5, 141.7, 146.2, 151.0, 156.5,
150.8, 141.0, 149.0, 163.2, 144.1, 147.1, 167.9, 155.3, 142.9, 148.7,
164.8, 154.1, 150.4, 154.2, 161.4, 155.0, 146.8, 154.2, 152.7, 149.7,
151.5, 154.5, 156.8, 150.3, 143.2, 149.5, 145.6, 140.4, 136.5, 146.9,
158.9, 144.4, 148.1, 155.5, 152.4, 153.3, 142.3, 155.3, 153.1, 152.3,
}
// 合計値を求める
func sum(buff []float64) float64 {
a := 0.0
for _, v := range buff {
a += v
}
return a
}
func meanSD(buff []float64) (float64, float64) {
n := float64(len(buff))
m := sum(buff) / n
s := 0.0
for _, x := range buff {
s += (x - m) * (x - m)
}
return m, math.Sqrt(s / n)
}
func meanSD2(buff []float64) (float64, float64) {
n := float64(len(buff))
m, s := 0.0, 0.0
for i, x := range buff {
x -= m
m += x / float64(i + 1)
s += float64(i) * x * x / float64(i + 1)
}
s = math.Sqrt(s / n)
return m, s
}
// P08
// 引数の取得
func getRange(buff, args []int) (int, int) {
var s, e int
switch len(args) {
case 0: s, e = 0, len(buff)
case 1: s, e = args[0], len(buff)
default: s, e = args[0], args[1]
}
return s, e
}
// 最小値を求める
func minimum(buff []int, args ... int) (int, int) {
s, e := getRange(buff, args)
m := s
for s++ ; s < e; s++ {
if buff[s] < buff[m] {
m = s
}
}
return buff[m], m
}
// 最大値を求める
func maximum(buff []int, args ... int) (int, int) {
s, e := getRange(buff, args)
m := s
for s++ ; s < e; s++ {
if buff[s] > buff[m] {
m = s
}
}
return buff[m], m
}
// P09
func selectSort(buff []int) []int {
k := len(buff)
for i := 0; i < k - 1; i++ {
v, m := minimum(buff, i, k)
buff[i], buff[m] = v, buff[i]
}
return buff
}
// P10
func bubleSort(buff []int) []int {
k := len(buff) - 1
for i := 0; i < k; i++ {
for j := k; j > i; j-- {
if buff[j - 1] > buff[j] {
buff[j - 1], buff[j] = buff[j], buff[j - 1]
}
}
}
return buff
}
// 簡単なテスト
func main() {
fmt.Println("----- P01 -----")
fmt.Println(sumOfInt(1, 1000))
fmt.Println(sumOfSquare(1, 1000))
fmt.Println(sumOfCube(1, 1000))
fmt.Println(sumOfInt0(1, 1000))
fmt.Println(sumOfSquare0(1, 1000))
fmt.Println(sumOfCube0(1, 1000))
fmt.Println("----- P02 -----")
primeFactor(12345678)
primeFactor(123456789)
primeFactor(1234567890)
primeFactor(1111111111)
fmt.Println("----- P03 -----")
for i := 0; i <= 10; i++ {
fmt.Println(i, ": ", fibo(i), fiboi(i), fibol(i))
}
for i := 31; i <= 40; i++ {
fmt.Println(i, ": ", fiboi(i), fibol(i))
}
fmt.Println("----- P04 -----")
for i := 16; i <= 31; i++ {
fmt.Println(i * 2, i, ": ", combNum(i * 2, i))
}
fmt.Println("----- P05 -----")
fmt.Println("10", sqrtInt(10), sqrtInt1(10))
fmt.Println("100", sqrtInt(100), sqrtInt1(100))
fmt.Println("1000", sqrtInt(1000), sqrtInt1(1000))
fmt.Println("123456789", sqrtInt(123456789), sqrtInt1(123456789))
fmt.Println("----- P06 -----")
for p := 3; p <= 8; p++ {
for i := 1; i <= 20; i++ {
fmt.Print(polygonalNum(p, i), " ")
}
fmt.Println("")
}
fmt.Println("----- P07 -----")
fmt.Println(meanSD(height))
fmt.Println(meanSD2(height))
fmt.Println("----- P08 -----")
a := []int{5,9,4,7,3,8,2,6,1,0}
fmt.Println(minimum(a))
fmt.Println(maximum(a))
fmt.Println(minimum(a, 2))
fmt.Println(maximum(a, 2))
fmt.Println(minimum(a, 2, 7))
fmt.Println(maximum(a, 2, 7))
fmt.Println("----- P09 -----")
b := []int{5,6,4,7,3,8,2,9,1,0}
fmt.Println(selectSort(b))
fmt.Println("----- P10 -----")
c := []int{5,6,4,7,3,8,2,9,1,0}
fmt.Println(bubleSort(c))
}
$ go run yagp01.go ----- P01 ----- 500500 333833500 250500250000 500500 333833500 250500250000 ----- P02 ----- 2 3 3 47 14593 3 3 3607 3803 2 3 3 5 3607 3803 11 41 271 9091 ----- P03 ----- 0 : 0 0 0 1 : 1 1 1 2 : 1 1 1 3 : 2 2 2 4 : 3 3 3 5 : 5 5 5 6 : 8 8 8 7 : 13 13 13 8 : 21 21 21 9 : 34 34 34 10 : 55 55 55 31 : 1346269 1346269 32 : 2178309 2178309 33 : 3524578 3524578 34 : 5702887 5702887 35 : 9227465 9227465 36 : 14930352 14930352 37 : 24157817 24157817 38 : 39088169 39088169 39 : 63245986 63245986 40 : 102334155 102334155 ----- P04 ----- 32 16 : 601080390 34 17 : 2333606220 36 18 : 9075135300 38 19 : 35345263800 40 20 : 137846528820 42 21 : 538257874440 44 22 : 2104098963720 46 23 : 8233430727600 48 24 : 32247603683100 50 25 : 126410606437752 52 26 : 495918532948104 54 27 : 1946939425648112 56 28 : 7648690600760440 58 29 : 30067266499541040 60 30 : 118264581564861424 62 31 : -284401161134521734 ----- P05 ----- 10 3 3 100 10 10 1000 31 31 123456789 11111 11111 ----- P06 ----- 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 1 5 12 22 35 51 70 92 117 145 176 210 247 287 330 376 425 477 532 590 1 6 15 28 45 66 91 120 153 190 231 276 325 378 435 496 561 630 703 780 1 7 18 34 55 81 112 148 189 235 286 342 403 469 540 616 697 783 874 970 1 8 21 40 65 96 133 176 225 280 341 408 481 560 645 736 833 936 1045 1160 ----- P07 ----- 150.62699999999998 6.433472701426501 150.62699999999998 6.433472701426506 ----- P08 ----- 0 9 9 1 0 9 8 5 2 6 8 5 ----- P09 ----- [0 1 2 3 4 5 6 7 8 9] ----- P10 ----- [0 1 2 3 4 5 6 7 8 9]