posts - 3,  comments - 28,  trackbacks - 0
题目:

从1到N(100000)中任意拿掉两个数,把剩下的99998个数顺序打乱,并且放入数组A中。要求只扫描一遍数组,把这两个数找出来。可以使用最到不超过5个局部变量,不能用数组变量,并且不能改变原数组的值。

思路:

遍历一次数组,求出这两个数的和a+b 与积a*b
a+b = 1+2+3+4+...+N- sum(A[]);    (1)
a*b =  1*2*3*4*...*N / multi(A[]);   (2)

主要解决sum与multi的溢出问题

(1) 可化为 (N-A[0]) + (N-1-A[1]) + ...+ (3-A[N-3]) + 2 + 1

(2) 可以用对数来代替原数进行求积的等价运算,避免溢出的问题,但是这种方法会产生一些精度上的问题,不知道大家有什么更好的方法!
先求出log(a*b) :
                         = log(1*2*3*4*....*N)/log(A[0]*A[1]*A[2]*...*A[N-3])
                         = log(N)-log(A[0]) + log(N-1)-log(A[1]) + ... +log(3)-log(A[N-3]) + log(2) + log(1)
         
知道了两数的和与积,由此就可以计算出a跟b的值来.

代码如下:


#include 
<iostream>
#include 
<Ctime>
#include 
<Cmath>
using namespace std;


#define N 100000

//生成不同的随机数的数组
void GetDiffRandomNum(int A[], int n)
{
    srand(unsigned(time(NULL)));
    
int i=0;

    
for(int index = n-1; index > 0; index--)
    
{
        i 
= rand() % index;
        swap(A[i], A[index]);
    }


}



int main()
{
  
    
int A[N]={0};
    
for(int i=0; i<N; i++)
    
{
        A[i] 
= i+1;
    }

    GetDiffRandomNum(A, N);
    
//DISPLAY(A, N);
    
    unsigned 
int sum = 0;
    
double logSum = 0;

    
for(i=0; i<N-2; i++)
    
{
        sum 
+= N-i-A[i];             
        logSum 
+= log(N-i)-log(A[i]);
    }

    sum 
+= 2 + 1;
    logSum 
+= log(2)+log(1);

    
double multi = exp(logSum);

    
//两数的和与积
    cout<<int(sum)<<'\t'<<int(multi)<<endl;

    
//求出两数
    for(i=1; i<=N; i++)
    
{
        
double temp = i*(sum-i);
        
if(multi-0.5<=temp && temp <= multi+0.5)
            cout
<<i<<'\t'<<int(sum-i)<<endl;
    }

 
    
return 0;
}



PS(谢谢枝~的帮助)请大家指导

//................................
通过大家的帮助:
得到另一个写法,不会产生精度问题

(1+N)*N /2 - S = a + b
1/6 * n*(n + 1)*(2n + 1) - X = a*a + b*b

注:
1/6 * n*(n + 1)*(2n + 1)=1*1 + 2*2 + 3*3 +...+N*N
X = A[0]*A[0] + A[1]*A[1] +...A[N-3]*A[N-3]
 
==>
a + b = m
a*a + b*b = n

由于可解出a,b

    unsigned int sum = 0;
    unsigned 
int sqrSum = 0;

    
for(i=0; i<N-2; i++)
    {
        sum 
+= N-i-A[i];       
        sqrSum 
+= ((N-i)*(N-i)) - ((A[i])*A[i]);
     
    }
    sum 
+= 2 + 1
    sqrSum 
+= 2*2 + 1*1;




posted @ 2007-03-22 23:14 猪头饼 阅读(3502) | 评论 (18)编辑 收藏

看了两三天的KMP算法,一直看的迷迷糊糊的.现在把这些资料贴在这里...以备日后之需
 
1.串的模式匹配的改进算法(这个网站对我的理解帮助很大,特别是右边的那块说明部分,以前自己脑筋老是转不过来) http://cist.dhu.edu.cn/kejian/%CA%FD%BE%DD%BD%E1%B9%B9%BE%AB%C6%B7%BF%CE%B3%CC/%D4%DA%CF%DF%D1%A7%CF%B0/text/chapter04/section3/c5.htm

2.KMP 算法的注记 http://www.cublog.cn/u/20/showart_136705.html 

