課題5: 制御構造を使ったアルゴリズム実装

課題概要

制御構造を使って、様々なアルゴリズムとデザインパターンを実装します。条件分岐、ループ、エラーハンドリングの実践的な使い方を学びます。

マンダトリー要件

要件1: 数値処理アルゴリズム

基本的な数値アルゴリズムを実装してください。

ファイル: algorithm/numbers.go

package algorithm

// IsPrime は素数判定
func IsPrime(n int) bool {
    // TODO: 実装してください
    // - 2未満はfalse
    // - 2はtrue
    // - 偶数はfalse
    // - √nまでの奇数で割り切れるかチェック
}

// Fibonacci はn番目のフィボナッチ数を返す
func Fibonacci(n int) int {
    // TODO: 実装してください
    // F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
}

// GCD は最大公約数を返す（ユークリッドの互除法）
func GCD(a, b int) int {
    // TODO: 実装してください
}

// Factorial は階乗を返す
func Factorial(n int) int {
    // TODO: 実装してください
    // - 0! = 1
    // - n! = n * (n-1)!
}

// SumDigits は数値の各桁の和を返す
func SumDigits(n int) int {
    // TODO: 実装してください
    // 例: 1234 → 10
}

// IsPerfectNumber は完全数判定
func IsPerfectNumber(n int) bool {
    // TODO: 実装してください
    // 完全数: 自分自身を除く約数の和が自分自身と等しい
    // 例: 6 = 1 + 2 + 3
}

要件2: 文字列処理パターン

文字列処理の典型的なパターンを実装してください。

ファイル: algorithm/strings.go

package algorithm

// IsPalindrome は回文判定
func IsPalindrome(s string) bool {
    // TODO: 実装してください
    // 空白、記号を無視し、大文字小文字を区別しない
    // 例: "A man, a plan, a canal: Panama" → true
}

// ReverseWords は単語を逆順にする
func ReverseWords(s string) string {
    // TODO: 実装してください
    // 例: "Hello World" → "World Hello"
}

// CountVowels は母音の数を返す
func CountVowels(s string) int {
    // TODO: 実装してください
    // a, e, i, o, u（大文字小文字両方）
}

// RemoveDuplicateChars は連続する重複文字を削除
func RemoveDuplicateChars(s string) string {
    // TODO: 実装してください
    // 例: "aaabbbccc" → "abc"
}

// Caesar はシーザー暗号で暗号化
func Caesar(s string, shift int) string {
    // TODO: 実装してください
    // アルファベットのみをシフト
    // 例: Caesar("abc", 1) → "bcd"
}

要件3: ファイル処理とエラーハンドリング

安全なファイル処理を実装してください。

ファイル: fileutil/fileutil.go

package fileutil

import (
    "bufio"
    "errors"
    "os"
)

var (
    ErrFileNotFound = errors.New("file not found")
    ErrEmptyFile    = errors.New("file is empty")
)

// ReadLines はファイルを行ごとに読み込む
func ReadLines(filename string) ([]string, error) {
    // TODO: 実装してください
    // - deferでファイルをクローズ
    // - 空ファイルはErrEmptyFileを返す
}

// CountLines はファイルの行数を返す
func CountLines(filename string) (int, error) {
    // TODO: 実装してください
}

// SearchInFile はファイル内の文字列を検索
func SearchInFile(filename, query string) ([]int, error) {
    // TODO: 実装してください
    // 見つかった行番号のスライスを返す
}

// SafeWrite は安全にファイルに書き込む
func SafeWrite(filename, content string) error {
    // TODO: 実装してください
    // - deferでファイルをクローズ
    // - panic発生時はrecoverして適切なエラーを返す
}

// CopyFile はファイルをコピー
func CopyFile(src, dst string) error {
    // TODO: 実装してください
    // - 両方のファイルをdeferでクローズ
}

要件4: コマンドラインツール

すべての機能を統合したCLIツールを作成してください。

ファイル: main.go

package main

import (
    "fmt"
    "os"
    "strconv"
    "yourproject/algorithm"
    "yourproject/fileutil"
)

func main() {
    if len(os.Args) < 2 {
        printUsage()
        os.Exit(1)
    }

    command := os.Args[1]

    switch command {
    case "prime":
        handlePrime()
    case "fib":
        handleFibonacci()
    case "palindrome":
        handlePalindrome()
    case "count":
        handleCount()
    default:
        fmt.Println("Unknown command:", command)
        printUsage()
        os.Exit(1)
    }
}

func printUsage() {
    fmt.Println("Usage:")
    fmt.Println("  prime <number>      - Check if number is prime")
    fmt.Println("  fib <n>            - Get nth Fibonacci number")
    fmt.Println("  palindrome <text>  - Check if text is palindrome")
    fmt.Println("  count <filename>   - Count lines in file")
}

