奇数位丢弃

思路：数学推导

以 n = 37 为例，即 0 ~ 37

• 第一次删除：time = 1,开始位置 base = 0,每次位置新增为 up=2，删除的值为：
  0 2 4 6 8 10 12 14 16 18 20 22 24 26 28...
• 第二次删除：time = 2,开始位置 base = 1,每次位置新增为 up = 4，删除的值为：
  1 5 9 13 17 21 25 29...
• 第三次删除：time = 3,开始位置 base = 3,每次位置新增 up = 8,删除的值为：
  3 11 19 27 35
  .....

import java.util.Scanner;

/**
 * @author GJXAIOU
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int inputValue = scanner.nextInt();
            if (inputValue == 0) {
                System.out.println(0);
            }
            int[] values = new int[inputValue + 1];
            for (int i = 0; i < values.length; i++) {
                values[i] = i;
            }

            // time 表示第几次运行删除
            int time = 1;
            // 每次删除的第一个数
            int base = 0;
            // 每次删除时候递增的间隔
            int up = 2;
            // 还有多少值没有检查替换
            int left = values.length;
            while (left > 1) {
                for (int i = base; i < values.length; i += up) {
                    values[i] = 0;
                    left--;
                }
                base = (int) (base + Math.pow(2, time - 1));
                // 进行下一次
                time++;
                // 每次运行删除间隔都是 2 的倍数
                up *= 2;
            }

            for (int i = 0; i < values.length; i++) {
                if (values[i] != 0) {
                    System.out.println(values[i]);
                }
            }
        }
    }
}

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int times=1,begin=0;
        while(n!=1){
            begin=begin+pow(2,(times-1));
            n/=2;
            times++;
        }
        cout<<begin<<endl;
    }
    return 0;
}
/*每次只需记录第一个记录，由于数字之间的间隔每分一次增大一倍，可以由公式begin=begin+pow(2,(times-1)); 计算出下一个第一位数的值*/

import java.util.Scanner;
// 找规律每次删除后的第一个数为2^times  - 1然后算出 times 即可
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int total = n + 1;
            int times = 0;
            while (total != 1) {
                total /= 2;
                times++;
            }
            System.out.println(String.format("%.0f", Math.pow(2, times) - 1));
        }


    }
}

n = int(input())
b = 1
while True:
    if b <= n + 1:  
        b <<= 1
    else:
        b = (b >> 1) - 1
        print(b)
        break

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            ArrayList<Integer> array=new ArrayList<Integer>();
            for(int i=0;i<n;i++)
                array.add(i);
                int i=0;
            while(array.size()>1){
                array.remove(i);
                i++;
                if(i>=array.size())
                    i=0;
            }
            System.out.println(array.get(0));
        }
    }
} 

import java.util.Scanner;

