数学的な処理

プログラムで次の処理をしたいのですが、どうすればよいでしょうか。計算部分をどのように書けば良いかわかりません。

1桁の整数a,b,c,dがあります。
条件は、 a<b<c<d かつ 1≦a,b,c,d≦9です。

このとき、 a,b,c,d の数字間に四則演算符号+-*/を入れ、結果が10になるようにします。整数は順序を入れ替えてもかまわず、()を利用して計算の順序を制御してもかまいません。同じ整数は2度使えません。

結果は数式で表示します。

例： 1+2+3+4=10　(1,2,3,4)
2*3+5-1=10 (1,2,3,5)
(3-7/4)*8=10 (3,4,7,8) など。

よろしくおねがいします。

No.12 回答者： BLUEPIXY 回答日時： 2005/05/16 06:23

#10>対応するカッコまでじゃなくちゃ。

#9>token=sc.findInLine(".+\\)");//最後のカッコまで取り出す。
を
String wk="";
int level=1;
while(sc.hasNext()){
token=sc.next();
if(token.equals("(")){
level++;
} else if (token.equals(")")){
level--;
}
wk += " " + token;
if(level==0) break;
}
に修正

No.11 回答者： BLUEPIXY 回答日時： 2005/05/16 05:52

#9です。

＞token=sc.findInLine(".+\\)");//最後のカッコまで取り出す。
最後のカッコまで取り出したらダメじゃん。
対応するカッコまでじゃなくちゃ。
また今度直します。

No.10 回答者： BLUEPIXY 回答日時： 2005/05/16 04:57

Integerの範囲で有理数演算するクラスを作ってみました。

if(Fraction.compute("( 3 - 7 / 4 ) * 8").equals(new Fraction(10)))
System.out.println("yes");
などとできます。(※computeは、空白が区切りになっているので詰めて書くことはできません)

文字列で試してみる数式を（他の人が言ってるようなやりかたで）作成できれば、とりあえず計算ができます。
とりあえず、作ってみたのでバグがあったらすみません。
まあ、参考程度に。
import java.util.*; //Stack,Scanner
//import java.lang.Number;

