課題6: 関数の実践

マンダトリー要件 (80点)

Part 1: 基本的な数学関数 (20点)

基本的な数学関数を実装してください。

ファイル: part1/math_basic.zig

const std = @import("std");

// TODO: 最大公約数（ユークリッドの互除法）
fn gcd(a: u64, b: u64) u64 {
    // 実装
}

// TODO: 最小公倍数
fn lcm(a: u64, b: u64) u64 {
    // 実装
    // ヒント: lcm(a, b) = (a * b) / gcd(a, b)
}

// TODO: べき乗計算
fn power(base: i64, exp: u32) i64 {
    // 実装（繰り返し二乗法を推奨）
}

// TODO: 階乗
fn factorial(n: u64) u64 {
    // 実装
}

// TODO: 組み合わせ C(n, k) = n! / (k! * (n-k)!)
fn combination(n: u64, k: u64) u64 {
    // 実装
}

pub fn main() void {
    std.debug.print("=== GCD/LCM ===\n", .{});
    std.debug.print("gcd(48, 18) = {}\n", .{gcd(48, 18)});
    std.debug.print("lcm(12, 18) = {}\n", .{lcm(12, 18)});

    std.debug.print("\n=== Power ===\n", .{});
    std.debug.print("2^10 = {}\n", .{power(2, 10)});
    std.debug.print("3^5 = {}\n", .{power(3, 5)});

    std.debug.print("\n=== Factorial ===\n", .{});
    std.debug.print("5! = {}\n", .{factorial(5)});
    std.debug.print("10! = {}\n", .{factorial(10)});

    std.debug.print("\n=== Combination ===\n", .{});
    std.debug.print("C(5, 2) = {}\n", .{combination(5, 2)});
    std.debug.print("C(10, 3) = {}\n", .{combination(10, 3)});
}

Part 2: comptime関数 (20点)

コンパイル時計算を活用した関数を実装してください。

ファイル: part2/comptime_funcs.zig

const std = @import("std");

// TODO: コンパイル時にフィボナッチ数を計算
fn fibonacci(comptime n: u32) u64 {
    // 実装
}

// TODO: コンパイル時に素数判定
fn isPrime(comptime n: u64) bool {
    // 実装
}

// TODO: ジェネリック関数: 配列の合計
fn sum(comptime T: type, array: []const T) T {
    // 実装
}

// TODO: ジェネリック関数: 配列の平均
fn average(comptime T: type, array: []const T) ?T {
    // 実装（空配列の場合はnull）
}

// TODO: ジェネリック関数: 配列の最大値と最小値を返す
fn minMax(comptime T: type, array: []const T) ?struct { min: T, max: T } {
    // 実装
}

pub fn main() void {
    std.debug.print("=== Compile-time Fibonacci ===\n", .{});
    const fib_10 = fibonacci(10);
    const fib_20 = fibonacci(20);
    std.debug.print("fib(10) = {}\n", .{fib_10});
    std.debug.print("fib(20) = {}\n", .{fib_20});

    std.debug.print("\n=== Compile-time Prime Check ===\n", .{});
    std.debug.print("17 is prime: {}\n", .{isPrime(17)});
    std.debug.print("18 is prime: {}\n", .{isPrime(18)});

    std.debug.print("\n=== Generic Sum ===\n", .{});
    const int_arr = [_]i32{ 1, 2, 3, 4, 5 };
    const float_arr = [_]f64{ 1.5, 2.5, 3.5 };
    std.debug.print("Sum of integers: {}\n", .{sum(i32, &int_arr)});
    std.debug.print("Sum of floats: {d:.1}\n", .{sum(f64, &float_arr)});

    std.debug.print("\n=== Generic Average ===\n", .{});
    if (average(i32, &int_arr)) |avg| {
        std.debug.print("Average: {}\n", .{avg});
    }

    std.debug.print("\n=== Generic Min/Max ===\n", .{});
    if (minMax(i32, &int_arr)) |result| {
        std.debug.print("Min: {}, Max: {}\n", .{result.min, result.max});
    }
}

Part 3: 高階関数 (20点)

関数を引数に取る高階関数を実装してください。

ファイル: part3/higher_order.zig

const std = @import("std");

// TODO: map関数（配列の各要素に関数を適用）
fn map(
    comptime T: type,
    comptime R: type,
    allocator: std.mem.Allocator,
    array: []const T,
    func: *const fn(T) R,
) ![]R {
    // 実装
}

