猜猜我的手机号码？

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 <stdio.h>
#include <conio.h>
//#include <windows.h>

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<N-1;i++)
{
flag=true; //如已排列完,falg为真

if(p[i]<p[i+1]) //如果发现第一个倒序的数组元素,p[i+1]被称为倒序元素
{
flag=false; //说明未排列完

int j=0;
while(p[j++]>=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<N;i++)
printf("%2d",p[i]);
printf("\n");

}

medie2005

hugecalc没有自带全排列算法.

gxqcn

44# 〇〇
兄弟，
全排列调用的是STL里的标准模板，与 HugeCalc 完全无关。

我在 35# 中调用 HugeCalc，
仅仅是用到其高精度计时器，以及快速得到指定范围内的素数清单，
而这些不涉及大数算法的接口，HugeCalc 是不作任何限制的，即无须注册亦可免费调用。

mathe

直接试除还是挺快的:

1. 
   
2. #include <algorithm>
   
3. using namespace std;
   
4. using namespace LiDIA;
   
5. 
   
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. }
    
26. 
    
27. static int digitss[6]={0,1,2,5,6,7};
    
28. 
    
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. }
    
39. 
    
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中都有了，而且速度比我写的快的多。看国外的书一般都是推荐使用的，可以大大减少代码长度。