新约瑟夫游戏(josephus)

新约瑟夫游戏(josephus)

【问题描述】
你一定听说过经典的“约瑟夫”问题吧!现在我们组织一个皆大欢喜的新游戏:假设 n 个人站成一圈,从第 1 人开始交替的去掉游戏者,但只是暂时去掉(例如,首先去掉 2),直到最后剩下唯一的幸存者为止。幸存者选出后,所有比幸存者号码高的人每人将得到 1 块钱,并且永久性地离开,其余剩下的人将重复以上过程,比幸存者号码高的人每人将得到1 块钱后离开。一旦经过这样的过程后,人数不再减少,最后剩下的那些人将得到2 块钱。请你计算一下组织者一共要付出多少钱?

图 9-4-5 新约瑟夫游戏
如图 9-4-5 所示,第一轮有 5 人,幸存者是 3,所以 4、5 得到 1 块钱后离
开,下一轮幸存者仍然是 3,因此没有人离开,所以每人得到 2 块钱,总共要付
出 2+2*3=8 块钱。
【输入格式】
一行一个整数 n,不超过 32767。
【输出格式】
一行一个整数,不超过 65535,表示总共要付出多少钱。
【输入样例】
10
【输出样例】
13

信息

ID
1670
难度
10
分类
(无)
标签
递交数
1
已通过
0
通过率
0%
被复制
2
上传者