C言語関係掲示板

過去ログ

No.３０２．四則演算と括弧と4桁の数字を使って10にするゲーム

[戻る]　[ホームページ]
No.1814
教えてください
投稿者---musashi(2002/06/26 01:11:46)


四則演算と括弧と4桁の数字を使って10にするというゲームで、0000から9999までの10000個の組み合わせのうち、10ができない組み合わせは何%か調べよ。
という課題が出されました。
数字の組み合わせはfor文を４つ使って表現するということを思いついたのですが、演算子の組み合わせをうまく表現することができません。どうすればいいか教えていただけませんか?
No.1827
Re:教えてください
投稿者---かずま(2002/06/26 19:58:17)


> 四則演算と括弧と4桁の数字を使って10にするというゲームで、0000から9999までの10000個の組み合わせのうち、10ができない組み合わせは何%か調べよ。

「教えてください」というのは不適切な題名ですが、面白そうな問題なので
やってみました。正解かどうかわかりませんので、正解がわかりましたら、
「教えてください」
#include <stdio.h>

typedef int (*Op)(int, int);

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 div(int a, int b) { return b ? a / b : 9999; }

Op o[] = { add, sub, mul, div };

int main()
{
  int a, b, c, d, i, j, k, n = 0;

  for (a = 0; a < 10; a++)
    for (b = 0; b < 10; b++)
      for (c = 0; c < 10; c++)
        for (d = 0; d < 10; d++)
          for (i = 0; i < 4; i++)
            for (j = 0; j < 4; j++)
              for (k = 0; k < 4; k++)
                n +=
                  (o[i](a, o[j](b, o[k](c, d))) != 10) +
                  (o[i](a, o[k](o[j](b, c), d)) != 10) +
                  (o[j](o[i](a, b), o[k](c, d)) != 10) +
                  (o[k](o[i](a, o[j](b, c)), d) != 10) +
                  (o[k](o[j](o[i](a, b), c), d) != 10);
  printf("%f %%\n", n * 100.0 / (10000 * 4 * 4 * 4 * 5));
  return 0;
}

No.1828
Re:教えてください
投稿者---かずま(2002/06/26 20:10:36)


> 面白そうな問題なのでやってみました。

このプログラムは、次のものを別の式として扱うので、正しくないようですね。
失礼しました。

　1+(2+(3+4))=10
　1+((2+3)+4)=10
　(1+2)+(3+4)=10
　(1+(2+3))+4=10
　((1+2)+3)+4=10
No.1829
Re:教えてください
投稿者---musashi(2002/06/26 21:08:19)


>> 面白そうな問題なのでやってみました。
>

考えていただき、ありがとうございます。
このプログラムについて質問なのですが、Opというのは一体何なのでしょうか？知識不足なので、自分にはわかりません。お答えいただければありがたいです。
No.1838
Re:教えてください
投稿者---かずま(2002/06/27 02:06:27)


> このプログラムについて質問なのですが、Opというのは一体何なのでしょうか？

typedef をご存知ありませんか。

Op は、型名です。Op は、ポインタ型です。関数へのポインタです。その関数は、
引数が(int, int) で int を返す関数です。
Op は、引数が (int, int) で int を返す関数へのポインタという型を表します。

typedef を使わないですまそうとすれば、o の宣言を次のように書けばよいだけです。

int (*o[])(int, int) = { add, sub, mul, div };

o は、変数です。o の型は配列です。ポインタの配列です。
そのポインタは関数へのポインタです。その関数は、引数が (int, int) で、
int を返す関数です。
o は、引数が (int, int) で int を返す関数へのポインタの配列変数です。
No.1847
Re:教えてください
投稿者---musashi(2002/06/27 18:07:59)


かずまさん、詳しい解説ありがとうございます。
おかげでよくわかりました。
このプログラムを元に、もう少し自分で考えてみようと思います。
No.1850
Re:教えてください
投稿者---かずま(2002/06/27 18:48:04)