class Fraction extends Number implements Cloneable, Comparable<Fraction> {
private int numerator;
private int denominator;

public Fraction(int n){
numerator=n;
denominator=1;
}
public Fraction(int n, int d) throws FractionException {
if(d<0){
d*=-1;
n*=-1;
} else if(d==0) {
throw new FractionException("denominator is zero!");
}
numerator=n;
denominator=d;
reduction();
}
public static int gcd(int x, int y){
int wk=1;
x*=Integer.signum(x);//符号無しにする
y*=Integer.signum(y);
while(y != 0){
wk = x % y;
x = y;
y = wk;
}
return x;
}
public static Fraction compute(String exp) throws FractionException {
// "( 3 + 5 ) * 7 - 2" のような文字列を計算する
// 各トークンはスペースで区切られている必要がある。
Stack<String> cstack = new Stack<String>(); //演算子スタック
Stack<Fraction> vstack = new Stack<Fraction>(); //値スタック
Scanner sc = new Scanner(exp);
String token, op;
Fraction x,y;

while(sc.hasNext()){
token=sc.next();
if(token.equals("(")){
token=sc.findInLine(".+\\)");//最後のカッコまで取り出す。
//最後のカッコは捨てて、スタックに積む
vstack.push(compute(token.substring(0,token.length()-1)));
} else if (token.equals("*") || token.equals("/")){
if(cstack.empty()){
cstack.push(token);
} else {
op = cstack.peek();
if(op.equals("+") || op.equals("-")){
cstack.push(token);
} else {
y=vstack.pop();x=vstack.pop();
if(op.equals("*")){
vstack.push(x.multiply(y));
} else if(op.equals("/")){
vstack.push(x.divide(y));
}
cstack.pop();
cstack.push(token);
}
}
} else if (token.equals("+") || token.equals("-")){
if(cstack.empty()){
cstack.push(token);
} else {
op = cstack.peek();
y=vstack.pop();x=vstack.pop();
if(op.equals("+")){
vstack.push(x.add(y));
} else if(op.equals("-")){
vstack.push(x.subtract(y));
} else if(op.equals("*")){
vstack.push(x.multiply(y));
} else if(op.equals("/")){
vstack.push(x.divide(y));
}
cstack.pop();
cstack.push(token);
}
} else { //数字である
vstack.push(new Fraction(Integer.parseInt(token)));
}
}
sc.close();
while(!cstack.empty()){
op=cstack.pop();
y=vstack.pop();x=vstack.pop();
if(op.equals("+")){
vstack.push(x.add(y));
} else if(op.equals("-")){
vstack.push(x.subtract(y));
} else if(op.equals("*")){
vstack.push(x.multiply(y));
} else if(op.equals("/")){
vstack.push(x.divide(y));
}
}
return(vstack.pop());
}
public Fraction clone() throws CloneNotSupportedException {
return (Fraction)super.clone();
}
private void reduction(){
int gcd = gcd(numerator, denominator);
numerator/=gcd;
denominator/=gcd;
}
public Fraction negate() throws FractionException {
return(new Fraction(numerator*-1, denominator));
}
public Fraction invert() throws FractionException {
return(new Fraction(denominator, numerator));
}
public Fraction add(Fraction x) throws FractionException {
return(new Fraction(
this.numerator * x.denominator + this.denominator * x.numerator,
this.denominator * x.denominator));
}
public Fraction add(int n) throws FractionException {
return(new Fraction(numerator+n*denominator, denominator));
}
public Fraction subtract(Fraction x) throws FractionException {
return(new Fraction(
this.numerator * x.denominator - this.denominator * x.numerator,
this.denominator * x.denominator));
}
public Fraction subtract(int n) throws FractionException {
return(new Fraction(numerator-n*denominator, denominator));
}
public Fraction multiply(Fraction x) throws FractionException {
return(new Fraction(
this.numerator * x.numerator,
this.denominator * x.denominator));
}
public Fraction multiply(int x) throws FractionException {
return(new Fraction(numerator * x, denominator));
}
public Fraction divide(Fraction x) throws FractionException {
return(new Fraction(
this.numerator * x.denominator,
this.denominator * x.numerator));
}
public Fraction divide(int x) throws FractionException {
return(new Fraction(numerator, denominator * x));
}
public boolean equals(Fraction x){
return (this.numerator==x.numerator && this.denominator==x.denominator);
}
public int compareTo(Fraction x){
return (this.numerator*x.denominator-this.denominator*x.numerator);
}
public String toString(){
return (denominator==1)? ""+numerator : ""+numerator+"/"+denominator;
}

public byte byteValue(){
byte ret=(byte)(numerator/denominator);
return ret;
}
public double doubleValue(){
double ret=(double)numerator/denominator;
return ret;
}
public float floatValue(){
float ret=(float)numerator/denominator;
return ret;
}
public int intValue(){
return (numerator/denominator);
}
public long longValue(){
long ret=(long)numerator/denominator;
return ret;
}
public short shortValue(){
short ret=(short)(numerator/denominator);
return ret;
}
}

class FractionException extends Exception {
public FractionException() {
super();
}
public FractionException(String msg){
super(msg);
}
}

No.9 回答者： ymmasayan 回答日時： 2005/05/14 09:05

No.2、No.4、No.5です。

たびたびすみません。

No.6さんの言われるように逆ポーランドでケースを網羅して評価するのがいいようですね。

数字と演算子の組み合わせのケースは（数字をＮ、演算子を＄で表すと）
ＮＮ＄Ｎ＄Ｎ＄
ＮＮ＄ＮＮ＄＄
ＮＮＮ＄＄Ｎ＄
ＮＮＮ＄Ｎ＄＄
ＮＮＮＮ＄＄＄
の５通りです。
この５つがＮＮＮ＄＄＄に集約できるかどうかは自信がありません。
おそらく無理でしょうね。
ここでは単項演算子はないものとしています。
ただ、ダブりはたくさん出るのでこの扱いが次の課題です。
６＊７＋８＊９と８＊９＋６＊７等。
さらにNo.6さんの言われる（　）の使い方によるダブりも出ます。
（４＋５）＋（６＋７）と４＋５＋６＋７等。

No.8 回答者： kacchann 回答日時： 2005/05/14 03:23

ちょっと自信ないんだけど…。

---

4つのボールを用意する。これらはそれぞれ
a, b, c, dという値を持つ。
これらのボールを箱の中に入れる。
---

箱の中から2つのボールを選択し取り出す。
今は仮にa, bを取り出したとする。
この取り出した2つのボールに対して
「適用する演算」を選択する。
今は仮に「 + という演算」を選択したとする。

ここで、実際に演算を決行する。
(a+b)

次に、あらたに
(a+b)
という値を持ったボールを作成し、
これを箱に戻す。
ボールa, bは、破棄する。
[この結果、箱の中味は (a+b), c, d)]
---

