2026-11-07
parity.c
typedef struct Bounce Bounce;
struct Bounce {
Bounce (*next)(unsigned long* n, bool* result);
};
Bounce odd_step(unsigned long* n, bool* result);
Bounce even_step(unsigned long* n, bool* result) {
}
Bounce odd_step(unsigned long* n, bool* result) {
}
bool is_even(unsigned long n) {
bool result = false;
for (Bounce b = {even_step}; b.next;)
b = b.next(&n, &result);
return result;
}
is_even(n) は、n が偶数かどうかを「0は偶数、1以上の n は n - 1 が奇数なら偶数」「0は奇数ではない、1以上の n は n - 1 が偶数なら奇数」という2つの規則で判定します。n は10億にもなるので、2つの規則を互いに呼び合う関数のまま書くと、呼び出しが深くなりすぎてスタックが足りなくなります。そこで、相手の関数を呼ぶ代わりに次に呼ぶ関数を Bounce に入れて返し、呼ぶのは is_even のループに任せます。いまの *n が偶数かを調べる even_step と、奇数かを調べる odd_step を書いてください。答えが決まった関数は、その答えを *result に入れ、next が NULL の Bounce を返します。
入力例 1
is_even(10)
出力例 1
true
入力例 2
is_even(7)
出力例 2
false
入力例 3
is_even(0)
出力例 3
true
Reference
Reference
typedef struct Bounce Bounce;
struct Bounce {
Bounce (*next)(unsigned long* n, bool* result);
};
Bounce odd_step(unsigned long* n, bool* result);
Bounce even_step(unsigned long* n, bool* result) {
if (*n == 0) {
*result = true;
return (Bounce){NULL};
}
--*n;
return (Bounce){odd_step};
}
Bounce odd_step(unsigned long* n, bool* result) {
if (*n == 0) {
*result = false;
return (Bounce){NULL};
}
--*n;
return (Bounce){even_step};
}
bool is_even(unsigned long n) {
bool result = false;
for (Bounce b = {even_step}; b.next;)
b = b.next(&n, &result);
return result;
}
どちらの関数も、規則の2つの場合をそのまま書きます。*n が0なら答えが決まるので、even_step は true を、odd_step は false を *result に入れ、next が NULL の Bounce を返して終わりを知らせます。1以上なら *n を1減らし、相互再帰で呼ぶはずだった相手の関数を Bounce に入れて返します。呼ばずに返すので、関数はすぐに is_even へ戻り、スタックは1段より深くなりません。これは参考実装で、唯一の正解ではありません。Bounce に n を持たせて値で受け渡す書き方もあります。
C では、関数の戻り値の型に、その関数自身へのポインタの型を直接書けません。Bounce (*)(…) を返す関数の型を書こうとすると、型の中に同じ型が無限に現れるからです。構造体に包めば、struct Bounce という名前を先に宣言してから、その中で自分を返す関数ポインタを持てます。入力例1は even_step と odd_step が交互に10回 n を減らし、11回目に呼ばれた even_step が0を見て true を入れます。入力例2は7回減らしたあとの8回目が odd_step なので false です。入力例3は最初の even_step がそのまま true を入れます。