C言語関係掲示板

過去ログ

No.483.覆面算を解く

[戻る] [ホームページ]
No.3524

覆面算を解く
投稿者---aki(2002/11/21 03:17:49)


覆面算を解くプログラムを作ろうとしています。

a, b, c, d, e, f の6つの変数にいろいろな値を与えて、これらの変数
がある条件を満たしているかどうかを調べる関数 test を呼びだします。

これらの変数は互いに異なる値を持ち、1〜9までのいずれかの整数値をとり
ます。下のプログラムでは、変数が同じ値である場合も調べているのでまず
いです。どのようにすればスッキリと書けるでしょうか。

#include <stdio.h>

int test(int a, int b, int c, int d, int e, int f)
{
    printf("%d %d %d %d %d %d\n", a, b, c, d, e, f);
    /* 省略 */
    return 0;
}

int main(void)
{
    int a, b, c, d, e, f;

    for (a = 1; a < 10; a++)
      for (b = 1; b < 10; b++)
        for (c = 1; c < 10; c++)
          for (d = 1; d < 10; d++)
            for (e = 1; e < 10; e++)
              for (f = 1; f < 10; f++)
                if (test(a, b, c, d, e, f))
                  goto found;
    printf("見つかりませんでした\n");
    return 1;
found:
    printf("found: %d %d %d %d %d %d", a, b, c, d, e, f);
    return 0;
}


No.3527

Re:覆面算を解く
投稿者---かずま(2002/11/21 11:29:41)


> これらの変数は互いに異なる値を持ち、1〜9までのいずれかの整数値をとり
> ます。下のプログラムでは、変数が同じ値である場合も調べているのでまず
> いです。どのようにすればスッキリと書けるでしょうか。

スッキリといえるかどうか分かりませんが、.....。
#include <stdio.h>

int test(int a, int b, int c, int d, int e, int f)
{
    printf("%d %d %d %d %d %d\n", a, b, c, d, e, f);
    /* 省略 */
    return 0;
}

int try(int *a, int *x, int n)
{
    int i;

    if (n == 6)
        return test(a[0], a[1], a[2], a[3], a[4], a[5]);
    for (i = 1; i < 10; i++) {
        if (x[i] == 0) {
            x[i] = 1;
            a[n] = i;
            if (try(a, x, n+1)) return 1;
            x[i] = 0;
        }
    }
    return 0;
}

int main(void)
{
    int a[6], x[10] = { 0 };

    if (try(a, x, 0))
        printf("found: %d %d %d %d %d %d",
            a[0], a[1], a[2], a[3], a[4], a[5], a[6]);
    else
        printf("not found\n");
    return 0;
}


No.3528

Re:覆面算を解く
投稿者---かずま(2002/11/21 11:32:14)


>        printf("found: %d %d %d %d %d %d",
>            a[0], a[1], a[2], a[3], a[4], a[5], a[6]);
訂正です。最後の , a[6] は余計でした。

No.3537

Re:覆面算を解く
投稿者---aki(2002/11/21 23:10:25)


>スッキリといえるかどうか分かりませんが、.....。

ありがとうございます。私が考えたものよりスッキリしているのでとり
あえず満足です。

しかし、ある変数(a〜f)の値を決めるにあたって、その値がすでに使われ
ていないかどうかを調べるためには、配列xを順番にノックして空き部屋
を探すしか方法はないのでしょうか。

for (i = 1; i < 10; i++) {
    if (x[i] == 0) {
        /*...*/
    }
}

再帰呼び出しのレベルが深いところでは、空き部屋が少なくなっている
ので、無駄なノックが増えてしまいます。人間だったら配列全体をみて、
ここが次の空き部屋だとすぐにわかるのですが。

普通の覆面算ではアルファベットの種類と数字の種類は共に10種類以内
ですが、数字の種類がもっと多くて、アルファベットの種類が数字の種
類と同じくらいある場合、なるべく効率よく調べるにはどうしたらよい
でしょうか。下のプログラムを実行すると約53秒かかりました。

#include <stdio.h>

#define NUM_ALPHA 10
#define NUM_DIGIT 12

int test(int *a) { /*...*/ return 0; }

int try(int *a, int *x, int n)
{
    int i;

    if (n == NUM_ALPHA)
        return test(a);
    for (i = 0; i < NUM_DIGIT; i++) { /* 0からに変更 */
        if (x[i] == 0) {
            x[i] = 1;
            a[n] = i;
            if (try(a, x, n+1)) return 1;
            x[i] = 0;
        }
    }
    return 0;
}

