Dain

写出一个可以工作的程序并不够

统计

留言簿(3)

积分与排名

良师益友

阅读排行榜

评论排行榜

#

全排列

首先,给出算法的思路
设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{ri}。
集合X中元素的全排列记为permutation(X),(ri)permutation(X)表示在全排列permutation(X)的每一个排列前加上前缀ri得到的排列。
R的全排列可归纳定义如下:
当n=1时,permutation(R)={r},r是集合R中唯一的元素;
当n>1时,permutation(R)由(r1)permutation(R1),(r2)permutation(R2),……,(rn)permutation(Rn)构成。

此算法要求待排列的数据是互异的,因为该算法不能检测同种排列是否已经输出,如:
1, 1, 2
那么,全排列期望输出是:
1, 1, 2
1, 2, 1
2, 1, 1
但是该算法的输出:
1, 1, 2
1, 2, 1
2, 1, 1
1, 1, 2
1, 2, 1
2, 1, 1

这是该算法的缺点,也限制了它的适用范围。

程序描述如下:

#include  < iostream >
#include 
< algorithm >  

using   namespace  std; 

//  递归产生R[k:n]的所有的排列,元素是互异的
template  < class  Type >
void  permutation(Type  * R, int  k, int  n)
{
    
if (k == n)
    {
        
for ( int  i = 0 ;i < n; ++ i)
            cout 
<<  R[i]  <<   " \t " ;
        cout 
<<  endl;
    }
    
else
        
for ( int  i = k;i < n; ++ i)
        {
            swap(R[k],R[i]);
            permutation(R,k
+ 1 ,n);
            swap(R[k],R[i]);
        }
}

还有一种很简单的方法,使用GP中的方法

该算法是STL中的范型算法,当然效果是很好的,不会出现上面的算法的情况。

程序描述如下:

//  使用泛型算法next_permutation()
#include  < iostream >
#include 
< vector >
#include 
< algorithm >  

using   namespace  std; 

//  产生R[k:n]的所有的排列
template  < class  Type >  

void  pernutation(Type  * R, int  k, int  n)
{
 vector
< Type >  myVec;
 
int  i,size  =  n  -  k;
 
for (i  =  k;i  <  n;i ++ )
  myVec.push_back(R[i]);
 
//  使用next_permutation()函数必须是有序的数据
 sort(myVec.begin(),myVec.end());
  
 
do
 {
  
for (i  =   0 ;i  <  size;i ++ )
   cout 
<<  myVec[i]  <<   " \t " ;
  cout 
<<  endl;
 }
 
while (next_permutation(myVec.begin(),myVec.end()));
}

注:这里的待全排的数据是存在数组或者向量中的。

posted @ 2006-12-25 10:17 Dain 阅读(1039) | 评论 (2)编辑 收藏

算法求解(还没有人做出来,唉)

     摘要: Given an int m and a vector a containing n numbers, return the result of the following expression:   阅读全文

posted @ 2006-12-21 10:58 Dain 阅读(945) | 评论 (6)编辑 收藏

卫星还是光纤

我们能访问其他国家的网络,比如美国,那些数据是通过什么方式传送的啊?卫星,还是海底光纤
要是海底光纤,那要铺很长地阿
who来说说哈

posted @ 2006-12-13 13:41 Dain 阅读(291) | 评论 (3)编辑 收藏

string和int间的类型转换

int 转换 string
string  int2str( int  num)
{
   
if (num  ==   0 )
      
return   " 0 " ;
   
   
string  str  =   "" ;
   
int  num_  =  num  >   0   ?  num :  - 1   *  num;

   
while (num_)
   
{
      str 
=  ( char )(num_  %   10   +   48 +  str;
      num_ 
/=   10 ;
    }


   
if (num  <   0 )
      str 
=   " - "   +  str;

   
return  str;
}
string 转换 int
int  str2int( string  str)
{
   
int  i,len  =  str.size(),num  =   0 ;

    i 
=   0 ;   
   
if (str[ 0 ==   ' - ' )
      i 
=   1 ;
   
   
while (i  <  len)
   
{
      num 
=  num  *   10   +  ( int )(str[i]  -   ' 0 ' );
      i
++ ;
    }


   
if (str[ 0 ==   ' - ' )
      num 
*=   - 1 ;

   
return  num;
}

string和int间是可以自己写函数实现类型转换的,但是string和double就不太方便了,stirng转换double可以自定义函数实现,但是,double转换string就需要使用库函数了,如sprintf

posted @ 2006-12-10 13:05 Dain 阅读(13385) | 评论 (10)编辑 收藏

励志

师兄太强了,拿到了baidu、M$、Google的offer,可是实验室第一人啊,实在是admire
现在都说工作难找,不过只要努力,总会找到自己满意的,向师兄学习
我一定要努力啊

posted @ 2006-12-08 10:42 Dain 阅读(798) | 评论 (14)编辑 收藏

仅列出标题
共2页: 1 2