信息学奥赛初赛天天练-80-NOIP2015普及组-基础题5-错位排列、二叉树、完全二叉树、叶子节点、完全二叉树叶子节点

本文主要是介绍信息学奥赛初赛天天练-80-NOIP2015普及组-基础题5-错位排列、二叉树、完全二叉树、叶子节点、完全二叉树叶子节点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

NOIP 2015 普及组 基础题5

21 重新排列 1234使得每一个数字都不在原来的位置上,一共有( )种排法

22 一棵结点数为 2015的二叉树最多有( )个叶子结点

2 相关知识点

1) 错位排列

考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)

错排问题最早被尼古拉·伯努利和欧拉研究,因此历史上也称为伯努利-欧拉的装错信封的问题。

这个问题有许多具体的版本,如在写信时将n封信装到n个不同的信封里,有多少种全部装错信封的情况?

又比如四人各写一张贺年卡互相赠送,有多少种赠送方法?自己写的贺年卡不能送给自己,也是典型的错排问题

例题

有99封信,装到99个信箱中,正确的装法是,每封信装到正确的信箱中,即1号信装1号信箱,2号信装2号信箱

每封信都恰好装错的装法一个有多少种?

解析

D[i]表示i封信进行错排
此题需要计算D[99]
通过枚举可知,D[1]=0,D[2]=1,D[3]=2
此题可分2步
第1步
1 把信放入信箱,第1个信箱可以放2~99总共n-1封,即98封信,具体如下

第2步
2 要求装错,1号信不能放入1号信封,除1号信,其他都可以放入1号信封
考虑3号放入1号信封,此时分两种情况
1号信放入3号信和1号信不放入3号信箱2种情况

1号信放入3号信封时
1号信和3号信分别3号信封和1号信封,剩余2,4,5...99封信和2,4,5...99个信箱进行错排
满足97封信进行错排即D[n-2]=D[97]1号信不放3号信封时
此时3号信已经放入1号信封,不需要考虑3号信和1号信封
把1号替换到3号信,此时1号信不能放入3号信封,观察信2,1,4,5...99和信封2,3,4,5...99,满足错排
98封信进行错排,这种情况错排D[n-1]=D[98]

根据乘法原理,所以错排的递推公式为

D[n] = (n-1) * (D[n-1] +D[n-1])
D[99]=98 * (D[98] + D[97] )
由前面枚举可知
D[1]=0,D[2]=1,D[3]=2
推出以下错排
D[4]=(4-1) * (D[4-1] + D[4-2])=3*(D[3]+D[2])=3 * (2+1)= 9
D[5]=(5-1) * (D[5-1] + D[5-2])=4*(D[4]+D[3])=4 * (9+2)= 44

2) 树的相关概念

根节点

在一颗树形结构中,最顶层的那个节点就是根节点了,所有的子节点都源自它发散开来。

父节点

树的父子关系和现实中很相似,若一个节点含有子节点,则这个节点称为其子节点的父节点。

叶子节点

直观来看叶子节点都位于树的最底层,就是没有分叉的节点,严格的定义是度为 0 的节点叫叶子节点。

非叶节点

在树中的所有节点,除去叶子节点都为非叶节点

二叉树

每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒

例如下面是一棵二叉树

完全二叉树

除了最下层,其他每层都饱满,去除最后一层是一棵满二叉树,最下层的结点都集中在该层最左边的若干位置上

完全二叉树最后1层叶子节点的数量
包括最后1层所有节点和倒数第2层的叶子节点数量
上图如果3没有子节点,也为叶子节点

3 思路分析

21 重新排列 1234使得每一个数字都不在原来的位置上,一共有( 9 )种排法

分析

根据错排公式
D[n] = (n-1) * (D[n-1] +D[n-1])
由前面枚举可知
D[1]=0,D[2]=1,D[3]=2
推出以下错排
D[4]=(4-1) * (D[4-1] + D[4-2])=3*(D[3]+D[2])=3 * (2+1)= 9

22 一棵结点数为 2015的二叉树最多有( 1008 )个叶子结点

分析

二叉树是每个节点最多有两个子节点的树结构。通常,我们称子节点为左子节点和右子节点。
为了最大化叶子节点的数量,我们应该尽量让每个非叶子节点只有两个子节点(即完全二叉树)
根节点高度为1,则高度为n的满二叉树所有节点树为2^n-1
2015个节点在高度10和11之间
2^10-1=1023
2^11-1=2047
完全二叉树最后一层都为叶子节点2015-1023=992个
倒数第2层有些没有子节点,也是叶子节点2047-2015=32,对应上一层会少一半32/2=16
所以总的叶子节点数量为992+16=1008

这篇关于信息学奥赛初赛天天练-80-NOIP2015普及组-基础题5-错位排列、二叉树、完全二叉树、叶子节点、完全二叉树叶子节点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1125149

相关文章

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

nginx配置多域名共用服务器80端口

《nginx配置多域名共用服务器80端口》本文主要介绍了配置Nginx.conf文件,使得同一台服务器上的服务程序能够根据域名分发到相应的端口进行处理,从而实现用户通过abc.com或xyz.com直... 多个域名,比如两个域名,这两个域名其实共用一台服务器(意味着域名解析到同一个IP),一个域名为abc

Nginx启动失败:端口80被占用问题的解决方案

《Nginx启动失败:端口80被占用问题的解决方案》在Linux服务器上部署Nginx时,可能会遇到Nginx启动失败的情况,尤其是错误提示bind()to0.0.0.0:80failed,这种问题通... 目录引言问题描述问题分析解决方案1. 检查占用端口 80 的进程使用 netstat 命令使用 ss

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型,3步搞定一个应

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面:幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*