問題
１つの正方形から始めて、その外周に正方形を足していくアルゴリズムがあるとする。
n回の繰り返しを行った後に正方形は何個になっているか？
方針
nが1増えるごとに、(n-1)*4個正方形が増える（但しn!=1の場合）
n
|
増大する正方形の数
|
全部の正方形の数
|
1
|
1
|
1
|
2
|
4(1*4)
|
5
|
3
|
8(2*4)
|
13
|
4
|
12(3*4)
|
25
|
・
|
・・・・・
|
・・・・
|
n
|
(n-1)*4
但しn!=1の場合
|
コード
swift3
//
// main.swift
// SquareBuildUp
//
// Created by 山崎真一郎 on 2017/02/05.
// Copyright © 2017 山崎真一郎. All rights reserved.
//
import Foundation
func GetAddNum(n: Int) -> Int
{
if (n == 1)
{
return 1
}
return (n - 1) * 4
}
var sum: Int = 0
for i in 1...10
{
sum += GetAddNum(n: i)
print("i:\(i) sum:\(sum)")
}
実行結果
i:1 sum:1
i:2 sum:5
i:3 sum:13
i:4 sum:25
i:5 sum:41
i:6 sum:61
i:7 sum:85
i:8 sum:113
i:9 sum:145
i:10 sum:181
Program ended with exit code: 0
解説
方針をそのままコードに落とすと上記のようになりますが、実際にはもっと良い方法があります。
正方形の数：
1 + 1*4 + 2*4 + 3*4 + ・・・・・・ (n - 1)*4
= 1 + 4 (1 + 2 + ・・・・・・ + (n-1))
ここで等差数列の公式を適用して
= 1 + 4 (n-1) * n / 2
= 2n^2 - 2n + 1
となるので、１回計算しただけで求まる事になります。
（上のコードはGetAddNumをn回繰り返す）
等差数列の公式：
1 + 2 + 3 + ・・・・・+(n - 1) + n = (n+1) * n / 2
