あなたは8つの同じサイズのボールを持っています(C)

http://d.hatena.ne.jp/torazuka/20130626/balls
http://qiita.com/Nabetani/items/62135c9b556f7cb9e07d

再帰を使ってシンプルに書けないかなと思ったのでやってみました。

#include <stdio.h>

int sum(int *x, int n)
{
    int s, i;

    s = 0;
    for (i = 0; i < n; i++)
        s += x[i];

    return s;
}

int solve(int *balls, int n)
{
    int d, m;

    if (n == 1)
        return 0;

    m = (n > 2) ? (n - 1) >> 1 : 1;
    d = sum(balls, m) - sum(balls + m, m);
    if (d > 0)
        return solve(balls, m);
    else if (d < 0)
        return solve(balls + m, m) + m;
    else
        return solve(balls + 2 * m, n - 2 * m) + 2 * m;
}

void test(int e, int n)
{
    int balls[n];
    int i, r;

    for (i = 0; i < n; i++)
        balls[i] = (i == e) ? 1 : 0;

    r = solve(balls, n);

    printf("n:%d e:%d r:%d ==> %s\n", n, e, r, r == e ? "ok" : "ng");
}

int main(void)
{
    int n, i;

    for (n = 1; n <= 20; n++)
        for (i = 0; i < n; i++)
            test(i, n);

    return 0;
}