#7475. 【提高】bonbon 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

N 个人在操场上围成一圈,将这N 个人按顺时针方向从1到N编号,然后,从第一个人起,每隔一个人让下一个人离开操场,显然,第一轮过后,具有偶数编号的人都离开了操场。

依次做下去,直到操场上只剩下一个人,记这个人的编号为J(N) ,例如,J(5)=3 ,J(10)=5 ,等等。你的任务是对于键盘输入的N,编一个递归函数求出J(N)。

输入格式

从键盘输入一个正整数N,N不超出长整型数 long int 的范围。

输出格式

输出一个正整数,表示操场上剩下的最后一个人的编号。

样例

样例输入1

10

样例输出1

5

数据范围与提示

如果N为偶数,第一轮过后,具有偶数编号的人都离开了操场,剩下的奇数编号的人还有N/2个,此时还是从第一个人起,每隔一个人让下一个人离开操场,这个问题与原问题本质相同,规模变小了,

所以我们可以用递归的方法来处理,只要将剩下的人重新编号:
1 3 5 7 9 ......第一轮过后剩下的人的编号
1 2 3 4 5 ......对剩下的人重新编号
重新编号后的问题就成了一个N/2个人的问题,它的结果为J(N/2),它与J(N)的关系为J(N)=J(N/2)*2-1,如
样例要求的J(10)=J(5)2-1=32-1=5。

对于N为奇数的情况,你可以参照以上的分析得出相似的结论,最后得出完整的递归式,递归终止条件为J(1)=1。