> このプログラムを元に、もう少し自分で考えてみようと思います。

この問題、難しすぎませんか。
1 * (5 / 3) * 6 も 10 になると考えていいんでしょうか。
それだと、単純な整数演算では出来なくなるように思うんですが。
No.1851
Re:教えてください
投稿者---musashi(2002/06/27 19:07:02)


>この問題、難しすぎませんか。
全くその通りだと思います。自分の頭ではやり方が思い浮かびませんでしたし。
>1 * (5 / 3) * 6 も 10 になると考えていいんでしょうか。
いいみたいです。
>それだと、単純な整数演算では出来なくなるように思うんですが。
整数演算で考えるより、実数も考えた方が作りやすいのですか？
No.1852
Re:教えてください
投稿者---かずま(2002/06/27 19:45:06)


>> 1 * (5 / 3) * 6 も 10 になると考えていいんでしょうか。
> いいみたいです。
>> それだと、単純な整数演算では出来なくなるように思うんですが。
> 整数演算で考えるより、実数も考えた方が作りやすいのですか？

整数演算では、5/3 は 1 です。
浮動小数点演算では、5/3 は 1.6666666666666667 です。
6倍して 10になる保証はありません。

割り切れない場合は、分子と分母を整数で保持し、最後に 10 になるか
どうかを判定する「複雑な整数演算」が必要ではないでしょうか
ということです。
No.1853
Re:教えてください
投稿者---musashi(2002/06/27 20:00:54)


>割り切れない場合は、分子と分母を整数で保持し、最後に 10 になるか
>どうかを判定する「複雑な整数演算」が必要ではないでしょうか
>ということです。

なるほど、そういうことも考慮しなければいけないということですね。
やはりこれは難しい！
No.1854
Re:教えてください
投稿者---かずま(2002/06/27 20:17:42)


>>割り切れない場合は、分子と分母を整数で保持し、最後に 10 になるか
>>どうかを判定する「複雑な整数演算」が必要ではないでしょうか

間違っていますが、こんな感じ。
#include <stdio.h>

typedef struct {
    int n, d;     /* 分子(numerator) と 分母(denominator) */
} Frac;           /* 分数(fraction) */

Frac add(Frac a, Frac b)
{
    a.n = a.n * b.d + b.n * a.d;
    a.d *= b.d;
    return a;
}

Frac sub(Frac a, Frac b) { b.n = -b.n; return add(a, b); }

Frac mul(Frac a, Frac b) { a.n *= b.n; a.d *= b.d; return a; }

Frac div(Frac a, Frac b)
{ 
    if (b.n == 0)
        a.n = 999999;
    else {
        a.n *= b.d;
        a.d *= b.n;
    }
    return a;
}

typedef Frac (*Op)(Frac, Frac);

Op o[] = { add, sub, mul, div };

int main()
{
  Frac a, b, c, d, x;
  int i, j, k, n = 0;

  a.d = b.d = c.d = d.d = 1;
  for (a.n = 0; a.n < 10; a.n++)
    for (b.n = 0; b.n < 10; b.n++)
      for (c.n = 0; c.n < 10; c.n++)
        for (d.n = 0; d.n < 10; d.n++)
          for (i = 0; i < 4; i++)
            for (j = 0; j < 4; j++)
              for (k = 0; k < 4; k++) {
                x = o[i](a, o[j](b, o[k](c, d)));
                n += (x.n != x.d * 10);
                x = o[i](a, o[k](o[j](b, c), d));
                n += (x.n != x.d * 10);
                x = o[j](o[i](a, b), o[k](c, d));
                n += (x.n != x.d * 10);
                x = o[k](o[i](a, o[j](b, c)), d);
                n += (x.n != x.d * 10);
                x = o[k](o[j](o[i](a, b), c), d);
                n += (x.n != x.d * 10);
              }
  printf("%f %%\n", n * 100.0 / (10000 * 4 * 4 * 4 * 5));
  return 0;
}

