信息学奥赛初赛天天练-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

相关文章

如何使用Nginx配置将80端口重定向到443端口

《如何使用Nginx配置将80端口重定向到443端口》这篇文章主要为大家详细介绍了如何将Nginx配置为将HTTP(80端口)请求重定向到HTTPS(443端口),文中的示例代码讲解详细,有需要的小伙... 目录1. 创建或编辑Nginx配置文件2. 配置HTTP重定向到HTTPS3. 配置HTTPS服务器

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

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