posts - 3,  comments - 28,  trackbacks - 0
2007年3月22日
一道算法面试题，大家讨论看看
题目：

从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 猪头饼 阅读(3577) | 评论 (18) | 编辑 收藏
2006年11月10日
KMP算法资料

看了两三天的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 猪头饼 阅读(1444) | 评论 (0) | 编辑 收藏
2006年2月12日
[讨论]临时对象有地址么？

 

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 猪头饼 阅读(947) | 评论 (10) | 编辑 收藏
仅列出标题  
<2024年11月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

积分与排名

  • 积分 - 6957
  • 排名 - 1370

最新评论

阅读排行榜

评论排行榜