メインメニュー
PR
facebook
別フォーラムへ

四則演算で10を作る


投稿ツリー


前の投稿 - 次の投稿 | 親投稿 - 子投稿.1 .2 .3 .4 | 投稿日時 2014/9/13 21:46
LuckyHill  一人前   投稿数: 1190
 昔、切符を買って電車に乗った時に、発券番号の4つの数字を足したり引いたり掛けたり割ったりして、答えを10にするということを暇つぶしによくやりました。携帯ゲーム機とかスマホとか、ありませんでしたからね(汗)。

 例.4と5と7と9 → 5 × 4 /( 9 - 7 ) = 10

【問題】四則演算(+-×÷)を行って10を作ってください。
(1)9と9と9と9

(2)1と1と9と9

(3)1と1と5と8

(4)3と4と7と8


【問題】次の3問は24にしてください。
(5)4と4と10と10

(6)3と3と7と7

(7)3と3と8と8
投票数:1 平均点:10.00
返信する
前の投稿 - 次の投稿 | 親投稿 - 子投稿なし | 投稿日時 2014/9/14 14:48
zima  常連   投稿数: 121
# 解答ではありませーん(^_^;

四色問題の証明で、ヘーシュの放電法を計算機でシミュレートすることで解決したアペルとハーケンの手法が「エレファントな数学」と揶揄されたりしましたが、エレガントな解答が分からなくても腕力で総当たりすればグゥの音も出ない完璧な答えが出せるハズ。

と思いつつ、どうプログラミングすれば良いのか分からないwww

0~9の数字を4つ、+-×÷の4種類の演算記号を4つ、並べて式を作る。数字も記号も文字と考えれば8文字。式として成立しないモノもあるが、とにかく全部調べる。調べる総数は8の8乗。

ではなくw、カッコを使うことも考慮しなくちゃいけない。

カッコの配置について、全てのケースを漏れなく網羅するには、どのように考えれば良いでしょうか。

この問題で想定される範囲の式をBNFで書き下ろしてカッコが登場し得る位置を分析すれば。。。。

