(追記)
AtCoderのABC165のC問題を再帰と多重forで解いた。
・再帰
https://atcoder.jp/contests/abc165/submissions/12674026
・多重for
https://atcoder.jp/contests/abc165/submissions/12686227
(追記ここまで)
C++で、1〜4の数字を1回ずつ使った4桁の数を出力する。
const int N = 4; void hoge1() { int p[N] = {}; for (int i4 = 0; i4 < N; i4++){ if (p[i4]) continue; p[i4] = 1; for (int i3 = 0; i3 < N; i3++){ if (p[i3]) continue; p[i3] = 1; for (int i2 = 0; i2 < N; i2++){ if (p[i2]) continue; p[i2] = 1; for (int i1 = 0; i1 < N; i1++){ if (p[i1]) continue; printf("%d\n", (i4+1)*1000 + (i3+1)*100 + (i2+1)*10 + (i1+1)); } p[i2] = 0; } p[i3] = 0; } p[i4] = 0; } }
この4重のfor文は、読みにくいわけではないが、書くのが面倒だ。
また、Nを4から5に変更したいときにも、手間がかかる。
そこで、再帰を使って書き直す。
const int N = 4; void fuga(int _d) { static int p[N] = {}, q[N]; int d = _d - 1; for (int i = 0; i < N; i++){ if (p[i]) continue; q[d] = i + 1; if (d == 0){ printf("%d\n", q[3]*1000 + q[2]*100 + q[1]*10 + q[0]); continue; } p[i] = 1; fuga(d); p[i] = 0; } } void hoge2() { fuga(N); }
以下が出力。hoge1()とhoge2()は同じものを出力する。
1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321