Liny_@NotePad

沉迷ACG中

递归求全排列

 其实它是没有排序的全排列……

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define N 30
  5.  
  6. /********************************
  7. * 打印数组函数
  8. ********************************/
  9. void printArray(int A[], int n){
  10.         for(int i=0; i<n; i++){
  11.                         cout<<A[i]<<" ";
  12.                 }
  13.         cout<<endl;
  14. }
  15.  
  16. /********************************************
  17. * 全排列算法
  18. *
  19. * 输入：数组A[]，数组的元素个数n，
  20. *       当前递归层次已完成排列的元素个数k（0<=k<n)
  21. * 输出：数组A[]的全排列
  22. ********************************************/
  23. void perm(int A[], int n, int k){
  24.         if(k==n-1){                    //   已完成排列则打印
  25.                 printArray(A,n);
  26.         }else{
  27.                 for(int i=k; i<n ;i++){ //       生成后续的一系列排列
  28.                         swap(A[i], A[k]);
  29.                         perm(A, n, k+1);
  30.                         swap(A[i], A[k]);
  31.                 }
  32.         }
  33. }
  34.  
  35. int main(){
  36.         int A[N], n;
  37.  
  38.         cout<<"请输入数组的元素个数：";
  39.         cin>>n;
  40.  
  41.         cout<<"请输入数组的元素：";
  42.         for(int i=0; i<n; i++){
  43.                 cin>>A[i];
  44.         }
  45.  
  46.         cout<<"数组的全排列是："<<endl;
  47.         perm(A,n,0);
  48.  
  49.         return 0;
  50. }

【算法】与【数据结构】 递归 全排列 Comments(0) 2009年4月29日 08:00

合并排序实现

 = =

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. /******************************************
  5. * 合并两个有序的子数组
  6. *
  7. * 输入：整数数组A[]，下标p,q,r，元素个数m
  8. *            其中A[p]~A[q]和A[q+1]~A[r]已按递增顺序排序
  9. * 输出：按递增顺序排序的子数组A[p]~A[r]
  10. ******************************************/
  11. void merge(int A[], int p, int q, int r, int m){
  12.         int *bp = new int[m];
  13.         int i,j,k;
  14.         i = p; j = q+1; k=0;
  15.         while(i<=q&&j<=r){      //    i从p开始，j从q+1开始 比较A[i]和A[j]，递减放入新数组
  16.                 if(A[i]<=A[j]){
  17.                         bp[k++] = A[i++];
  18.                 }else{
  19.                         bp[k++] = A[j++];
  20.                 }
  21.         }
  22.         if(i==q+1){     // 若A[p]~A[q]已经输入完，则将A[q+1]~A[r]中未录入的继续录入
  23.                 for(;j<=r;j++){
  24.                         bp[k++] = A[j];
  25.                 }
  26.         }else{  //        若A[q+1]~A[r]已经输入完，则A[p]~A[q]将中未录入的继续录入
  27.                 for(;i<=q;i++){
  28.                         bp[k++] = A[i];
  29.                 }
  30.         }
  31.         k = 0;
  32.         for(i=p; i<=r; i++){    //  把排序好的数存回A
  33.                 A[i] = bp[k++];
  34.         }
  35.         delete bp;
  36. }
  37.  
  38. /******************************************
  39. * 合并排序算法
  40. *
  41. * 输入：具有n个元素的数组A[]
  42. * 输出：按递增顺序排序的数组A[]
  43. ******************************************/
  44. void merge_sort(int A[], int n){
  45.         int i,s,t = 1;
  46.         while(t<n){     //   每2个含t/2个元素的数组进行合并，合并完后t*2
  47.                 s = t, t = 2*s, i = 0;
  48.                 while(i+t<n){
  49.                         merge(A,i,i+s-1,i+t-1,t);
  50.                         i = i + t;
  51.                 }
  52.                 if(i+s<n){
  53.                         merge(A,i,i+s-1,n-1,n-i);
  54.                 }
  55.         }
  56. }
  57.  
  58. int main(){
  59.         int i,n;
  60.  
  61.         cout<<"请输入数组元素个数：";
  62.         cin>>n;
  63.  
  64.         cout<<"请输入元素："<<endl;
  65.         int* A = new int[n];
  66.         for(i=0;i<n;i++){
  67.                 cin>>A[i];
  68.         }
  69.  
  70.         merge_sort(A,n);
  71.  
  72.         cout<<"排序结果："<<endl<<A[0];
  73.         for(i=1;i<n;i++){
  74.                 cout<<" "<<A[i];
  75.         }
  76.         cout<<endl;
  77.  
  78.         return 0;
  79. }

