信息学奥赛初赛全部知识汇总.ppt

信息学奥林匹克分区联赛的基础知识 初赛试题结构 第一部分基础知识第二部分问题求解第三部分阅读程序第四部分完善程序 第一部分 一 计算机的发展与应用二 计算机概述三 多媒体技术应用四 计算机网络使用基础 一 计算机的发展与应用 一 计算机的发展与应用 1 下面列出的四项中 不属于计算机病毒特征的是 A 潜伏性B 激发性C 传播性D 免疫性2 国产银河型数字式电子计算机是属于下列哪种类型计算机 A 微型B 小型C 中型D 巨型3 计算机病毒是指 A 能传染给用户的磁盘病毒B 已感染病毒的磁盘C 具有破坏性的特制程序D 已感染病毒的程序4 最早的计算机的用途是用于 A 科学计算B 自动控制C 辅助设计D 系统仿真5 操作系统在第几代计算机开始应用 A 第一代B 第二代C 第三代D 第四代 第二代晶体管计算机 1956 1963 1948年 晶体管的发明大大促进了计算机的发展 晶体管代替了体积庞大电子管 电子设备的体积不断减小 1956年 晶体管在计算机中使用 晶体管和磁芯存储器导致了第二代计算机的产生 第二代计算机体积小 速度快 功耗低 性能更稳定 首先使用晶体管技术的是早期的超级计算机 主要用于原子科学的大量数据处理 这些机器价格昂贵 生产数量极少 1960年 出现了一些成功地用在商业领域 大学和政府部门的第二代计算机 第二代计算机用晶体管代替电子管 还有现代计算机的一些部件 打印机 磁带 磁盘 内存 操作系统等 计算机中存储的程序使得计算机有很好的适应性 可以更有效地用于商业用途 在这一时期出现了更高级的COBOL CommonBusiness OrientedLanguage 和FORTRAN FormulaTranslator 等语言 以单词 语句和数学公式代替了含混晦涩的二进制机器码 使计算机编程更容易 新的职业 程序员 分析员和计算机系统专家 和整个软件产业由此诞生 1什么是CISC机 什么是RISC机 2计算机的发展分为几个阶段 正在研制的新型计算机具有哪些特点 3简述 三金 工程的含义 4什么是计算机病毒 它具有哪些特征 如何采取具体的防范措施 资料 CISC微处理器是台式计算机系统的中心 这个核心中的核心就是运行指令的电路 指令由完成任务的多个步骤所组成 例如把数值传送进寄存器或进行相加运算 都是需要指令的 这些指令被称为微代码 microcode 不同制造商的微处理器有不同的微代码系统 制造商可按自己的意愿使微代码做得简单或复杂 指令系统越丰富 微处理器编程就越简单 然而 执行速度也相应越慢 而且设计这样的处理器的代价也就越大 但是由于指令系统丰富 对上层的支持就比较好 下面我们来看看两种处理器的比较 复杂指令系统计算机 CISC 包含一个丰富的微代码系统 简化了处理器上运行程序的编制 精简指令系统计算机 RISC 有一个精简的指令系统 从而提高了微理器的效率 但需要更复杂的外部程序 也就是把在处理器层没有完成的工作放到了上层进行 而处理器层少的这些成本可以用对物理器件速度的提高上去 RISC方案基于JohnCocke在IBM公司的工作 他发现约20 的计算机指令完成约80 的工作 因此 RISC系统通常比CISC系统要快 他的80 20规则促进了RISC体系结构的开发 大多数台式微处理器方案如Intel和Motorola芯片都采用CISC方案 工作站处理器加MIDS芯片DECAlpha和IBMRS系列芯片均采用RISC体系结构 将来的处理器会在RISC和CISC之间寻找到一条合适的途径来保证处理器的成本较小 而且功能比较合适 二 计算机概述 1 世界上首先实现存储程序的电子数字计算机是 A ENIACB UNIVACC EDVACD EDSAC2 计算机能直接执行的指令包括两部分 它们是 A 源操作数与目标操作数B 操作码与操作数C ASCII码与汉字代码D 数字与字符3 下列诸因素中 对微机工作影响最小的是 A 尘土B 噪声C 温度D 湿度4 在计算机中 ASCII码是几位二进制代码 A 7B 8C 12D 165 下面四个不同进制的数 最小的一个数是 A 11011001 2B 37 8C 75 10D A7 16 资料 1简述冯 诺依曼型计算机的组成与工作原理 2计算机硬件系统由哪五个基本部分组成 它们各自的功能是什么 3机器指令由哪几部分组成 按其功能分为哪几种指令类型 4 在计算机中 带符号数有几种表示方法 它们之间的转换关系是什么 各自有什么用途 5ASCII码由几位二进制数组成 它能表示什么信息 6二进制的计算规则 三 多媒体技术应用 1 彩色显示器所显示的五彩斑斓的色彩 是由哪三色混合而成的 A 红B 白C 蓝D 绿E 橙2 下面哪个部件对于个人桌面电脑的正常运行不是必需的 A CPUB 图形卡 显卡 C 光驱D 主板E 内存3 下列哪个 些 不是个人计算机的硬件组成部分 A 主板B 虚拟内存C 电源D 硬盘E 总线4 一个文本屏幕有25列及80行 屏幕的左上角以 1 1 表示 而右下角则以 80 25 表示 屏幕上每一个字符占用两字节 byte 整个屏幕则以线性方式存储在电脑的存储器内 屏幕左上角开始 位移为0 然后逐列逐列存储 求位于屏幕 X Y 的第一个字节的位移是 A Y 80 X 2 1B Y 1 80 X 1 2C Y 80 X 1 2D Y 1 80 X 2 1 1 多媒体计算机系统的基本配置包含了哪些设备 2CD ROM的功能大小取决于哪几个参数 3显示存储空间由哪几个主要的因素决定 4目前国际上有哪几种压缩数据的标准 资料 四 计算机网络使用基础 1 Internet的规范译名应为 A 英特尔网B 因特网C 万维网D 以太网2 下列哪些计算机网络不是按覆盖地域划分的 d A 局域网B 都市网C 广域网D 星型网3 以下列举Internet的各种功能中 错误的是 A 编译程序B 传送电子邮件C 查询信息D 数据库检索4 计算机网络最突出的优点是 A 传送信息速度高B 共享资源C 内存容量大D 交互性好5 TCP IP协议共有 层协议A 3B 4C 5D 6 1什么是WAN网 什么是LAN网 他们各自的功能是什么 2什么是计算机网络的拓扑结构 常见的拓扑结构有几种 3 什么是计算机网络协议 说出OSI的七层协议的名称 4 在Internet中 IP地址和域名的作用是什么 它们之间有什么异同 资料 第二部分 数学知识组合 排列 集合等数据结构图 树等 第三部分阅读程序 直接推理有流程图推断算法动态模拟由底向上阅读分析 例一 Varm n i integer t extended Beginread n m t 1 fori 1tomdot t n i 1 i writeln t 0 0 End 输入 105输出 10 45 120 210 252 例二 Label10 20 30 Vars p string I k n j m integer Beginreadln s n length s readln p m length p i 0 10 i i 1 j I k 1 例二 续 20 Ifs j p k thenbeginifi n m 1thengoto10 i 0 goto30 endelseifk mthenbeginj j 1 k k 1 goto20 end 30 writeln i End 输入asabcdffdinfdi输出 例三 Vari j integer a array 1 3 1 3 ofinteger Beginfori 1to3dobeginforj 1to3dobeginifi 3thena i j a i 1 a i 1 j 1elsea i j j write a i j end WritelnEndReadlnEnd 例四 Vara d array 1 100 ofinteger N I j k x s integer Beginn 5 a 1 1 d 1 1 fori 1tondobegins i 1 x 0 forj 1ton 1 Idobegink s x x x 1 a j 1 a j k write a j end writeln d i 1 d i I a 1 d i 1 end End 输出 第四部分完善程序 变量方面的填空 定义类型 设定初值 变量赋值等 循环方面的填空 定义变量 设定循环的初值和终值 在循环中如何引用 分支转移方面的填空 定义布尔表达式 确定程序的走向 主程序和子程序关系方面的填空 值参 变参 调用格式 输入输出方面的填空 不含子程序 例一 求元素之和最大的子方阵 在m4 n5的正整数数字方阵中 找出一个p3 q3的子阵 使得其元素之和最大 程序清单 Vara array 1 20 1 20 ofinteger m n p q I j max p1 q1 s i1 j1 integer Beginfori 1to20doforj 1to20doa i j 0 readln m n fori 1tomdobeginforj 1tondoread a i j readlnend readln p q max 0 程序清单 续 Fori 1tom p 1doforj 1ton q 1dobegin 1 fori1 Itop i 1doforj1 jtoq j 1do 2 ifs maxthenbegin 3 p1 I q1 j end end Fori p1to 4 doBeginforj q1to 5 dowrite a I j 3 writeln end readlnend 例二 Constmaxm 10000 VarI k m n rest start temp longint a array 0 maxm oflongint Beginwrite inputm n readln m n fori 0tom 1doa i random 100 writeln beforemove fori 0tom 1dowrite a i 5 writeln rest m start 0 while 1 dobegink start repeatk k n modmuntilk start 例二 续 If 2 thenBegintemp a k Repeata k a m n k n modm k m n k n modm 3 untilk start 4 End 5 End Writeln aftermove Fori 0tom 1dowrite a i 5 WritelnEnd 完善含有子程序的程序 例 输入任意一个正整数n 输出组成n的互不相同的菲波那契数 Varn integer first boolean Functionfind n integer integer Vara b c integer Begina 1 b 1 repeatc 1 a b b c untilb n ifb nthenfind 2 elsefind 3 End 例 续 Procedurep n integer Vara integer begina find n iffirstthenbeginwrite a 4 first false endelsewrite a 4 ifa nthenp 4 End beginreadln n first true write n 5 p n writeln readlnend 1 1CISC与RISC CISC即ComplexInstructionSetComputer 在最初 人们采用的优化方法是增强计算机指令系统功能的方法 就是设置一些功能复杂的指令 把一些原来由软件实现的 常用的功能改用硬件的指令系统实现 以提高计算机的执行速度 这种计算机系统就被称为复杂指令系统计算机 RISC即ReducedInstructionSetComputer 是在80年代才发展起来的 其基本思想是尽量简化计算机指令功能 只保留那些功能简单 能在一个节拍内执行完成的指令 而把较复杂的功能用一段子程序来实现 这种计算机系统就被称为精简指令系统计算机 1 2计算机发展的阶段 1 2研制中的第五代计算机 1 创建非冯 诺伊曼式语言LISP PROLOG2 创建以人脑神经系统处理信息的原理为基础的非冯 诺伊曼式的计算机模型生物计算机光子计算机量子计算机 1 3三金工程 金桥 工程又称经济信息通信网工程 它是建设国家公用经济信息通信网 实现国民经济信息化的基础设施 这项工程的建设 对于提高我国宏观经济调控和决策水平以及信息资源共享 推动信息服务业的发展 都具有十分重要的意义 金关 工程又称为海关联网工程 其目标是推广电子数据交换 EDI 技术 以实现货物通关自动化 国际贸易无纸化 金卡 工程又称电子货币工程 它是借以实现金融电子化和商业流通现代化的必要手段 1 4计算机病毒 计算机病毒是一种功能特殊的计算机程序 它一旦运行 便取得系统控制权 同时把自己复制到媒体中去 计算机病毒的特征 1 能够自身复制到其他程序中 2 不独立以文件形式存在 仅附加在别的程序上 当调用该程序运行时 此病毒则首先运行 2 1冯 诺伊曼型计算机 输入设备 运算器CPU 存储器 控制器cpu 输出设备 输入 输出 第一台具有存储功能的计算机EDVAC逻辑功能图 2 2计算机硬件系统 1 输入设备若要计算机按我们的要求进行工作 计算机必须接受外部的信息 使计算机从外部获得信息的设备 称为输入设备 inputdevice 常用的输入设备包括键盘 光笔 鼠标器 扫描仪 话筒等 通过它们可以输入文字 图像 声音等不同的信息 输入设备种类很多 近几年来出现了触摸屏 手写汉字输入设备 自然语言输入设备 数码照相机等 2 输出设备计算机把信息处理的结果以人们能够识别的形式表示出来的设备 称为输出设备 outputdevice 例如 显示器 打印机 绘图仪等 3 存储器计算机在处理信息的过程中 许多信息被存放在存储器 memory 中 存储器又分为内存储器和外存储器两种 4 运算器运算器 arithmeticunit 是计算机实施算术运算和逻辑判断的主要部件 它能按照计算机程序的要求 在控制器的控制下 进行加 减 乘 除等基本运算和进行判别数的符号 比较数的大小等逻辑运算 5 控制器控制器 controller 是指挥 控制计算机运行的中心 它从存储器中取出信息并进行分析 然后根据指令向计算机各个部分发出各种控制信息 使计算机按照要求自动 协调地完成任务 一般将运算器和控制器合称为中央处理器 简称CPU 2 3计算机指令系统 机器指令是要计算机执行某种操作的命令 且由计算机直接识别执行 所有指令的集合称为计算机的指令系统 一条指令通常有操作码和地址码两部分组成 操作码地址码指令按功能可分为操作类命令和控制转移类命令 操作码指明计算机执行的某种操作的性质和功能 地址码指出被操作的数据 简称操作数 存放在何处 即指明操作数地址 有的指令格式允许地址码部分就是操作数本身 2 6软件系统 软件一般分为系统软件和应用软件 系统软件是生成 准备和执行其他程序所需要的一组程序 它通常负责管理 控制和维护计算机的各种软硬件资源 并为用户提供友好的操作界面 应用软件是专业人员为各种应用目的而编写的程序 一般不能独立地在计算机上运行 必须要有系统软件的支持 2 4机器数 在计算机中 数是存放在由寄存单元组成的寄存器中 二进制数码1和0是由寄存器单元的两种不同的状态来表示的 为了运算的方便 在计算机中常用三种表示法 原码补码反码 原码表示法 也称为符号 幅值表示法符号位用0 正数符号位用1 负数其余位表示数的大小例 X 1011 X 原 01011X 1011 X 原 11011缺点 运算 加 减法 低效0有两个表示 0 00000000 0 10000000表示为 127 127 补码表示法 X 补 X 当X 0 X 补 2 n 1 X 当 2n 1例如 X 100101 X 补 0100101X 100101 X 补 1011011特点 1 补码的和等于和的补码 符号位和数值位一样参加运算 不必单独处理 即 X 补 Y 补 X Y 补2 补码相减 X 补 Y 补 X 补 Y 补 Y 补 Y 补 符号位连同数值位一起取反加13表示范围 128 127 反码表示法 当X 0时 X 反 X当X 0时 符号位为1 其余各位取反 特点 1 反码的和等于和的反码2 有二个零 0 00 0 0 11 13 当最高位有进位而丢掉进位 即2 时 要在最低位加1 循环进位 表示范围 127 127 原码 反码和补码之间的转换 X 反符号位不变 数值位不变 符号位为0 变反 符号位为1 0 1 X真值 X 原数值位不变 数值位不变 符号位为0 变反加1 符号位为1 符号位不变 X 补 当X为正数 X 反 X 原 X 补 X 当X为负数时 X 补 X 反 1 X 补 X 原 2 5ASCII码 ASCII码是美国信息交换标准代码的缩略语 是目前国际上最为流行的字符信息编码方案 它包括数字0 9 大小写字母和专用符号等95种可打印字符 还有33种控制字符 一个字符ASCII码通常占一个字节 用七位二进制编码组成 ASCII码最多可表示128个不同的符号 字节的最高位被很多系统用做校验码 以便提高字符信息传输的可靠性 2 12汉字信息编码 3 汉字交换码 1 区位码 GB2312 80 信息交换用汉字编码字符集 组成一个94 94的矩阵 每一行称为一个 区 每一列称为一个 位 一个汉字的区号和位号合在一起构成 区位码 2 汉字交换码 国标码 GB2312 80 国标码收入6763个汉字 其中一级汉字 最常用 3755个 按拼音排序 二级汉字3008个 按部首排序 另外还包括682个西文字符 图符 区位码 十进制 的两个字节分别转换为十六进制后加20H转换成国际码 4 汉字机内码 是计算机系统中对汉字的一种运行代码 系统内部的存储 传输都是对机内码进行的 它也和汉字存在着一一对应的关系 机内码也占两个字节 且最高位为1 同一个汉字 在同一种汉字操作系统中 内码是相同的 汉字机内码是汉字交换码两个字节的最高位分别加 1 即汉字交换码的两个字节分别加80H 或区位码 十进制 的两个字节分别转换为十六进制后加A0H 由于GB2312 80是80年代制定的标准 在实际应用时常常感到不够 所以 建议处理文字信息的产品采用新颁布的GB18030信息交换用汉字编码字符集 这个标准繁 简字均处同一平台 可解决两岸三地间GB码与BIG5码间的字码转换不便的问题 字形存储码是指供计算机输出汉字 显示或打印 用的二进制信息 也称字模 通常 采用的是数字化点阵字模 有16 16 24 24 64 64等 每一个点在存储器中用一个二进制位 bit 存储 例如 在16 16的点阵中 需8 32bit的存储空间 每8bit为1字节 所以 需32字节的存储空间 在相同点阵中 不管其笔划繁简 每个汉字所占的字节数相等 2 6二进制 采用二进制 优点 1 易于物理实现 2 二进制运算简单 3 机器可靠性高 4 通用性强 乘法除法整数转换小数转换 0 0 00 1 11 0 11 1 100 0 00 1 01 0 01 1 1 数的定点表示和浮点表示 1 定点小数格式任何一个M位的小数可以表示成 N Ns N 1N 2 N m 其中Ns是符号位 其值表示的范围 N 1 2 m 2 定点整数格式任何一个N位带符号的整数都可表示为 N NsNn 1Nn 2 N0 其中Ns是符号位 其值表示的范围 N 2n 1 3 数的浮点表示浮点数是指小数点在数据中的位置可以左右移动的数 一个数N要用浮点表示可以写成 N M RE其中M表示浮点数的尾数 E表示浮点数的指数或称为阶码 R指的是在这个指数下的基数 浮点数通常表示成如下格式 1位m位n位M 浮点数的尾数 用定点小数表示 小数点在尾数最高位之前 是默认的 尾数用于表示浮点数的有效位 其位数N的大小反映了此浮点数的精度 E 浮点数的阶码 用定点整数表示 Ms 浮点数的符号位 也就是尾数的符号位 一般放在整个浮点数的最高位 信息在计算中的存储地址所有的存储单元都按顺序排列 计算机中以一个字节为单位处理 所以计算机对每个存储单元进行了编号 这种编号称为单元地址 通过地址编号寻找在存储器中的数据单元称为 寻址1 地址编号 用二进制数编码 存储器的总容量决定了地址的范围 也决定了地址编号的二进制数位数 如存储器的总容量为64MB 那么它的地址编码为0 64 220 1 对应的二进制数是00000000000000000000000000 11111111111111111111111111 对应的十六进制数是0000000 3FFFFFF 需要用26位二进制来表示 也就是需要26根地址线 2 地址和容量的计算 1 由地址线 求寻址空间 若地址线有32根 则它的寻址空间为232B 222KB 212MB 4GB 2 由起始地址和末地址 求存储空间 若编号为4000H 4FFFH的地址中 包含的单元数的计算 方法一 用十六进制计算 4FFFH 4000H FFFH 1 1000H 1 163 4096 4KB方法二 转换成十进制计算 4FFFH 4000H 20479 16384 4096 4KB 3 由存储容量和起始地址 求末地址 若存储器的容量32KB 地址起始编号为0000H 末地址的计算 方法一 用十六进制计算 0000H 32KB 1H 0000H 32 1024 1H 0000H 8000H 1H 7FFFH方法二 转换成十进制计算 0 32KB 1 0 32768 1 32767 7FFFH方法三 转换成二进制计算 0000H 32KB 1H 0000H 32 210 1H 0000H 215 1H 0000000000000000B 1000000000000000B 0000000000000001B 0111111111111111B 7FFFH 3 2CD ROM 光驱的技术指标 1 数据传输率 DataTransferRate 即大家常说的倍速 它是衡量光驱性能的最基本指标 单倍速光驱就是指每秒可从光驱存取150KB数据的光驱 现在年青一代的40或48倍速光驱每秒钟能读取6000KB和7200KB的数据 2 平均寻道时间 AverageAccessTime 平均寻道时间是指激光头 光驱中用于读取数据的一个装置 从原来位置移到新位置并开始读取数据所花费的平均时间 显然 平均寻道时间越短 光驱的性能就越好 3 CPU占用时间 CPULoading CPU占用时间是指光驱在维持一定的转速和数据传输率时所占用CPU的时间 它也是衡量光驱性能好坏的一个重要指标 CPU占用时间越少 其整体性能就越好 4 数据缓冲区 Buffer 数据缓冲区是光驱内部的存储区 它能减少读盘次数 提高数据传输率 现在大多数光驱的缓冲区为128K或256K 3 3显示存储空间 显示存储空间 水平分辨率 垂直分辨率 色彩数目例如 若采用640 480 16色显示模式 只需要150KB的存储空间 但是 如果想在1280 1024 16M色的显示模式下运行 4MB的显示存储空间是不可能运行的 3 4压缩标准 目前 国际上的压缩技术标准有JPEG MPEG和P 4 JPEG适合于连续色调 多级灰度 彩色或单色静止图象数据压缩的国际标准 可获得10 1到80 1的压缩比 MPEG包括MPEGeg mp4视频 MPEGeg MP3音频和MPEG系统三部分 处理活动影象中的视频压缩 音频压缩 以及多种压缩后数据流的复合和同步问题 可获得50 1到00 1的压缩比 P 4目标是针对可视电话和电视会议的 适应各种通道容量的传输 4 1广域网和局域网 1 广域网WAN wideareanetwork 是跨地域性的网络系统 大多数WAN都是网络互连而成的 如著名的Internet网络 2 局域网LAN LocalAreaNetwork 一般由一个部门或公司组建 地理范围仅在建筑楼内或单位内部 3 城域网 可以看成是广域网的一种 4 2计算机网络拓扑结构 网络中各个站点相互连接的方法和形式称之为网络拓扑 把向工作站 服务器等网络单元抽象成为 点 把网络中的电缆等通信媒体抽象为 线 从而抽象出了络系统的具体结构 即为逻辑结构 网络拓扑结构有 计算机网络拓扑结构 4 3网络协议 计算机通信协议指双方在通信中所应共同遵守的约定 计算机通信协议精确地定了计算机在彼此通信时的所有细节 它规定每台计算机发送每条信息的格式和含义 规定哪些情况下应发送那些特殊的信息 以及接受方的计算机所应作出什么反映等等 OSI七层协议 主机A主机B1应用层应用层2表示层表示层3会话层会话层4运输层运输层5网络层网络层6数据链路层数据链路层7物理层物理层 应用层协议 表示层协议 会话层协议 运输层协议 网络层协议 链路层协议 物理层协议 4 4IP地址 Internet中的每台主机都被分配一个唯一的32位地址 即IP地址 该地址由网络号和主机号两部分组成 其中网络号表示一个网络 而主机号表示这个网络中的一台计算机 IP地址由4个十进制数字字段组成 字段之间用点分开 4个字段中的每个数字在0 255之间 如210 30 240 11 IP地址类型 IP地址按网络规模的大小主要可分成三类 A类地址 B类地址 C类地址 A类的第一个字段的值在1 126之间 一般用于大型网络 B类的第一个字段的值在128 191之间 一般用于中型网络或网络管理器 如路由器等 C类的第一个字段在值在191 233之间 一般用于小型网络 网络地址数网络主机数主机总数A类12616 387 0642 064 770 064B类16 25664 5161 048 872 096C类2 064 512254524 386 048 域名 用IP地址标识主机既没有规律 又很难记忆 用户很难用数字表示的IP地址与计算机的情况联系起来 给访问Internet带来了很大的不便如果采用域名系统 就可以很好地解决这些问题 域名系统是由TCP IP提供的一种服务 可以将域名翻译成相应的IP地址 域名系统采用层次结构 按地理域或组织域进行分层 各层间用圆点 隔开 在主机的域名表示中 从左向右 域名依次从小到大 例如在中 最高域名为cn 次高域名为com 最后一个域名为easthuman 数学相关题目 1 第八届 在书架上放有编号为1 2 n的n本书 现将n本书全部取下然后再放回去 当放回去时要求每本书都不能放在原来的位置上 例如 n 3时 原来位置为123 放回去时只能为 312或231这两种 问题 求当n 5时满足以上条件的放法共有多少种 不用列出每种放法 2 第九届 某年级学生共选修6门课程 期末考试前 必须提前将这6门课程考完 每人每天只在下午至多考一门课程 设6门课程为C1 C2 C3 C4 C5 C6 S Ci 为学习Ci的学生集合 已知S Ci S C6 i 1 2 5 S Ci S Ci 1 i 1 2 3 4 S C5 S C1 问至少安排 天才能考完这6门课程 题目 3 第七届 平面上有三条平行直线 每条直线上分别有7 5 6个点 且不同直线上三个点都不在同一条直线上 问用这些点为顶点 能组成多少个不同四边形 4 第十届 已知a b c d e f g七个人中 a会讲英语 b会讲英语和汉语 c会讲英语 意大利语和俄语 d会讲汉语和日语 e会讲意大利语和德语 f会讲俄语 日语和法语 g会讲德语和法语 能否将他们的座位安排在圆桌旁 使得每个人都能与他身边的人交谈 如果可以 请以 ab 开头写出你的安排方案 从n个不同元素中 任取m个元素 按照一定的顺序排成一列 叫做从n个不同元素中取出m个元素的一个排列 2 组合的定义 从n个不同元素中 任取m个元素 并成一组 叫做从n个不同元素中取出m个元素的一个组合 3 排列数公式 4 组合数公式 1 排列的定义 排列与组合的区别与联系 与顺序有关的为排列问题 与顺序无关的为组合问题 例1学校师生合影 共8个学生 4个老师 要求老师在学生中间 且老师互不相邻 共有多少种不同的合影方式 解先排学生共有种排法 然后把老师插入学生之间的空档 共有7个空档可插 选其中的4个空档 共有种选法 根据乘法原理 共有的不同坐法为种 结论1插入法 对于某两个元素或者几个元素要求不相邻的问题 可以用插入法 即先排好没有限制条件的元素 然后将有限制条件的元素按要求插入排好元素的空档之中即可 分析此题涉及到的是不相邻问题 并且是对老师有特殊的要求 因此老师是特殊元素 在解决时就要特殊对待 所涉及问题是排列问题 解因为女生要排在一起 所以可以将3个女生看成是一个人 与5个男生作全排列 有种排法 其中女生内部也有种排法 根据乘法原理 共有种不同的排法 例25个男生3个女生排成一排 3个女生要排在一起 有多少种不同的排法 结论2捆绑法 要求某几个元素必须排在一起的问题 可以用捆绑法来解决问题 即将需要相邻的元素合并为一个元素 再与其它元素一起作排列 同时要注意合并元素内部也可以作排列 分析此题涉及到的是排队问题 对于女生有特殊的限制 因此 女生是特殊元素 并且要求她们要相邻 因此可以将她们看成是一个元素来解决问题 解把所有的硬币全部取出来 将得到0 05 23 0 10 10 2 15元 所以比2元多0 15元 所以剩下0 15元即剩下3个5分或1个5分与1个1角 所以共有种取法 例3袋中有5分硬币23个 1角硬币10个 如果从袋中取出2元钱 有多少种取法 结论3剩余法 在组合问题中 有多少取法 就有多少种剩法 他们是一一对应的 因此 当求取法困难时 可转化为求剩法 分析此题是一个组合问题 若是直接考虑取钱的问题的话 情况比较多 也显得比较凌乱 难以理出头绪来 但是如果根据组合数性质考虑剩余问题的话 就会很容易解决问题 例4学校安排考试科目9门 语文要在数学之前考 有多少种不同的安排顺序 解不加任何限制条件 整个排法有种 语文安排在数学之前考 与 数学安排在语文之前考 的排法是相等的 所以语文安排在数学之前考的排法共有种 结论4对等法 在有些题目中 它的限制条件的肯定与否定是对等的 各占全体的二分之一 在求解中只要求出全体 就可以得到所求 分析对于任何一个排列问题 就其中的两个元素来讲的话 他们的排列顺序只有两种情况 并且在整个排列中 他们出现的机会是均等的 因此要求其中的某一种情况 能够得到全体 那么问题就可以解决了 并且也避免了问题的复杂性 例5某个班级共有43位同学 从中任抽5人 正 副班长 团支部书记至少有一人在内的抽法有多少种 解43人中任抽5人的