int main(void)
{
    int a[NUM_ALPHA], x[NUM_DIGIT] = {0};
    return !try(a, x, 0);
}


No.3539

Re:覆面算を解く
投稿者---かずま(2002/11/22 03:09:22)


> しかし、ある変数(a〜f)の値を決めるにあたって、その値がすでに使われ
> ていないかどうかを調べるためには、配列xを順番にノックして空き部屋
> を探すしか方法はないのでしょうか。

空き部屋の配列を双方向リストにするのはどうでしょうか。
約53秒が、約44秒になりませんか。
#include <stdio.h>

#define NUM_ALPHA 10
#define NUM_DIGIT 12

typedef struct { int next, prev; } Aki;

int test(int *a) { /*... */ return 0; }

int try(int *a, Aki *x, int n)
{
    int i;

    if (n == NUM_ALPHA)
        return test(a);
    for (i = x[NUM_DIGIT].next; i < NUM_DIGIT; i = x[i].next) {
        x[x[i].prev].next = x[i].next;
        x[x[i].next].prev = x[i].prev;
        a[n] = i;
        if (try(a, x, n+1)) return 1;
        x[x[i].next].prev = i;
        x[x[i].prev].next = i;
    }
    return 0;
}

int main(void)
{
    int a[NUM_ALPHA], i;
    Aki x[NUM_DIGIT + 1];

    for (i = 0; i <= NUM_DIGIT; i++) {
        x[i].prev = (i == 0) ? NUM_DIGIT : (i - 1);
        x[i].next = (i == NUM_DIGIT) ? 0 : (i + 1);
    }
    return !try(a, x, 0);
}


No.3541

Re:覆面算を解く
投稿者---かずま(2002/11/22 03:53:27)


最後に 1回余計に再起呼び出ししているのをやめると、もっと速くなるようです。
int try(int *a, Aki *x, int n)
{
    int i;

    for (i = x[NUM_DIGIT].next; i < NUM_DIGIT; i = x[i].next) {
        x[x[i].prev].next = x[i].next;
        x[x[i].next].prev = x[i].prev;
        a[n] = i;
        if ((n == NUM_ALPHA-1) ? test(a) : try(a, x, n+1)) return 1;
        x[x[i].next].prev = i;
        x[x[i].prev].next = i;
    }
    return 0;
}


No.3540

Re:覆面算を解く
投稿者---kikk(2002/11/22 03:30:33)


ども。


横から失礼します。

以下のコードは参考になりませんでしょか?


#include <stdio.h>

#define N 3

char num_tbl[] = "01234567890abcdef";

void genParmutation(int result[], int remained[], int n) {
	int selected, i;

	if (n<0) {
		for (i=0; i<=N; i++)
			putchar(num_tbl[result[i]]);
		putchar('\n');
		return;
	}
	for (i=0; i<=n; i++) {
		selected = remained[i];
		result[n] = selected;
		remained[i] = remained[n];
		genParmutation(result, remained, n-1);
		remained[i] = selected;
	}

	return;
}

int main() {
	int i;
	int result[1+N], remained[1+N];

	for (i=0; i<=N; i++)
		remained[i] = i;

	genParmutation(result, remained, N);

	return 0;
}


なお、順列の発生する順や変数の使い方が違います
(やれば/見ればわかりますけど)。


では。

No.3552

Re:覆面算を解く
投稿者---aki(2002/11/23 03:26:03)


>以下のコードは参考になりませんでしょか?

大変参考になりました。kikkさん、ありがとうございます。No.3537
のプログラムと比較するために、下のプログラムを走らせたところ、
21秒でした。スッキリしていてうまいアルゴリズムですね。多分、順
列生成の定跡的な方法なんでしょうけど知りませんでした。

かずまさんの方のプログラムは私の環境では38秒でした。こちらも勉
強になりました。ありがとうございます。

#include <stdio.h>

#define NUM_ALPHA 10
#define NUM_DIGIT 12

int test(int *a) { /*...*/ return 0; }

int try(int *a, int *x, int n)
{
    int i;

    if (n == NUM_ALPHA)
        return test(a);
    for (i = 0; i < NUM_DIGIT - n; i++) {
        a[n] = x[i];
        x[i] = x[NUM_DIGIT-n-1];
        if (try(a, x, n+1)) return 1;
        x[i] = a[n];
     }
    return 0;
}

int main(void)
{
    int i, a[NUM_ALPHA], x[NUM_DIGIT];

    for (i = 0; i < NUM_DIGIT; i++)
        x[i] = i;
    return !try(a, x, 0);
}