【算法】与【数据结构】 排序 Comments(0) 2009年4月29日 07:56

C的RSA密码算法实现

C写的，囧，网络课本上看过，对于我这种数学白痴怎么可能会？拖住wekooo要了公式，随便写写……

【算法】与【数据结构】 RSA 加密 解密 Comments(0) 2009年4月25日 00:26

求主元素的线性算法

 知道怎么算，实现起来好囧，百度了一下，发现这个好简洁 = =，不过这个输入时就一定有主元素，故没有再对函数找出来的A[x]作判定：

【算法】与【数据结构】 主元素 Comments(0) 2009年3月12日 21:32

基数排序实现

rt……

【算法】与【数据结构】 基数排序 Comments(0) 2009年3月12日 21:29

求亲密数对

= =

【算法】与【数据结构】 亲密数对 Comments(0) 2009年3月12日 21:28

离散集合的find与union操作

 @ _ @

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define Type int
  5. #define N 100
  6.  
  7. typedef struct Tree_node {
  8.         struct Tree_node*  parent;
  9.         int rank;
  10.         Type value;
  11. }NODE;
  12.  
  13. NODE* find(NODE *xp){
  14.         NODE *wp, *yp = xp, *zp = xp;
  15.         while(yp->parent){
  16.                 yp = yp->parent;
  17.         }
  18.         while(zp->parent){
  19.                 wp = zp->parent;
  20.                 zp->parent = yp;
  21.                 zp = wp;
  22.         }
  23.         return yp;
  24. }
  25.  
  26. NODE* unionTree(NODE *xp, NODE *yp){
  27.         NODE *up, *vp;
  28.         up = find(xp);
  29.         vp = find(yp);
  30.         if(up->rank<=vp->rank){
  31.                 up->parent = vp;
  32.                 if(up->rank == vp->rank){
  33.                         vp->rank ++;
  34.                 }
  35.                 up = vp;
  36.         }else{
  37.                 vp->parent = up;
  38.         }
  39.         return up;
  40. }
  41.  
  42. NODE* createNode(Type value, NODE* parent = NULL){
  43.         NODE* p = new NODE;
  44.         if(parent){
  45.                 p->rank = parent->rank + 1;
  46.         }else{
  47.                 p->rank = 1;
  48.         }
  49.         p->parent = parent;
  50.         p->value = value;
  51.         return p;
  52. }
  53.  
  54. int main(){
  55.         NODE* A[N];
  56.  
  57.         /* 建立集合{1,2,3,4} */
  58.         A[4] = createNode(4);   
  59.         A[3] = createNode(3,A[4]);     
  60.         A[2] = createNode(2,A[4]);
  61.         A[1] = createNode(1,A[2]);
  62.        
  63.        
  64.  
  65.         /* 建立集合{5,6,7,8} */
  66.         A[8] = createNode(8);   
  67.         A[7] = createNode(7,A[8]);     
  68.         A[6] = createNode(6,A[8]);
  69.         A[5] = createNode(5,A[6]);
  70.  
  71.         /*      合并两集合 */
  72.         unionTree(A[1],A[5]);
  73.  
  74.         /* 遍历集合 */
  75.         for(int i = 1; i<=8; i++){
  76.                 cout<<"结点"<<(A[i]->value)<<" ";
  77.                 if(A[i]->parent)cout<<"父结点"<<(A[i]->parent->value);
  78.                 else cout<<"该结点为根结点";
  79.                 cout<<endl;
  80.         }
  81.  
  82.         return 0;
  83. }

【算法】与【数据结构】 离散集合 find union Comments(0) 2009年3月10日 21:59

合并堆算法