この操作を繰り返し、箱の中味が1つになるまで続ける。
最後に箱の中に1個のボールが残った時に
そのボールの値が「10」なら、成功。

---
自信ないです。

No.7 回答者： unibon 回答日時： 2005/05/14 01:05

既出の回答をヒントにしたのですが、逆ポーランドを基本にして、

数値と演算子のすべての組み合わせをしらみつぶしに計算していくほうが
手っ取り早いだろうと思います。
4つの数値を a, b, c, d とし、
加減乗除用の2項演算子のバリエーションは +, -, *, / であるわけですから、
正規表現風に書くと、
\d \d \d \d [+-*/] [+-*/] [+-*/]
になり、単純に考えると、
10×10×10×10×4×4×4 = 640,000とおり
です。あと、負号の単項演算子があるのですが、
数値や演算子ごとに負にする操作もあるとしてもせいぜい各項ごとに2倍に増えるのが精一杯ですから、
さらに 2 の 7 乗を掛けて、81,920,000とおり位？
いまどきのコンピューターならこれくらいは瞬時(?)に計算できるはずです。

そうやって結果が10になるものを一旦求めてから、
それを逆ポーランドでない普通の数式に変換します。

ただ、疑問なのは、
1+2+3+4=10
((1+2)+3)+4)=10
は同じものなのか違うものとするのか、
などがやっかいかもしれません。
違うものとするならば、

\d [+-*/]* \d [+-*/]* \d [+-*/]* \d [+-*/]*

みたいな感じ(雰囲気だけですが)で、
ちょっと複雑になります。

No.6 回答者： ymmasayan 回答日時： 2005/05/13 17:58

No.2、No.4です。

私のやり方には２つの欠陥があることが判明しました。

１．６つの演算子だけでは表現できないケースがある。
　　例えば５＊（４－３／２）は表現できない。
２．同じ式がダブってカウントされる。
　　例えば３＋４＋５＋６と３○４○５○６

対策としては演算子数が３個限定ならさらに強い＊／を作ることで１は解決できます。
しかし２は最終結果を比較して消しこんでいくしか方法がないようです。

ということで根本的には（　）にまじめに取り組むか、
木構造に取り組んだほうがよさそうです。

お騒がせしました。

No.5 回答者： ymmasayan 回答日時： 2005/05/13 16:19

No.2です。

補足質問に回答します。

>　強い＋－の定義方法が分かりません。
>　括弧の存在があると複雑に感じてしまいます。

強い＋－をとりあえず○●で表すことにします。
例えば、５－４＊３●２なら５－４＊（３－２）とするという風な感じです。
５＊６●７○８なら５＊（６－７＋８）ですね。

蛇足ですが、演算子はプログラム中では１から６とかであらわせばいいので
記号で悩む必要はありません。

なお、木であらわすとあとの処理が簡単ですが、全部のケースを網羅した木を
作り出すのが結構大変かも知れません。

No.4 回答者： ymmasayan 回答日時： 2005/05/13 16:19

No.2です。

補足質問に回答します。

>　強い＋－の定義方法が分かりません。
>　括弧の存在があると複雑に感じてしまいます。

強い＋－をとりあえず○●で表すことにします。
例えば、５－４＊３●２なら５－４＊（３－２）とするという風な感じです。
５＊６●７○８なら５＊（６－７＋８）ですね。

蛇足ですが、演算子はプログラム中では１から６とかであらわせばいいので
記号で悩む必要はありません。

なお、木であらわすとあとの処理が簡単ですが、全部のケースを網羅した木を
作り出すのが結構大変かも知れません。

No.3 回答者： neKo_deux 回答日時： 2005/05/13 11:15

遺伝的プログラミング(Genetic Programing)で使う手ですが、

> 四則演算符号+-*/

この２項演算子を２進木の枝の分岐に見立てて、木で式を表現する手法があります。

> 例： 1+2+3+4=10　(1,2,3,4)
> 2*3+5-1=10 (1,2,3,5)
> (3-7/4)*8=10 (3,4,7,8) など。

＝＋─＋─＋─１
　｜　｜　└─２
　｜　└─３
　└─４

＝－─＋─＊─２
　｜　｜　└─３
　｜　└─５
　└─１

＝＊─－─３
　｜　└─÷─７
　｜　　　└─４
　└─８

とか。
√などの単項演算子が無いので木の長さが有限な事と、
懐かしい逆ポーランド記法になるのが特徴ですね。

この回答への補足

ご回答ありがとうございます。逆ポーランド記法は難しいですね。もうすこし勉強してみます。

補足日時：2005/05/13 15:41