桥本分数(回溯)
题目:
把{1, 2, 3…9}这9个数填入图中9个方格当中,使得等式成立(要求不得重复)。
大致过程如下: 该过程是前几次操作得到第一个符合全部填满并且数字不同的情况,没有画出前两个式子。
(仅供参考)
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
int a[10];
int main()
{
int i, g, s;
long m1, m2, m3; // 分母
s = 0;
i = 1, a[1] = 1;
while(1)
{
g = 1; // 判断是否存在相同数字的标志数
for(int k = i - 1; k >= 1; k --)
{
if(a[k] == a[i]) {g = 0; break;} // 维护数字的不同
}
if(i == 9 && g == 1 && a[1] > a[4])
{
m1 = a[2] * 10 + a[3];
m2 = a[5] * 10 + a[6];
m3 = a[8] * 10 + a[9];
if(a[1] * m2 * m3 + a[4] * m1 * m3 == a[7] * m1 * m2) // 分数变成乘数好计算 ( 两边同时乘以 m1 * m2 * m3 )
{
printf("%d/%ld + %d/%ld = %d/%ld", a[1], m1, a[4], m2, a[7], m3);
cout << endl;
s ++;
}
}
if(i < 9 && g == 1) {i ++; a[i] = 1; continue;} // 各个位置的数字都是从 1 开始递增的,包括全部填满之后
while(a[i] == 9 && i > 1) i --; // 回溯
if(a[i] == 9 && i == 1) break; // 如果回溯的递增到第一个格子为 9 时,回溯结束
else a[i] ++;
}
cout << "解法总共有 " << s << " 种" << endl;
return 0;
}