帮我看看这道题
  • 板块学术版
  • 楼主123ytq666
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/9/28 15:05
  • 上次更新2024/9/28 17:14:32
查看原帖
帮我看看这道题
1121305
123ytq666楼主2024/9/28 15:05

4.奶牛家谱树(cowtree)

问题描述

学校开展社会实践活动,小John随老师和同学们一道来到了奶牛场。奶牛场经理听了小John的故事,说他这里也有一个问题需要解决,想请小John帮忙,小John拍着胸脯说,“没问题,交给我吧!请您告诉我问题”,经理告诉小John:奶牛场准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示,这些二叉树总共有 N 个节点(3≤N < 200),并具有如下性质:

(1)每一个节点的度只能是 0 或 2。度是这个节点的孩子的数目;

(2)经过的节点数(包括根节点和最远的叶子节点);叶子节点是指没有孩子的节点。树的高度等于 K(1 < K < 100)。高度是从根到最远的那个叶子节点所需要的层次。

如果一个家谱的树结构不同于另一个的,那么这两个家谱就是不同的。请问,有多少种不同的家谱树结构?输出可能的家谱树的个数除以9901的余数。

输入格式

一行,两个正整数N和K(中间用空格隔开),分别表示二叉树的节点总数和二叉树的高度。

输出格式

一行。一个正整数,表示可能的家谱树的个数除以9901的余数。

输入样例

5 3

输出样例

2

样例说明

输出结果表示在 5 个节点,高为 3 的情况下,有两个不同的家谱树,除以 9901 的余数为 2。家谱树结构如下:

其中,

家谱树 1 中共 5 个节点,树的高度为 3,A 为根节点,C、D、E 为叶子节点(没有孩子节点),A、B 节点的度均为 2;

家谱树 2 中共 5 个节点,树的高度为3,A 为根节点,B、D、E 为叶子节点(没有孩子节点),A、C 节点的度均为 2。

数据范围

3≤N < 200, 1 < K < 100

2024/9/28 15:05
加载中...