// TODO: filter関数（条件を満たす要素を抽出）
fn filter(
    comptime T: type,
    allocator: std.mem.Allocator,
    array: []const T,
    predicate: *const fn(T) bool,
) ![]T {
    // 実装
}

// TODO: reduce関数（配列を単一の値に集約）
fn reduce(
    comptime T: type,
    comptime R: type,
    array: []const T,
    initial: R,
    func: *const fn(R, T) R,
) R {
    // 実装
}

// TODO: forEach関数（各要素に対して処理を実行）
fn forEach(
    comptime T: type,
    array: []const T,
    callback: *const fn(T) void,
) void {
    // 実装
}

// テスト用の関数
fn double(x: i32) i32 {
    return x * 2;
}

fn isEven(x: i32) bool {
    return @mod(x, 2) == 0;
}

fn add(acc: i32, x: i32) i32 {
    return acc + x;
}

fn printValue(x: i32) void {
    std.debug.print("{} ", .{x});
}

pub fn main() !void {
    const allocator = std.heap.page_allocator;
    const numbers = [_]i32{ 1, 2, 3, 4, 5 };

    std.debug.print("=== Map ===\n", .{});
    const doubled = try map(i32, i32, allocator, &numbers, &double);
    defer allocator.free(doubled);
    std.debug.print("Doubled: ", .{});
    for (doubled) |n| std.debug.print("{} ", .{n});
    std.debug.print("\n", .{});

    std.debug.print("\n=== Filter ===\n", .{});
    const evens = try filter(i32, allocator, &numbers, &isEven);
    defer allocator.free(evens);
    std.debug.print("Evens: ", .{});
    for (evens) |n| std.debug.print("{} ", .{n});
    std.debug.print("\n", .{});

    std.debug.print("\n=== Reduce ===\n", .{});
    const sum_result = reduce(i32, i32, &numbers, 0, &add);
    std.debug.print("Sum: {}\n", .{sum_result});

    std.debug.print("\n=== ForEach ===\n", .{});
    std.debug.print("Numbers: ", .{});
    forEach(i32, &numbers, &printValue);
    std.debug.print("\n", .{});
}

Part 4: 再帰関数 (20点)

再帰を使った関数を実装してください。

ファイル: part4/recursion.zig

const std = @import("std");

// TODO: ハノイの塔
fn hanoi(n: u32, from: []const u8, to: []const u8, aux: []const u8) void {
    // 実装
    // n枚のディスクを from から to へ移動（aux を補助として使用）
}

// TODO: 二分探索（再帰版）
fn binarySearch(comptime T: type, array: []const T, target: T, left: usize, right: usize) ?usize {
    // 実装
}

// TODO: クイックソート
fn quickSort(comptime T: type, array: []T) void {
    if (array.len <= 1) return;
    // 実装
}

// TODO: マージソート
fn mergeSort(comptime T: type, allocator: std.mem.Allocator, array: []T) !void {
    if (array.len <= 1) return;
    // 実装
}

// TODO: パスカルの三角形のn行目を生成
fn pascalRow(allocator: std.mem.Allocator, n: usize) ![]u64 {
    // 実装
}

pub fn main() !void {
    std.debug.print("=== Hanoi Tower ===\n", .{});
    hanoi(3, "A", "C", "B");

    std.debug.print("\n=== Binary Search ===\n", .{});
    const sorted = [_]i32{ 1, 3, 5, 7, 9, 11, 13, 15 };
    if (binarySearch(i32, &sorted, 7, 0, sorted.len)) |index| {
        std.debug.print("Found 7 at index {}\n", .{index});
    }

    std.debug.print("\n=== Quick Sort ===\n", .{});
    var arr1 = [_]i32{ 5, 2, 8, 1, 9, 3 };
    quickSort(i32, &arr1);
    std.debug.print("Sorted: ", .{});
    for (arr1) |n| std.debug.print("{} ", .{n});
    std.debug.print("\n", .{});

    std.debug.print("\n=== Merge Sort ===\n", .{});
    const allocator = std.heap.page_allocator;
    var arr2 = [_]i32{ 5, 2, 8, 1, 9, 3 };
    try mergeSort(i32, allocator, &arr2);
    std.debug.print("Sorted: ", .{});
    for (arr2) |n| std.debug.print("{} ", .{n});
    std.debug.print("\n", .{});

    std.debug.print("\n=== Pascal's Triangle ===\n", .{});
    for (0..6) |i| {
        const row = try pascalRow(allocator, i);
        defer allocator.free(row);
        for (row) |n| std.debug.print("{} ", .{n});
        std.debug.print("\n", .{});
    }
}

ボーナス課題 (20点)

