抽签

X星球要派出一个5人组成的观察团前往W星。 其中: A国最多可以派出4人。 B国最多可以派出2人…

X星球要派出一个5人组成的观察团前往W星。
其中:
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
….

那么最终派往W星的观察团会有多少种国别的不同组合呢?

下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为:
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
….
(以下省略,总共101行)

给出代码,请你填空:

思路:

很少做这种填空的,但是递归的话,会有遵循一定的技巧
可以看到递归的首次调用:

a, b数组肯定是不变的参数了,关键是如何确定中间的参数

通过题意理解,中间的参数应该是:

关键是看递归中是如何实现的:

k的判断:

终止条件是k==N,那么应该是k逐渐递增的,这也符合逻辑:各个国家按顺序,派遣人员,逐渐填满下标,所以大概率是填:k+1

m的判断:

  • 观察这个循环,a[k]是第k个国家可以派遣的人员的最大数量,从0a[k]说明是在穷举第k个国家派出人员的情况
  • 而内循环则是:第k个国家派遣了i人,循环填掉i个位置(m越少,M-m越大,空位起始的下标逐渐靠后,也是合理的)

那么递归就很清晰了:
k个国家出了i个人,剩下m-i个空位,留给k+1 ~ N个国家,于是m大概率填 m-i,因为循环结束,i==j,填m-j也可以

答案:

完整代码

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/2612.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部