4桁の数字を+-*/を使って10にするプログラム

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
ロード

4桁の数字を+-*/を使って10にするプログラム

#1

投稿記事 by ロード » 9年前

C言語をほぼ独学で勉強しています。
4桁の数字(0000~9999)で+-*/の演算子を使いどうにかして10に出来る数列を探すプログラムを作ろうとしています。
(例)1811→(1+1)*1+8=10

コード:

#include<stdio.h>

bool keisan(int,int,int,int);
bool hanbetu(int*);

int suu[1000][4];
int j = 0;
int main(){
	int i1, i2, i3, i4;
	int khairetu[4];
	int atai=0;

	for (i1 = 0; i1 < 1000; i1++){
		for (i2 = 0; i2 < 4; i2++){
			suu[i1][i2] = -1;
		}
	}



	for (i1 = 0; i1 < 10; i1++){
		for (i2 = 0; i2 < 10; i2++){
			for (i3 = 0; i3 < 10; i3++){
				for (i4 = 0; i4 < 10; i4++){
					khairetu[0] = i1;
					khairetu[1] = i2;
					khairetu[2] = i3;
					khairetu[3] = i4;

					if (hanbetu(khairetu) ==true){
						continue;
					}
					if (keisan(khairetu[0], khairetu[1], khairetu[2], khairetu[3]) == false){
						printf("%d,%d,%d,%d\n",  khairetu[0], khairetu[1], khairetu[2], khairetu[3]);
					}
				}
			}
		}
	}
	
	printf("j=%d",j);
	rewind(stdin);
	getchar();
	return 0;
}

bool keisan(int a1, int a2, int a3, int a4){
	int i1,i2,i3,i4,ans=0;
	for (i1 = 0; i1 < 4; i1++){
		for (i2 = 0; i2 < 4; i2++){
			for (i3 = 0; i3 < 4; i3++){
				ans = 0;

				switch (i1){
				case 0:ans = a1 + a2; break;
				case 1:ans = a1 - a2; break;
				case 2:ans = a1 * a2; break;
				case 3:if (a2 == 0) break;
					if (a1%a2 > 0){
						ans = -100000;
					}else ans = a1 / a2;
				}

				switch (i2){
				case 0:ans += a3; break;
				case 1:ans -= a3; break;
				case 2:ans *= a3; break;
				case 3:if (a3 == 0)break;
					if (ans%a3 > 0){
					ans = -100000;
				}
					   else ans /= a3;
				}
				switch (i3){
				case 0:ans += a4; break;
				case 1:ans -= a4; break;
				case 2:ans *= a4; break;
				case 3:if (a4 == 0) break;
					if (ans%a4 > 0){
					ans = -100000;
				}
					   else ans /= a4;
				}
				if (ans == 10){
					return true;
				}
			}
		}
	}
	return false;
}

bool hanbetu(int *k){
	int i, t, tmp;
	bool h=false;
	for (i = 0; i < 3; i++){
		for (t = i + 1; t < 4; t++){
			if (k[i]<k[t]){
				tmp = k[i];
				k[i] = k[t];
				k[t] = tmp;
			}
		}
	}
	for (i = 0; i <= j; i++){
		if (suu[i][0] == k[0] && suu[i][1] == k[1] && suu[i][2] == k[2] && suu[i][3] == k[0]){
			h = true;
		}
	}
	if (h == true){
		return true;
	}else{
		suu[j][0] = k[0];
		suu[j][1] = k[1];
		suu[j][2] = k[2];
		suu[j][3] = k[3];
		/*printf("%d%d%d%d\n", suu[j][0], suu[j][1], suu[j][2], suu[j][3]);*/
		j++;
		return false;
	}
}
いろんな勉強も兼ねて作っているのでポインタ使ったり値直接引数にしたりとぐちゃぐちゃなことをしています。
0001と0100などは同じものとして扱うように出力から弾き出そうとしています。
出力結果で数字がいくつか飛んでしまいます。原因がわからないので質問させてもらいます。
またプログラムの書き方等指摘していただけるとありがたいです。

box
記事: 2002
登録日時: 14年前

Re: 4桁の数字を+-*/を使って10にするプログラム

#2

投稿記事 by box » 9年前

