欢迎来到大分享文库-在线教育资源分享平台 ! | 帮助中心 大分享文库-在线教育资源分享平台
大分享文库-在线教育资源分享平台
全部分类
  • 经济管理 >
    经济管理
    对外贸易 金融银行 财政税收 会计财务 股票投资 人力资源 项目管理 市场营销 企业文化 企业战略 物流管理 工程管理 电子商务 经济学论文 管理学论文
  • 理工学科 >
    理工学科
    计算机设计 机械制造 通讯电子 航空航天 建筑工程 地质水利 交通运营 工学设计 数理学 测绘工程 物理学论文 毕业论文 环境工程论文 工业工程设计 生物技术 汽车工程设计 轮机工程论文 电气自动化设计 电气工程 有机化学 印刷工程 信息管理 安全工程 材料工程
  • 教育文化 >
    教育文化
    广告传媒 思想哲学 语言文化 军事政治 文学外语 心理学 幼儿教育 教育论文 教学课件 小说传记
  • 艺术医学 >
    艺术医学
    艺术论文 医学论文 综合资源 群众路线 公务员考试 婚礼PPT模版 党政PPT模版
  • 企划文书 >
    企划文书
    求职简历 演讲致辞 合同协议 工作计划总结 调研报告文书 调研报告策划 业务推广模板 应用文书 工作报告 微信营销 项目建议书 商业计划书 百事生活 游戏策划 思想汇报 年会策划 一带一路
  • 计算机设计 >
    计算机设计
    JAVA/JSP设计 Android安卓/IOS设 ASP.NET设计 C#设计 ASP设计 PHP设计 VB设计 C/C++设计 VF设计 flash设计 信息技术 QT设计 delphi设计 网络工程设计 其他设计
  • 设计图纸 >
    设计图纸
    CAD设计图纸 通信工程 solidworks模型 ProE模型 土木工程设计 UG模型 catia模型 其他设计模型 采矿工程设计 仿真设计 工业设计
  • 综合资源 >
    综合资源
    港口航道工程 过程装备与控制工程 体育论文 法律论文 公共行政 复习笔记 真题试卷 读后感 炒股资料 可行性研究报告 城市规划 旅游管理 技术规范标准 地理信息系统 行业资料下载 食品工程 消防指挥 社会责任报告 运动健身
  • 专业文献 >
    专业文献
    开题报告 外文翻译 文献综述 任务书 答辩指导 文献资料 实习报告 调查报告 工作报告 论文写作指导 论文答辩PPT模板
  • 首页 大分享文库-在线教育资源分享平台  > 资源分类 > PPT文档下载
     

    余林韵_运用化归思想解决信息学中的数列问题

    • 资源ID:180090       资源大小:3.12MB        全文页数:28页
    • 资源格式: PPT        下载权限:游客/注册会员/VIP会员    下载费用:8
    游客快捷下载 游客一键下载
    会员登录下载
    下载资源需要8

    邮箱/手机:
    温馨提示:
    支付成功后,系统会根据您填写的邮箱或者手机号作为您下次登录的用户名和密码(如填写的是手机,那登陆用户名和密码就是手机号),方便下次登录下载和查询订单;
    特别说明:
    请自助下载,系统不会自动发送文件的哦;
    支付方式: 微信支付    支付宝   
    验证码:   换一换

          加入VIP,免费下载资源
     
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,既可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

    余林韵_运用化归思想解决信息学中的数列问题

    福建省福州市第一中学,余林韵,运用化归思想解决信息学中的数列问题,1、1、1、2、1 1、1、1、2、1 ,走队列喊口号,日常生活中,年份,2006,2007,2008,2009,按某种法则排列着的一列数,,数列,解决数列问题,知识,化归、猜想,化归,就是转化和归结,问题甲,比较容易解决的问题乙,,,化归方法的要素,化归对象 即对什么东西进行化归 化归目标 即化归到何处去 化归途径 即如何进行化归,Dispute Ural 1309,数列Fn满足 其中 给定n,求解Fn。,数据规模 0N108,Dispute Ural 1309,数据规模太大,化归到小规模,,Dispute Ural 1309,分而治之,,,,,,算法一,预处理,求出数列F的所有项 将所有的F100000k保存下来 当给定N的时候,我们可以先找到离N最接近的一项F100000k 简单的递推即可解决,复杂度O100000,,将数据规模继续扩大,,拓展,Dispute Ural 1309,Dispute Ural 1309,算法一不能胜任,108s27777h1157d3年,,黄花菜都凉了,Dispute Ural 1309,算法一分割的太暴力,如何“温柔”一些,再次观察数列,函数gx,y 的特点 gx,y y-1*x5x3-xy3x7y mod 9973 1、所有项y的指数非0即1 2、式子的最后取模了一个质数9973,性质1,把x看作一个常数,整理后可得 gx,yx5-x7y -x5x33x mod 9973 数列Fn是个1阶线性递推数列。 联想计算常系数线性递推数列的第N项可以利用矩阵乘法的方法 调整化归目标看看能否通过合理的分段,将数列变成常系数线性递推数列。,性质2,令M9973 则有常数A,B使得 FkmA*Fk-1mB,,成功化归,其余三道例题,ABS序列(Top Coder SRM 369 - Div 1 - 500 Points) Count(NOI2007) Maximum. Version 2(Ural 1396),Time Limit,总结,数列问题千变万化,化归不是万能的,牢牢抓住问题的本质,认真仔细观察,敢于大胆猜想 富有创新精神,发现数列的美,走向成功,谢谢大家,欢迎提问,性质2的证明,令Uij5-j7 mod M, Vi-j5j33*j mod M, ji mod M 1 Fi1 Ui *FiVi FKM1UKM1*FKMVKM1 mod M FKM2UKM2*FKM1VKM2 mod M FKM3UKM3*FKM2VKM3 mod M FK1MUK1M*FK1M-1VK1M mod M,性质2的证明,FK1MUK1M*FK1M-1VK1M mod M UK1M*UK1M-1*FK1M-2VK1M-1 VK1M mod M UK1M*UK1M-1*FK1M-2UK1M*VK1M-1VK1M mod M,性质2的证明,FK1MA*FKMB mod M Uij5-j7 mod MUiUiM Vi-j5j33*j mod MViViM A,B为定值,计算常系数线性递推数列的第N项,矩阵乘法 两个矩阵A,B,Aai,jn*m,Bbi,jm*t 复杂度ONMT 满足结合律,即,计算常系数线性递推数列的第N项,递推数列 一个数列的连续项之间的关系叫递推关系,由递推关系确定的数列叫递推数列 常系数线性递推数列 由初始值和方程ankFank-1,,an的数列{an}称为k阶递推数列 特别的,当方程形如下式的时候数列{an}称为k阶常系数线性递推数列。 ankc1ank-1c2ank-2ckanfn,这里c1,c2ck为常数,其中ck≠0 如果fn0,那么数列{an}称为k阶常系数齐次线性递推数列。,计算常系数线性递推数列的第N项,以广义Fibonacci数列为例 F1a,F2b,FNFN-1FN-2 观察数列前几项 F3F1F2ab F4F2F3F2aba2b F5F3F4aba2b2a3b 数列的任意一项都是由若干个a与b相加组成的,计算常系数线性递推数列的第N项,用矩阵乘法解决,

    注意事项

    本文(余林韵_运用化归思想解决信息学中的数列问题)为本站会员(海迅科技)主动上传,大分享文库-在线教育资源分享平台 仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即阅读大分享文库-在线教育资源分享平台 的“版权提示”【网址:https://www.west960.com/h-34.html】,按提示上传提交保证函及证明材料,经审查核实后我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们 豫ICP备17044489号-3
    收起
    展开