C言語関係掲示板過去ログ１０６４

過去ログ

No．１０６４　あるパズル　階乗をマクロで実装する方法

No.13912

並び順表作成とマクロ
投稿者---とおり(2004/05/10 14:39:25)

あるパズルを解くプログラムを作ろうとしたのですが、
その下準備段階でいきなり詰まってしまいました。
やりたいことは、table変数に項目の全並び順を設定することです。

・※1:表作成
項目が[ABC]の3つなら、
    table[0][0-2] = { 'A', 'B', 'C' }
    table[1][0-2] = { 'A', 'C', 'B' }
    table[2][0-2] = { 'B', 'A', 'C' }
    table[3][0-2] = { 'B', 'C', 'A' }
    table[4][0-2] = { 'C', 'A', 'B' }
    table[5][0-2] = { 'C', 'B', 'A' }
項目が[ABCD]の4つなら、
    table[ 0][0-3] = { 'A', 'B', 'C', 'D' }
    ...
    table[23][0-3] = { 'D', 'C', 'B', 'A' }
for文で回すだけで出来るだろうと思っていたのですが、
いざやってみるとうまく組めませんでした。
いい方法をご存知の方よろしくお願いします。

・※2:表サイズ
項目数に変更があったときに、
const char item[] = { 'A', 'B', 'C' };
    ↓
const char item[] = { 'A', 'B', 'C', 'D' };
と、1ヶ所変更するだけで済むようにしたいと考えています。
今のプログラムのSIZE算出部を、
#define SIZE (3 * 2 * 1)
    ↓
#define SIZE FACT(NUM)    /* FACT():階乗マクロ */
のようにできたら実現できるのですが、
階乗をマクロで実装する方法はないでしょうか。

---

#include <stdio.h>

#define ARRAYSIZE(array) (sizeof(array) / sizeof(array[0]))

const char item[] = { 'A', 'B', 'C' };

#define NUM  ARRAYSIZE(item)
#define SIZE (3 * 2 * 1)        /* ※2:表サイズ */

char table[SIZE][NUM];

void make(char table[][NUM], const char item[], int num);
void disp(const char val[], int num);

int main(void)
{
    int i;

    make(table, item, NUM);

    for ( i = 0; i < SIZE; i++ )
        disp(table[i], NUM);

    return 0;
}

void make(char table[][NUM], const char item[], int num)
{
    /* ※1:表作成 */
    table[0][0] = 'A';  table[0][1] = 'B';    table[0][2] = 'C';
    table[1][0] = 'A';  table[1][1] = 'C';    table[1][2] = 'B';
    table[2][0] = 'B';  table[2][1] = 'A';    table[2][2] = 'C';
    table[3][0] = 'B';  table[3][1] = 'C';    table[3][2] = 'A';
    table[4][0] = 'C';  table[4][1] = 'A';    table[4][2] = 'B';
    table[5][0] = 'C';  table[5][1] = 'B';    table[5][2] = 'A';
}

void disp(const char val[], int num)
{
    int i;

    printf("[%c", val[0]);
    for ( i = 1; i < num; i++ )
        printf(" %c", val[i]);
    printf("]\n");
}

No.13915

Re:並び順表作成とマクロ
投稿者---かずま(2004/05/10 18:44:30)

> #define SIZE FACT(NUM)    /* FACT():階乗マクロ */
> のようにできたら実現できるのですが、
> 階乗をマクロで実装する方法はないでしょうか。

NUM が sizeof を含んでいるのでプリプロセッサでは評価できないでしょう。
階乗の計算は実行時に行うものとして、次のプログラムはいかがでしょうか？

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARRAYSIZE(array)  (sizeof(array) / sizeof(array[0]))
#define NUM  ARRAYSIZE(item)

char item[] = { 'A', 'B', 'C' };
char (*table)[NUM];

int  factorial(int n);
int  permutate(int i, int j);
void make_table(int n);
void disp(const char val[], int num);

int main(void)
{
    int i, n = factorial(NUM);

    make_table(n);
    for (i = 0; i < n; i++)
        disp(table[i], NUM);
    return 0;
}

int factorial(int n)
{
    int i, f = 1;
    for (i = n; i > 0; i--) f *= i;
    return f;
}

int permutate(int i, int j)
{
    int k, c;

    if (j == NUM) {
        memcpy(table[i], item, NUM);
        return i+1;
    }
    for (k = j; k < NUM; k++) {
        c = item[k]; memmove(item+j+1, item+j, k-j); item[j] = c;
        i = permutate(i, j+1);
        c = item[j]; memmove(item+j, item+j+1, k-j); item[k] = c;
    }
    return i;
}

void make_table(int n)
{
    table = malloc(n * NUM);
    permutate(0, 0);
}

void disp(const char val[], int num)
{
    int i;

    printf("[%c", val[0]);
    for (i = 1; i < num; i++)
        printf(" %c", val[i]);
    printf("]\n");
}

No.13927

Re:並び順表作成とマクロ
投稿者---かずま(2004/05/10 23:33:26)

> 階乗の計算は実行時に行うものとして、次のプログラムはいかがでしょうか？