Bonus 1: メモ化フィボナッチ (10点)

メモ化を使った効率的なフィボナッチ関数を実装してください。

ファイル: bonus1/memoization.zig

const std = @import("std");

const Memoizer = struct {
    cache: std.AutoHashMap(u64, u64),
    allocator: std.mem.Allocator,

    pub fn init(allocator: std.mem.Allocator) Memoizer {
        return Memoizer{
            .cache = std.AutoHashMap(u64, u64).init(allocator),
            .allocator = allocator,
        };
    }

    pub fn deinit(self: *Memoizer) void {
        self.cache.deinit();
    }

    // TODO: メモ化付きフィボナッチ
    pub fn fibonacci(self: *Memoizer, n: u64) !u64 {
        // 実装
        // 1. キャッシュをチェック
        // 2. キャッシュにあれば返す
        // 3. なければ計算してキャッシュに保存
    }
};

pub fn main() !void {
    const allocator = std.heap.page_allocator;
    var memo = Memoizer.init(allocator);
    defer memo.deinit();

    std.debug.print("Memoized Fibonacci:\n", .{});
    for (0..45) |i| {
        const result = try memo.fibonacci(@intCast(i));
        std.debug.print("fib({}) = {}\n", .{i, result});
    }
}

Bonus 2: 関数合成 (10点)

関数合成を実装してください。

ファイル: bonus2/composition.zig

const std = @import("std");

// TODO: 2つの関数を合成
fn compose(
    comptime A: type,
    comptime B: type,
    comptime C: type,
    f: *const fn(B) C,
    g: *const fn(A) B,
) fn(A) C {
    // 実装
    // (f ∘ g)(x) = f(g(x))
}

// TODO: カリー化（部分適用）
fn curry(
    comptime A: type,
    comptime B: type,
    comptime R: type,
    comptime a_val: A,
) fn(B) R {
    // 実装
}

// テスト用関数
fn addOne(x: i32) i32 {
    return x + 1;
}

fn double(x: i32) i32 {
    return x * 2;
}

fn square(x: i32) i32 {
    return x * x;
}

pub fn main() void {
    // 関数合成のテスト
    const addOneThenDouble = compose(i32, i32, i32, &double, &addOne);
    const doubleThenSquare = compose(i32, i32, i32, &square, &double);

    std.debug.print("(addOne then double)(5) = {}\n", .{addOneThenDouble(5)});
    std.debug.print("(double then square)(5) = {}\n", .{doubleThenSquare(5)});
}

評価基準

項目 配点
Part 1: 基本的な数学関数 20点
Part 2: comptime関数 20点
Part 3: 高階関数 20点
Part 4: 再帰関数 20点
**マンダトリー合計** **80点**
Bonus 1: メモ化フィボナッチ 10点
Bonus 2: 関数合成 10点
**ボーナス合計** **20点**

合格基準

  • マンダトリー: 64点以上で合格（80点満点の80%）
  • ボーナス: 追加評価（最終成績の加算）

    • 提出方法

    exercise06/
├── part1/
│   └── math_basic.zig
├── part2/
│   └── comptime_funcs.zig
├── part3/
│   └── higher_order.zig
├── part4/
│   └── recursion.zig
├── bonus1/
│   └── memoization.zig
└── bonus2/
    └── composition.zig

    テスト実行

    # マンダトリー
zig run part1/math_basic.zig
zig run part2/comptime_funcs.zig
zig run part3/higher_order.zig
zig run part4/recursion.zig

# ボーナス
zig run bonus1/memoization.zig
zig run bonus2/composition.zig

    ヒント

  • ユークリッドの互除法:
fn gcd(a: u64, b: u64) u64 {
    if (b == 0) return a;
    return gcd(b, a % b);
}

  • 繰り返し二乗法:
// power(2, 10)の場合
// 2^10 = (2^5)^2 = ((2^2)^2 * 2)^2

  • 高階関数のアロケーション:
var result = std.ArrayList(T).init(allocator);
defer result.deinit();
try result.append(item);
return result.toOwnedSlice();

  • ハノイの塔:
// n=1: from -> to
// n>1:
//   1. n-1枚を from -> aux
//   2. 1枚を from -> to
//   3. n-1枚を aux -> to

参考資料

  • Zig Language Reference - Functions: https://ziglang.org/documentation/master/#Functions
  • Ziglearn - Generic Types: https://ziglearn.org/chapter-2/#generic-types
  • Ziglearn - Comptime: https://ziglearn.org/chapter-2/#comptime

Previous
第6章: 関数
Next
第7章: ポインタ