Chinaunix首页 | 论坛 | 博客
  • 博客访问: 471466
  • 博文数量: 59
  • 博客积分: 345
  • 博客等级: 二等列兵
  • 技术积分: 1380
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-18 22:44
个人简介

to be myself

文章分类

全部博文(59)

文章存档

2017年(5)

2013年(47)

2012年(3)

2011年(4)

分类: C/C++

2013-03-03 11:42:05

/*类循环排列*/
Input:
3 2
Output:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

点击(此处)折叠或打开

  1. #include <stdio.h>

  2. #define MAX 10

  3. int rcd[MAX];
  4. int n, m; //n位数,有0-m-1数字构成

  5. void loop_permutation(int l)
  6. {
  7.     int i;
  8.     if(l == n)
  9.     {
  10.         for(i=0; i<n; i++)
  11.         {
  12.             printf("%d", rcd[i]);
  13.             if(i < l-1)
  14.             {
  15.                 printf(" ");
  16.             }
  17.         }
  18.         printf("n");
  19.         return ;
  20.     }
  21.     for(i=0; i<m; i++)
  22.     {
  23.         rcd[l] = i;
  24.         loop_permutation(l+1);
  25.     }
  26. }

  27. int main()
  28. {
  29.     while(scanf("%d %d", &n, &m) == 2)
  30.     {
  31.         loop_permutation(0);
  32.     }
  33.     return 0;
  34. }

--------------------------------------------------

/*全排列*/
Input:
3
1 2 3
Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #define MAX 10

  4. int rcd[MAX];
  5. int used[MAX];
  6. int num[MAX];
  7. int n;

  8. void full_permutation(int l)
  9. {
  10.     int i;
  11.     if(l == n)
  12.     {
  13.         for(i=0; i<n; i++)
  14.         {
  15.             printf("%d", rcd[i]);
  16.             if(i < n-1)
  17.             {
  18.                 printf(" ");
  19.             }
  20.         }
  21.         printf("n");
  22.         return ;
  23.     }
  24.     for(i=0; i<n; i++)
  25.     {
  26.         if(!used[i])
  27.         {
  28.             used[i] = 1;
  29.             rcd[l] = num[i];
  30.             full_permutation(l+1);
  31.             used[i] = 0;
  32.         }
  33.     }
  34. }

  35. int main()
  36. {
  37.     int i;
  38.     while(scanf("%d", &n) != EOF)
  39.     {
  40.         for(i=0; i<n; i++)
  41.         {
  42.             scanf("%d", &num[i]);
  43.         }
  44.         memset(used, 0, sizeof(used));
  45.         full_permutation(0);
  46.     }
  47.     return 0;
  48. }


--------------------------------------------------

/*不重复全排列*/
Input:
3
1 1 2
Output:
1 1 2
1 2 1
2 1 1
 

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #define MAX 10

  4. int rcd[MAX];
  5. int used[MAX];
  6. int num[MAX]; //存放互不相同的m个数
  7. int n, m; //n个数,互不相同有m个

  8. void unrepeat_full_permutation(int l)
  9. {
  10.     int i;
  11.     if(l == n)
  12.     {
  13.         for(i=0; i<n; i++)
  14.         {
  15.             printf("%d", rcd[i]);
  16.             if(i < n-1)
  17.             {
  18.                 printf(" ");
  19.             }
  20.         }
  21.         printf("n");
  22.         return ;
  23.     }
  24.     for(i=0; i<n; i++)
  25.     {
  26.         if(used[i] > 0)
  27.         {
  28.             used[i]--;
  29.             rcd[l] = num[i];
  30.             unrepeat_full_permutation(l+1);
  31.             used[i]++;
  32.         }
  33.     }
  34. }

  35. int main()
  36. {
  37.     int i, j, val;
  38.     while(scanf("%d", &n) != EOF)
  39.     {
  40.         m = 0;
  41.         memset(used, 0, sizeof(used));
  42.         for(i=0; i<n; i++)
  43.         {
  44.             scanf("%d", &val);
  45.             for(j=0; j<m; j++)
  46.             {
  47.                 if(num[j] == val)
  48.                 {
  49.                     used[j]++;
  50.                     break;
  51.                 }
  52.             }
  53.             if(j == m)
  54.             {
  55.                 num[m] = val;
  56.                 used[m++] = 1;
  57.             }
  58.         }
  59.         unrepeat_full_permutation(0);
  60.     }
  61. }

