首页 > 试题广场 >

奇数位丢弃

[编程题]奇数位丢弃

热度指数：14114 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一个由 0..n 的所有数按升序组成的序列，我们要进行一些筛选，每次我们丢弃去当前所有数字中第奇数位个的数。重复这一过程直到最后剩下一个数。请求出最后剩下的数字。

数据范围： $1 \le n \le 1000 \$ ，本题有多组输入

输入描述:

每组数据一行一个数字，为题目中的n(n小于等于1000)。

输出描述:

一行输出最后剩下的数字。

示例1

输入

输出

算法知识视频讲解

Java

京东内推君

思路：数学推导

以 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]);
                }
            }
        }
    }
}

发表于 2020-06-23 16:33:19 回复(0)

OnePiece~~

#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)); 计算出下一个第一位数的值*/

编辑于 2016-08-28 13:29:09 回复(2)

C/C++

邂逅龙

#include<iostream>
using namespace std;
int main()
{
	int n;
	while(cin>>n)
	{
		int b=1;
		while(b<=n) b=2*b+1;
		cout<<(b/2)<<endl;
	}
	return 0;
}

看完大佬们的想法，也就是寻找0到n的二进制情况下1的个数最多的那个数嘞

#include<iostream>
using namespace std;
int main()
{
	int n;
	while(cin>>n)
	{
		int b=1;
		while(b<=n) b=(b<<1)+1;//b=2*b+1;
		cout<<(b>>1)<<endl;
	}
	return 0;
}

或者，采用数学公式的方法：

#include<bits/stdc++.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; 
}

编辑于 2020-08-30 13:10:15 回复(0)

李启辰

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){
int n;
while(cin>>n){
vector<int> store;
for(int i=0;i<=n;i++){
store.push_back(i);
}
vector<int> pre=store;
while(pre.size()>1){
vector<int> temp;
for(int i=0;i<pre.size();i++){
if((i+1)%2!=1) temp.push_back(pre[i]);
}
pre=temp;
}
cout<<pre[0]<<endl;
}
}

发表于 2020-01-11 16:59:31 回复(0)

Java

若相熙

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));
        }


    }
}

发表于 2019-04-08 14:27:48 回复(0)

心灵蚂蚁

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

参考大佬的解法，不过这个在我自己的编译器就运行得过，牛客网的就不行，一直显示输出为空，好奇怪

发表于 2019-01-02 02:26:20 回复(1)

kestars

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));
        }
    }
}

发表于 2018-10-11 22:27:41 回复(0)

开心超人129267

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();
    }
}

发表于 2018-09-05 14:52:28 回复(0)

亘

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);
    }
}

}

发表于 2017-12-16 23:44:51 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        int k = 1;
        while(k<=n+1)
            k <<= 1;
        cout<<((k>>1) - 1)<<endl;
    }
    return 0;
}

发表于 2017-10-29 01:18:10 回复(0)

C/C++

Cavs

#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;
}

发表于 2017-08-15 21:07:54 回复(0)

C/C++

zy在路上

include<iostream>

include<vector>

using namespace std;
int main()
 {
 int n;
 while(cin>>n)
 {
 vector<int>a;
 for(int i=0;i<=n;i++)
 a.push_back(i);
 while(a.size()!=1)
 {
 for(int j=0;j<a.size();j=j+1)
 a.erase(a.begin()+j);
 }
 cout<<a[0]<<endl;
 }
}

发表于 2017-07-23 21:33:19 回复(0)

Python

QuestCompleted

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

发表于 2017-01-06 12:59:27 回复(1)

fight灬奋斗

//总结规律
#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;
}

编辑于 2016-08-25 07:25:39 回复(0)

Java

writeless

import java.util.Scanner;

public class Main {

public static void main(String[] a){

Scanner s=new Scanner(System.in);

while (s.hasNextInt()){

int n=s.nextInt();

int k=1;

while(n>0){

n/=2;

k*=2;

}

System.out.println(k/2-1);

}

发表于 2016-08-13 15:04:44 回复(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);
			
		}
	}
}

编辑于 2016-04-14 01:37:43 回复(0)

一只补习的Fyu

因为是从0开始，所以第一轮移走的是二进制下最右边为0的位置（从0开始的偶数位置）上的数，然后我们发现第二轮各个number的位置等于number/2，即从number位置到number>>1位置，这时候我们依然移走二进制下最右边为0的位置（1(01) 5(101) 9(1001) ……它们第二轮对应的位置是0， 2， 4），最后剩一个数肯定是0到n中二进制下1最多的那个数，因为它每次的位置都是奇数位置。代码如下

#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;
}

编辑于 2018-04-28 20:50:15 回复(18)

Java

詆調壹點

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));
		}
	}
}

编辑于 2017-03-20 12:57:53 回复(13)

Python

华科平凡

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

编辑于 2017-09-12 10:30:08 回复(1)

C/C++

cycleof

//常规做法，比较直观，用数组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;
    }
}

编辑于 2017-06-30 15:30:55 回复(0)