华为面试题,大家讨论下!
求组合数: 求n个数(1....n)中k个数的组合....如:combination(5,3)
要求输出:543,542,541,532,531,521,432,431,421,321
给定一个数组,这个数组中既有正数又有负数,找出这个数组中的子数组,此子数组的和最大!
#include <stdio.h> int data[100] = {5,4,3,2,1}; bool foot[100] = {0}; int cool = 0; void com(int n,int k,int mem[],int depth,int begin) { int i,j; if(k == depth) { for(i = 0;i<k;i++) printf("%d ",mem[i]); cool++; printf("\n"); return ; } for(i = 0;i<n;i++) { if(!foot[i]) { foot[i] = true; mem[begin] = data[i]; com(n,k,mem,depth+1,begin+1); foot[i] = false; } } } int main() { int mem[100] = {0}; com(5,3,mem,0,0); return 0; }以上程序完成 A(m,n)并且将其打印出来
#include <stdio.h> int data[100] = {5,4,3,2,1}; bool foot[100] = {0}; int cool = 0; void com(int n,int k,int mem[],int depth,int begin,int pos) { int i,j; if(k == depth) { for(i = 0;i<k;i++) printf("%d ",mem[i]); cool++; printf("\n"); return ; } for(i = pos;i<n;i++) { if(!foot[i]) { foot[i] = true; mem[begin] = data[i]; com(n,k,mem,depth+1,begin+1,i+1); foot[i] = false; } } } int main() { int mem[100] = {0}; com(5,3,mem,0,0,0); return 0; }上面程序完成了 C(m,n)并且将其打印出来
#include<stdio.h> int main() { int i,j,k; int b,c,n; while(EOF != scanf("%d",&n)) { if(0 == n) break; int a[10001] = {0}; int max[10001] = {0}; int begin = 0,end = 0,tempmax = -1; int tempbegin = 0; for(i = 1;i<=n;i++) { scanf("%d",&a[i]); if(1 == i) { max[i] = a[i]; tempmax = max[i]; tempbegin = begin = end = i; } else { if(max[i-1]>=0) { max[i] = max[i-1]+a[i]; } else { max[i] = a[i]; tempbegin = i; } if(tempmax < max[i]) { tempmax = max[i]; end = i; begin = tempbegin; } } } for(i = 1;i<=n;i++) if(a[i]>=0) break; if(i > n) printf("0 %d %d\n",a[1],a[n]); else printf("%d %d %d\n",tempmax,a[begin],a[end]); } return 0; }
#include<stdio.h> void combination(int n,int k); static path[100]={0}; int cnt=0; void main() { combination(5,3); } void combination(int n,int k) { if(n>=k) { if(n==k) { for(int i=n;i!=0;--i) path[cnt++]=i; for(i=0;i<cnt;i++) printf("%d",path[i]); printf(" "); cnt-=n+1; return; } if(k==0) { for(int i=0;i<cnt;i++) printf("%d",path[i]); printf(" "); cnt--; return; } if(k==1) { for(int i=n;i!=0;--i) { path[cnt++]=i; combination(i,0); } cnt--; } else { path[cnt++]=n; combination(n-1,k-1); combination(n-1,k); } } else printf("data error!\n"); }第二个是不是只要找出所有正数就可以了呢?