「問題解決力を鍛える!アルゴリズムとデータ構造」のコードをSwiftで書き換えていく 第2章

概要

Swiftの勉強のために、昔読んだ「問題解決力を鍛える!アルゴリズムとデータ構造」(通称けんちょん本)のコードをC++からSwiftに書き換えていく記事です。
けんちょん本の詳しい内容であるアルゴリズムの考え方などは本を買えば解決するものとして説明は行いません。
あくまで本のコードを書き換えてSwiftだったらこう書く、というのを学んだものを残します。
なお、コードはPlaygroundで実行可能な形式とすることで読者の手元で再現可能なものとします。

一部標準入力が記載している部分があるため、その場合はReadLine()を自身で実装し直して呼び出すか、意図的に値を引数で与えるようにしています。

※ReadLine()は本来Playgroundで使用できないが、以下の方法を取れば疑似的に再現可能なため、こちらの方法を使用することで標準入力を行う。

今回は第二章、計算量とオーダー記法を対象とします。

詳細

code2.1 一重のfor文(O(N))

// for Test
var inputs = ["10000"]
func readLine() -> String? {
    guard !inputs.isEmpty else {
        return nil
    }
    return inputs.removeFirst()
}
// for Test

// 以下Swiftで記載
let N = Int(readLine()!)!
var count = 0

for _ in 0..<N {
    count += 1
}

print(count) // "10000\n"

code2.2 二重のfor文(O(N^2))

// for Test
var inputs = ["10000"]
func readLine() -> String? {
    guard !inputs.isEmpty else {
        return nil
    }
    return inputs.removeFirst()
}
// for Test

// 以下Swiftで記載
let N = Int(readLine()!)!
var count = 0

for i in 0..<N {
    for j in 0..<N{
        count += 1
    }
}

print(count) // 100000000

code2.3 偶数の列挙

// for Test
var inputs = ["10000"]
func readLine() -> String? {
    guard !inputs.isEmpty else {
        return nil
    }
    return inputs.removeFirst()
}
// for Test

// 以下Swiftで記載
let N = Int(readLine()!)!
var count = 0

for i in stride(from: 0, to: N, by: 2) {
    print(i)
}

code2.4 最近点対問題に対する全探索

// 以下Swiftで記載
import Foundation

func calcDist(x1: Int, y1: Int, x2: Int, y2: Int) -> Double {
    return sqrt(Double((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)))
}

let N = 100
var x = [Int]()
var y = [Int]()

for _ in 0..<N {
    x.append(Int.random(in: -N*N...N*N))
    y.append(Int.random(in: -N*N...N*N))
}
// 求める値を十分大きい値で初期化しておく
var minimumDist = 10000000.0

// 探索開始
for i in 0..<N {
    for j in (i + 1)..<N {
        // (x[i],y[i])と(x[j],y[j])との距離
        let distIJ = calcDist(x1: x[i], y1: y[i], x2: x[j], y2: y[j])
        
        // 暫定最小値のminimumDistをdistIJと比べる
        if distIJ < minimumDist {
            minimumDist = distIJ
        }
    }
}

print(minimumDist) // ex."179.12007146045917"