No.1855
Re:教えてください
投稿者---musashi(2002/06/27 20:40:56)


>間違っていますが、こんな感じ。

間違っているとのことですが、どこがおかしいのでしょうか？
どこが間違っているかわかりません。
教えていただけますか？
No.1863
Re:教えてください
投稿者---かずま(2002/06/28 14:05:30)


> 間違っているとのことですが、どこがおかしいのでしょうか？

No.1828 に書いたはずですが。
#include <stdio.h>

typedef struct {
    int n, d;     /* 分子(numerator) と 分母(denominator) */
} Frac;           /* 分数(fraction) */

Frac add(Frac a, Frac b) {
    a.n = a.n * b.d + b.n * a.d;  a.d *= b.d;  return a; }

Frac sub(Frac a, Frac b) {
    a.n = a.n * b.d - b.n * a.d;  a.d *= b.d;  return a; }

Frac mul(Frac a, Frac b) { a.n *= b.n;  a.d *= b.d;  return a; }

Frac div(Frac a, Frac b) {
    if (b.n) { a.n *= b.d; a.d *= b.n; } else a.n = 9999;  return a; }

int ten(Frac x) { return x.n == x.d * 10; }

typedef Frac (*Optr)(Frac, Frac);

Optr o[] = { add, sub, mul, div };
char s[] = "+-*/";

void make_ten(int d1, int d2, int d3, int d4)
{
    Frac  a, b, c, d;    int  i, j, k;

    a.n = d1;  b.n = d2;  c.n = d3;  d.n = d4;
    a.d = b.d = c.d = d.d = 1;
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            for (k = 0; k < 4; k++) {
                if (ten(o[i](a, o[j](b, o[k](c, d)))))
                     printf("%d %c (%d %c (%d %c %d)) = 10\n",
                         a.n, s[i], b.n, s[j], c.n, s[k], d.n);
                if (ten(o[i](a, o[k](o[j](b, c), d))))
                     printf("%d %c ((%d %c %d) %c %d) = 10\n",
                         a.n, s[i], b.n, s[j], c.n, s[k], d.n);
                if (ten(o[j](o[i](a, b), o[k](c, d))))
                     printf("(%d %c %d) %c (%d %c %d) = 10\n",
                         a.n, s[i], b.n, s[j], c.n, s[k], d.n);
                if (ten(o[k](o[i](a, o[j](b, c)), d)))
                     printf("(%d %c (%d %c %d)) %c %d = 10\n",
                         a.n, s[i], b.n, s[j], c.n, s[k], d.n);
                if (ten(o[k](o[j](o[i](a, b), c), d)))
                     printf("((%d %c %d) %c %d) %c %d = 10\n",
                         a.n, s[i], b.n, s[j], c.n, s[k], d.n);
            }
        }
    }
}

int main()
{
    int  a, b, c, d;

    while (printf("4 digits: "), scanf("%1d%1d%1d%1d", &a,&b,&c,&d)==4)
        make_ten(a, b, c, d);
    return 0;
}

このプログラムを実行し、1234 を入力すると、
  4 digits: 1234
  1 + (2 + (3 + 4)) = 10
  1 + ((2 + 3) + 4) = 10
  (1 + 2) + (3 + 4) = 10
  (1 + (2 + 3)) + 4 = 10
  ((1 + 2) + 3) + 4 = 10
  1 * ((2 * 3) + 4) = 10
  (1 * (2 * 3)) + 4 = 10
  ((1 * 2) * 3) + 4 = 10
  4 digits: q
となりますが、これは、本来
1+2+3+4 と 1*2*3+4 の 2つの式と数えるべきではないでしょうか。
No.1865
Re:教えてください
投稿者---Aki(2002/06/28 14:28:42)