func handlePrime() {
    if len(os.Args) < 3 {
        fmt.Println("Error: number required")
        os.Exit(1)
    }

    n, err := strconv.Atoi(os.Args[2])
    if err != nil {
        fmt.Println("Error: invalid number")
        os.Exit(1)
    }

    if algorithm.IsPrime(n) {
        fmt.Printf("%d is prime\n", n)
    } else {
        fmt.Printf("%d is not prime\n", n)
    }
}

func handleFibonacci() {
    // TODO: 実装してください
}

func handlePalindrome() {
    // TODO: 実装してください
}

func handleCount() {
    // TODO: 実装してください
}

期待される出力

# 素数判定
$ go run main.go prime 17
17 is prime

$ go run main.go prime 20
20 is not prime

# フィボナッチ数
$ go run main.go fib 10
55

# 回文判定
$ go run main.go palindrome "A man, a plan, a canal: Panama"
"A man, a plan, a canal: Panama" is a palindrome

# ファイルの行数カウント
$ echo -e "line1\nline2\nline3" > test.txt
$ go run main.go count test.txt
3 lines

ボーナス課題

ボーナス1: 高度なアルゴリズム

より複雑なアルゴリズムを実装してください。

package algorithm

// Sieve はエラトステネスの篩でn以下の素数を返す
func Sieve(n int) []int {
    // TODO: 実装してください
}

// LongestCommonSubsequence は最長共通部分列の長さを返す
func LongestCommonSubsequence(s1, s2 string) int {
    // TODO: 動的計画法で実装
}

// KMP はKMPアルゴリズムでパターンマッチング
func KMP(text, pattern string) []int {
    // TODO: パターンが見つかった位置のスライスを返す
}

ボーナス2: リトライメカニズム

失敗時に自動リトライする仕組みを実装してください。

package retry

import (
    "errors"
    "time"
)

var ErrMaxRetriesExceeded = errors.New("max retries exceeded")

// RetryConfig はリトライ設定
type RetryConfig struct {
    MaxRetries int
    Delay      time.Duration
    Backoff    float64  // 遅延の倍率（指数バックオフ）
}

// Retry は関数をリトライ実行
func Retry(fn func() error, config RetryConfig) error {
    // TODO: 実装してください
    // - 成功するまでMaxRetries回リトライ
    // - 各リトライの間にDelayだけ待機
    // - Backoff > 1.0 の場合、待機時間を指数的に増加
}

// 使用例
func main() {
    err := Retry(func() error {
        return doSomethingUnreliable()
    }, RetryConfig{
        MaxRetries: 3,
        Delay:      100 * time.Millisecond,
        Backoff:    2.0,
    })

    if err != nil {
        log.Fatal(err)
    }
}

ボーナス3: パターンマッチング言語

簡単なパターンマッチングエンジンを実装してください。

package pattern

// Match はシンプルなパターンマッチング
// サポート: * (任意の文字列), ? (任意の1文字)
func Match(pattern, text string) bool {
    // TODO: 実装してください
    // 例:
    // Match("h*o", "hello") → true
    // Match("h?llo", "hello") → true
    // Match("h*o", "hi") → false
}

// MatchMultiple は複数パターンのいずれかにマッチするか判定
func MatchMultiple(patterns []string, text string) bool {
    // TODO: いずれかのパターンにマッチすればtrue
}

評価基準

提出方法

submission/
├── go.mod
├── main.go
├── algorithm/
│   ├── numbers.go
│   ├── numbers_test.go
│   ├── strings.go
│   └── strings_test.go
├── fileutil/
│   ├── fileutil.go
│   └── fileutil_test.go
└── bonus/
    ├── retry/
    └── pattern/

ヒント

• 素数判定: √n まで調べれば十分
• フィボナッチ: 再帰ではなくループで実装
• 回文: 文字列を正規化してから比較
• defer: defer file.Close() はOpenの直後
• switch: fallthrough はほとんど使わない
• panic/recover: deferの中でrecoverを呼ぶ

テストケース

// algorithm/numbers_test.go
func TestIsPrime(t *testing.T) {
    tests := []struct {
        input    int
        expected bool
    }{
        {1, false},
        {2, true},
        {3, true},
        {4, false},
        {17, true},
        {100, false},
    }

    for _, tt := range tests {
        result := IsPrime(tt.input)
        if result != tt.expected {
            t.Errorf("IsPrime(%d) = %v; want %v",
                tt.input, result, tt.expected)
        }
    }
}

学習リソース

• Effective Go - Control structures
• Go by Example - Switch
• Go by Example - Defer
• Go by Example - Panic
• Go by Example - Recover