2026-10-15
reverse_invariant.c
#include <stddef.h>
bool reverse_invariant(int (*f)(const int *, size_t), int *a, size_t n) {
}
長さ n の配列 a に対する計算 f が、要素を逆順に並べ替えても同じ値を返すかを確かめる reverse_invariant を書いてください。f(a, n) の値と、a を逆順にしてから求めた f(a, n) の値が等しければ true、違えば false を返します。a はその場で並べ替えてかまいませんが、返る前に元の順に戻します。n が 0 や 1 のときも、f を2回呼んで比べます。入力例の sum は要素の総和を返す関数、first は先頭の要素を返す関数です。
入力例 1
reverse_invariant(sum, (int[]){3, 1, 2}, 3)
出力例 1
true
入力例 2
reverse_invariant(first, (int[]){3, 1, 2}, 3)
出力例 2
false
入力例 3
reverse_invariant(first, (int[]){7}, 1)
出力例 3
true
Reference
static void reverse(int *a, size_t n) {
for (size_t i = 0; i < n / 2; i++) {
int t = a[i];
a[i] = a[n - 1 - i];
a[n - 1 - i] = t;
}
}
bool reverse_invariant(int (*f)(const int *, size_t), int *a, size_t n) {
int before = f(a, n);
reverse(a, n);
int after = f(a, n);
reverse(a, n);
return before == after;
}
総和や最大値のように要素の順序に依らないはずの計算なら、正しい値を知らなくても、逆順の配列で結果が変わらないことは確かめられます。正しい出力の代わりに、入力の変え方と出力の変わり方の関係を確かめる検査をメタモルフィックテスト(metamorphic testing)といい、ここで使っている関係は「逆順にしても値が変わらない」です。先頭の要素を見る first は、この関係を満たさないので false になります。
reverse は a を直接書き換えるので、2回目の f の値を after に取っておいてから、もう一度 reverse を呼んで元の順に戻しています。逆順の逆順は元の並びなので、コピー用の配列は要りません。n が 0 や 1 なら reverse のループは1回も回らず、f の2回の呼び出しは同じ配列を見ます。
掲載したのは参考実装で、唯一の正解ではありません。a に触れたくないなら、malloc で確保した別の配列へ逆順にコピーして比べる書き方もあります。その場合は確保の失敗をどう返すかを決める必要があります。