permutation と書くつもりだったのを、permutate と書いてしまいました。
お詫びといっては何ですが、再帰を使わないプログラムを書いてみました。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM  (sizeof item / sizeof item[0])

char item[] = { 'A', 'B', 'C' };
char (*table)[NUM];

void make(int n);
void disp(const char val[], int n);
int  perm(void);

int main(void)
{
    int i, n = 1;

    for (i = NUM; i > 0; i--) n *= i;
    make(n);
    for (i = 0; i < n; i++) disp(table[i], NUM);
    return 0;
}

void make(int n)
{
    int i;

    table = malloc(n * NUM);
    memcpy(table[0], item, NUM);
    for (i = 1; perm(); i++) memcpy(table[i], item, NUM);
}

void disp(const char val[], int n)
{
    int i;

    printf("[%c", val[0]);
    for (i = 1; i < n; i++) printf(" %c", val[i]);
    printf("]\n");
}

int perm(void)
{
    int i = NUM, j, k, t;

    while (--i > 0 && item[i-1] >= item[i]) ;
    if (i <= 0) return 0;
    k = i;
    for (j = NUM; i < --j; i++)
        t = item[i], item[i] = item[j], item[j] = t;
    t = item[k-1];
    for (i = k; item[i] <= t; i++) ;
    item[k-1] = item[i], item[i] = t;
    return 1;
}

No.13931		Re:並び順表作成とマクロ投稿者---とおり(2004/05/11 13:47:59)
		返信ありがとうございます。 > NUM が sizeof を含んでいるのでプリプロセッサでは評価できないでしょう。 [4 * ]を追加するだけっていう、人の手ならものすごく簡単なことなので、マクロでももしかしたらと思ったんですが、残念です。プログラムありがとうございます。変数名をいじったり、動きを試してみてなんとか理解できました。 ※2:表サイズ・配列へのポインタを使うことによって通常の2次元配列と同等の使い勝手を確保している。ほとんど使ったことないんですが、配列へのポインタって便利ですね。 ※1:表作成・item変数のconstを外し、この中身を操作することによって実現している。・j位置の項目をA→B→Cと変化させ、再帰関数に投げたあと、元に戻す。・j位置が末尾まできたらtable変数にコピーしてリターン。なるほど、constを外したitem変数がキモですね。 item変数を直接操作するとは思いつきませんでした。 2つ目のプログラムはこれから読んでみますが、ぱっと見た感じ苦戦しそう。 1つ目の考え方の方がシンプルで分かりやすそうなので、とりあえずこちらで進めてみます。ありがとうございました。

No.13954		あるパズル投稿者---とおり(2004/05/11 21:30:35)
		おかげで解くことができました。 TV番組の平成教育委員会で見たのですが、詳細は忘れてしまったので自分で勝手に決めました。 --- 数字カードが5枚と演算子カードが4枚ある。 [2][3][5][7][11] [+][-][][/] 数字カードと演算子カードを交互に置き、答えが一番大きくなる並べ方を求めよ。 ※すべてのカードを使うこと ※[/]は小数点以下切り捨て ※演算子の優先順位はすべて同じ例) 　　[11][+][2][][3][-][5][/][7] 　　11 + 2 = 13 　　→ 13 * 3 = 39 　　→ 39 - 5 = 34 　　→ 34 / 7 = 4 　　答え:4

No.13959

Re:あるパズル
投稿者---かずま(2004/05/12 01:18:25)

面白そうなパズルですね。私もプログラムを書いてみました。

#include <stdio.h>
#include <string.h>

int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
int mul(int a, int b) { return a * b; }
int dvd(int a, int b) { return a / b; }

int (*op[4])(int, int) = { add, sub, mul, dvd };
int opr[4] = { 0, 1, 2, 3 };
int num[5] = { 2, 3, 5, 7, 11 };
int o[4], n[5], val;

void check(void)
{
    int v = op[opr[0]](num[0], num[1]);
    v = op[opr[1]](v, num[2]);
    v = op[opr[2]](v, num[3]);
    v = op[opr[3]](v, num[4]);
    if (v > val)
        val = v,  memcpy(o, opr, sizeof o),  memcpy(n, num, sizeof n);
}
    
void perm_op(int k)
{
    int i, t;
    if (k == 4) check();
    else
        for (i = k; i < 4; i++) {
            t = opr[k], opr[k] = opr[i], opr[i] = t;
            perm_op(k+1);
            t = opr[k], opr[k] = opr[i], opr[i] = t;
        }
}

void perm_num(int k)
{
    int i, t;
    if (k == 5) perm_op(0);
    else
        for (i = k; i < 5; i++) {
            t = num[k], num[k] = num[i], num[i] = t;
            perm_num(k+1);
            t = num[k], num[k] = num[i], num[i] = t;
        }
}

#define X(o) "+-*/"[o]

int main(void)
{
    perm_num(0);
    printf("%d %c %d %c %d %c %d %c %d = %d\n", n[0], X(o[0]),
        n[1], X(o[1]), n[2], X(o[2]), n[3], X(o[3]), n[4], val);
    return 0;
}