编程 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);
要求有输入输出,而不是仅仅做一个函数出来..
/************************************************************ *名称: problem01.c * *描述: 给定一个字符串,输出给定字符串所有的组合的函数 * *假设: 假设字符串中的字母不重复 * *思路: 对输入字符数组下标全排列再按照排列顺序输出即可 * *环境: Code::Blocks & Windows 7 & x86 * *备注: davelv于09年光棍节19点 * *************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #define BUF_LEN 1024 //排列输出函数 void perm(char *buf, int start, int end); int main(void) { char buf[BUF_LEN]; printf("Please input string less than %d letters:", BUF_LEN); fgets(buf, BUF_LEN, stdin); if (buf[strlen(buf)-1] == '/n') buf[strlen(buf)-1] = '/0';//去除控制台附加的/n perm(buf, 0, strlen(buf));//排列输出 system("PAUSE"); return 0; } //buf 待字符串;start 排列开始位置;end 排列结束位置 void perm(char *buf, int start, int end) { int i; char temp; if (start == end) {//当排列到最后一个字符时输出 puts(buf); } else {//否则继续排列 for (i=start; i<end; i++) { //交换 temp = buf[start]; buf[start] = buf[i]; buf[i] = temp; //递归排列 perm(buf, start+1, end); //换回原位置 buf[i] = buf[start]; buf[start] = temp; } } }
/************************************************************ *名称: problem02.c * *描述: 整形数组中取n个元素和等于元素个数m(m>=n) * *假设: 不能重复取某个元素 * *思路: 从1到m 组和数组元素并求和判断是否等于m * *改进: 见107行注释 * *环境: Code::Blocks & Windows 7 & x86 * *备注: davelv于09年光棍节20点 * *************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #define BUF_LEN 1024 //比较函数,用于qsort int compare ( const void *a , const void *b ); //求有几种取法的函数 int getotalNum (int array[], int m); //数字组合函数 void combine(int array[], int result[], int m, int n); int main(void) { int buf[BUF_LEN], m, i; printf("Please input NO. of integer(s) no more than %d:", BUF_LEN); scanf("%d",&m); printf("Please input integer(s):"); for(i=0; i<m; i++) { scanf("%d",buf+i); } printf("Totle %d way(s)/n", getotalNum(buf,m)); system("PAUSE"); return 0; } int compare ( const void *a , const void *b ) { return *(int *)a - *(int *)b; } //返回值为取法的总数,如果是-1则表示函数失败 int getotalNum (int array[], int m) { int i, totle; int *result; qsort(array, m, sizeof(array[0]), compare);//排序 //排除大于m的数字 for(i=0; i<m; i++) { if (array[i] > m) { m = i; break; } } result = (int*)malloc(m * sizeof(int));//为combine函数分配缓存空间 if (result == NULL) return -1; //循环从1组和到m totle=0; for(i=1; i<=m; i++) { combine(array, result, m, i); totle += *result; } free(result); return totle; } //array:存储数字,result:存储本次结果,m:array长度即组合下标,n:组合上标 void combine(int array[], int result[], int m, int n) { int i,t;//计数器,begin变量的中间变量 static int totle=0,level=0,begin=0,num=0;//已经组合数字和,已递归深度,组合开始元素的下标,符合要求组合的个数 for (i=begin; i<=m-n+level; i++) { if ( totle+array[i] <= m)//判断当前组合数字和是否已经超出m限制 { totle += array[i]; result[level] = array[i];//保存当前数字 //判断当前层数是不是N-1 if (level < n-1) { level++; t = begin;begin = i+1; combine(array, result, m, n); //下层递归 begin= t; level--; } else { if(totle == m)//判断当前数字和是否符合要求 { int j; for(j=0; j<=level; j++)//符合则输出数字 printf("%d ",result[j]); puts(""); num++; //计数器加一 } } totle -= array[i]; } else break;//超出限制则跳出 /************************************************** *若使用longjmp直接跳回getotalNum可获得更好的性能* **************************************************/ } if (level == 0) { result[0] = num; totle = num = 0;//将static变量归零 } }
[大笑]
很经典的算法
自己想了一节课,没想出算法,递归难
<div class="quote"><span class="q"><b>西安邮电学院 胡海浪(C/C++学生)</b>: 自己想了一节课,没想出算法,递归难</span></div>递归算法要用递归的思想去理解,我现在也是做得不够呢
不错
代码写的很漂亮[惊讶]
好啊。。。不错
额???居然没要求时间复杂度。。。
<div class="quote"><span class="q"><b>重庆邮电大学 吴小伟(C/C++学生)</b>: 额???居然没要求时间复杂度。。。</span></div>第一个是O(n!)
第二个是O(sigama(1,n,A(n,i)))
第二个题目还可以进一步优化,优化后是O(n!),等会贴新帖子.
等有时间也写一下 试试呵呵
<div class="quote"><span class="q"><b>CAS davelv(C/C++学生)</b>: 第一个是O(n!)
第二个是O(sigama(1,n,A(n,i)))
第二个题目还可以进一步优化,优化后是O(n!),等会贴新帖子.</span></div>n!这个是不是有点恐怖了哦? 能否优先到n^2?甚至是n, logn……
能写出n!也相当不错了,楼主继续加油,我们的路都还很长。
<div class="quote"><span class="q"><b>CAS davelv(C/C++学生)</b>: 第一个是O(n!)
第二个是O(sigama(1,n,A(n,i)))
第二个题目还可以进一步优化,优化后是O(n!),等会贴新帖子.</span></div>第二题用DP试试吧,应该可以达到O(NM2)
<div class="quote"><span class="q"><b>哈尔滨工业大学 赵昱(C/C++学生)</b>: 第二题用DP试试吧,应该可以达到O(NM2)</span></div>DP是动态规划吧.貌似动态规划只能求得一个解,而不是全部的解.题目要求要计算出全部解的个数,所以,DP在这里不好用.
<div class="quote"><span class="q"><b>重庆邮电大学 吴小伟(C/C++学生)</b>: n!这个是不是有点恐怖了哦? 能否优先到n^2?甚至是n, logn……
能写出n!也相当不错了,楼主继续加油,我们的路都还很长。</span></div>今天TSU的朋友让我看MATRIX67的blog上生成函数这一问,他说觉得这个可能对本题有帮助,回去看下,再做总结
[大笑],我通过了
[e03]
哥今天去面试,遇到这题没答上来….[e08]
今天逛博客来看看你之前的日志。
第二题:我刚开始还以为是0/1背包,我还在郁闷你为啥不直接DP。。。后来一看原来是完全背包。。。。
我对背包也不怎么熟悉,完全是凭感觉去做。优化http://blog.csdn.net/davelv/archive/2009/12/06 /4950605.aspx 进一步优化http://blog.csdn.net/davelv/archive/2009/12/15/5007625.aspx