ken_non_sumの日記: 62: 三進数にはロマンがある 2
A7M 氏の日記エントリ「おいらも大概だけど…」で、おそらくは十二十三重にネストされたループのスクリーンショットが示されているのを見る。
しかし、インデントの深さという見た目のインパクトはともかく、処理としては、しごく単純かつ明瞭であって、へたにサブルーチンを定義しても二度手間でしかない気もする。
よく見ると、ループ変数の sisun はどれも [0, 3) の整数しかとっていないようだ。 {0, 1, 2} が 1 ダース 13 個ある順列組み合わせ問題として考えると、つまり 1213 ケタの三進数を用意してその各桁を拾っていけばうまく指数の組が作れるかもしれない。
コードはこんな感じか?
試しに動かして見るために指数の個数は 4 にしてある。
#include<stdio.h>
#include<string.h>
enum { NUMEXPTS = 4 };
int expt(int base, int exp)
{
if (exp == 0) {
return 1;
} else if (exp == 1) {
return base;
} else {
return expt(base * base, exp / 2) * expt(base, exp % 2);
}
}
int main(void)
{
int i, j, k, max;
int expts[NUMEXPTS] = { 0 };
max = expt(3, NUMEXPTS);
for (i = 0; i < max; i++) {
memset(expts, 0, sizeof(int) * NUMEXPTS);
for (k = 0, j = i; 0 < j; j /= 3, k++) {
expts[k] = j % 3;
}
/* to be replaced with the assignment */
for (k = 0; k < NUMEXPTS; k++) {
printf("%d ", expts[k]);
}
printf("\n");
}
return 0;
}
memset は蛇足かも。
1530 JST 追記
[Re: 手続き型脳の恐怖 (#2070365) from AC]
真意ははかりかねますが、書けと言われた気がしたので再帰で組を生成する方法も示しておきます。
ただし Scheme で。
(define (make-expts p n)
(if (= n 0) (list p)
(append (make-expts (cons 0 p) (- n 1))
(make-expts (cons 1 p) (- n 1))
(make-expts (cons 2 p) (- n 1)))))
(map reverse (make-expts '() 3)
;Value;
;((0 0 0) (0 0 1) (0 0 2)
; (0 1 0) (0 1 1) (0 1 2)
; (0 2 0) (0 2 1) (0 2 2)
; (1 0 0) (1 0 1) (1 0 2)
; (1 1 0) (1 1 1) (1 1 2)
; (1 2 0) (1 2 1) (1 2 2)
; (2 0 0) (2 0 1) (2 0 2)
; (2 1 0) (2 1 1) (2 1 2)
; (2 2 0) (2 2 1) (2 2 2))
append を使わずに済ませられたらよかったのですが。
手続き型脳の恐怖 (スコア:0)
または「ほげ」言語のパラドックス
再帰より12重のループのほうが「単純明瞭で正しい」
expt計算しなくても (スコア:0)
int sisu[NUMSISU] = { 0 };
int sisumax[NUMSISU];
for (int i = 0; i < NUMSISU; i++ )
sisumax[i] = 3;
do
{
for (int i = 0; i < NUMSISU; i++ )
printf("%2d,",sisu[i]);
printf("\n");
for (int i = 0; i < NUMSISU; i++ )
{
sisu[i] += 1;
if (sisu[i] == sisumax[i]) && i < NUMSISU - 1)
sisu[i] = 0;
else
break;
}
}
while (sisu[NUMSISU - 1] < sisumax[NUMSISU - 1]);