>　4 digits: 1234
> 1 + (2 + (3 + 4)) = 10
> 1 + ((2 + 3) + 4) = 10
> (1 + 2) + (3 + 4) = 10
> (1 + (2 + 3)) + 4 = 10
> ((1 + 2) + 3) + 4 = 10
> 1 * ((2 * 3) + 4) = 10
> (1 * (2 * 3)) + 4 = 10
> ((1 * 2) * 3) + 4 = 10
> 4 digits: q
>
>となりますが、これは、本来
>1+2+3+4 と 1*2*3+4 の 2つの式と数えるべきではないでしょうか。

これ全部で1個と数えるのだと思います。
No.1869
Re:教えてください
投稿者---かずま(2002/06/28 16:08:38)


> これ全部で1個と数えるのだと思います。

あ、そういうことか。それなら簡単。
int make_ten(int d1, int d2, int d3, int d4)
{
    Frac  a, b, c, d;    int  i, j, k;

    a.n = d1;  b.n = d2;  c.n = d3;  d.n = d4;
    a.d = b.d = c.d = d.d = 1;

    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            for (k = 0; k < 4; k++) {
                if (ten(o[i](a, o[j](b, o[k](c, d)))))
                    return 1;
                if (ten(o[i](a, o[k](o[j](b, c), d))))
                    return 1;
                if (ten(o[j](o[i](a, b), o[k](c, d))))
                    return 1;
                if (ten(o[k](o[i](a, o[j](b, c)), d)))
                    return 1;
                if (ten(o[k](o[j](o[i](a, b), c), d)))
                    return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int  a, b, c, d, n = 0;

    for (a = 0; a < 10; a++)
        for (b = 0; b < 10; b++)
            for (c = 0; c < 10; c++)
                for (d = 0; d < 10; d++)
                    n += make_ten(a, b, c, d);
    printf("%.2f%%\n", (10000 - n) * 100.0 / 10000);
    return 0;
}

No.1871
Re:教えてください
投稿者---Aki(2002/06/28 16:37:48)


41.22%とでました。これが正解かどうかを知ることはでるんでしょうか？

#include <stdio.h>
typedef struct {
    int n;      /* 分子(numerator) */
    int d;      /* 分母(denominator) */
    int op;     /* この値の直後の演算子。0は+, 1は-, 2は*, 3は/ */
} Num;

#define STACK_SIZE  4
Num     stack[STACK_SIZE];
int     sp;

void push(Num x)
{
    stack[sp++] = x;
}

Num pop(void)
{
    return stack[--sp];
}

Num top(void)
{
    return stack[sp-1];
}

/* a op bを計算する */
Num calc(Num a, int op, Num b)
{
    Num c;

    switch (op) {
      case 0:   /*  (+)  */
        c.n = (a.n * b.d) + (b.n * a.d);
        c.d = a.d * b.d;
        break;
      case 1:   /*  (-)  */
        c.n = (a.n * b.d) - (b.n * a.d);
        c.d = a.d * b.d;
        break;
      case 2:   /*  (*)  */
        c.n = b.n * a.n;
        c.d = a.d * b.d;
        break;
      case 3:   /*  (/)  */     /* 0除算は考慮しなくてよい。*/
        c.n = a.n * b.d;
        c.d = a.d * b.n;
        break;
      default:
        break;
    }
    c.op = b.op;
    return c;
}

Num     n[4];
int     success_fail;

/* 括弧による式のグループ分けをすべて試し、実際に計算する。*/
void eval_sub(int i)
{
    if (i < 4) {
        push(n[i]);
        eval_sub(i + 1);
        pop();
    }
    if (sp >= 2) {
        Num a = pop();
        Num b = pop();
        push(calc(b, b.op, a));
        eval_sub(i);
        pop(), push(b), push(a);
    } else if (i >= 4)
        if (top().n == top().d * 10 && top().d != 0)    /* && top().d != 0 は必要 */
           success_fail = 1;
}

/* ある特定の数字列と演算子について、10を作ることができるか調べる */
int eval(void)
{
    success_fail = 0;
    eval_sub(0);
    return success_fail;
}

/* ある特定の数字列について、10を作ることができるか調べる */
int make10(void)
{
    int     i;

    n[0].op = n[1].op = n[2].op = 0;

    do {
        if (eval())
            return 1;
        for (i = 0; i < 3 && ++n[i].op >= 4; i++)
            n[i].op = 0;
    } while (i < 3);
    return 0;
}

int main(void)
{
    int     i, count;

    n[0].d = n[1].d = n[2].d = n[3].d = 1;

    count = 0;
    do {
        if (make10())
            count++;
        for (i = 0; i < 4 && ++n[i].n >= 10; i++)
            n[i].n = 0;
    } while (i < 4);

    /* 結果表示 */
    printf("%g%% impossible\n", ((10000 - count) / 10000.0) * 100);
    return 0;
}

No.1874
Re:教えてください
投稿者---musashi(2002/06/28 19:02:47)


かずまさん、Akiさん、返答ありがとうございます。
大変参考になりました。
でもさきほど気付いたのですが、
単項のマイナス符号演算子は使用できるという条件と、

(例)
4627→4 * 6 + 2 * (-7) = 10

与えられた数字の順番を変更できるとすると、
何％になるかと書いてあるのを見逃していました。
すみませんが、もう少し考えていただけませんか？

>41.22%とでました。これが正解かどうかを知ることはでるんでしょうか？
今はまだわかりませんが、わかり次第報告させていただきます。
No.1878
Re:教えてください
投稿者---Aki(2002/06/29 22:54:21)		 


#include <stdlib.h>を追加して、eval関数を下のように変更すれば、
単項の-演算子を考慮したバージョンになります。結果は31.09%でした。

int eval(void)
{
    int     i, j;

    do {
        success_fail = 0;
        eval_sub(0);
        if (success_fail) {
            for (j = 0; j < 4; j++)
                n[j].n = abs(n[j].n);
            return 1;
        }
        for (i = 0; i < 4 && (n[i].n *= -1) >= 0; i++)
            ;
    } while (i < 4);
    return 0;

}
No.1880
Re:教えてください
投稿者---かずま(2002/06/30 02:51:30)


> #include&nbsp;<stdlib.h>を追加して、eval関数を下のように変更すれば、
> 単項の-演算子を考慮したバージョンになります。結果は31.09%でした。

私も 31.09% になりました。
main で、change_sign の代わりに make_ten を呼び出すと、41.22% です。
#include <stdio.h>

typedef struct { int n, d; } Num;   /* 分子(numerator), 分母(denominator) */

int ten(Num x) { return x.n == x.d * 10  &&  x.d != 0; }

Num add(Num a, Num b) { a.n = a.n * b.d + b.n * a.d; a.d *= b.d; return a; }
Num sub(Num a, Num b) { a.n = a.n * b.d - b.n * a.d; a.d *= b.d; return a; }
Num mlt(Num a, Num b) { a.n *= b.n; a.d *= b.d; return a; }
Num dvd(Num a, Num b) { a.n *= b.d; a.d *= b.n; return a; }

Num (*o[])(Num, Num) = { add, sub, mlt, dvd };       /* 演算子(operator) */

int make_ten(int d1, int d2, int d3, int d4)
{
    Num  a, b, c, d;    int  i, j, k;

    a.n = d1;  b.n = d2;  c.n = d3;  d.n = d4;
    a.d = b.d = c.d = d.d = 1;
    for (i = 0; i < 4; i++)
        for (j = 0; j < 4; j++)
            for (k = 0; k < 4; k++)
                if (ten(o[i](a, o[j](b, o[k](c, d)))) ||
                    ten(o[i](a, o[k](o[j](b, c), d))) ||
                    ten(o[j](o[i](a, b), o[k](c, d))) ||
                    ten(o[k](o[i](a, o[j](b, c)), d)) ||
                    ten(o[k](o[j](o[i](a, b), c), d))) return 1;
    return 0;
}

int change_sign(int a, int b, int c, int d)
{
    do do do do if (make_ten(a, b, c, d)) return 1;
             while ((d = -d) < 0);
          while ((c = -c) < 0);
       while ((b = -b) < 0);
    while ((a = -a) < 0);
    return 0;
}


int main()
{
    int  a, b, c, d, n = 0;

    for (a = 0; a < 10; a++)
        for (b = 0; b < 10; b++)
            for (c = 0; c < 10; c++)
                for (d = 0; d < 10; d++)
                    n += change_sign(a, b, c, d);
    printf("%g%%\n", (10000 - n) * 100.0 / 10000);
    return 0;
}

No.1879
Re:教えてください
投稿者---Aki(2002/06/29 22:59:41)


数字の順序の変更が許される場合のプログラムは次のように根本的に方法
を変えてみました。結果は20.15%でした。

#include <stdlib.h>
#include <stdio.h>
#define NUM_SIZE 10000

typedef struct {
    int flg;
    int digit[4];
} Num;

void init_num(Num x[])
{
    int     i, j;

    for (i = 0; i < NUM_SIZE; i++) {
        int a = i;
        for (j = 0; j < 4; j++) {
            x[i].digit[j] = a % 10;
            a /= 10;
        }
    }
}

int calc(Num x, const int op[])
{
    int     i, n, d = 1;

    n = x.digit[0];
    for (i = 0; i < 3; i++) {
        switch (op[i]) {
          case 0:   /*  (+)  */
            n += d * x.digit[i+1];
            break;
          case 1:   /*  (-)  */
            n -= d * x.digit[i+1];
            break;
          case 2:   /*  (*)  */
            n *= x.digit[i+1];
            break;
          case 3:   /*  (/)  */
            d *= x.digit[i+1];
            break;
          default:
            break;
        }
    }
    if (d != 0 && n == d * 10)
        return 1;
    return 0;
}

int try_sub(Num x)
{
    int     i, op[3] = {0};

    do {
        if (calc(x, op))
            return 1;
        for (i = 0; i < 3 && ++op[i] >= 4; i++) /* 演算子の組み合わせを変える */
            op[i] = 0;
    } while (i < 3);
    return 0;
}

int try(Num x)
{
    int     i;

    do {
        if (try_sub(x))
            return 1;
        for (i = 0; i < 4 && (x.digit[i] *= -1) >= 0; i++)  /* -符号の付け方を変える */
            ;
    } while (i < 4);
    return 0;
}

int cmp_digit(const int *d1, const int *d2)
{
    if (*d1 > *d2)
        return 1;
    else if (*d1 < *d2)
        return -1;
    else
        return 0;
}

int cmp_num(const Num *num1, const Num *num2)
{
    int     i;

    for (i = 0; i < 4; i++) {
        if (num1->digit[i] > num2->digit[i])
            return 1;
        else if (num1->digit[i] < num2->digit[i])
            return -1;
    }
    return 0;
}

typedef int (*CmpFunc)(const void*, const void*);
Num num[NUM_SIZE];

int main(void)
{
    int     i, cnt, fg, count;

    init_num(num);
    for (i = 0; i < NUM_SIZE; i++)
        if (try(num[i]))
            num[i].flg = 1;

    for (i = 0; i < NUM_SIZE; i++)
        qsort(num[i].digit, 4, sizeof(num[i].digit[0]), (CmpFunc)cmp_digit);
    qsort(num, NUM_SIZE, sizeof(num[0]), (CmpFunc)cmp_num);

    count = 0;
    cnt = 0, fg = 0;
    for (i = 0; i < NUM_SIZE; i++) {
        if (i == 0 || cmp_num(&num[i], &num[i-1]) != 0) {
            count += cnt * fg;
            cnt = 0, fg = 0;
        }
        cnt++;
        if (num[i].flg == 1)
            fg = 1;
    }

    /* 結果表示 */
    printf("%g%% impossible\n", ((10000 - count) / 10000.0) * 100);
    return 0;
}

No.1881
Re:教えてください
投稿者---かずま(2002/06/30 02:53:57)


> 数字の順序の変更が許される場合のプログラムは次のように根本的に方法
> を変えてみました。結果は20.15%でした。

私の場合、18.53% でした。
先ほどの単項-演算子を許すプログラムの main を次のように変えたものです。
#include <stdlib.h>

int comp(const void *a, const void *b) { return *(int *)a - *(int *)b; }

int hash(int a, int b, int c, int d)
{
    int t[4];

    t[0] = a, t[1] = b, t[2] = c, t[3] = d;
    qsort(t, 4, sizeof *t, comp);
    return t[0]*1000 + t[1]*100 + t[2]*10 + t[3];
}

char ok[10000];

int main()
{
    int  a, b, c, d, n = 0;

    for (a = 0; a < 10; a++)
        for (b = 0; b < 10; b++)
            for (c = 0; c < 10; c++)
                for (d = 0; d < 10; d++)
                    ok[hash(a, b, c, d)] |= change_sign(a, b, c, d);
    for (a = 0; a < 10; a++)
        for (b = 0; b < 10; b++)
            for (c = 0; c < 10; c++)
                for (d = 0; d < 10; d++)
                    n += ok[hash(a, b, c, d)];
    printf("%g%%\n", (10000 - n) * 100.0 / 10000);
    return 0;
}

Akiさんのプログラムですが、main の最後に、
    printf("%d: %d\n", 19, num[19].flg);
    printf("%d: %d\n", 25, num[25].flg);
    printf("%d: %d\n", 130, num[130].flg);
    printf("%d: %d\n", 131, num[131].flg);

を追加してみると、0019 や 0025 は 10が作れなくて、
0130 や 0131 は 10 が作れるという結果になっているようです。
No.1882
Re:教えてください
投稿者---かずま(2002/06/30 16:32:49)


> Akiさんのプログラムですが、main の最後に、
>
>　　printf("%d: %d\n", 19, num[19].flg);
>　　printf("%d: %d\n", 25, num[25].flg);
>　　printf("%d: %d\n", 130, num[130].flg);
>　　printf("%d: %d\n", 131, num[131].flg);
>
> を追加してみると、0019 や 0025 は 10が作れなくて、
> 0130 や 0131 は 10 が作れるという結果になっているようです。

すみません。これは私の勘違いでした。既にソートされたあとなので、
19番目は 0019 ではないんですね。

そこで、count += cnt * fg; の直前に、
    if (i > 0 && fg == 0)
        printf("%d%d%d%d\n", num[i-1].digit[0], num[i-1].digit[1],
            num[i-1].digit[2], num[i-1].digit[3]);
を入れてダメな 4桁を出してみたところ、その中に、1114 や 6779 など
がありました。(1+1)*(1+4) = 10、6/(-7+9)+7 = 10 ですから、これらは
「できない」ではありませんね。まだ、私は勘違いをしているのでしょうか。
No.1883
Re:教えてください
投稿者---Aki(2002/06/30 17:58:02)


>そこで、count += cnt * fg; の直前に、
>
> if (i > 0 && fg == 0)
> printf("%d%d%d%d\n", num[i-1].digit[0], num[i-1].digit[1],
> num[i-1].digit[2], num[i-1].digit[3]);
>
>を入れてダメな 4桁を出してみたところ、その中に、1114 や 6779 など
>がありました。(1+1)*(1+4) = 10、6/(-7+9)+7 = 10 ですから、これらは
>「できない」ではありませんね。まだ、私は勘違いをしているのでしょうか。

いいえ、すみません。バグです。calc関数に問題がありました。
calc関数では、5通りの括弧のつけ方をすべてを調べるべきところ
だったのですが、私のプログラムでは、

((a●b)●c)●d)

