r****y
发帖数: 1437 | 1
此程序four1.for用于追赶法加FFT解椭圆方程会出问题, 需要使用
realft.for如下
SUBROUTINE realft(data,n,isign)
INTEGER isign,n
REAL data(n)
CU USES four1
INTEGER i,i1,i2,i3,i4,n2p3
REAL c1,c2,h1i,h1r,h2i,h2r,wis,wrs
DOUBLE PRECISION theta,wi,wpi,wpr,wr,wtemp
theta=3.141592653589793d0/dble(n/2)
c1=0.5
if (isign.eq.1) then
c2=-0.5
call four1(data,n/2,+1)
else
c2=0.5
theta=-theta
endif
wpr=-2.0d0*sin(0.5d0*theta) |
|
Q*****a
发帖数: 33 | 2 没想到什么比O(n^2)好的方法，毕竟是partially order, 不是total order
但到不了O(n^2*l), 只是O(n^2 + nl).只需要过一遍string计算sign就可以了，另外将
数组按长度从大到小排列，提前剪枝也可以优化一些，但复杂度还是O(n^2)
const int INT_BITS = sizeof(int) * 8;
const int DATA_LEN = 256/INT_BITS;
class Int256 {
vector data;
public:
Int256(): data(DATA_LEN, 0) {
}
Int256(string s): data(DATA_LEN, 0) {
for (auto c: s) {
Set((unsigned char)c);
}
}
void Set(int l) {
data[l/INT_BITS] |= 1 << (l%INT_BITS);
}
... 阅读全帖 |
|
r****y
发帖数: 1437 | 3
SUBROUTINE four1(data,nn,isign)
INTEGER isign,nn
REAL data(2*nn)
INTEGER i,istep,j,m,mmax,n
REAL tempi,tempr
DOUBLE PRECISION theta,wi,wpi,wpr,wr,wtemp
n=2*nn
j=1
do 11 i=1,n,2
if(j.gt.i)then
tempr=data(j)
tempi=data(j+1)
data(j)=data(i)
data(j+1)=data(i+1)
data(i)=tempr
data(i+1)=tempi
endif
m=n/2
1 if ((m.ge.2).and.(j.gt.m)) then
j=j-m
|
|
|