コードにコメントがないので意図がよく見えないところがありますが、
まあそれはさておき、例えば
1 + 2 * 3 - 4
なんていう式が登場したとき、どういう風に計算することをお考えですか?

それから、例えば
1 - 2 * (3 + 4)
なんていう式のように、カッコがからんでくるととたんに難易度が上がるということは
ご承知の上ですね?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

ロード
記事: 12
登録日時: 9年前

Re: 4桁の数字を+-*/を使って10にするプログラム

#3

投稿記事 by ロード » 9年前

ソートしてしまうと結果がうまく出ないですね。
例に挙げてくださった1 - 2 * (3 + 4)の場合数字が3421と並んだ時に()付きと同じ計算が出来てるように考えてみたのですがこれではだめでしょうか?
矛盾点を見つけて治してみましたがまだおかしいようです。

コード:

#include<stdio.h>

bool keisan(int,int,int,int);//4桁の数列で10に出来るか計算
void chan(int); //結果の並び替えと表示

int suubuf[7000][4]; //10に出来る数列の保存先

int main(){
	int i1, i2, i3, i4; //forの変数
	int j=0;//結果の個数

	//0000~9999まで総当たり
	for (i1 = 0; i1 < 10; i1++){
		for (i2 = 0; i2 < 10; i2++){
			for (i3 = 0; i3 < 10; i3++){
				for (i4 = 0; i4 < 10; i4++){

					//4桁の数列で10になるか計算(10になるとき真
					if (keisan(i1, i2, i3, i4) == true){
						suubuf[j][0] = i1;
						suubuf[j][1] = i2;
						suubuf[j][2] = i3;
						suubuf[j][3] = i4;
						j++;
					}
				}
			}
		}
	}

	chan(j);

	rewind(stdin);
	getchar();
	return 0;
}

bool keisan(int a1, int a2, int a3, int a4){
	int i1,i2,i3,i4,ans=0; //forの変数宣言、答えの初期化

	//+-*/の総当たり
	for (i1 = 0; i1 < 4; i1++){
		for (i2 = 0; i2 < 4; i2++){
			for (i3 = 0; i3 < 4; i3++){


				ans = 0;
				switch (i1){
				case 0:ans = a1 + a2; break;
				case 1:ans = a1 - a2; break;
				case 2:ans = a1 * a2; break;
				case 3:if (a2 == 0 || a1%a2 > 0){ //割る数が0の時または余りが出る除算の時
						continue;
					}else ans = a1 / a2;
				}
				switch (i2){
				case 0:ans += a3; break;
				case 1:ans -= a3; break;
				case 2:ans *= a3; break;
				case 3:if (a3 == 0 || ans%a3 > 0){//割る数が0の時または余りが出る除算の時
						continue;
				}
					   else ans /= a3;
				}
				switch (i3){
				case 0:ans += a4; break;
				case 1:ans -= a4; break;
				case 2:ans *= a4; break;
				case 3:if (a4 == 0 || ans%a4 > 0){//割る数が0の時または余りが出る除算の時
						continue;
				}
					   else ans /= a4;
				}
				if (ans == 10){ //答えが10になったとき
					return true;
				}
			}
		}
	}
	return false;//答えが10以外の時
}

void chan(int j){
	int i1,i2,i3,t,tmp;
	
	//数値を整列
	for (i1 = 0; i1 < j; i1++){
		for (i2 = 0; i2 < 3; i2++){
			for (i3 = i2 + 1; i3 < 4; i3++){
				if (suubuf[i1][i2] > suubuf[i1][i3]){
					tmp = suubuf[i1][i2];
					suubuf[i1][i2] = suubuf[i1][i3];
					suubuf[i1][i3] = tmp;
				}
			}
		}
	}

	//数値の出力
	for (i1 = 0; i1 < j; i1++){
		printf("%d%d%d%d\n", suubuf[i1][0], suubuf[i1][1], suubuf[i1][2], suubuf[i1][3]);
	}
}

box
記事: 2002
登録日時: 14年前

Re: 4桁の数字を+-*/を使って10にするプログラム

#4

投稿記事 by box » 9年前

演算子(四則とカッコ)の優先順位について、どのようにプログラミングするか

スタックというデータ構造
に関する知識が必要であるように思います。

今のプログラムで、例えば
9 / ( 8 * ( 7 + 6 ) )
というような式(答えが10にならないのは承知の上です)を処理できるでしょうか。

