○○○○ - ○○○○ = ○○○○
他のサイトにあった問題です。
この計算の中に0~9の数字を使わなければいけないといった問題です。
同じ数字を使っても良いです。
0~9の数字を全て使ってかつ、正しい筆算になるのは何通りなのか求めたいです。
javaかCで解きたいのですが、解き方が浮かびません。
また、このような問題を解くときに便利なライブラリ等はあるのでしょうか?
解き方や考え方を教えてください。
スタック・オーバーフローはプログラマーとプログラミングに熱心な人のためのQ&Aサイトです。すぐ登録できます。
登録してこのコミュニティに参加する式をA-B=Cと表すと、
と限定できます。なお0000や9999のようなぞろ目は残り9文字を使い切れないので実際にはあり得ません。
全ての組み合わせを考慮しても5000万通りぐらいしかありませんので工夫せずに計算してもすぐ終わります。C#でこんな感じに書くと300960通りとなりました。
for (int a = 1; a < 10000; a++)
{
for (int b = 1; b < a; b++)
{
int c = a - b;
if (c < 0)
{
continue;
}
// 10種類含まれているかの判定
// C#以外ではこの部分を変える必要がある
if ((a * 100000000L + b * 10000 + c).ToString("D12").Distinct().Count() == 10)
{
count++;
}
}
}
正しい筆算ということなので、4718 - 0023 = 4695
のような式は除外しました。
#include <stdio.h>
int digit(int num) {
int a = num / 1000;
int b = (num - a * 1000) / 100;
int c = (num - a * 1000 - b * 100) / 10;
int d = (num - a * 1000 - b * 100 - c * 10);
return (1 << a) | (1 << b) | (1 << c) | (1 << d);
}
int main(void) {
int cnt = 0;
int lhs, rhs;
for (rhs = 1000; rhs <= 9999; ++rhs) {
for (lhs = rhs + 1000; lhs <= 9999; ++lhs) {
int ans = lhs - rhs;
if ((digit(lhs) | digit(rhs) | digit(ans)) == 0x3ff /* 0b1111111111 */) {
cnt++;
}
}
}
printf("%d\n", cnt);
return 0;
}
即席ですが
#include <stdio.h>
#include <stdbool.h>
bool test( int a, int b, int c )
{
int flg= 0;
//
while( a != 0 ){
flg |= (1 << a % 10);
a /= 10;
}
while( b != 0 ){
flg |= (1 << b % 10);
b /= 10;
}
while( c != 0 ){
flg |= (1 << c % 10);
c /= 10;
}
return (flg & 0x3ff) == 0x3ff;
}
int main()
{
int cnt= 0;
for( int a= 1; a < 9999; a++ ){
for( int b= 1; b < a; b++ ){
int c= a - b;
if( c <= 0 ){
continue;
}
if( test( a, b, c )){
printf( "a= %d, b= %d, c= %d\n", a, b, c);
cnt++;
}
}
}
printf("count=%d\n",cnt);
return 0;
}
結果
a= 1026, b= 437, c= 589
a= 1026, b= 439, c= 587
a= 1026, b= 487, c= 539
a= 1026, b= 489, c= 537
a= 1026, b= 537, c= 489
・
・
a= 9990, b= 8734, c= 1256
a= 9990, b= 8736, c= 1254
a= 9990, b= 8754, c= 1236
a= 9990, b= 8756, c= 1234
count=215436
pgrhoさんのと数がちがう・・・バグあればまた報告します。