3.KMP算法中推导next[],nextval[]--手记 http://jiasimon040510.t8log.ccut.cn/blog-htm-do-showone-tid-6983.html


4.算法原理:

在匹配过和中,当主串中第i个字符与模式串中第j个字符“失配”时(s[i]!=t[j]),将模式串尽量向右移动,让模式串中第k(k<j)个字符与si对齐继续比较,

要让这个条件成立,那么在k之前的k个t字符[0 到 k-1]必须在i之前的k个s字符[i-k 到 i-1]相匹配即:

   t[0, 1, 2...k-1] == s[i-k, i-k+1, i-k+2...i-1]     ---(1)

而由之前的部分匹配成功的结果可知:
  
   t[0, 1, 2...j-1] == s[i-j, i-j+1, i-j+2...i-1]     ---(2)
==>
   t[j-k, j-k+1, j-k+2...j-1] == s[i-k, i-k+1, i-k+2...i-1]   --(3)

由(1)与(3)可得:

   t[0, 1, 2...k-1] == t[j-k, j-k+1, j-k+2...j-1]     ---(4)

求出k值,就是next[j]的值了

总之,相对我来说,算法不是很好懂.但是大家看到我这么笨的人到最后都能明白一二.大家就更没有理由看不懂了,祝大家成功附上我的测试源码:



#include 
< iostream >

using   namespace  std;


void  GetNext( char  t[],  int  next[])
{
    
int  j  =   0 ;
    
int  k  =   - 1 ;
    next[j] 
=  k;
    
int  tlen  =  strlen(t);

    
while (j < tlen)
    
{
        
if (k  ==   - 1   ||  t[j]  ==  t[k])
        
{
            j
++ ;
            k
++ ;
            
if (t[j]  ==  t[k])
            
{
                next[j] 
=  next[k];
            }

            
else
                next[j] 
=  k;
        }

        
else
        
{
            k 
=  next[k];
        }

    }

}



int  KMP( char  s[],  char  t[],  int  pos,  int  next[])
{
    
int  slen  =  strlen(s);
    
int  tlen  =  strlen(t);
    
int  i  =   0 ;
    
int  j  =   0 ;

    
while (i < slen  &&  j < tlen)
    
{
        
if (j  ==   - 1   ||  s[i]  ==  t[j])
        
{
            i
++ ;
            j
++ ;
        }

        
else
        
{
            j 
=  next[j];    
        }

    }


    
if (j  ==  tlen)
    
{
        
return  i - tlen;
    }

    
else
        
return   - 1 ;
}


int  main ( int  argc,  char   ** argv)
{
    
    
char  s[]  =   " aaaabaabaaabaaabaaaaabaaabaaabaaabaaabaaabaaabaaabaaabaaabacb " ;
    
    
char  t[]  =   " aabaaa " ;

    
int  next[ 20 ] = { 0 } ;
    GetNext(t, next);    
    
for ( int  i = 0 ; i < 20 ; i ++ )
        cout
<< " next[ " << i << " ]:   " << next[i] << endl;
    
    cout
<< KMP(s, t,  0 , next) << endl;
}
posted @ 2006-11-10 01:51 猪头饼 阅读(1420) | 评论 (0)编辑 收藏

 

class  A
{

private :
    
int  i;
public :
    A(
int  ii):i(ii) {} // cout<<i<<"  A() "<<endl;
    A():i( 0 ) {}

    
~ A() {cout << " ~A( " << i << " " << endl;}

    
const  A  operator   + ( const  A  & r)  const
    
{
        
return  A(i + r.i);

    }

}
;

int  main()
{
    
int  i = 10 ,j = 20 ;
    
// cout<<&(i+j)<<endl;           // 这里为什么会出错呢?
    A a1( 10 ),a2( 20 ),a3( 30 ),a4( 40 );
    cout
<<& (a1 + a2) << endl;        // 这里就应该是临时变量的地址了吧
    system( " pause " );
    
return   0 ;
}



既然这样可以运行,那为什么内置的类型如:int float之类的不能取临时对象的值呢?
我重载的+号运算符应该没有写错吧、、
请大家指教。。谢谢我还只是一个初学者

posted @ 2006-02-12 22:12 猪头饼 阅读(915) | 评论 (10)编辑 收藏
仅列出标题  
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

积分与排名

  • 积分 - 6785
  • 排名 - 1367

最新评论

阅读排行榜

评论排行榜