首页 > 代码库 > 练习20140814
练习20140814
/********************************************************************@file Main_practise.cpp@date 2014-8-14@author Tiger@brief 全排列 由于采用非递归的C++函数来输出n个元素的所有排列方式很困难, 所以可以开发一个递归函数来实现。令E={e1,...,en}表示n个元素 的集合,我们的目标是生成该集合的所有排列方式。令Ei为E中移 去元素i以后所获得的集合,perm(X)表示集合X中元素的排列方式, ei.perm(X)表示在perm(X)中的每个排列方式的前面均加上ei以后所 得到的排列方式。例如,如果E={a,b,c},那么E1={b,c},perm(E1)=(bc,cb), e1.perm(E1)=(abc,acb)。对于递归的基本部分,采用n=1。当只有一 个元素时,只可能产生一种排列方式,所以perm(E)=(e),其中e是 E中的唯一元素。当n>1时,perm(E)=e1.perm(E1)+e2.perm(E2)+e3.perm(E3)+ ? +en.perm(En)。 这种递归定义形式是采用n个perm(X)来定义perm (E), 其中每个X包含n-1个元素。 至此,一个完整的递归定义所需要的基本部分和递归部分都已完成。 当n=3并且E=(a,b,c)时,按照前面的递归定义可得perm(E)=a.perm({b,c})+b.perm({a,c})+c.perm({a,b})。 同样,按照递归定义有perm({b,c})=b.perm({c})+c.perm({b}), 所以 a.perm({b,c})=ab.perm({c})+ac.perm({b})=ab.c+ac.b=(abc,acb)。同理可得 b.perm({a,c})=ba.perm({c})+bc.perm({a})=ba.c+bc.a=(bac,bca), c.perm({a,b})=ca.perm({b})+cb.perm({a})=ca.b+cb.a=(cab,cba)。 所以perm(E)=(abc,acb,bac,bca,cab,cba)。********************************************************************/#include <iostream>const int SIZE = 5;template <typename T>void CalFullArray(T array[], int nBeg, int nEnd);template <typename T>void Swap(T& a, T& b);int main(int argc, const char* argv[]){ int array[SIZE] = {1, 2, 3, 4, 5}; CalFullArray(array, 0, SIZE-1); system("pause"); return 0;}template <typename T>void CalFullArray(T array[], int nBeg, int nEnd){ if (nBeg == nEnd) { for (int i=0; i<=nEnd; ++i) { std::cout << array[i]; } std::cout << std::endl; } else { for (int i=nBeg; i<=nEnd; ++i) { Swap(array[nBeg], array[i]); CalFullArray(array, nBeg+1, nEnd); Swap(array[nBeg], array[i]); } }}template <typename T>void Swap(T& a, T& b){ int temp = a; a = b; b = temp;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。