public class DiscardOdd {
    /**
     * 思路: 序列是从 0 到 n-1 的 n 个数, 但是序列的索引是从 1 开始的;<br>
     * 假如 n = 10, 那么序列的索引为: 1, 2, 3, ...10;<br>
     * 第一次被淘汰掉的索引为: 1, 3, 5,7, 9; 这些索引满足的条件为: index%2 != 0;<br>
     * 剩下来的序列索引为: 2, 4, 6, 8, 10; 在这些索引中满足奇数条件: index%4 != 0 的索引为: 2, 6, 10;<br>
     * 所以这些索引对应的值将会被在第二轮被淘汰掉;<br>
     * 剩下类的索引为: 4, 8;其中满足奇数条件: index%8 !=0 的索引为: 8; 所以最后剩下来的索引就是 8;<br>
     * 而索引 8 对应的值为 7, 所以最后剩下来的值为 7.<br>
     * 
     * 由以上推理可以得知, 最后剩下来的那个索引满足条件: index%2^n != 0, 其中 2^n 为小于 n 里面的最大一个.<br>
     * 由于索引是从 1 开始的, 而序列的值是从 0 开始的, 所以最后的结果应该为 index - 1;<br>
     * 
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int base = (int) Math.floor(Math.log(n) / Math.log(2));
            System.out.println((1 << base) - 1);
        }
        scanner.close();
    }
}

package NiuKeBianMa;
//有些像那个约瑟夫环的题目
//重复置零的操作
import java.util.Scanner;

public class Main84 {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner scanner = new Scanner(System.in);
    while (scanner.hasNext()) {
        int n = scanner.nextInt();
        int i = 1;
        int count = 1;
        while (Math.pow(2, i + 1) < n) {

            count += Math.pow(2, i);
            i = i + 1;
        }
        System.out.println(count);
    }
}

}

#include <iostream>
#include <list>

using namespace std;

int main()
{
	int n;
	while (cin >> n)
	{
		list<int> nums;
		for (int i = 0; i <= n; ++i) nums.emplace_back(i);
		while (nums.size() > 1)
		{
			int count = 0;
			for (auto p = nums.begin(); p != nums.end();)
			{
				++count;
				if (count & 1) p = nums.erase(p);
				else ++p;
			}
		}

		cout << *nums.begin() << endl;
	}

	return 0;
}

from math import log as f
try:
    while 1:
        print (1 << int(f(input(), 2))) - 1
except:
    pass

//总结规律
#include <iostream>
using namespace std;
int main(){
    int N;
    while(cin>>N){
        int count=1,n=N+1;
        while(n>1){
            n>>=1;
            count<<=1;
        }
        cout<<count-1<<endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main{
    static class Node{
		int index;
		Node next;
	}
	public static void main(String[] args) {
		Scanner in  = new Scanner(System.in);
		while(in.hasNext()){
			int n = in.nextInt();
			Node root = new Node();
			root.index = 0;
			Node temp = root;
			for(int i = 1;i<=n;i++){
				Node node = new Node();
				node.index = i;
				temp.next = node;
				temp = node;
			}
			temp = root.next;//删除第一个
			root = temp;
			while(root.next!=null){
                if(temp==null||temp.next==null){
					temp = root.next;//删除第一个
					root = temp;
				}else{
                    Node nextTemp = temp.next.next;
                    temp.next = nextTemp;
                    temp = nextTemp;
                }
				
			}
			System.out.println(root.index);
			
		}
	}
}

#include <cstdio>

int main()
{
    int n;
    while(scanf("%d", &n) != EOF){
		int b = 1;
        while(b <= n + 1){
            b <<= 1;
        }
        printf("%d\n", (b >> 1) - 1);
    }
    return 0;
} 

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			List<Integer> list = new ArrayList<Integer>();
			for (int i = 0; i <= n; i ++ )
				list.add(i);
			while (list.size() != 1) {
				// 从0开始list移除一次,i再加一次,i始终指向奇数位
				for (int i = 0; i < list.size(); i = i + 1)
					list.remove(i);
			}
			System.out.println(list.get(0));
		}
	}
}

python常规解法：

while True:
    try:
        a=list(range(int(input())+1))
        while len(a)>1:
            a=(list(filter(lambda c: a.index(c) % 2 == 1, a)))
        print(a[0])
    except:
        break

//常规做法，比较直观，用数组a每次循环清楚记录了每次删除后剩余的元素。
#include<iostream>
using namespace std;
int main(){
    int n,i,a[1001],count;
    while( cin >> n ){
        for(i=0;i<=n;i++)
            a[i] = i;
        count = n+1;
        while( count != 1 ){
            for(i=0;2*i+1<count;i++)
                a[i]  = a[2*i+1];
            count = i;
        }
        cout << a[0] << endl;
    }
}
//特殊思路，每次删除所在数组位置的二进制最右端为0的元素。如0（0）2（10）4（100）
//剩余的元素1（01）3（11）5（101）下一次其位置变成了之前位置左移一次后的
// 1（1） 3（10） 5(10) 然后继续按之前规则删除最右端为0的元素。故原始序列中，谁的//二进制下从右往左数，1最多，则最后删除，因每次删除移位后，最右端仍然为1，会保留
#include<iostream>
using namespace std;
int main(){
    int n;
    while( cin >> n ){
        int b = 1;
        while( b <= n )
            /*b = (b<<1) + 1;//或者 用*/ b = b*2 +1;
        cout << (b>>1) << endl;
    }
}

//m=log2(n+1)位全1组成
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
        {
        int m=log(n+1)/log(2);
        cout<<((1<<m) -1)<<endl;   
    }
    return 0;
}