具体数学毕业论文外文翻译

《具体数学毕业论文外文翻译》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科生毕业论文（设计）翻译ConcreteMathematicsR.L.Graham,D.E.Knuth,0.Patashnik《ConcreteMathematics》，1.3THEJOSEPHUSPROBLEMR.L.Graham,D.E.Knuth,O.PatashnikSixthprinting,PrintedintheUnitedStatesofAmerica1989byAddison-WesleyPublishingCompany,Reference8-16pages具体数学R丄.格雷厄姆，D

2、.E.克努特，O.帕塔希尼克《具体数学》，1.3,约瑟夫环问题R丄.格雷厄姆，D.E.克努特，O.帕塔希尼克第一版第六次印刷于美国，韦斯利出版公司，1989年，引用8-16页1.递归问题本章主要研究三个样本问题，这三个问题给出了递归问题的感性知识.它们有两个共同特点：即都是数学家们一直研究的问题;它们的解都用丫递归的概念，按照递归概念，每个问题解都依赖于相同的问题的若干个较小场合的解.2.约瑟夫环问题我们最后一个例子是一个以FlaviusJosephus命名的么老的问题变形，他是第一世纪一位著名的历史学家

3、.据传说，如果没有Josephus的数学天赋，他就不可能活下来然后成为著名的学者，当时在犹太罗马战争中，他是被困在一个山洞中的41个犹太叛军其中一人，这些叛军宁死不屈，都决定在罗马人俘虏他们之前自刎，他们站成一圈，从1开始，依次杀掉编号是3的倍数的那个人，直到一个人也不剩.但在这些叛军中Josephus和他的同伴觉得这么做没有意义，所以他就快速的计算出他和他的朋友应该站在这个圈的哪个位置.在这个变形的问题屮，我们以〃个人开始，从1到n编号围成一圈，每次消灭第二个人一直到只剩下一个人.例如，在这里我们以设n

4、=10开始.这时的消灭顺序为2,4,6,8,10,3,7,1，9.所以编号是5的人活了来.这个问题:就是定位了最后活下来的那个人的数字我们刚刚看到是J(10)=5的情况.我们可能会推测当是偶数的时候J(A2)=而且当n=2的时候结论同样验证了假设：J(2)二1.但是另外一些数字比较小的情况告诉我们当n=4，〃=6的时候这个假设是错误的.于是我们又冋到了起点3上我们尝试着来个更好的猜测.看起来总是奇数.这个现象的原因是：围成的圈的第一轮消灭了所有编号是偶数的人.之后我们乂回到了与我们开始时候类似情形，除了人

5、数只有原来一半，而且他们的编号也改变了.所以，让我们假设最开始有2〃个人，在第一轮消火结束后，我们剩下而且编号3将是下一个出局的.这个就像是以77个人开始的情况了，除了每个人的编号变为两倍减一.就是，7(2n)=27(zi)-1;当"21:现在我们可以快速的去计算一下当n比较大的时候的那个值,例如，我们知道7(10)=5,所1^7(20)=27(10)-1=25-1=9：同样知J(40)=17，从而我们可以推算出A52，=2剩+1但是,奇数的情况是怎么样的呢？当有2«+1个人的吋候，编号是1的那人会在第2

6、/r个人出局后紧接就会出局,然后，我们剩下我们再次获得形如n个人的情况，但是这次他们的编号变为两倍加一.所以J(2m+1)=2J(…+1;当，2之1;与等式J(1)=1组合，我们得到一个定义J的所有取值递推式：

7、找一个闭合形式的公式，因为那样会更加快速和有意义.用我们的递归式，可以很快地建造一张较小取值的表.我们可以通过这张表看出模式并猜出结果，n12345678910111213141516J(n)1131357135791113151从上我们可以以2的幂分组(通过表中的竖线)；在每组的开始，总是1,而iL在一组内以2递增.所以，如果把写成形如h=的公式，当是不超过Z2的2的最大次幂，且1是剩余的数.这样我们的递归式的解法是J(r^L)=2L-^}^m>OELO

8、1,那么余下的数1=«-2W满足不等式0^<2m+1-2