の１通りしか調べていません。したがって、ご指摘の1114については、

((4●1)●1)●1
((1●4)●1)●1
((1●1)●4)●1
((1●1)●1)●4

と、これらの数字の正負を変えたものだけしか調べておらず、その結果
(1+1)*(1+4)を見逃しています。

5通りの括弧のつけ方をすべて試すようにcalc関数を修正したところ、
結果は18.54%となりました。

さらに、main関数の結果表示の直前に、count += cnt * fg;の1文が必要
だということに気付き、これを追加すると結果は18.53%になりました。
No.1884
Re:教えてください
投稿者---musashi(2002/06/30 19:46:31)


かずまさん、Akiさん、ほんとうにありがとうございました。
お二人のプログラムを見せていただいたおかげで、
なんとか完成までいけそうです。
お二人とも、私では思いもつかない方法でやっていたので、
大変勉強になりました。
本当にありがとうございます。
途中で条件を追加してしまって、余分な時間をとらせてしまったことは
本当に申し訳ありませんでした。
またわからないことがあったら質問させていただくかもしれませんが、
そのときはよろしくお願いします。
あ、結果はわかり次第報告させていただきますね。
No.1951
Re:教えてください
投稿者---かずま(2002/07/04 20:44:18)


> 私の場合、18.53% でした。
> 先ほどの単項-演算子を許すプログラムの main を次のように変えたものです。

