作者youngkai (年轻人)
看板CGI-Game
标题Re: [IKA] 军事分析器 (Firefox/火狐限定) (更新:ꔠ…
时间Wed Jul 2 00:32:05 2008
想到一个解法
你另外写一只程式，function跟原来一样
只是多一行，在最後一个for加一个 if (answer[0] !=0 && answer[1] !=0 &&...自己填)
这代表这个input有解，就return 1; else return 0;
在主程式里加一个for
int has_answer[6000];
(for int i = 80; i < 6000; i++ ){
has_answer[i] = your_function(i);
}
(for int i = 80; i < 6000; i++ ){
if (has_answer[i] == 1)
cout << i << " has solution\n"; // 或者输出到一个文字档
}
接下来是改js
把上述80~6000有解的数字，放入int阵列，例如
int sol[];
sol[0] = 80;
sol[1] = 158;
sol[2] = 160;
.....
主程式改成
for(int i = 0; i < (sol的最大index); i++) {
if ( (input % sol[i]) == 0) //相除余数为零
your_function(input / sol[i], sol[i]);
}
这样一来，只要算sol[i]的解，结果都乘以input / sol[i]
就不用重复计算已经知道有解的整数倍的结果了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.168.217.123
1F：推 cowbaying:我写的不好吗? 哭哭 07/02 00:37
※ 编辑: youngkai 来自: 218.168.217.123 (07/02 00:39)
2F：推 shyangs:一楼有发布源码吗= =a 07/02 00:41
3F：推 neutrino:1. open source的好用 2. 网页的方便 07/02 00:42
4F：→ neutrino:我也在想一些修改 改好了在丢上来 07/02 00:42
5F：→ youngkai:我想到resursive的解法了，大致上原理差不多 07/02 00:43
6F：→ youngkai:如果80有解，80的倍数必定有解，所以先mod有解的i 07/02 00:44
7F：→ youngkai:如果是i的倍数，就不用跑那十几个for-loop了 07/02 00:44
8F：→ neutrino:不过这本来就是个np-hard问题 不用奢望他能跑太大的input 07/02 00:45
9F：→ neutrino:怎样设置一些(给使用者选择)的限定条件让他更实用才是重 07/02 00:46
10F：→ neutrino:点 07/02 00:46
11F：推 cowbaying:我没发原码...我用的只是简单的回圈而已 07/02 00:47
12F：→ cowbaying:等改进後再来发好了 目前在新增功能 07/02 00:48
13F：→ youngkai:因为是np-hard，所以用空间换时间是最好的解法 07/02 00:53
14F：推 neutrino:基本上 1082以後所有偶数都有解........这样帮助有限 07/02 13:01
15F：推 shyangs:更新，用一些代码取代最後一个兵种的for-loop计算。 07/02 13:28