gxqcn
发表于 2009-8-25 18:55:58
我用30楼代码 if( temp>189e8 &&temp<190e8 )还是9秒，不知道什么时候限制1出现2次
medie2005 的最大时间耗费是什么，int64的mod /运算？
你的建议中最大缩短时间是靠什么？
〇〇 发表于 2009-8-25 15:55 http://bbs.emath.ac.cn/images/common/back.gif
最大缩短时间应该是在 31# 除了第 1 条以外的建议，
其中最后一条比较重要，因为它避免了除法指令。
我之所以第1条未采用，也是因为它将涉及到除法指令，并让程序出现过多跳转而繁杂。
〇〇
发表于 2009-8-25 20:21:52
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
发表于 2009-8-25 20:45:03
我曾用 excel 表得到过上述数据，候选组合筛选比例为 40/2500 =1.6%，比较划算，
可惜需要除法运算（除法指令比较耗时），所以后来我就放弃用它了。
〇〇
发表于 2009-8-26 11:08:32
搜来的不依赖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<p) //如果发现第一个倒序的数组元素,p被称为倒序元素
{
flag=false; //说明未排列完
int j=0;
while(p>=p); //找到第一个大于或等于倒序元素的数组元素
j-=1;
temp=p; //交换这两个元素
p=p;
p=temp;
j=0;
while(j<(i+1)/2) //倒置倒充元素原位置以前的所有元素
{
temp=p;
p=p;
p=temp;
j++;
}
break; //跳出for循环,
}
}
if(flag) //如果排列完,结束循环
break;
output(p); //输出排列结果
}
}
void output(int *p)
{
for(int i=0;i<N;i++)
printf("%2d",p);
printf("\n");
}
medie2005
发表于 2009-8-26 11:23:35
hugecalc没有自带全排列算法.
gxqcn
发表于 2009-8-26 11:24:48
44# 〇〇
兄弟，
全排列调用的是STL里的标准模板，与 HugeCalc 完全无关。
我在 35# 中调用 HugeCalc，
仅仅是用到其高精度计时器，以及快速得到指定范围内的素数清单，
而这些不涉及大数算法的接口，HugeCalc 是不作任何限制的，即无须注册亦可免费调用。
mathe
发表于 2009-8-26 11:27:31
直接试除还是挺快的:
#include <algorithm>
using namespace std;
using namespace LiDIA;
#define HPRIME 1000
int primelist;
int pc;
void initp()
{
int i,j;
primelist=primelist=1;
for(i=2;i<HPRIME;i++){
if(!primelist){//this is prime
for(j=i*i;j<HPRIME*HPRIME;j+=i){
primelist=1;
}
}
}
for(i=2;i<HPRIME*HPRIME;i++){
if(!primelist){
primelist=i;
}
}
}
static int digitss={0,1,2,5,6,7};
void test(long long r)
{
int i;
for(i=2;i<pc;i++){///skip prime 2 and 3
if(primelist>=100000)return;
if(r%primelist==0)break;
}
if(primelist<10000)return;
printf("%lld=%lld*%lld\n",r,primelist,r/primelist);
}
int main()
{
int i,j;
long long r=18900000000LL;
initp();
printf("Total %d primes found\n");
do{
for(i=0,j=0;j!=6;j++){
i=i*10+digitss;
}
i=i*100+43;
test(r+i);
}while(next_permutation(digitss,digitss+6));
}
0.2秒
gxqcn
发表于 2009-8-26 11:30:24
不知道现在大学里教不教 STL，因为我本人不是学这个专业的。
感觉 STL 是 C++ 的重要组成部分，应该好好应用。
可惜我周边的一些科班出身的对它反而并不怎么了解。
medie2005
发表于 2009-8-26 12:17:07
呵呵,OO只是一时糊涂而已.
STL在现实软件中不知道应用如何.
winxos
发表于 2009-8-26 14:32:16
不知道现在大学里教不教 STL，因为我本人不是学这个专业的。
感觉 STL 是 C++ 的重要组成部分，应该好好应用。
可惜我周边的一些科班出身的对它反而并不怎么了解。
gxqcn 发表于 2009-8-26 11:30 http://bbs.emath.ac.cn/images/common/back.gif
是呀，接触了STL后才发现以前很多绞尽脑汁写的函数，STL中都有了，而且速度比我写的快的多。看国外的书一般都是推荐使用的，可以大大减少代码长度。