アルゴリズムの問題。数学ax+by=cを求めるプログラムを作っています。言語を問いません。

Question

仕事で金額の計算をしていて、
ポール : 24箇所 * 11789円 = 282936円
+
ポール用ボンド : a缶 * 2666円 = b円
+
取付費 : 24箇所 * c円 = d円

ポール + ボンド + 取付費 = 528000円(24箇所の合計金額)

となっていて、ボンドの数量a缶と取付費の単価c円を求めようとしています。
b + d = 528000 - 282936 = 245064
2666a + 24c = 245064
となりますので、つまり「ax + by = c」ということになります。

ネットで調べてみると「べズー等式」というやつらしくて、こちらを参考にしています。

上の画像の式の数字を置き換えると、
2666a % 24 = 245064 (2666aを24で割った余りが245064)
となり、プログラムでは、while文を使ってaを求めようとしています。

int a = 1;
while((2666 * a) % 24 != 245064)
    a ++;

System.out.println("a = " + a);

しかし、これではなぜか無限ループになってしまいます。
どこが違うんでしょうか？

Comments

[wake_up_kemeko]

2666a + 24c = 245064
を満たすaとcの組み合わせの一覧を出力したいのでしょうか？

Answer 1

べズー等式というのは全くわかりませんが…。
(2666 * a) % 24は24で割った余りなので、0～23しかありえません。
なので245064と一致することなく無限ループしているのだと思います。

Comments

[otftrough]

そうか、たしかにその通りだ。

Answer 2

aとcがどちらとも１以上の整数値を取るという条件であれば、

int aMax = Math.floor(245064 / 2666);
int tmp;
int c;

for(int a = 1; a <= aMax; a++){
    tmp = (245064 - a * 2666);
    if(tmp % 24 == 0){
        c = tmp / 24;
        System.out.println("a = " + i + ", c = " + c);
    }
}

ozwkさんの処理とほぼ一緒ですね。

Answer 3

ネットで調べてみると「べズー等式」というやつらしくて

ざっと調べた限り違います。
べズーの等式は
非0の2つの整数aとb、その最大公約数cに対して、
ax+by=cを満たすx,yの組が存在する。
ということです。

要するに今解こうとしている問題とべズーの等式は関係ないです。
問題を関係ない方法で解こうとしているので変なことになっています。

---

ax+by=cを求めたいとのことですが、
変数2つに対して式が1つと足りないので解けません。

x,yが自然数という条件つけても、解があるかは問題次第です。

---

間違っていたらすみません。:

//2666x + 24y = 245064 
int a = 2666;
int b = 24;
int c = 245064;

int x = 1;
while (a*x < c){
    if( (c - a*x)%b == 0){
        int y = (c - a*x)/b;
        printf("%d,%d\n",x,y);
    }
    x++;
}

12,8878
24,7545
36,6212
48,4879
60,3546
72,2213
84,880

Comments

[otftrough]

？？？工業高校卒なので、何言ってるのかさっぱりです...

[ozwk]

追記しました

[otftrough]

ありがとうございます、やっぱり計算だけが目的のプログラムなら、
手計算を忠実にプログラムに組み込むよりも、CPU任せにwhile文でただ答えをひとつひとつ調べて探すほうが楽ですね。

Answer 4

皆さん既出ですがC++で書いてみました。

#include<iostream>
int main() {
	int a, c;
	const int glue_val = 2666, attach_pos = 24, sum_val = 245064;

	int max_a = sum_val / glue_val;
	for (int i = 0; i < max_a; i++) {
		if ((sum_val - glue_val * i )% 24 == 0) {
			std::cout << "num_glue:" << i << "\t"
				<< "attach_val:" << (sum_val - glue_val * i) / attach_pos
				<< std::endl;
		}
	}


}

---

num_glue:0      attach_val:10211
num_glue:12     attach_val:8878
num_glue:24     attach_val:7545
num_glue:36     attach_val:6212
num_glue:48     attach_val:4879
num_glue:60     attach_val:3546
num_glue:72     attach_val:2213
num_glue:84     attach_val:880

Answer 5

すみません、計算方法が違ったみたいです。