パスワードを忘れた? アカウント作成
1094142 journal
日記

ken_non_sumの日記: 62: 三進数にはロマンがある 2

日記 by ken_non_sum

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 を使わずに済ませられたらよかったのですが。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2011年12月22日 14時35分 (#2070365)

    または「ほげ」言語のパラドックス
    再帰より12重のループのほうが「単純明瞭で正しい」

  • by Anonymous Coward on 2011年12月22日 16時05分 (#2070418)

    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]);

typodupeerror

にわかな奴ほど語りたがる -- あるハッカー

読み込み中...