猜猜我的手机号码？

gxqcn

我用30楼代码 if( temp>189e8 && temp<190e8 )还是9秒，不知道什么时候限制1出现2次 medie2005 的最大时间耗费是什么，int64的mod /运算？ 你的建议中最大缩短时间是靠什么？ 〇〇 发表于 2009-8-25 15:55

最大缩短时间应该是在 31# 除了第 1 条以外的建议， 其中最后一条比较重要，因为它避免了除法指令。 我之所以第1条未采用，也是因为它将涉及到除法指令，并让程序出现过多跳转而繁杂。

〇〇

with tmp as (select -1+level*2 p from dual connect by level<=50) select a.p*b.p,a.p,b.p from tmp a,tmp b where a.p>=b.p and mod(a.p*b.p,100)=43; A.P*B.P P P ---------- ---------- ---------- 143 13 11 243 27 9 1443 39 37 943 41 23 43 43 1 343 49 7 1643 53 31 3843 63 61 1943 67 29 3243 69 47 2343 71 33 4543 77 59 1343 79 17 243 81 3 1743 83 21 7743 89 87 6643 91 73 4743 93 51 1843 97 19 5643 99 57 20 rows selected.

gxqcn

我曾用 excel 表得到过上述数据，候选组合筛选比例为 40/2500 =1.6%，比较划算， 可惜需要除法运算（除法指令比较耗时），所以后来我就放弃用它了。

〇〇

搜来的不依赖hugecalc的非递归全排列实现 #include #include //#include void output(int *p); //输出函数 void permutation(int *p);//全排列函数 int a[]={0,1,2,5,6,7};//待排列数组 int N=sizeof(a)/sizeof(int); //数组长度 int *p=a; //数组指针 void main() { output(p); permutation(p); //调用全排列函数 //output(p); //输出排列结果 //getch(); } void permutation(int *p) { bool flag=false; //标志排列是否结束 int temp; //临时变量,用来交换数组元素 while(1) { for(int i=0;i=p[i+1]); //找到第一个大于或等于倒序元素的数组元素 j-=1; temp=p[i+1]; //交换这两个元素 p[i+1]=p[j]; p[j]=temp; j=0; while(j<(i+1)/2) //倒置倒充元素原位置以前的所有元素 { temp=p[j]; p[j]=p[i-j]; p[i-j]=temp; j++; } break; //跳出for循环, } } if(flag) //如果排列完,结束循环 break; output(p); //输出排列结果 } } void output(int *p) { for(int i=0;i

medie2005

hugecalc没有自带全排列算法.

gxqcn

44# 〇〇 兄弟， 全排列调用的是STL里的标准模板，与 HugeCalc 完全无关。 我在 35# 中调用 HugeCalc， 仅仅是用到其高精度计时器，以及快速得到指定范围内的素数清单， 而这些不涉及大数算法的接口，HugeCalc 是不作任何限制的，即无须注册亦可免费调用。

mathe

直接试除还是挺快的:

2. #include <algorithm>
3. using namespace std;
4. using namespace LiDIA;
6. #define HPRIME 1000
7. int primelist[HPRIME*HPRIME];
8. int pc;
9. void initp()
10. {
11. int i,j;
12. primelist[0]=primelist[1]=1;
13. for(i=2;i<HPRIME;i++){
14. if(!primelist[i]){//this is prime
15. for(j=i*i;j<HPRIME*HPRIME;j+=i){
16. primelist[j]=1;
17. }
18. }
19. }
20. for(i=2;i<HPRIME*HPRIME;i++){
21. if(!primelist[i]){
22. primelist[pc++]=i;
23. }
24. }
25. }
27. static int digitss[6]={0,1,2,5,6,7};
29. void test(long long r)
30. {
31. int i;
32. for(i=2;i<pc;i++){///skip prime 2 and 3
33. if(primelist[i]>=100000)return;
34. if(r%primelist[i]==0)break;
35. }
36. if(primelist[i]<10000)return;
37. printf("%lld=%lld*%lld\n",r,primelist[i],r/primelist[i]);
38. }
40. int main()
41. {
42. int i,j;
43. long long r=18900000000LL;
44. initp();
45. printf("Total %d primes found\n");
46. do{
47. for(i=0,j=0;j!=6;j++){
48. i=i*10+digitss[j];
49. }
50. i=i*100+43;
51. test(r+i);
52. }while(next_permutation(digitss,digitss+6));
53. }

复制代码

0.2秒

gxqcn

不知道现在大学里教不教 STL，因为我本人不是学这个专业的。 感觉 STL 是 C++ 的重要组成部分，应该好好应用。 可惜我周边的一些科班出身的对它反而并不怎么了解。

medie2005

呵呵,OO只是一时糊涂而已. STL在现实软件中不知道应用如何.

winxos

不知道现在大学里教不教 STL，因为我本人不是学这个专业的。 感觉 STL 是 C++ 的重要组成部分，应该好好应用。 可惜我周边的一些科班出身的对它反而并不怎么了解。 gxqcn 发表于 2009-8-26 11:30

是呀，接触了STL后才发现以前很多绞尽脑汁写的函数，STL中都有了，而且速度比我写的快的多。看国外的书一般都是推荐使用的，可以大大减少代码长度。