数学与程序设计.ppt

上传人:p** 文档编号:180331 上传时间:2023-03-27 格式:PPT 页数:29 大小:1.17MB
下载 相关 举报
数学与程序设计.ppt_第1页
第1页 / 共29页
数学与程序设计.ppt_第2页
第2页 / 共29页
数学与程序设计.ppt_第3页
第3页 / 共29页
数学与程序设计.ppt_第4页
第4页 / 共29页
数学与程序设计.ppt_第5页
第5页 / 共29页
数学与程序设计.ppt_第6页
第6页 / 共29页
数学与程序设计.ppt_第7页
第7页 / 共29页
数学与程序设计.ppt_第8页
第8页 / 共29页
数学与程序设计.ppt_第9页
第9页 / 共29页
数学与程序设计.ppt_第10页
第10页 / 共29页
亲,该文档总共29页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数学与程序设计.ppt》由会员分享,可在线阅读,更多相关《数学与程序设计.ppt(29页珍藏版)》请在第壹文秘上搜索。

1、数学与程序设计数学与程序设计引例 问题描述问题描述有一个自然数有一个自然数n,在他的首尾两,在他的首尾两端添上一个端添上一个1,由于,由于1是自然数之首,便形是自然数之首,便形成一个成一个“两头蛇数两头蛇数”1N1。如果。如果“两头蛇两头蛇”数数1N1正好是原自然数正好是原自然数N的的k倍,问倍,问n是多少?是多少? 现在请你编程解决。现在请你编程解决。两头蛇数100110.1.101000.1.10100.11.knNnkNnkNnk程序设计中的数学 数论 组合数学 母函数 计算几何 程序设计中的数学 基本数论 组合数学 计算几何 容斥原理 母函数 初等数论 整除 同余 素数指数取余 输入整

2、数输入整数m,n,k,求,求mn mod k的值。其中的值。其中m,n,k为为自然数(自然数(m,n在长整形范围内,在长整形范围内,k=46340)。)。ab (mod m)cd (mod m)acbd(mod m)次数压缩?次数压缩?同余同余 穷举穷举 (m mod k)n xkxxxn.321389 mod 7 89=64+16+8+1 313 (mod 7) 3232 (mod 7)2 (mod 7) 34(32)2 (mod 7)22 (mod 7)4 38(34)2 (mod 7)42 (mod 7)2 316(38)2 (mod 7)22 (mod 7)4 332(316)2 (m

3、od 7)42 (mod 7)2 364(332)2 (mod 7)22 (mod 7)4 389(364)(316)(38)(31) (mod 7) 5 (mod 7) 质多项式 给定多项式 f(x)=an*xn an-1*xn-1 . a0*x0,如果an0 ,我们称f(x)是一个n次多项式。 类似自然数里质数的概念,也可以给出“质多项式”概念。给定多项式f(x),如果找不到次数至少为1的多项式g(x)和h(x)满足f(x)=g(x) * h(x),我们称f(x)为质多项式 。 为了简化起见,我们规定多项式的系数只能取两个数:0或1。并且重新定义在0,1上的加法和乘法如下: 0+00 0+

4、11 1+01 1+10 0*00 0*10 1*00 1*11 如:(x2+x1)(x1+1)=x3+x2+x2+x1=x3+x1 对于给定的正整数k,求出次数为k的质多项式。 如:输入 1 输出 x+1 输入 5 输出 x5+x2+1 质多项式解题思路 寻找质数 + 穷举 穷举k次的多项式,检验能否被已经找到的质多项式整除,若不能则本身也是质多项式。 多项式除法 * 0+00 0+11 1+01 1+10 0*00 0*10 1*00 1*11 加法:XOR 乘法:正常 减法:XOR 除法:正常x3+x 、 x+1 、 x2+x程序设计中的数学 基本数论 组合数学 计算几何 容斥原理 母函