単項マイナス演算子を許さなくても、数字の入れ替えさえ許せば、10 が出来ないものは
18.53% になるようです。
#include <stdio.h>

typedef struct { int n, d; } Num;  /* 分子(numerator), 分母(denominator) */

int ten(Num x) { return x.n == x.d * 10  &&  x.d != 0; }

Num add(Num a, Num b) { a.n = a.n * b.d + b.n * a.d; a.d *= b.d; return a; }
Num sub(Num a, Num b) { a.n = a.n * b.d - b.n * a.d; a.d *= b.d; return a; }
Num mlt(Num a, Num b) { a.n *= b.n; a.d *= b.d; return a; }
Num dvd(Num a, Num b) { a.n *= b.d; a.d *= b.n; return a; }

Num (*o[])(Num, Num) = { add, sub, mlt, dvd };   /* 演算子(operator) */

int make_ten(int d1, int d2, int d3, int d4)
{
    Num  a, b, c, d;    int  i, j, k;

    a.n = d1;  b.n = d2;  c.n = d3;  d.n = d4;
    a.d = b.d = c.d = d.d = 1;
    for (i = 0; i < 4; i++)
        for (j = 0; j < 4; j++)
            for (k = 0; k < 4; k++)
                if (ten(o[i](a, o[j](b, o[k](c, d)))) ||
                    ten(o[i](a, o[k](o[j](b, c), d))) ||
                    ten(o[j](o[i](a, b), o[k](c, d))) ||
                    ten(o[k](o[i](a, o[j](b, c)), d)) ||
                    ten(o[k](o[j](o[i](a, b), c), d))) return 1;
    return 0;
}

int hash(int a, int b, int c, int d)
{
    int t;
    #define SORT(x, y) ((x > y) && (t = x, x = y, y = t))
    SORT(a, d); SORT(b, c); SORT(a, b); SORT(c, d); SORT(b, c);
    return a*1000 + b*100 + c*10 + d;
}

char ok[10000];

int main()
{
    int  a, b, c, d, n = 0;

    for (a = 0; a < 10; a++)
        for (b = 0; b < 10; b++)
            for (c = 0; c < 10; c++)
                for (d = 0; d < 10; d++)
                    if (make_ten(a, b, c, d))
                        ok[hash(a, b, c, d)] = 1;
    for (a = 0; a < 10; a++)
        for (b = 0; b < 10; b++)
            for (c = 0; c < 10; c++)
                for (d = 0; d < 10; d++)
                    n += ok[hash(a, b, c, d)];
    printf("%g%%\n", (10000 - n) * 100.0 / 10000);
    return 0;
}