1496: 【中级考试】谁是带头人

一群n个孩子围成一圈，每个人按顺时针方向从1到n编号，他们需要选出一个带头人，并且决定按以下的方式产生：第1个人留在圆圈上，第2个人离开，第3个人留下，第4个人离开……，如此继续，沿着圆圈每隔一人留下一人，圆圈不断收缩，直到最后圆圈上仅留下一人作为带头人，请你编一个程序，对输入的n，求带头人的编号

输入数据仅有一行包含一个正整数n，n≤10000

输出数据仅有一行包含一个正整数k，表示编号为k的孩子是带头人。

64

1

本题就是数到2出圈的约瑟夫问题，样例中圈上有64人，从1号开始报数，数到2出圈，一圈数下来所有编号为偶数的孩子都出圈了，此时圈上还有32人；接下去还是从1号开始报数，一圈数下来又有16人出圈，圈上还有16人；接下去还是从1号开始报数，一圈数下来又有8人出圈，圈上还有8人；接下去还是从1号开始报数，一圈数下来又有4人出圈，圈上还有4人；接下去还是从1号开始报数，一圈数下来又有2人出圈，圈上还有2人；此时从1号开始报数，另一人报到2出圈，最后圈上只留下1号。