现在的位置: 首页 > 综合 > 正文

金山两道程序题(排列和组合)

2014年09月05日 ⁄ 综合 ⁄ 共 4859字 ⁄ 字号 小 中 大 ⁄ 评论关闭
编程 1

  给定一个字符串，输出给定字符串所有的组合的函数，例如：字符串 abc  所有组合 abc  acb  bac b    ca cab  cba六种组合

编程 2

  给定一个数组大小m和一个数组array
  m = 10;  array = {1,2,3,4,5,6,7,8,9,10}
  求从array中任意取得n（n<=m）个数，使得和为m，总共有多少种取法，例如：10 1,9 2,3,5
  方法原型 ：int  getotalNum (int[] array, int m);

要求有输入输出,而不是仅仅做一个函数出来..

Code:
  1. /************************************************************  
  2. *名称:    problem01.c                                         *  
  3. *描述:    给定一个字符串，输出给定字符串所有的组合的函数 *  
  4. *假设:    假设字符串中的字母不重复                            *  
  5. *思路:    对输入字符数组下标全排列再按照排列顺序输出即可 *  
  6. *环境:    Code::Blocks & Windows 7 & x86                      *  
  7. *备注:    davelv于09年光棍节19点                                *  
  8. *************************************************************/  
  9. #include <stdio.h>   
  10. #include <stdlib.h>   
  11. #include <string.h>   
  12.   
  13. #define BUF_LEN 1024   
  14. //排列输出函数   
  15. void perm(char *buf, int start, int end);   
  16. int main(void)   
  17. {   
  18.     char buf[BUF_LEN];   
  19.   
  20.     printf("Please input string less than %d letters:", BUF_LEN);   
  21.     fgets(buf, BUF_LEN, stdin);   
  22.   
  23.     if (buf[strlen(buf)-1] == '/n')   
  24.         buf[strlen(buf)-1] = '/0';//去除控制台附加的/n   
  25.   
  26.     perm(buf, 0, strlen(buf));//排列输出   
  27.     system("PAUSE");   
  28.     return 0;   
  29. }   
  30. //buf 待字符串;start 排列开始位置;end 排列结束位置   
  31. void perm(char *buf, int start, int end)   
  32. {   
  33.     int i;   
  34.     char temp;   
  35.   
  36.     if (start == end)   
  37.     {//当排列到最后一个字符时输出   
  38.        puts(buf);   
  39.     }   
  40.     else  
  41.     {//否则继续排列   
  42.         for (i=start; i<end; i++)   
  43.         {   
  44.             //交换   
  45.             temp = buf[start];   
  46.             buf[start] = buf[i];   
  47.             buf[i] = temp;   
  48.             //递归排列   
  49.             perm(buf, start+1, end);   
  50.             //换回原位置   
  51.             buf[i] = buf[start];   
  52.             buf[start] = temp;   
  53.         }   
  54.     }   
  55. }   
Code:
  1. /************************************************************  
  2. *名称:    problem02.c                                         *  
  3. *描述:    整形数组中取n个元素和等于元素个数m(m>=n)            *  
  4. *假设:    不能重复取某个元素                                   *  
  5. *思路:    从1到m 组和数组元素并求和判断是否等于m           *  
  6. *改进:    见107行注释                                         *  
  7. *环境:    Code::Blocks & Windows 7 & x86                      *  
  8. *备注:    davelv于09年光棍节20点                                *  
  9. *************************************************************/  
  10. #include <stdio.h>   
  11. #include <stdlib.h>   
  12. #include <string.h>   
  13.   
  14. #define BUF_LEN 1024   
  15. //比较函数，用于qsort   
  16. int compare ( const void *a , const void *b );   
  17. //求有几种取法的函数   
  18. int  getotalNum (int array[], int m);   
  19. //数字组合函数   
  20. void combine(int array[], int result[], int m, int n);   
  21.   
  22. int main(void)   
  23. {   
  24.     int buf[BUF_LEN], m, i;   
  25.   
  26.     printf("Please input NO. of integer(s) no more than %d:", BUF_LEN);   
  27.     scanf("%d",&m);   
  28.     printf("Please input integer(s):");   
  29.     for(i=0; i<m; i++)   
  30.     {   
  31.         scanf("%d",buf+i);   
  32.     }   
  33.     printf("Totle %d way(s)/n", getotalNum(buf,m));   
  34.     system("PAUSE");   
  35.     return 0;   
  36. }   
  37.   
  38. int compare ( const void *a , const void *b )   
  39. {   
  40.     return *(int *)a - *(int *)b;   
  41. }   
  42. //返回值为取法的总数，如果是-1则表示函数失败   
  43. int  getotalNum (int array[], int m)   
  44. {   
  45.     int i, totle;   
  46.     int *result;   
  47.   
  48.     qsort(array, m, sizeof(array[0]), compare);//排序   
  49.     //排除大于m的数字   
  50.     for(i=0; i<m; i++)   
  51.     {   
  52.         if (array[i] > m)   
  53.         {   
  54.             m = i;   
  55.             break;   
  56.         }   
  57.     }   
  58.     result = (int*)malloc(m * sizeof(int));//为combine函数分配缓存空间   
  59.     if (result == NULL)   
  60.         return -1;   
  61.     //循环从1组和到m   
  62.     totle=0;   
  63.     for(i=1; i<=m; i++)   
  64.     {   
  65.         combine(array, result, m, i);   
  66.         totle += *result;   
  67.     }   
  68.     free(result);   
  69.     return totle;   
  70. }   
  71. //array:存储数字，result:存储本次结果,m:array长度即组合下标,n:组合上标   
  72. void combine(int array[], int result[], int m, int n)   
  73. {   
  74.     int i,t;//计数器,begin变量的中间变量   
  75.     static int totle=0,level=0,begin=0,num=0;//已经组合数字和,已递归深度,组合开始元素的下标,符合要求组合的个数   
  76.   
  77.     for (i=begin; i<=m-n+level; i++)   
  78.     {   
  79.         if ( totle+array[i] <= m)//判断当前组合数字和是否已经超出m限制   
  80.         {   
  81.             totle += array[i];   
  82.             result[level] = array[i];//保存当前数字   
  83.             //判断当前层数是不是N-1   
  84.             if (level < n-1)   
  85.             {   
  86.                 level++;   
  87.                 t = begin;begin = i+1;   
  88.                 combine(array, result, m, n);        //下层递归   
  89.                 begin= t;   
  90.                 level--;   
  91.             }   
  92.             else  
  93.             {   
  94.                 if(totle == m)//判断当前数字和是否符合要求   
  95.                 {   
  96.                     int j;   
  97.                     for(j=0; j<=level; j++)//符合则输出数字   
  98.                         printf("%d ",result[j]);   
  99.                     puts("");   
  100.                     num++;        //计数器加一   
  101.                 }   
  102.             }   
  103.             totle -= array[i];   
  104.         }   
  105.         else  
  106.             break;//超出限制则跳出   
  107.             /**************************************************  
  108.             *若使用longjmp直接跳回getotalNum可获得更好的性能*  
  109.             **************************************************/  
  110.     }   
  111.     if (level == 0)   
  112.     {   
  113.         result[0] = num;   
  114.         totle = num = 0;//将static变量归零   
  115.     }   
  116. }   
 
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