填數字（小町蛀蟲算 009） - 拼圖

※ 引述《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--;
}
}
}
}

--