0~9の数字は4重のfor文で回すのはまあいいとして、四則演算子とカッコは
どこに来るかわかりませんよね。けっこうハードル高いですよ。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

ロード
記事: 12
登録日時: 9年前

Re: 4桁の数字を+-*/を使って10にするプログラム

#5

投稿記事 by ロード » 9年前

確かに()による演算を考慮した部分が最初にしかないため複数の()もしくは割る数のほうに()がつく計算に全く対応出来てないですね。
演算子の優先順位のプログラミングについて考え直さないといけないですね。
スタックというものについて少し調べてきましたが
今回の物と関連性が分からなかったので少し教えてもらってもよろしいでしょうか?

かずま

Re: 4桁の数字を+-*/を使って10にするプログラム

#6

投稿記事 by かずま » 9年前

ロード さんが書きました: 演算子の優先順位のプログラミングについて考え直さないといけないですね。
スタックというものについて少し調べてきましたが
今回の物と関連性が分からなかったので少し教えてもらってもよろしいでしょうか?
4つの数と、3つの演算子による式 a - b - c - d (ただし- は、
+ - * / の演算子) において、演算の実行順序は、次の 5通り。

コード:

    ((a -   b) -  c)  - d   : 1 2 3
     (a -  (b  -  c)) - d   : 2 1 3
     (a -   b) - (c   - d)  : 1 3 2  or  3 1 2
      a - ((b  -  c)  - d)  : 2 3 1
      a -  (b  - (c   - d)) : 3 2 1
これらを全部試せばよいでしょう。
演算子の優先順位も、スタックも不要です。

それから、割り算をどう定義するかです。
0 で割るのはダメでしょうが、
割り切れない時もダメにするのか、それとも分数にするのか?

かずま

Re: 4桁の数字を+-*/を使って10にするプログラム

#7

投稿記事 by かずま » 9年前

関数ポインタを使わず、演算子を番号で表現してみました。

コード:

int f(int a, int o, int b)
{
    switch (o) {
    case 0: return a + b;
    case 1: return a - b;
    case 2: return a * b;
    case 3:
        if (b == 0) return 999999;
        if (a % b != 0) return 888888;
        return a / b;
    }
}

// a, b, c, d は数。p, q, r は演算子  
int can_make_ten(int a, int p, int b, int q, int c, int r, int d)
{
    if (f(f(f(a, p, b), q, c), r, d) == 10) return 1;
    if (f(f(a, p, f(b, q, c)), r, d) == 10) return 1;
    if (f(f(a, p, b), q, f(c, r, d)) == 10) return 1;
    if (f(a, p, f(f(b, q, c), r, d)) == 10) return 1;
    if (f(a, p, f(b, q, f(c, r, d))) == 10) return 1;
    return 0;
}
プログラムは書いていません。アイデアだけです。

ロード
記事: 12
登録日時: 9年前

Re: 4桁の数字を+-*/を使って10にするプログラム

#8

投稿記事 by ロード » 9年前

この考え方でpqrの数字を回せばうまくいきそうですね。ちょっと時間が出来たときにやってみます。

かずま

Re: 4桁の数字を+-*/を使って10にするプログラム

#9

投稿記事 by かずま » 9年前

ロード さんが書きました:この考え方でpqrの数字を回せばうまくいきそうですね。ちょっと時間が出来たときにやってみます。
回してみました。

コード:

int can_make_ten(int a, int b, int c, int d)
{
    int p, q, r;
    for (p = 0; p < 4; p++) {
        for (q = 0; q < 4; q++) {
            for (r = 0; r < 4; r++) {
                if (f(f(f(a, p, b), q, c), r, d) == 10) return 1;
                if (f(f(a, p, f(b, q, c)), r, d) == 10) return 1;
                if (f(f(a, p, b), q, f(c, r, d)) == 10) return 1;
                if (f(a, p, f(f(b, q, c), r, d)) == 10) return 1;
                if (f(a, p, f(b, q, f(c, r, d))) == 10) return 1;
            }
        }
    }
    return 0;
}
関数へのポインタを使うと、毎回 switch文で判別しなくてよくなります。

コード:

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 (b == 0) ? 999999 : (a / b); }

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

