Re: [問題] 填數字（小町蛀蟲算 009）

[utomaya (烏托馬雅)]

※ 引述《fredgo (F.D.)》之銘言：
: ※ 引述《utomaya (烏托馬雅)》之銘言：
: :    □           □           □
: : ________  -  ________  +  ________  = 0
: :  □ □        □ □        □ □
:     1/26    -    4/39    +    5/78    = 0
:     1/32    -    5/48    +    7/96    = 0
:     1/96    -    5/32    +    7/48    = 0
:     5/78    -    4/39    +    1/26    = 0
:     7/48    -    5/32    +    1/96    = 0
:     7/96    -    5/48    +    1/32    = 0
: :    □         □ □          □
: : ________  -  ________  + _________  = 0
: :    □         □ □        □ □
:      1/4    -   29/76    +    5/38    = 0
:      3/4    -   59/68    +    2/17    = 0
: : 上列兩式中，請在□中填入1~9的數字，使算式成立
: : 每個式子中1~9數字只能用一次。且每個分數必須為最簡分數，不可再約分。
: : 且不能為假分數
: : 例如
: :    7            3           4
: : ________  - ________  + _________  = 0 雖然1~9只用一次，且算式成立
: :   98           21          56
: : 但不是最簡分數，故為不合法的答案。
: :    5           29           7
: : ________  - ________  + _________  = 0 有假分數，也是不合法的答案。
: :    3           16          48
: 找到這幾組解
: 也許設計有唯一解的題目
: 會比較好推理吧^^a


是真的推理嗎? 還是跑程式的?

我是故意設計出那麼多解的，因為才可以看出是跑程式解出的，還是靠推理解出的?
怎麼你的解答和我的程式跑出來的解答一樣
連順序都一模一樣？

如果是推理的，大概找到一組解，就會認為自己已經解答出來了
(事實上，如果是用推理的，要找到一組解也很不簡單)
只有跑程式才能把所有的解找出來

在這邊說個故事好了，
                □           □           □
這題其實是從 ________  +  ________  +  ________  = 1 衍生出來的

               □ □        □ □        □ □

也就是帕索大說的那個著名的題目

當初是一個同事，mail給全公司的人的一個題目
當然，公司都是一些工程師，喜歡動動腦，大家就開始解題，

我做了幾分鐘後，就發覺根本沒有規律可言
於是就偷吃步，去跑程式
馬上解出來，有6解，但事實上是同一解，因為是同一解的3!種排列

然後我把解拿給原來寄給我們的同事，驗算後答案是對的
另外一個同事不太相信我能解那麼快，質問我：「你怎麼解的？」
我跟他說，我用程式去解的

後來，我對這些題目產生了興趣，就試了幾個這種題目的衍生題型
都用程式去解，有的可能有解，有的不一定有解
例如這個

    □           □         □ □
 ________  -  ________  +  ________  = 0
    □         □ □        □ □

此題無解，就算可以容許假分數，不一定要最簡分數，放寬條件後一樣無解。


而下面這題，假若不限制假分數跟最簡分數的話，有20解，2者皆限制只有一解。

    □           □         □ □
 ________  +  ________  +  ________  = 1
    □         □ □        □ □

最後，我得到一個結論，這只是自然界的偶然現象，
你要說這其中隱藏了什麼數論的大道理，我認為沒有，純粹只是巧合而已

為了證明我所言不虛，底下附上我的程式碼
有興趣的，可以用C++ compiler來驗證一下

solution代表的是第一式或第二式的解答
定義成1代表第一式的解答，2代表第二式的解答

#include "stdafx.h"
#include "iostream.h"
#include "math.h"
#include "conio.h"

#define NUMBER 9
#define solution 2
int a[NUMBER];
int head, tail;

int count;
bool flag;
void print(int n);

int main(int argc, char* argv[])
{
        for(int i=0;i<NUMBER;i++)
                a[i] = i+1;


        count=0;
        print(NUMBER);

        cout << "\nTotal solutions:" << count << "\n";

        return 0;
}

void swap(int &a, int& b)
{
        int temp = a;
        a = b;
        b = temp;
}

unsigned int get_gcd(unsigned int a, unsigned int b)
{
        if(a==0 || b==0)
                return 0;

        unsigned int quotient, remain=(a<b) ?a :b;

        while(remain!=0)
        {
                quotient = a/b;
                remain = a - quotient*b;
                a = b;
                b = remain;
        }
        return a;
}

void print(int n)
{
        if(n==1)
        {
                flag = false;
                unsigned int part_a, part_b, part_c, part_d, part_e, part_f;
                unsigned int answer;

#if solution==1
                part_a = a[0];
                part_b = 10*a[1]+a[2];
                part_c = a[3];
                part_d = 10*a[4]+a[5];
                part_e = a[6];
                part_f = 10*a[7]+a[8];

#else if solution==2

                part_a = a[0];
                part_b = a[1];
                part_c = 10*a[2]+a[3];
                part_d = 10*a[4]+a[5];
                part_e = a[6];
                part_f = 10*a[7]+a[8];
#endif

                answer = part_a*part_d*part_f - part_c*part_b*part_f + part_e*part_b*part_d;

                unsigned gcd1 = get_gcd(part_a, part_b);
                unsigned gcd2 = get_gcd(part_c, part_d);
                unsigned gcd3 = get_gcd(part_e, part_f);

                if(answer==0 && part_a<part_b && part_c<part_d && part_e<part_f && gcd1==1 && gcd2==1 && gcd3==1)
                {
                        flag=true;
                }

                if(flag)
                {
                        count++;
#if solution==1
                        cout << a[0] << "/" << a[1] << a[2] << " - ";
                        cout << a[3] << "/" << a[4] << a[5] << " + ";
                        cout << a[6] << "/" << a[7] << a[8] << " = " << " 0 ";
                        cout<<"\n";
#else if solution==2
                        cout << a[0] << "/" << a[1] << " - ";
                        cout << a[2] << a[3] << "/" << a[4] << a[5] << " + ";
                        cout << a[6] << "/" << a[7] << a[8] << " = " << " 0 ";
                        cout<<"\n";
#endif
                }
                return;
        }

        for(int j = 0; j<n;j++)
        {
                print(n-1);
                if(j<n-1)
                {
                        int index = NUMBER-j-1;
                        head = NUMBER-n;
                        tail = NUMBER-1;
                        swap(a[head], a[index]);
                        head++;
                        for(int k=0;k<n/2;k++)
                        {
                                swap(a[head], a[tail]);
                                head++;
                                tail--;
                        }
                }
        }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.115.136.209
※ 編輯: utomaya         來自: 58.115.136.209       (07/08 13:51)
推 puzzlez:靠推理還是可能找出全解的...至少我是這麼相信^^"
推 puzzlez:那個經典題可否用推理來推算？答案是肯定的，即使它不規則
推 puzzlez:http://tinyurl.com/2vap89 請參考此人的答案.....:-)
※ 編輯: utomaya         來自: 58.115.136.209       (07/08 14:54)
推 fredgo:哈哈 被抓包了XD 其實是看到很多這種題目 不過總是會懷疑
→ fredgo:是否有解 所以就寫了一個專門寫這類問題的程式啦^^a
→ fredgo:不過我是用fortran寫的 有空看看邏輯程序一樣不一樣^^
※ 編輯: utomaya         來自: 58.115.136.209       (07/10 22:00)