ぁぁぁ、知恵熱が(軟弱www

--
by なかぢー%鳩ヶ谷@埼玉
(末期高齢者ばちゅいちww)

投票数:1 平均点:10.00
返信する
前の投稿 - 次の投稿 | 親投稿 - 子投稿.1 | 投稿日時 2014/9/16 21:07
LuckyHill  一人前   投稿数: 1190
 こういう問題は、テンパズル(10 puzzle)という名前で呼ばれているらしいですね。解説しているページがありましたので、ヒントを兼ねてご紹介。

◆テンパズルの解の探索
 http://azisava.sakura.ne.jp/math/ten_puzzle.html

 これによると、最初の発言で問題(4)として出した{3,4,7,8}は、「一般の人が比較的簡単に見つけられるであろう解」がない、という判定になっていますね(汗)。


 ちなみに私が解けたのは(1)(2)(5)だけでした。
投票数:1 平均点:10.00
返信する
前の投稿 - 次の投稿 | 親投稿 - 子投稿なし | 投稿日時 2014/9/17 0:15
zima  常連   投稿数: 121
ぬー、やはりクールな頭脳でスッキリ整理して明快なアルゴリズム(概要設計)を組み立てた人はいるのですねー。

URL参照先の解説の中には、ワタクシ的には必ずしも自明とは思えない部分もあるのですが、落ち着いて(スンゲェ時間をかけてw)一歩ずつ追っていけば納得できるのかなー。
# いや、zima のことだから睡魔に負けるに決まってる!に1000カノッサww

まぁ、今日はこれぐらいにしといたる!(ヲイw

--
by なかぢー%鳩ヶ谷@埼玉
(末期高齢者ばちゅいちww)

投票数:1 平均点:10.00
返信する
前の投稿 - 次の投稿 | 親投稿 - 子投稿.1 | 投稿日時 2014/9/17 1:14
東 遥  スタッフ   投稿数: 3331
うふふ。

そこでですね、逆ポーランド記法を使うのですよ。

 ・ある特定の演算子(加減乗除算)よりも左に項が2以上あれば良い

という条件を満たす限りで順列組合せ・演算種目を網羅すればよい。例えば

 A B C D + ー ×

でも

 A B C + D ー ×

でも

 A B + C D ー ×

でも

 A B + C ー D ×

でも表せる。これでカッコの有無等を代表できるでしょう。変数A,B,C,Dの組み合わせが10000通り、3つの演算子の組み合わせが4^3=64通り、変数と演算子の配置方法は上記の4通り、ですから述べ

 2560000通り

で網羅でき、パソコンなりで解くには、実装するのがちょっと工夫が必要ですが、まぁ、出来る範囲内でしょう。

因みに、特定の4つの整数(それぞれ0~9の整数)を与えられた時にそれから求められうる計算パターンは数字の順列組合せ24通り、演算子の組み合わせ64通り、演算子の配置4通り、述べ6144通りという事で御座いましょう。

....酒が入る前の妄言なので正しいかどうかは保証の限りではありません。あしからず。
投票数:0 平均点:0.00
返信する
前の投稿 - 次の投稿 | 親投稿 - 子投稿なし | 投稿日時 2014/9/17 1:29 | 最終変更
zima  常連   投稿数: 121
RPN(逆ポーランド記法)でカッコの呪縛から解放される、知識としては知っていたけれども応用ができませんでした。

スタックマシンといえば Burroughs、プログラミング言語なら FORTH、コンパイラの内部ではRPNで扱う、なんてことも読んだことがあったのに。

かつて、パソコン通信時代(@Nifty より前w)に、HP社のRPN電卓ユーザーがいたことも思い出しました。
# と誘い水w

RPNなら、2項演算子のみならず、単項演算子や複数引数の関数なども見通しよく扱えそうです。

四則演算にとどまらず、アレコレ妄想が広がりますが、そろそろオネムなので、これにて(逃げ足の速いヤツwww

--
by なかぢー%鳩ヶ谷@埼玉
(末期高齢者ばちゅいちww)

投票数:0 平均点:0.00
返信する
前の投稿 - 次の投稿 | 親投稿 - 子投稿.1 | 投稿日時 2014/9/18 22:23
LuckyHill  一人前   投稿数: 1190
 あまり引っぱって、次の飛び石連休も皆さんの頭を煩わせたら申し訳ないので、解答を。

(1)
   

(2)
   

(3)
   

(4)
   

(5)
   

(6)
   

(7)
   

 分数の分母に、整数と分数(しかも仮分数)の加減算が来る形は、相当に慣れていないと思い付きませんね。
投票数:0 平均点:0.00
返信する
前の投稿 - 次の投稿 | 親投稿 - 子投稿なし | 投稿日時 2014/9/18 23:50 | 最終変更
東 遥  スタッフ   投稿数: 3331
そんな!?分数なんてズルイぞ!!(笑)>誰?
投票数:1 平均点:10.00
返信する
前の投稿 - 次の投稿 | 親投稿 - 子投稿なし | 投稿日時 2014/9/20 10:07 | 最終変更
東 遥  スタッフ   投稿数: 3331
悔しいので(笑)プログラムを組んでみました。

//
// TP.c  ( Ver. 1.5.4 )
// Ten Puzzle
// by ADUMA Haruka
//
// % gcc -o TP TP.c
// % ./TP | sort > RESULT.txt
//
// 1.5s @ Core i5-4200 ( 2.2GHz )
//

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

char *OPS[6] = { " +", "i-", "r-", " *", "i/", "r/" } ;

typedef struct { int n ; int d ; } FRACTION ;
FRACTION fA, fB, fC, fD, fT, fU, fV ;

char SORT_BUFFER[10] ;

#define START 0

int main ( int ARGC, char **ARGV, char **ENVV ) {
  int A, B, C, D, O, P, Q, R ;
  int REQUIRE = 10 ;
  char *s = "|>%d,%d,%d,%d |%s,%s,%s| <= %d %d %d : %d,%d,%d\n" ;
  for ( A = START ; A < 10 ; A++ ) {
    for ( B = START ; B < 10 ; B++ ) {
      for ( C = START ; C < 10 ; C++ ) {
        for ( D = START ; D < 10 ; D++ ) {
          for ( O = 0 ; O < 6 ; O++ ) {             
            for ( P = 0 ; P < 6 ; P++ ) {   
              for ( Q = 0 ; Q < 6 ; Q++ ) {
                if ( 0 ) printf ( s, A,B,C,D,OPS[O],OPS[P],OPS[Q],O,P,Q,0,0,0 ) ;
                R = calc_exp_1 (A,B,C,D,O,P,Q,REQUIRE) ; /* A B C D + - / */
                R = calc_exp_2 (A,B,C,D,O,P,Q,REQUIRE) ; /* A B C + D - / */
                R = calc_exp_3 (A,B,C,D,O,P,Q,REQUIRE) ; /* A B + C D - / */
                R = calc_exp_4 (A,B,C,D,O,P,Q,REQUIRE) ; /* A B + C - D / */
  } } } } } } }
  return 0 ;
}

char * sort_set ( int A, int B, int C, int D ) {
  int i ; char *p = SORT_BUFFER ; /* force to be A <= B<= C <= D */
  if ( A > B ) { i=A; A=B; B=i; }  if ( B > C ) { i=B; B=C; C=i; }
  if ( C > D ) { i=C; C=D; D=i; }  if ( B > C ) { i=B; B=C; C=i; }
  if ( A > B ) { i=A; A=B; B=i; }  if ( B > C ) { i=B; B=C; C=i; }
  sprintf ( p, "%1d%1d%1d%1d", A, B, C, D ) ;
  return p ;
}

int operate_one ( FRACTION *A, FRACTION *B, FRACTION *X, int O ) {
  int f = 1 ;    /* operand A,   operand B,    result X, operation type O */
  switch ( O ) { /* case 0: X=A+B; case 1:X=A-B; case 2:X=B-A; case 3:X=A*B; */ 
    case 0: X->n = (A->n * B->d)+(B->n * A->d); X->d = A->d * B->d; break;
    case 1: X->n = (A->n * B->d)-(B->n * A->d); X->d = A->d * B->d; break;
    case 2: X->n = (B->n * A->d)-(A->n * B->d); X->d = A->d * B->d; break;
    case 3: X->n = A->n * B->n ; X->d = A->d * B->d ; break ;
    case 4: if (B->n !=0) X->n= A->n * B->d, X->d= A->d * B->n; else f=0; break;
    case 5: if (A->n !=0) X->n= B->n * A->d, X->d= B->d * A->n; else f=0; break;
  } /* case 4:  X = A / B  ;  case 5:  X = B / A   */
  if ( f ) reduce ( X ) ;
  return f ; /* 1: Valid Value, 0: Invalid Value, denominator = 0 */
}

int reduce ( FRACTION *X ) { /* EX.  24 / 9 --> 8 / 3  */ 
  int tN, tD, iM, iN, iR, f = 0 ; /* if ( f ) it is minus */
  tN = X->n, tD = X->d ;
  if ( tD <  0 ) tN = -tN, tD = -tD ; 
  if ( tN <  0 ) tN = -tN,  f =  1 ;
  if ( tN < tD ) iM =  tD, iN = tN ; else iM = tN, iN = tD ;
  while ( iN ) iR = iM % iN, iM = iN, iN = iR ; /* EUCLID */ 
  tN = tN / iM, tD = tD / iM ;
  if ( f ) tN = -tN ;
  X->n = tN, X->d = tD ;
  return f ;
}

int setup_numbers ( int A, int B, int C, int D ) {
  fA.n = A ; fB.n = B ; fC.n = C ; fD.n = D ; /* numerator = given value */
  fA.d = 1 ; fB.d = 1 ; fC.d = 1 ; fD.d = 1 ; /* denominator = 1 */
  return 1 ;
}

int calc_exp_1 ( int A, int B, int C, int D, int O, int P, int Q, int R ) {
  char *p, *s="%s :EQ1: %2d %2d %2d %2d %s %s %s : %d\n" ; 
  int f = 1 ; setup_numbers ( A, B, C, D ) ;
  /**/     f = operate_one ( &fC, &fD, &fT, O ) ;   /* A B C D op/ op/ op/ */
  if ( f ) f = operate_one ( &fB, &fT, &fU, P ) ;   /*          O   P   Q  */
  if ( f ) f = operate_one ( &fA, &fU, &fV, Q ) ;   /*          T   U   V  */
  if ( f ) if ( ( fV.d == 1 ) && ( fV.n == R ) ) {
    p = sort_set ( A, B, C, D ) ;
    printf ( s, p, A, B, C, D, OPS[O], OPS[P], OPS[Q], fV. n ) ;
  }
  return f ;
} 

int calc_exp_2 ( int A, int B, int C, int D, int O, int P, int Q, int R ) {
  char *p, *s="%s :EQ2: %2d %2d %2d %s %2d %s %s : %d\n" ; 
  int f = 1 ; setup_numbers ( A, B, C, D ) ;
  /**/     f = operate_one ( &fB, &fC, &fT, O ) ;   /* A B C op/ D op/ op/ */
  if ( f ) f = operate_one ( &fT, &fD, &fU, P ) ;   /*        O     P   Q  */
  if ( f ) f = operate_one ( &fA, &fU, &fV, Q ) ;   /*        T     U   V  */
  if ( f ) if ( ( fV.d == 1 ) && ( fV.n == R ) ) {
    p = sort_set ( A, B, C, D ) ;
    printf ( s, p, A, B, C, OPS[O], D, OPS[P], OPS[Q], fV. n ) ;
  }
  return f ;
} 

int calc_exp_3 ( int A, int B, int C, int D, int O, int P, int Q, int R ) {
  char *p, *s="%s :EQ3: %2d %2d %s %2d %2d %s %s : %d\n" ; 
  int f = 1 ; setup_numbers ( A, B, C, D ) ;
  /**/     f = operate_one ( &fA, &fB, &fT, O ) ;   /* A B op/ C D op/ op/ */
  if ( f ) f = operate_one ( &fC, &fD, &fU, P ) ;   /*      O       P   Q  */
  if ( f ) f = operate_one ( &fT, &fU, &fV, Q ) ;   /*      T       U   V  */
  if ( f ) if ( ( fV.d == 1 ) && ( fV.n == R ) ) {
    p = sort_set ( A, B, C, D ) ;
    printf ( s, p, A, B, OPS[O], C, D, OPS[P], OPS[Q], fV. n ) ;
  }
  return f ;
} 

int calc_exp_4 ( int A, int B, int C, int D, int O, int P, int Q, int R ) {
  char *p, *s="%s :EQ4: %2d %2d %s %2d %s %2d %s : %d\n" ; 
  int f = 1 ; setup_numbers ( A, B, C, D ) ;
  /**/     f = operate_one ( &fA, &fB, &fT, O ) ;   /* A B op/ C op/ D op/ */
  if ( f ) f = operate_one ( &fT, &fC, &fU, P ) ;   /*      O     P     Q  */
  if ( f ) f = operate_one ( &fU, &fD, &fV, Q ) ;   /*      T     U     V  */
  if ( f ) if ( ( fV.d == 1 ) && ( fV.n == R ) ) {
    p = sort_set ( A, B, C, D ) ;
    printf ( s, p, A, B, OPS[O], C, OPS[P], D, OPS[Q], fV. n ) ;
  }
  return f ;
} 

何も考えず重複・冗長も気にせずとにかくあらゆるパターンを回します。VirtualBox上のFreeBSD 9.3R, CPUはi5(2.2GHz)で1.5秒ですね。現代のCPUは早いなぁ。
投票数:1 平均点:10.00
返信する

このトピックに投稿する

題名
ゲスト名
投稿本文
  条件検索へ


ログイン

ユーザー名:


パスワード:





パスワード紛失  |新規登録
PR
twitter
Created by: twitter website widget