10534


○○○○ － ○○○○ ＝ ○○○○

他のサイトにあった問題です。  
この計算の中に０～９の数字を使わなければいけないといった問題です。  
同じ数字を使っても良いです。  
０～９の数字を全て使ってかつ、正しい筆算になるのは何通りなのか求めたいです。

javaかCで解きたいのですが、解き方が浮かびません。  
また、このような問題を解くときに便利なライブラリ等はあるのでしょうか？  
解き方や考え方を教えてください。


CC BY-SA 3.0
2015-05-23T04:09:36.000
10531
2015-06-08T23:55:47.867
2015-05-23T07:24:43.653
49
9850
question
java c アルゴリズム
Java,Cの計算問題についての質問です


式をA-B=Cと表すと、

  * Aは0000～9999
  * Bは0000～A
  * CはA-B固定

と限定できます。なお0000や9999のようなぞろ目は残り9文字を使い切れないので実際にはあり得ません。

全ての組み合わせを考慮しても5000万通りぐらいしかありませんので工夫せずに計算してもすぐ終わります。C#でこんな感じに書くと300960通りとなりました。

[code]

    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++;
            }
        }
    }
    
[/code]


CC BY-SA 3.0
2015-05-23T04:35:44.863
10533
2015-05-23T04:35:44.863
5750
10531
answer


正しい筆算ということなので、`4718 - 0023 = 4695`のような式は除外しました。

[code]

    #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;
    }
    
[/code]


CC BY-SA 3.0
2015-05-23T05:04:08.817
10534
2015-05-23T05:10:02.580
2015-05-23T05:10:02.580
3639
3639
10531
answer


即席ですが

[code]

    #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;
    }
    
[/code]

結果  
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さんのと数がちがう・・・バグあればまた報告します。


CC BY-SA 3.0
2015-06-08T23:55:47.867
11139
2015-06-08T23:55:47.867
9528
10531
answer