对于含有 n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为（ ）。
①n! ② 2n ③ 2n+1-1 ④
这样的题就该我这数学小天才来解答一下了！！！！！
子集树和排列树的基本概念请转向https://blog.csdn.net/XD_fybdw/article/details/80870560，一定要看完这个帖子再看下面的！！！
1、子集树解空间的最大叶节点数目就是n个元素的最多的子集个数，很明显n个元素的每一个元素都有两种选择是否位于子集中，故最多的子集个数为2^n；
2、那么子集树解空间的最多节点数为多少？答案很简单：2^0+2^1+2^2+......+2^n=2^(n+1)-1，就是题目选项C的结果；
3、n个元素的排列树的最多叶节点个数就是n个元素的全排列，即n!
4、那么你应该很容易的想到选项D设置的意义在哪？？？？
没错！！选项D给出的就是排列树中最多的节点个数。简单的这样的理解：从叶子节点开始看起，为n!个节点，即n!/1!，倒数第二层的节点个数为：n!/2，即n!/2!，倒数第三次的节点个数为n!/2再除以3，即n!/3!，以此类推，自己推去吧，哈哈哈哈哈哈
发表于 2018-12-28 21:06:33
回复(11)
当所给问题是从 N 个元素的集合 S 中找出满足某种性质的子集时，相应的解空间称为子集树。
容易知道，所有可能解的数目是组合数求和 C0n + C1n + ... + Cnn = 2n 。
发表于 2017-09-14 17:12:37
回复(4)
问题信息
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
