递归算法的设计？

Question

如题所述

Answer 1

#include <stdio.h>

int C(int n,int m)

{ if(m==0||m==n)return 1;

  return C(n-1,m)+C(n-1,m-1);

}

int main()

{ int i,j;

  for(i=0; i<11; i++)

  { for(j=0; j<=i; j++)

      printf("%5d",C(i,j));

    printf("\n");

  }

  return 0;

}

Answer 2

基本思想是先用必要条件找，然后再遍历一遍验证是否满足条件，不用递归很容易。
因为你限制了要用递归，那么看上去只能这样了：
若a在A中占据一半以上，那么把A分成A1，A2两部分之后，a在其中至少一个子列中也占据一半以上。
利用这一性质，递归地在A1,A2中寻找候选元素，然后遍历数组以验证这两个候选元素(如果存在的话)是否满足条件。
根据归纳假设，在A1,A2中寻找候选元素的时间复杂度是O(n)，再对A遍历至多两遍，复杂度仍然是O(n)。

Answer 3

递归函数如下：
int fun(int n,int m){
if(m==0||m==n)
return 1;
else
return fun(n-1,m)+fun(n-1,m-1);
}
可以在其他函数中，用语句调用这个递归函数。
如：
printf("C(3,2)=%d\n",fun(3,2));
等等。本回答被网友采纳

Answer 4

C(n,m)=n!/[m!*(n-m)!]
。。。排列组合公式吧。

Answer 5

这道递归在于判断条件和转移的公式，题目很简单，是对新手的锻炼。本回答被网友采纳