5、数 平行四边形的个数平行四边形的个数 把三角形把三角形ABC的三边各的三边各n等分,过各等分点作等分,过各等分点作各边的平行线,将三角形各边的平行线,将三角形ABC分割成一些小平分割成一些小平行四边形,计算这些小平行四边形的个数。行四边形,计算这些小平行四边形的个数。就一类平行四边形进行讨论41nC31nC42nC方程的解方程的解 已知方程 x1+x2+x3+xm=n 其中x1=a1,x2=a2,xm=am 且miian1 求方程的非负整数解的组数 令x1= x1-a1, x2=x2-a2, xm= xm-am x1 + x2 + xm= P11mmpC程序设计中的数学 基本数论 组合数学 计

6、算几何 容斥原理 母函数 蜂族的旅行 和其他昆虫不同,为了不至于迷路,蜜蜂在蜂巢(紧密连接的正六边形)中行走必须遵守一定的路线。把一个正方形的中心看作原点。如果一只蜜蜂要从A(x1,y1)点飞到B(x2,y2)点,且AB不在同一六边形的话,那么它必须按照蜂族的飞行规则,首先飞到包含A点的正六边形的中心,然后每次都只能从一个正六边形的中心飞到和它相邻的六边形中心,直到它飞到包含B点的正六边形的中心为止,然后再飞往B点。 知道正六边形的边长d与A、B点的坐标,算出蜜蜂的飞行距离。(A、B都不会刚好落在某个六边形的边上)。 样例1.0 -3.2 2.2 3.3 07.737蜂族的旅行 A、B在同一六

7、边形,直接计算直线距离 如何判断两点在同一正六边形?)3,0(kd pdypdx2323)233,23(pdkdpd12p3dy32233213232),(或或pdykdxdxpyx确定所在的六边形并计算到顶点的距离从AB经过的六边形个数程序设计中的数学 基本数论 组合数学 计算几何 容斥原理 母函数 小虫问题 在一个7*7的方格中,每个小方格内都有一条小虫,约定在同一个时刻方格中的小虫必须向周围(上下左右4个方向)爬一格。 证明:在爬了一格之后,至少有一个小方格是空的。被绘坏的玉米地 “哈姆,外星人又在那了!”。埃塞和哈姆他们的玉米地是长方形的。每年在丰收之前,他们的玉米地都会很奇怪的遭到毁

8、坏(据埃塞说是外星人干的)。所有破坏的地方都是以 1 米为半径的圆米为半径的圆。哈姆发现,如果玉米地上建立一个适当的直角坐标系的话,那些圆心的坐标将都为整数圆心的坐标将都为整数。万幸的是,埃塞和哈姆有玉米保险,但必须把损坏的面积统计出来。程序设计中的数学 基本数论 组合数学 计算几何 容斥原理 母函数 质数分解问题 任何大于 1 的自然数 n,都可以写成若干个大于等于 2 ,且小于等于 n 的质数之和表达式(包括只有一个数构成的和表达式的情况),并且可能有不止一种质数和的形式。例如9 的质数和表达式就有四种本质不同的形式: 9 = 2+2+5 = 2+2+2+3 = 3+3+3 = 2+7 。

9、 自然数 n (2n200)可以写成多少种本质不同的质数和表达式。 母函数 给定数列a0,a1,an,构造一函数 F(x)=a0f0(x)+a1f1(x)+anfn(x)+ 称F(x)为数列a0,a1,an,的母函数, 序列f0(x),f1(x),fn(x),称为标志函数。 F(x)=a0 x0+a1x1+anxn+ 普通型母函数 设从n元集合S=a0,a1,an中取个元素的组合为bk,若限定元素ai出现的次数不超过mi,则该组合数系列的母函数为:nimmmix10砝码称重 有重量为1,3,5克的砝码各两个,问 (1)可以称出多少种不同重量的物品? (2)若要称出重量为7克的物品,所使用的砝码有多少种本质不同的情况? G(x)=(1+x+x2)(1+x3+x6)(1+x5+x10)=1+x+x2+x3+x4+2x5+2x6+2x7+2x8+x9+2x10+2x11+2x12+2x13+x14+x15+x16+x17+x18 (1)19 (2)2

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > C/C++资料

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!