编写一个算法，把两个相同大小的堆合并成一个堆。

  1. /*
  2. * Title: 编写一个算法，把两个相同大小的堆，合并成一个堆。
  3. * Author: YOYO
  4. * Time: 2009-3-8
  5. *
  6. * 合并算法即其中的merge_heaps(Type A[], Type B[], Type C[], int n)
  7. * 该算法将两个相同大小的堆A和B合并为一个大顶堆，并存储到C中。时间复杂度为O(n*log(n))
  8. *
  9. */
  10. #include<iostream>
  11. using namespace std;
  12.  
  13. #define Type int
  14. #define N 100
  15.  
  16. void shift_up(Type H[], int i);
  17. void shift_down(Type H[], int n, int i);
  18. void insert(Type H[], int &n, Type x);
  19. void del(Type H[], int &n, int i);
  20. Type delete_max(Type H[], int &n);
  21. void print_heap(Type H[], int n);
  22. void make_heap(Type H[], int n);
  23. void heap_sort(Type H[], int n);
  24. void merge_heaps(Type A[], Type B[], int n);
  25.  
  26. void shift_up(Type H[], int i){
  27.         bool done = false;
  28.         while(i!=1){
  29.                 if(H[i]<=H[i/2]){
  30.                         break;
  31.                 }
  32.                 swap(H[i], H[i/2]);
  33.                 i /= 2;
  34.         }
  35. }
  36.  
  37. void shift_down(Type H[], int n, int i){
  38.         bool done = false;
  39.         while( (i=2*i)<=n ){
  40.                 if(i+1<=n&&H[i+1]>H[i]){
  41.                         i ++;
  42.                 }
  43.                 if(H[i/2]>=H[i]){
  44.                         break;
  45.                 }
  46.                 swap(H[i/2], H[i]);
  47.         }
  48. }
  49.  
  50. void insert(Type H[], int &n, Type x){
  51.         n++;
  52.         H[n] = x;
  53.         shift_up(H,n);
  54. }
  55.  
  56. void del(Type H[], int &n, int i){
  57.         Type x, y;
  58.         x = H[i], y = H[n];
  59.         n--;
  60.         if(i<=n){
  61.                 H[i] = y;
  62.                 if(y>=x){
  63.                         shift_up(H,i);
  64.                 }else{
  65.                         shift_down(H,n,i);
  66.                 }
  67.         }
  68. }
  69.  
  70. Type delete_max(Type H[], int &n){
  71.         Type x = H[1];
  72.         del(H, n, 1);
  73.         return x;
  74. }
  75.  
  76. void heap_sort(Type H[], int n){
  77.         make_heap(H,n);
  78.         for( int i = n; i>1; i--){
  79.                 swap(H[1],H[i]);
  80.                 shift_down(H,i-1,1);
  81.         }
  82. }
  83.  
  84. void print_heap(Type H[], int n){
  85.         for( int i = 1, j = 1; i<=n; i++){
  86.                 printf("%-4d",H[i]);
  87.                 if((i+1)%j==0){
  88.                         cout<<endl;
  89.                         j*=2;
  90.                 }
  91.         }
  92.         cout<<endl;
  93.         if(i%j)cout<<endl;
  94. }
  95.  
  96. void make_heap(Type H[], int n){
  97.         H[n] = H[0];
  98.         for( int i= n/2; i>=1; i--){
  99.                 shift_down(H,n,i);
  100.         }
  101. }
  102.  
  103. /*
  104. *      合并堆算法
  105. *
  106. *      输入：堆A，堆B，堆的长度n
  107. *      输出：由堆A和堆B合并成的新大顶堆C
  108. *
  109. *      该算法执行了2n次时间复杂度为O(log(n))的insert操作，故
  110. *      它的执行时间为O(n*log(n))
  111. *
  112. */
  113. void merge_heaps(Type A[], Type B[], Type C[], int n){
  114.         int i,k;
  115.         for(i=1, k = 0; i<=n; i++){
  116.                 insert(C, k, A[i]);
  117.         }
  118.         for(i=1, k = n; i<=n; i++){
  119.                 insert(C, k, B[i]);
  120.         }
  121. }
  122.  
  123. int main(){
  124.         int i,n;
  125.         Type A[N],B[N],C[2*N];
  126.  
  127.         /*      输入堆的元素 */
  128.         cout<<"请输入堆的元素个数：";
  129.         cin>>n;
  130.  
  131.         cout<<"请输入堆A的元素：";
  132.         for(i = 0; i<n; i++){
  133.                 cin>>A[i];
  134.         }
  135.  
  136.         cout<<"请输入堆B的元素：";
  137.         for(i = 0; i<n; i++){
  138.                 cin>>B[i];
  139.         }
  140.  
  141.         /*      建堆 */
  142.         make_heap(A,n);
  143.         make_heap(B,n);
  144.  
  145.         /*      打印堆*/
  146.         cout<<"大顶堆A："<<endl;
  147.         print_heap(A,n);
  148.  
  149.         cout<<"大顶堆B："<<endl;
  150.         print_heap(B,n);
  151.  
  152.         /*      合并堆 */
  153.         merge_heaps(A,B,C,n);
  154.  
  155.         /*      打印堆*/
  156.         cout<<"合并后的大顶堆C："<<endl;
  157.         print_heap(C,2*n);
  158.  
  159.         return 0;
  160. }

【算法】与【数据结构】 堆 Comments(2) 2009年3月10日 21:31