《剁树枝问题数学与应用数学毕业论文(剁树枝问题组合数学初等数论方向》由会员分享，可在线阅读，更多相关《剁树枝问题数学与应用数学毕业论文(剁树枝问题组合数学初等数论方向（18页珍藏版）》请在金锄头文库上搜索。
1、剁树枝问题剁树枝问题摘要摘要有一根正整数单位长树枝，要剁成一定长的短树枝，在剁的过程中可以重叠，问如何剁次数最少？这样的问题被称为剁树枝问题。剁树枝问题是许多实际问题的一个模型，有着广泛的应用。本课题的任务是提供一般的方法使剁的次数最少。采用例举、分析、归纳、证明的流程，给出了剁树枝问题最少次数的递推关系和具体表达式，并对其进行了证明。关键词关键词 初等数论；组合数学；递归；数学归纳法AbstractAbstractSuppose there is a positive integer units long branches, to chop them into a certain lengt
2、h of short branches. During the cutting process overlap is allowed, then how many times is needed at least? This problem is known as cutting the tree problem. The cutting branches-problem is a model for many practical problems, with a wide range of applications. Based on the idea of dynamic programm
3、ing, the recursion formula of the least number of movements necessary for this problem is presented. The direct formula of the least number of movements necessary for this problem is given and proved by triple mathematical induction and pure combinatorics.KeyKey wordswords number theory；combinatoria
4、l mathematics；recursive; mathematical目录目录摘要 2第一章绪论41.1 剁树枝问题的简介 41.2 剁树枝问题的研究意义及主要方法 4第二章主要理论：递归关系5第三章推导过程 63.1 剁成 1 分米长的短树枝的情况63.2 剁成 2 或 3 分米长的短树枝的情况9第四章结论 13致谢 14参考文献 15附录：外文参考文献 16参考文献翻译 18- 3 -第一章第一章. .绪论绪论1.11.1 剁树枝问题的简介剁树枝问题的简介有一根正整数单位长树枝，要剁成一定长的短树枝，在剁的过程中可以重叠，问如何剁次数最少？这样的问题被称为剁树枝问题。例如：长为 4 分
5、米的树枝要剁成 1 分米长的短树枝，先剁成两个 2 分米长度的树枝，再重叠剁成四个 1 分米的长度的短树枝，这样剁的次数最少，为两次。又如，长为 9 分米的树枝要剁成 2 分米或 3分米长的短树枝最少次数是两次。剁树枝问题是许多实际问题的一个模型，有着广泛的应用。本课题的任务是提供一般的方法使剁的次数最少。1.21.2 剁树枝问题的研究意义及主要方法剁树枝问题的研究意义及主要方法本课题是主要研究剁树枝这样一个数学模型的一般性解决方法，涉及数论和组合数学知识，为日常生产生活、以及数学中类似问题的解决提供模型和参考。本课题的研究主要将涉及初等数论、组合数学等方面的知识，尤其是组合数学中的递推关系，
6、将在本课题的研究中起到重要的作用。力图通过研究任意正整数长度的树枝分别剁成 1 分米，2 或 3 分米两种情况的最少次数的情况，由其归纳出普遍适用的函数关系式，并通过验证、证明，归纳出最终的结论。第二章第二章 主要理论：递归关系主要理论：递归关系在组合数学中，递归关系是求解计数问题的重要方法。一般地说，当时，若数列01nnk 0( ( )( (0), (1),., ( ),.)nf nhhh n满足(h(n)=F(h(n-1),h(n-2),h(n-k) （*）（这里 F 是 k 元函数）则称式（*）为这数列的递推关系递推关系（或递归关系递归关系） 。而满足递推关系（*）的数列称为这递推关系的
7、解。当这数列的初始值h(0),h(1),h()0n给定时，从式（*）可依次计算出,. 从而就确定了这数列，00(1), (2)h nh n也就是可以计算出这数列的每一项。有时还能得到这数列的通项公式。第三章第三章. .推导过程推导过程3.13.1 剁成剁成 1 1 分米长的短树枝的情况分米长的短树枝的情况（为书写方便，所有单位 dm 均忽略不写）：设n为树枝长度（nZ*），f(n)为最少剁的次数。例举n 1,50的情形。如：当n =1时，f(1)=0.当n=2 时，剁一次，f(2)=1.n=3, f(3)=2. n=16 时，先在中间剁一次为 2 个 8（记为 82） ，重叠在中间成 4 个
8、4（422） ，如此往复，依次可得：16=82=422=2222=12222，共剁 4 次,f(16)=4n=17,先剁成 8+9，重叠后剁成(4+4)+(4+5)，重叠后剁成 27+3，- 5 -再次重叠剁成 115+2，最后将 2 剁成两个 1，共计 5 次。n=50, 50=252=(12+13)2=(63+7)2=(37+4)2=(29+17)2=150,由等号的个数可以看出f(50)=6.结果如下表所列：n12345f(n)01223n678910f(n)33344n1112131415f(n)44444n1617181920f(n)45555n2122232425f(n)55555
9、n2627282930f(n)55555n3132333435f(n)55666n3637383940f(n)66666n4142434445f(n)66666n4647484950f(n)66666通过以上表格和在分析得到此表格的过程，我们可以得到如下发现：1. f(n) 随着 n 的增大而增大或不变，即 f(m) f(n),m n.2. f(n) 在以下位置之后值发生改变：f(1)=0, f(2)=1,f(4)=2, f(8)=3, f(16)=4, f(32)=5. 不难发现这样的规律：f()= n，f(+ t )= n+1 (1 t 0时，由引理1.2，有f()=f (2)=f()+1
10、=f()+2=f()+n=n.2n12n12n22n02得证。【二】再考虑 t0 ，即1t 2的情形。【一】先考虑 t=0 的情形：n=3时，g(3)=g(3)=0 .结论成立。02n3时，由引理2.2，有g(3)=g(32)=g(3)+1=g(3)+2=g(3)+n=n .2n12n12n22n02- 11 -结论成立。【二】再考虑 t0 ，即1t 3的情形：2nn1 时，33+t3，故由引理 1.1，2n2n12n有 g(3) g(3+t) g(3) （2）2n2n12n而由引理 2.3: g(2n-1)=g(2n) n3， 故g(3+1)=g(3+2)=g2(3+1)=g(3+1)+1=
11、g(3+2)2n2n12n12n12n+1=g(3+1)+2=g(3+1)+n=g(4)+n=n+1 .22n2n n又 g(3)=n , g(3+1)=n+1 , g(3)=n+1,由（2）式及引理 2.1，2n2n12n有 n+1= g(3+1) g(3+t) g(3)=n+12n2n12n得 g(3+t)=n+1, 1t 3 . 得证。2n2n第四章第四章 结论结论通过本次课题的研究，得到了对于剁树枝问题的一些基本结论和定理，也为以后此类问题的研究提供依据。在研究的过程中发现，这类问题是数论、组合数学在现实生活中较为具体的实例，且趣味性较强。但是虽然不是难题，此类问题的研究还是具有非常重
12、要的意义的，特别是对于数学与应用数学师范类的本科生，未来的职业生涯将主要从事初等数学的教学和研究，这类与初等数学联系较为密切的问题，对于以后在中小学生的奥数及趣味数学、数学建模中的应用，有着尤为重要的作用和帮助。致谢致谢致 谢:本论文是在 XXX 老师的悉心指导下完成的。X 老师渊博的学识给与了我极大的帮助，使我在论文的编写过程中受益匪浅，不但提高了科研水平，而且还提高了科技论文的写作水平。通过论文的写作，使我对以前学的课本知识能够有效地运用到实践当中，使理论与实践得到很好的结合，对于此类实际问题的解决，也有了更强的兴趣和信心。在此论文完成之际，谨向 X 老师表示由衷的感谢。与此同时，向在我的
13、本科生学习当中给与了极大帮助和支持的我的家人及XXXX 大学 XXXX 学院的老师和领导表示感谢，谢谢你们的辛劳！最后祝所有关心过我的同学、朋友、导师、领导、家人身体健康、工作顺利、好人一生平安。- 13 -XXXXXX参考文献参考文献1越民义 组合优化导论 浙江科学技术出版社 20012孙淑玲、许胤龙 组合数学引论 中国科学技术大学出版社 第二版 20103李文林 王元论哥德巴赫猜想 山东教育出版社 19994加R.K.盖伊 数论中未解决的问题 科学出版社 第三版 20075李凡长 编著组合理论及其应用清华大学出版社 20056美 Fred S. Roberts, Barry Tesman
14、应用组合数学 机械工业出版社 20077Soederstroem.T.， 递推辨识的理论与实践科学出版社 19898李乔组合学讲义高等教育出版社 20089蔡锁章 主编数学建模：原理与方法海洋出版社 200010魏有德 递推法 四川教育出版社 198911陈永明 递推式 上海科学技术出版社 198912华罗庚 华罗庚文集 数论卷科学出版社 201013美Joseph H.Silverman 数论概论机械工业出版社 200814英Burn.R.P 数论入门高等教育出版社 199015丁石孙 主编 归纳递推无字证明坐标复数北京大学出版社 1995附录：外文参考文献附录：外文参考文献Proof by inductionSince number theory is largely concerned with the positive integers, some of its theorems are of form, “such-and-such is true for all positive integers n.” Propositions likes this can often be proved by mathematical induction (or induction for short we will n