int can_make_ten(int a, int b, int c, int d)
{
   int i, j, k;
   for (i = 0; i < 4; i++) {
      int (*p)(int, int) = o[i];
      for (j = 0; j < 4; j++) {
         int (*q)(int, int) = o[j];
         for (k = 0; k < 4; k++) {
            int (*r)(int, int) = o[k];
            if (r(q(p(a, b), c), d) == 10) return 1;
            if (r(p(a, q(b, c)), d) == 10) return 1;
            if (q(p(a, b), r(c, d)) == 10) return 1;
            if (p(a, r(q(b, c), d)) == 10) return 1;
            if (p(a, q(b, r(c, d))) == 10) return 1;
         }
      }
   }
   return 0;
}
やっぱり、割り算の結果は分数で持ちたいですね。
1158 は、8 / (1 - (1 / 5)) ですから。

整数の割り算なら、(5 / (1 + 1)) + 8 もありかな?

ロード
記事: 12
登録日時: 9年前

Re: 4桁の数字を+-*/を使って10にするプログラム

#10

投稿記事 by ロード » 9年前

もともと考えてたことは一応出来たので完成は完成しました。
(ただちゃんとコード化しただけですが)
分母が1になる計算以外全部切り捨ててしまえばいいのでちょっと分数の計算も比較的簡単に出来そうですがやめておきます。
完成したコードも載せておきます。ありがとうございました。

コード:

#include<stdio.h>

int f(int, int, int);
bool can_make_ten(int, int, int, int);
int seiretu(int);
int ans[6000][4];
int ans_s[6000];

int main(void){
	int a, b, c, d,cnt=0;
	bool y;
	for (a = 0; a < 10; a++){
		for (b = 0; b < 10; b++){
			for (c = 0; c < 10; c++){
				for (d = 0; d < 10; d++){
					y = can_make_ten(a, b, c, d);
					if (y == false){
						ans[cnt][0] = a;
						ans[cnt][1] = b;
						ans[cnt][2] = c;
						ans[cnt][3] = d;
						cnt++;
					}
				}
			}
		}
	}
	cnt=seiretu(cnt);
	for (a = 0; a < cnt; a++){
		printf("%d\n", ans_s[a]);
	}
	printf("cnt=%d", cnt);
	rewind(stdin);
	getchar();
	return 0;
}

int f(int a, int o, int b)
{
	switch (o) {
	case 0: return a + b;
	case 1: return a - b;
	case 2: return a * b;
	case 3:
		if (b == 0) return 999999;
		if (a % b != 0) return 888888;
		return a / b;
	}
}

bool can_make_ten(int a, int b, int c, int d)
{
	int p, q, r;
	for (p = 0; p < 4; p++) {
		for (q = 0; q < 4; q++) {
			for (r = 0; r < 4; r++) {
				if (f(f(f(a, p, b), q, c), r, d) == 10) return true;
				if (f(f(a, p, f(b, q, c)), r, d) == 10) return true;
				if (f(f(a, p, b), q, f(c, r, d)) == 10) return true;
				if (f(a, p, f(f(b, q, c), r, d)) == 10) return true;
				if (f(a, p, f(b, q, f(c, r, d))) == 10) return true;
			}
		}
	}
	return false;
}

int seiretu(int cnt){
	int a,tmp,i,j;
	for (a = 0; a < cnt; a++){
		for (i = 0; i < 3; i++){
			for (j = i+1; j < 4; j++){
				if (ans[a][i]>ans[a][j]){
					tmp = ans[a][i];
					ans[a][i] = ans[a][j];
					ans[a][j] = tmp;
				}
			}
		}
		ans_s[a] = 1000 * ans[a][0] + 100 * ans[a][1] + 10 * ans[a][2] + ans[a][3];
	}
	for (i = 0; i < cnt - 1; i++){
		for (j = i + 1; j < cnt; j++){
			if (ans_s[i]>ans_s[j]){
				tmp = ans_s[i];
				ans_s[i] = ans_s[j];
				ans_s[j] = tmp;
			}
			else if (ans_s[i] == ans_s[j]){
				for (a = j; a < cnt; a++) ans_s[a] = ans_s[a + 1];
				cnt--;
			}
		}
	}
	return cnt;
}

閉鎖

“C言語何でも質問掲示板” へ戻る