剁树枝和组合数学初步研究

《剁树枝和组合数学初步研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、剁树枝问题摘要有一根正整数单位长树枝，要剁成一定长的短树枝，在剁的过程中可以重叠，问如何剁次数最少？这样的问题被称为剁树枝问题。剁树枝问题是许多实际问题的一个模型，有着广泛的应用。本课题的任务是提供一般的方法使剁的次数最少。采用例举、分析、归纳、证明的流程，给出了剁树枝问题最少次数的递推关系和具体表达式，并对其进行了证明。关键词初等数论；组合数学；递归；数学归纳法AbstractSupposethereisapositiveintegerunitslongbranches,tochopthemintoacertain

2、lengthofshortbranches.Duringthecuttingprocessoverlapisallowed,thenhowmanytimesisneededatleast?Thisproblemisknownascuttingthetreeproblem.Thecuttingbranches-problemisamodelformanypracticalproblems,withawiderangeofapplications.Basedontheideaofdynamicprogramming,th

3、erecursionformulaoftheleastnumberofmovementsnecessaryforthisproblemispresented.Thedirectformulaoftheleastnumberofmovementsnecessaryforthisproblemisgivenandprovedbytriplemathematicalinductionandpurecombinatorics.Keywordsnumbertheory；combinatorialmathematics；recu

4、rsive;mathematical-18-剁树枝问题目录摘要……………………………………………………………………………2第一章．绪论……………………………………………………………41.1剁树枝问题的简介…………………………………………………41.2剁树枝问题的研究意义及主要方法……………………………4第二章．主要理论：递归关系……………………………………………5第三章．推导过程…………………………………………………………63.1剁成1分米长的短树枝的情况…………………………………63.2剁成2或3分米长的短树枝的情

5、况…………………………9第四章．结论………………………………………………………………13致谢…………………………………………………………………………14参考文献……………………………………………………………………15附录：外文参考文献………………………………………………………16参考文献翻译………………………………………………………………18-18-剁树枝问题第一章.绪论1.1剁树枝问题的简介有一根正整数单位长树枝，要剁成一定长的短树枝，在剁的过程中可以重叠，问如何剁次数最少？这样的问题被称为剁树枝问题。例如：长为4

6、分米的树枝要剁成1分米长的短树枝，先剁成两个2分米长度的树枝，再重叠剁成四个1分米的长度的短树枝，这样剁的次数最少，为两次。又如，长为9分米的树枝要剁成2分米或3分米长的短树枝最少次数是两次。剁树枝问题是许多实际问题的一个模型，有着广泛的应用。本课题的任务是提供一般的方法使剁的次数最少。1.2剁树枝问题的研究意义及主要方法本课题是主要研究剁树枝这样一个数学模型的一般性解决方法，涉及数论和组合数学知识，为日常生产生活、以及数学中类似问题的解决提供模型和参考。本课题的研究主要将涉及初等数论、组合数学等方面的知识，尤其是组

7、合数学中的递推关系，将在本课题的研究中起到重要的作用。力图通过研究任意正整数长度的树枝分别剁成1分米，2或3分米两种情况的最少次数的情况，由其归纳出普遍适用的函数关系式，并通过验证、证明，归纳出最终的结论。-18-剁树枝问题第二章主要理论：递归关系　在组合数学中，递归关系是求解计数问题的重要方法。一般地说，当时，若数列满足(h(n))=F(h(n-1),h(n-2),…,h(n-k))（*）（这里F是k元函数）则称式（*）为这数列的递推关系（或递归关系）。而满足递推关系（*）的数列称为这递推关系的解。当这数列的初始值

8、h(0),h(1),…,h()给定时，从式（*）可依次计算出,….从而就确定了这数列，也就是可以计算出这数列的每一项。有时还能得到这数列的通项公式。-18-剁树枝问题第三章.推导过程3.1剁成1分米长的短树枝的情况（为书写方便，所有单位dm均忽略不写）：设n为树枝长度（nZ*），f(n)为最少剁的次数。例举n[1,50]的情形。如：当n=1时，