Question

猫吃老鼠的程序问题，用free pascal的，感激不尽！

一只猫一天可以抓n个老鼠，他吃老鼠时把所有的老鼠排成队，吃掉单数位上的老鼠后，再按现在的排序再吃掉单数位上的老鼠，求当猫抓n个老鼠时第一次排序时的第几只老鼠最后一个被吃掉？用pascal编写出程序。

Answer 1

你这个问题是一个很经典的问题，叫做约瑟夫问题！
而你这道题目的规模不知道可以去到多大，如果是比较小的话，可以直接采用模拟的方法，
可是当数据量达到n=10^100的时候，就明显会TLE了。
所以这道题目最好的方法就是LS的方法了，找到它的规律，至于怎么找到它的规律的，这里有一个范例，当然，找规律的方法有很多种，你也可以直接推到！不必一字一句都按它的来！

约瑟夫问题10e100版(from vijios)
　　描述 Description
　　n个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。
　　输入格式 Input Format
　　一个正整数n，表示人的个数。输入数据保证数字n不超过100位。
　　输出格式 Output Format
　　一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。
　　样例输入 Sample Input
　　9
　　样例输出 Sample Output
　　3
　　时间限制 Time Limitation
　　各个测试点1s
　　注释 Hint
　　样例说明
　　当n=9时，退出圈子的人的编号依次为：
　　2 4 6 8 1 5 9 7
　　最后剩下的人编号为3
　　初见这道题，可能会想到模拟。可是数据实在太大啦！！
　　我们先拿手来算，可知n分别为1，2，3，4，5，6，7，8...时的结果是1，1，3，1，3，5，7，1...
　　有如下规律：从1到下一个1为一组，每一组中都是从1开始递增的奇数，且每组元素的个数分别为1，2，4...
　　这样就好弄了！！
　　大体思路如下：
　　①read(a)
　　②b:=1,c:=1{b为某一组的元素个数，c为现在所加到的数}
　　③while c<a do (b:=b*2,c:=b+c){超过目标时停止加数}
　　⑥c:=c-b{退到前一组}
　　⑦x:=a-c{算出目标为所在组的第几个元素}
　　⑧ans:=x*2-1{求出该元素}
　　⑨write(ans)

同理，你这里是报的单数，思路是一样的，找到它的规律后就明显知道它是2^x(其中x尽量大)，当然，这道题如果是大牛的话，一看就知道答案，因为你每次都去一半，那么反过来就是求一个不断加倍的数，那么也就是最大的2^x了！

Answer 2

一定剩下2^x号的，其中x尽量大：
var n,x:word;
begin
readln(n);
x:=1;
while x<n do x:=2*x;
writeln(x div 2);
end.

追问

程序看懂了，求原理

Answer 3

您想在自己的网站上展示百度“知道”上的问答吗？来获取免费代码吧！

如要投诉或提出意见建议，
请到百度知道投诉吧反馈。

Answer 4

用递归把，每次除二，得到最后数的位置，再乘回去

Answer 5

好像做过，现在忘了