--------------------------------------------------


/*组合*/
Input:
4 3
1 2 3 4
Output:
1 2 3
1 2 4
1 3 4
2 3 4
 

点击(此处)折叠或打开

  1. #include <stdio.h>

  2. #define MAX 10

  3. int rcd[MAX];
  4. int num[MAX];
  5. int n, m; //从n个数中选m个数

  6. void select_combination(int l, int z)
  7. {
  8.     int i;
  9.     if(l == m) //已选m个数
  10.     {
  11.         for(i=0; i<m; i++)
  12.         {
  13.             printf("%d", rcd[i]);
  14.             if(i < m-1)
  15.             {
  16.                 printf(" ");
  17.             }
  18.         }
  19.         printf("n");
  20.         return ;
  21.     }
  22.     for(i=z; i<n; i++) //上次为num[z-1],此次从num[z]开始
  23.     {
  24.         rcd[l] = num[i];
  25.         select_combination(l+1, i+1); //i+
  26.     }
  27. }

  28. int main()
  29. {
  30.     int i;
  31.     while(scanf("%d %d", &n, &m) != EOF)
  32.     {
  33.         for(i=0; i<n; i++)
  34.         {
  35.             scanf("%d", &num[i]);
  36.         }
  37.         select_combination(0, 0);
  38.     }
  39.     return 0;
  40. }


--------------------------------------------------

/*全组合*/
Input:
3
1 2 3
Output:
1
1 2
1 2 3
1 3
2
2 3
3
 

点击(此处)折叠或打开

  1. #include <stdio.h>

  2. #define MAX 10

  3. int rcd[MAX];
  4. int num[MAX];
  5. int n;

  6. void full_combination(int l, int z)
  7. {
  8.     int i;
  9.     for(i=0; i<l; i++)
  10.     {
  11.         printf("%d", rcd[i]);
  12.         if(i < l-1)
  13.         {
  14.             printf(" ");
  15.         }
  16.     }
  17.     printf("n");
  18.     for(i=z; i<n; i++) //i=
  19.     {
  20.         rcd[l] = num[i];
  21.         full_combination(l+1, i+1);
  22.     }
  23. }

  24. int main()
  25. {
  26.     int i;
  27.     while(scanf("%d", &n) != EOF)
  28.     {
  29.         for(i=0; i<n; i++)
  30.         {
  31.             scanf("%d", &num[i]);
  32.         }
  33.         full_combination(0, 0);
  34.     }
  35.     return 0;
  36. }

--------------------------------------------------


/*不重复组合*/
Input:
3
1 1 3
Output:
1
1 1
1 1 3
1 3
3

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #define MAX 10

  4. int rcd[MAX];
  5. int num[MAX];
  6. int used[MAX];
  7. int n, m; //n个数中有m个不同的数

  8. void unrepeat_combination(int l, int z)
  9. {
  10.     int i;
  11.     for(i=0; i<l; i++)
  12.     {
  13.         printf("%d", rcd[i]);
  14.         if(i < l-1)
  15.         {
  16.             printf(" ");
  17.         }
  18.     }
  19.     printf("n");
  20.     for(i=z; i<m; i++)
  21.     {
  22.         if(used[i] > 0)
  23.         {
  24.             used[i]--;
  25.             rcd[l] = num[i];
  26.             unrepeat_combination(l+1, i); //l+
  27.             used[i]++;
  28.         }
  29.     }
  30. }

  31. int main()
  32. {
  33.     int i, j, val;
  34.     while(scanf("%d", &n) != EOF)
  35.     {
  36.         m = 0;
  37.         memset(used, 0, sizeof(used));
  38.         for(i=0; i<n; i++)
  39.         {
  40.             scanf("%d", &val);
  41.             for(j=0; j<m; j++)
  42.             {
  43.                 if(num[j] == val)
  44.                 {
  45.                     used[j]++;
  46.                     break;
  47.                 }
  48.             }
  49.             if(j == m)
  50.             {
  51.                 num[m] = val;
  52.                 used[m++] = 1;
  53.             }
  54.         }
  55.         unrepeat_combination(0, 0);
  56.     }
  57.     return 0;
  58. }

2011-05-12 18:23  发表于百度空间,今搬至CU。
阅读(1505) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~