普通个人电脑
#include <iostream>
using namespace std;
const int N = 6; //number of rulers
const int MAX = N*(N+1)*(N+2)/6; //number of lengths
int i, j; //indexes for traversing array
int temp; //temp lengths for current ruler
int b; //for checking repeat lengths
int a; //answer array
int back() //back one section
{
a = 0;
j--;
if (j == 0) {i++; j = i;}
return 0;
}
int next() //forward to next section
{
j++;
if (j > i) {i--; j = 1;}
return 0;
}
int showAnswer() //show an anwser
{
int i, j;
for (i = N; i > 0; i--)
{
for (j = i; j > 1; j--) cout << a << ",";
cout << a << "|";
}
cout << endl;
return 0;
}
int check() //check for duplicated or invalid lengths
{
int m;
if (a > a) return 1; //ruler in wrong direction
temp = a;
for (m = 1; m < j; m++)
{
temp = temp + a;
if (temp > MAX) return 1; //length exceeds MAX
if (b]) return 2; //length exists already
}
for (m = 0; m < j; m++) b] = 1;
return 0;
}
int cancel() //cancel and rollback current section
{
int m;
temp = a;
b] = 0;
for (m = 1; m < j; m++)
{
temp = temp + a;
b] = 0;
}
return 0;
}
int main()
{
int flag, count = 0;
// initialisation
for (i = 0; i <= N; i++) for (j = 0; j <= N; j++) a = 0;
for (i = 0; i <= MAX; i++) b = 0;
i = N, j = 1; // start at last ruler, first section
while (1)
{
if (a && b]) cancel(); // rollback previous actions
a++;
if (i == N && j == 1) cout << "[" << a << "]" << endl; //track progress
while (b] && a + a <= MAX) a++;
if (a + a > MAX)
{
back();
if (i > N) break;
}
else
{
flag = check();
if (flag == 0)
{
if (i == 1)
{
count++;
showAnswer();
}
else next();
}
else if (flag == 1)
{
back();
if (i > N) break;
}
}
}
cout << "\nThe number of answers is: " << count << endl;
return 0;
} //rulers.cpp
这个C++程序是根据几年前百度贴吧一位吧友的算法改编而成，可能不及mathe站主的C程序有效率，在我的core-i7手提电脑上也要运行接近十分钟才完成穷搜。。。
我的台式机性能应该比笔记本好。core i7 3.7GHz
我运行了下你的代码，在我机器上4分多一点
mathe 发表于 2014-12-16 21:47
我运行了下你的代码，在我机器上4分多一点
可能我的compiler不好，不能尽用四核CPU的威力。。。另外我的2.9GHz CPU的确不及你的快。。。
编译器我是g++ -O3
我的结果也出来了。搜索6把尺子，在我的笔记本电脑上用时3分钟。
我的运行环境：
CPU i7-4700HQ 2.4GH，编译器：VS 2010.
我们程序可搜1-8把尺子的方案。目前只计算了前6把尺子。下面我的程序的运行结果。
Is searching the soultion when rule count is 1
(1,)
It take 0 ms and find 1 solution
Is searching the soultion when rule count is 2
(4,)
(1,2,)
(2,)
(1,3,)
It take 0 ms and find 2 solution
Is searching the soultion when rule count is 3
(9,)
(4,6,)
(1,2,5,)
(8,)
(2,5,)
(1,3,6,)
(6,)
(4,5,)
(2,1,7,)
(7,)
(2,8,)
(3,1,5,)
(10,)
(1,7,)
(3,2,4,)
It take 0 ms and find 5 solution
Is searching the soultion when rule count is 4
(19,)
(6,8,)
(4,7,9,)
(1,2,10,5,)
(15,)
(8,10,)
(4,5,7,)
(1,2,11,6,)
(16,)
(9,10,)
(5,2,13,)
(1,3,8,6,)
(13,)
(6,12,)
(7,2,8,)
(1,3,11,5,)
(18,)
(6,14,)
(2,7,10,)
(1,4,8,3,)
(20,)
(6,8,)
(7,3,9,)
(1,4,11,2,)
(8,)
(6,14,)
(7,3,9,)
(1,4,11,2,)
(20,)
(4,14,)
(2,9,8,)
(1,5,7,3,)
(11,)
(8,10,)
(3,2,12,)
(1,6,9,4,)
(14,)
(3,13,)
(4,5,6,)
(1,7,10,2,)
(9,)
(4,14,)
(5,7,8,)
(2,1,10,6,)
(7,)
(8,10,)
(6,5,9,)
(2,1,12,4,)
(10,)
(8,9,)
(6,1,12,)
(2,3,11,4,)
(12,)
(6,13,)
(7,1,9,)
(2,3,11,4,)
(19,)
(7,11,)
(3,5,12,)
(2,4,9,1,)
(16,)
(9,10,)
(1,7,5,)
(2,4,11,3,)
(14,)
(9,11,)
(5,3,7,)
(2,4,12,1,)
(14,)
(5,10,)
(3,4,9,)
(2,6,11,1,)
(10,)
(4,12,)
(5,1,13,)
(2,7,8,3,)
(19,)
(8,12,)
(1,6,10,)
(3,2,9,4,)
(17,)
(6,10,)
(1,7,12,)
(3,2,9,4,)
(9,)
(8,12,)
(6,4,7,)
(3,2,13,1,)
(16,)
(9,11,)
(1,5,13,)
(3,4,8,2,)
(18,)
(4,10,)
(2,7,6,)
(3,5,11,1,)
(10,)
(4,14,)
(2,7,6,)
(3,5,11,1,)
(12,)
(4,14,)
(2,5,8,)
(3,6,10,1,)
(10,)
(7,12,)
(6,3,8,)
(4,1,13,2,)
(8,)
(6,11,)
(7,3,9,)
(4,1,13,2,)
(8,)
(5,15,)
(3,7,9,)
(4,2,11,1,)
(15,)
(5,7,)
(1,8,10,)
(4,2,11,3,)
(10,)
(7,11,)
(5,3,9,)
(4,2,13,1,)
(9,)
(5,12,)
(7,3,8,)
(4,2,13,1,)
(15,)
(2,18,)
(5,6,8,)
(4,3,9,1,)
(9,)
(4,16,)
(3,7,8,)
(5,1,11,2,)
(14,)
(9,11,)
(1,15,3,)
(5,2,6,4,)
(19,)
(9,11,)
(1,14,2,)
(5,3,4,6,)
(9,)
(2,16,)
(4,6,7,)
(5,3,11,1,)
(12,)
(2,16,)
(4,3,10,)
(5,6,8,1,)
(18,)
(8,11,)
(2,3,12,)
(6,1,9,4,)
(15,)
(5,14,)
(4,3,13,)
(6,2,9,1,)
(17,)
(6,10,)
(1,14,4,)
(7,2,3,8,)
(16,)
(6,12,)
(4,1,14,)
(7,2,8,3,)
(12,)
(4,13,)
(1,14,5,)
(7,3,6,2,)
(19,)
(2,16,)
(3,10,4,)
(8,1,6,5,)
(20,)
(6,12,)
(1,13,3,)
(8,2,5,4,)
(13,)
(3,14,)
(4,11,5,)
(10,2,6,1,)
(17,)
(3,13,)
(4,10,5,)
(11,1,6,2,)
It take 0 ms and find 47 solution
Is searching the soultion when rule count is 5
(34,)
(14,18,)
(5,20,8,)
(9,7,15,4,)
(1,2,10,11,6,)
(33,)
(5,22,)
(7,12,16,)
(4,9,11,10,)
(1,2,15,8,6,)
(22,)
(9,23,)
(5,15,14,)
(7,10,16,2,)
(1,3,8,13,6,)
(35,)
(16,17,)
(6,14,12,)
(10,5,8,11,)
(1,3,18,7,2,)
(30,)
(12,19,)
(2,9,15,)
(10,8,14,3,)
(1,4,16,7,6,)
(32,)
(16,18,)
(7,15,13,)
(8,11,12,2,)
(1,5,4,17,3,)
(27,)
(4,18,)
(8,16,9,)
(7,10,11,2,)
(1,5,14,12,3,)
(20,)
(4,28,)
(2,15,10,)
(11,5,13,6,)
(1,7,14,9,3,)
(23,)
(12,22,)
(6,20,7,)
(4,13,15,3,)
(1,8,2,14,5,)
(26,)
(4,25,)
(12,3,20,)
(6,10,11,7,)
(1,8,5,17,2,)
(29,)
(5,22,)
(4,14,12,)
(3,8,13,7,)
(1,9,6,17,2,)
(29,)
(6,25,)
(7,13,8,)
(3,9,14,4,)
(1,10,5,17,2,)
(32,)
(9,15,)
(8,13,14,)
(3,2,20,6,)
(1,10,7,12,4,)
(22,)
(8,19,)
(3,12,13,)
(5,4,20,6,)
(1,10,7,14,2,)
(28,)
(4,27,)
(6,13,11,)
(5,9,12,8,)
(2,1,15,7,10,)
(18,)
(10,22,)
(7,6,17,)
(9,11,14,1,)
(2,3,16,8,4,)
(32,)
(14,20,)
(1,12,17,)
(9,7,8,11,)
(2,3,18,4,6,)
(24,)
(14,20,)
(1,16,11,)
(7,6,9,10,)
(2,3,18,8,4,)
(21,)
(16,17,)
(11,7,13,)
(8,1,14,12,)
(2,3,19,6,4,)
(25,)
(9,22,)
(1,20,7,)
(10,5,8,11,)
(2,4,12,14,3,)
(27,)
(15,20,)
(11,10,13,)
(16,3,9,5,)
(2,4,18,7,1,)
(25,)
(15,17,)
(4,8,18,)
(10,1,20,3,)
(2,5,9,13,6,)
(34,)
(6,22,)
(13,4,16,)
(9,3,15,8,)
(2,5,14,10,1,)
(22,)
(6,28,)
(13,4,16,)
(9,3,15,8,)
(2,5,14,10,1,)
(26,)
(15,17,)
(3,16,11,)
(13,1,8,12,)
(2,5,18,6,4,)
(31,)
(10,18,)
(11,5,19,)
(8,4,21,1,)
(2,7,6,14,3,)
(33,)
(16,19,)
(4,20,6,)
(10,5,12,1,)
(2,7,14,8,3,)
(21,)
(1,29,)
(5,15,13,)
(9,3,19,4,)
(2,8,6,11,7,)
(35,)
(13,20,)
(4,12,14,)
(6,1,21,3,)
(2,9,8,10,5,)
(31,)
(4,20,)
(3,23,6,)
(7,8,10,9,)
(2,11,1,16,5,)
(25,)
(5,26,)
(7,10,18,)
(12,9,11,2,)
(3,1,15,8,6,)
(17,)
(5,26,)
(7,18,10,)
(12,9,11,2,)
(3,1,15,8,6,)
(28,)
(5,26,)
(10,7,18,)
(12,9,11,2,)
(3,1,15,8,6,)
(24,)
(13,22,)
(7,16,9,)
(15,5,6,8,)
(3,1,17,10,2,)
(26,)
(12,23,)
(5,15,7,)
(8,6,10,9,)
(3,1,17,11,2,)
(23,)
(11,24,)
(4,16,14,)
(12,6,7,8,)
(3,2,17,9,1,)
(33,)
(5,21,)
(2,20,12,)
(10,8,11,6,)
(3,4,9,14,1,)
(26,)
(10,19,)
(13,1,20,)
(2,6,16,9,)
(3,4,11,12,5,)
(21,)
(10,16,)
(1,24,9,)
(11,6,12,2,)
(3,4,15,8,5,)
(20,)
(10,19,)
(2,16,15,)
(8,1,13,12,)
(3,4,17,6,5,)
(29,)
(16,19,)
(5,12,15,)
(13,1,9,11,)
(3,4,18,6,2,)
(19,)
(13,16,)
(5,10,17,)
(14,9,11,1,)
(3,4,18,6,2,)
(23,)
(10,21,)
(2,9,15,)
(4,12,17,1,)
(3,5,14,6,7,)
(29,)
(8,26,)
(4,20,11,)
(10,5,17,1,)
(3,6,7,12,2,)
(30,)
(15,16,)
(2,21,12,)
(8,1,19,6,)
(3,7,4,13,5,)
(30,)
(9,17,)
(1,14,19,)
(5,6,16,2,)
(3,7,13,8,4,)
(29,)
(6,17,)
(5,16,9,)
(7,12,14,1,)
(3,8,2,18,4,)
(17,)
(6,23,)
(5,16,9,)
(7,12,14,1,)
(3,8,2,18,4,)
(21,)
(8,23,)
(1,26,7,)
(11,2,17,5,)
(3,9,6,10,4,)
(32,)
(1,23,)
(8,11,14,)
(7,2,20,6,)
(3,10,5,12,4,)
(29,)
(5,26,)
(9,6,19,)
(4,7,16,1,)
(3,10,8,12,2,)
(31,)
(7,17,)
(1,15,11,)
(5,4,19,6,)
(3,10,8,12,2,)
(17,)
(7,24,)
(1,15,11,)
(5,4,19,6,)
(3,10,8,12,2,)
(26,)
(10,24,)
(2,23,8,)
(1,6,13,9,)
(3,11,4,12,5,)
(33,)
(10,13,)
(2,22,7,)
(8,1,19,6,)
(3,11,4,12,5,)
(13,)
(10,23,)
(2,22,7,)
(8,1,19,6,)
(3,11,4,12,5,)
(30,)
(12,19,)
(9,2,23,)
(8,10,14,3,)
(4,1,15,6,7,)
(21,)
(15,19,)
(6,8,16,)
(3,7,13,12,)
(4,1,17,9,2,)
(31,)
(15,17,)
(7,11,16,)
(12,2,8,13,)
(4,1,19,6,3,)
(29,)
(13,19,)
(8,14,12,)
(16,2,9,6,)
(4,1,20,3,7,)
(23,)
(11,17,)
(1,19,13,)
(9,3,15,7,)
(4,2,8,16,5,)
(15,)
(9,23,)
(3,16,11,)
(8,5,20,1,)
(4,2,12,10,7,)
(21,)
(11,15,)
(10,9,14,)
(5,3,17,7,)
(4,2,16,12,1,)
(21,)
(11,14,)
(3,16,15,)
(5,7,10,13,)
(4,2,18,8,1,)
(20,)
(12,18,)
(3,16,15,)
(8,2,11,14,)
(4,5,17,6,1,)
(26,)
(6,25,)
(7,16,12,)
(5,3,14,10,)
(4,9,2,18,1,)
(20,)
(8,22,)
(6,11,12,)
(7,2,24,1,)
(4,10,5,13,3,)
(23,)
(9,22,)
(2,14,10,)
(3,5,20,7,)
(4,11,6,12,1,)
(28,)
(10,14,)
(8,9,16,)
(3,2,21,6,)
(4,11,7,12,1,)
(18,)
(14,15,)
(2,21,11,)
(9,10,12,4,)
(5,1,7,17,3,)
(27,)
(7,19,)
(3,14,18,)
(2,8,12,11,)
(5,1,15,9,4,)
(24,)
(2,30,)
(7,11,15,)
(4,10,13,8,)
(5,1,16,3,9,)
(24,)
(7,14,)
(4,15,16,)
(3,10,12,8,)
(5,1,17,9,2,)
(27,)
(14,16,)
(2,20,13,)
(11,4,8,9,)
(5,1,18,7,3,)
(32,)
(12,16,)
(8,13,14,)
(1,10,19,4,)
(5,2,15,3,6,)
(27,)
(11,14,)
(9,8,13,)
(3,12,19,1,)
(5,2,16,6,4,)
(22,)
(10,24,)
(8,12,11,)
(15,1,13,4,)
(5,2,19,6,3,)
(27,)
(16,18,)
(2,12,17,)
(8,3,21,1,)
(5,4,6,13,7,)
(26,)
(14,16,)
(3,17,15,)
(10,2,11,8,)
(5,4,18,6,1,)
(31,)
(13,15,)
(4,22,8,)
(10,9,14,2,)
(5,6,1,17,3,)
(28,)
(4,27,)
(14,2,17,)
(8,3,15,6,)
(5,7,13,9,1,)
(14,)
(15,17,)
(3,16,9,)
(2,4,20,7,)
(5,8,10,11,1,)
(22,)
(6,26,)
(4,13,12,)
(3,8,16,7,)
(5,9,1,18,2,)
(23,)
(7,22,)
(11,8,13,)
(6,3,24,1,)
(5,10,2,14,4,)
(24,)
(8,23,)
(10,3,19,)
(9,5,16,4,)
(6,1,11,15,2,)
(30,)
(10,22,)
(12,9,14,)
(16,2,11,4,)
(6,1,19,5,3,)
(22,)
(12,18,)
(2,14,17,)
(11,4,9,10,)
(6,1,20,5,3,)
(25,)
(15,17,)
(4,14,16,)
(10,1,12,8,)
(6,3,19,5,2,)
(31,)
(13,22,)
(3,17,9,)
(2,5,14,11,)
(6,4,8,15,1,)
(33,)
(3,23,)
(7,11,17,)
(2,13,14,5,)
(6,4,12,8,1,)
(20,)
(8,26,)
(1,17,13,)
(4,3,16,9,)
(6,5,10,12,2,)
(21,)
(2,28,)
(4,16,11,)
(1,8,15,10,)
(6,7,5,14,3,)
(32,)
(14,20,)
(1,15,11,)
(3,2,19,9,)
(6,7,10,8,4,)
(22,)
(3,29,)
(2,15,8,)
(4,12,14,5,)
(6,7,11,9,1,)
(33,)
(15,17,)
(1,24,5,)
(9,3,19,4,)
(6,8,2,11,7,)
(35,)
(5,22,)
(4,21,8,)
(1,10,13,7,)
(6,9,3,14,2,)
(30,)
(8,26,)
(5,12,11,)
(7,3,21,1,)
(6,9,4,14,2,)
(31,)
(10,22,)
(4,17,13,)
(6,3,15,5,)
(7,1,11,14,2,)
(20,)
(4,28,)
(2,21,10,)
(5,11,13,6,)
(7,1,14,3,9,)
(33,)
(13,18,)
(3,12,17,)
(11,5,9,10,)
(7,1,20,2,4,)
(29,)
(15,16,)
(5,13,17,)
(11,3,9,10,)
(7,1,20,4,2,)
(23,)
(15,20,)
(1,26,6,)
(4,12,13,5,)
(7,2,8,11,3,)
(30,)
(13,20,)
(4,22,5,)
(6,10,18,1,)
(7,2,12,3,8,)
(35,)
(16,17,)
(1,26,4,)
(10,5,13,6,)
(7,2,12,8,3,)
(12,)
(13,18,)
(5,16,6,)
(4,10,19,1,)
(7,2,15,8,3,)
(26,)
(6,18,)
(5,14,15,)
(2,9,21,1,)
(7,3,13,4,8,)
(31,)
(6,26,)
(1,16,12,)
(14,8,11,2,)
(7,3,15,5,4,)
(26,)
(14,16,)
(2,18,13,)
(11,4,8,9,)
(7,3,19,5,1,)
(21,)
(6,26,)
(2,15,14,)
(3,10,12,8,)
(7,4,5,18,1,)
(21,)
(1,28,)
(9,6,19,)
(5,13,14,3,)
(7,4,12,8,2,)
(25,)
(5,29,)
(1,22,9,)
(3,10,11,6,)
(7,8,4,14,2,)
(27,)
(11,22,)
(1,17,13,)
(3,9,16,7,)
(8,2,4,15,5,)
(19,)
(11,23,)
(1,16,15,)
(4,5,21,3,)
(8,2,12,6,7,)
(31,)
(4,17,)
(7,12,11,)
(1,13,15,5,)
(8,2,16,6,3,)
(26,)
(4,28,)
(1,20,13,)
(6,9,14,2,)
(8,3,7,12,5,)
(12,)
(13,19,)
(5,23,6,)
(10,4,16,1,)
(8,3,15,7,2,)
(31,)
(13,14,)
(3,20,9,)
(5,2,17,11,)
(8,4,6,15,1,)
(29,)
(1,24,)
(2,21,10,)
(5,13,14,3,)
(8,4,7,9,6,)
(19,)
(4,28,)
(7,11,12,)
(2,13,14,6,)
(9,1,16,5,3,)
(18,)
(4,28,)
(7,12,11,)
(2,13,14,6,)
(9,1,16,5,3,)
(23,)
(4,28,)
(11,7,12,)
(2,13,14,6,)
(9,1,16,5,3,)
(29,)
(8,26,)
(11,5,14,)
(3,12,13,7,)
(9,1,17,4,2,)
(25,)
(11,20,)
(1,17,16,)
(2,6,21,3,)
(9,4,10,5,7,)
(21,)
(15,16,)
(7,10,18,)
(2,4,23,3,)
(9,5,8,11,1,)
(32,)
(12,17,)
(8,13,10,)
(3,2,22,6,)
(9,7,4,14,1,)
(19,)
(13,15,)
(1,20,11,)
(4,3,22,5,)
(9,8,6,10,2,)
(31,)
(3,27,)
(4,15,13,)
(5,9,12,8,)
(10,1,6,16,2,)
(22,)
(14,17,)
(12,8,13,)
(2,5,23,4,)
(10,1,15,3,6,)
(25,)
(16,17,)
(8,13,14,)
(1,5,23,3,)
(10,2,7,11,4,)
(30,)
(4,29,)
(3,17,11,)
(6,8,13,5,)
(10,2,7,15,1,)
(27,)
(9,20,)
(5,6,19,)
(4,13,15,3,)
(10,2,14,7,1,)
(24,)
(6,28,)
(2,16,11,)
(5,9,17,4,)
(10,3,12,7,1,)
(27,)
(11,20,)
(6,17,12,)
(3,4,21,5,)
(10,8,1,13,2,)
(32,)
(16,17,)
(7,14,13,)
(2,4,22,3,)
(11,1,8,10,5,)
(31,)
(14,20,)
(10,9,13,)
(3,4,21,5,)
(11,1,15,2,6,)
(18,)
(8,25,)
(5,23,6,)
(4,10,16,1,)
(11,2,7,12,3,)
It take 265 ms and find 136 solution
Is searching the soultion when rule count is 6
(39,)
(15,27,)
(7,33,11,)
(13,19,22,2,)
(8,10,16,12,9,)
(3,14,6,25,4,1,)
It take 182256 ms and find 1 solution
这是我编写的代码。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
/* 说明：
我们定义尺子编号为i,(i>=0), 尺子i总是有i+1段。
我们首先搜索编号最大的尺子，然后搜索编号次小的尺子，最后搜索编号为0的尺子，在本程序尺子编号用rule_idx来表示
*/
#define MAX_RULES_COUNT 8 //最多可搜索8把尺子
#define MAX_SEG_COUNT120 //最多可覆盖120种不同的长度
int g_used; //used=1表示长度i可被尺子测量
int g_maxSegArr[]={1,4,10,20,35,56,84,120}; //maxSegArr表示尺子i可测量的不同长度的总数
int g_result; // result表示尺子i第j+1段的长度
int g_count;
void output_result( int rule_count)
{
int i,j;
for(i=0;i<rule_count;i++)
{
printf("(");
for(j=0;j<=i;j++)
printf("%d,",g_result);
printf(")\n");
}
printf("\n");
g_count++;
}
int check(int rule_idx, int deep, int *pNewSegCount, int newSegs[] )
{
int i,c,sum;
for (c=0,sum=0,i=deep-1;i>=0;i--)
{
sum += g_result;
if ( g_used )
return 0;
g_used=1;
newSegs=sum;
*pNewSegCount=c;
}
return 1;
}
//deep: 表示将要确定尺子第deep+1段的长度
void new_mark(int rule_count,int seg_count,int rule_idx, int deep)
{
int i,j,mid,flag,sum,new_used_count;
int new_used;
mid=rule_idx/2; //第rule_idx+1把尺子中间段的编号
for (sum=0,i=0;i<deep;i++)
sum += g_result;
for (i=1;i<=seg_count;i++)
{
if ( g_used)
continue;
if ( i + sum > seg_count)
break;
if ( deep==mid+1 && i< g_result )
continue;//消除重复的结果
g_result=i;
flag=check(rule_idx,deep+1,&new_used_count,new_used);
if (flag )
{
if ( rule_idx==0)
output_result(rule_count);
if ( deep==rule_idx)
new_mark(rule_count,seg_count,rule_idx-1,0);
else
new_mark(rule_count,seg_count,rule_idx,deep+1);
}
for ( j=0;j<new_used_count;j++)
g_used]=0;
}
}
void search(int n)
{
DWORD t;
printf("\nIs searching the soultion when rule count is %d\n",n);
t=::GetTickCount();
g_count=0;memset(g_result,0,sizeof(g_result));
new_mark(n,g_maxSegArr,n-1,0);
t=::GetTickCount()-t;
printf("It take %d ms and find %d solution\n",t,g_count);
}
int main(int argc, char* argv[])
{
int i;
for (i=1;i<=6;i++ ) search(i);
return 0;
}
我觉得上楼的58-62行是瓶颈。它需要检查很多次。改用链接来存储尚未可被尺子度量的数应该可加快搜索过程。晚上下班后重写一版，看看速度能否提高。
if ( g_used)
continue;
if ( i + sum > seg_count)
break;
不打算编写新版了。
刚刚测试了下3个程序的在我的电脑 (I7-4700HQ Vs2010) 运行时间，12#，22#和28#，仅仅测试一次。
12# 代码应该是没有消除对称的代码，运行时间为7分35秒
22# 代码的运行时间为5分34秒
28# 代码的的运行时间为2分35秒