首页 > 试题广场 >

奇数位丢弃

[编程题]奇数位丢弃

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

输出

算法知识视频讲解

Java

Dandaalayyaa

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while (in.hasNextInt()) {

int n = in.nextInt();

System.out.println((int)(Math.pow(2,Math.floor(Math.log(n)/Math.log(2)))-1));

}

发表于 2023-05-18 03:51:12 回复(0)

Java

牛客773335897号

//數學規律
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in) ;
		while(sc.hasNext()){
        int n=sc.nextInt();
		int m=0;
		int sum=0;
		while(n>1) 
        {
			n=n/2;
			m++;
			sum=sum+(int)Math.pow(2, m-1);
		}
		System.out.println(sum);
        }
    }
}

发表于 2021-08-12 21:06:23 回复(0)

Java

牛客49495154号

  public static void main(String[] args) { int size = 5000;
        LinkedList<Integer> integers = intToLList(size);
        LinkedList<Integer> integers2 = new LinkedList<>(); while (integers.size() != 1) { for (int i = 0; i < integers.size(); i++) { if ((i+1)%2 != 0) {
                    integers2.add(integers.get(i));
                }
            } for (Integer integer : integers2) {
                integers.remove(integer);
            }
        }
        System.out.println(integers.get(0));
    } private static LinkedList<Integer> intToLList(int n) {
        LinkedList<Integer> integers = new LinkedList<>(); for (int i = 0; i <= n; i++) {
            integers.add(i);
        } return integers;
    }

发表于 2020-09-19 22:38:27 回复(0)

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)

Java

hshorse168

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){
                for(int i=0; i < list.size();i++)
                    list.remove(i);
            }
            System.out.println(list.get(0));
        }
    }
}

发表于 2019-04-16 20:22:29 回复(1)

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)

Java

blingblingbling2018010612

//一开始以为是约瑟夫环问题，后来自己试了连个例子，不太像。
//每次去除奇数位只留下原来的个数的一半，m次后只剩下一个数
//假设将剩下的数看做1，则在原来的序列中他是2^m，m=logn
//不知道说的明白不，贴出来给大家一个思路吧



import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner in =new Scanner(System.in);

        while(in.hasNext()){

            int n=in.nextInt();

            int m = (int)(Math.log(n)/Math.log(2));

            System.out.println((int)(Math.pow(2,m))-1);

        }

    }

}

发表于 2018-04-19 10:57:23 回复(0)

Java

no_and_life

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        while(input.hasNext()) {
            int n=input.nextInt();
            int len=0;
            while(n>1) {
                n=n>>1;
                len++;
            }
            System.out.println((1<<len)-1);
        }
        input.close();
    }
}

编辑于 2018-04-13 00:10:32 回复(0)

Java

dong1234

求大神解疑惑。本地运行答案都对，为什么在这里却没有输出。 import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double tmp = Math.log(n)/Math.log(2);
        double count = Math.floor(tmp);
		System.out.println((int)Math.pow(2,count)-1);
        
    }
}

发表于 2017-07-26 10:38:43 回复(0)

Java

珍爱生命，远离加班

public class Main{

public static void main(String[] args) throws IOException {

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

String str = "";

while ((str = bf.readLine()) != null) {

int n = Integer.valueOf(str);

System.out.println(deleteAllOdd02(n));

}

bf.close();

}

public static int deleteAllOdd02(int n) {

int i = 1;

while (true) {

if (Math.pow(2, i) - 1 > n) {

break;

}

i++;

}

return (int) (Math.pow(2, i - 1) - 1);

}

发表于 2017-07-25 18:20:16 回复(0)

Java

牛客2796735号

import java.util.*;

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

发表于 2017-07-04 15:29:00 回复(0)

Java

华仔17

import java.util.Scanner;

public class JiShu{

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

while(sc.hasNext()){

String str = sc.nextLine();

double n = Double.parseDouble(str);

int m = (int)(Math.log(n)/Math.log(2));

System.out.println((int)(Math.pow(2,m)-1));

}

发表于 2017-03-12 18:59:04 回复(0)

Java

java的神秘男友script

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            int n =in.nextInt();
            int num=0;
            int s=1;
            for(int i=0;num<n;i++ ){
                num=2*s-2;
                s*=2;
            }
            System.out.println(num/2);
        }
    }
}

学会找规律

发表于 2017-03-09 01:09:29 回复(0)

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();
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<=n;i++){
                list.add(i);
            }
            while(list.size()>1){
                for(int i=0;i<list.size();i=i+1){//注意不是i+2，因为删除了右边的前移
               		list.remove(i);
                }
            }
            System.out.println(list.get(0));
        }
    }
}

编辑于 2017-03-06 18:58:02 回复(0)

Java

C r 7

用一个辅助的数组，1代表死，2代表活。不断地挑出筛选过的数组，不断递归。 import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n = in.nextInt();
			int[] arr = new int[n+1];
			//初始化数组
			for(int i=0;i<n+1;i++){
				arr[i] = i;
			}
			while(arr.length!=1){
				arr=getNewArr(arr);
			}
			System.out.println(arr[0]);
		}
	}
	public static int[] getNewArr(int[] arr){
		if(arr == null){
			return null;
		}
		//标志数组，初始化为0，1为死，2为活
		int[] vice = new int[arr.length];
		int[] result = new int[arr.length/2];
		for(int i=0;i<vice.length;i++){
			//如果是双数位，令他死置为1
			if(i%2==0){
				vice[i] = 1;
			}else{
				vice[i] = 2;
			}
		}
		//result数组的标志
		int num = 0;
		for(int i=0;i<arr.length;i++){
			if(vice[i] == 2){
				result[num++] = arr[i];
			}
		}
		
		return result;
	}
}

发表于 2016-09-13 16:13:17 回复(0)

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)

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)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师数组安卓工程师运维工程师链表前端工程师算法工程师测试工程师 PHP工程师 c#工程师 2016 美团模拟测试开发工程师大数据开发工程师 Java工程师

来自：美团2016研发工程师...

难度：

21条回答 134收藏 31800浏览

通过挑战的用户

查看代码

有点心碎的小师...

2022-12-10 15:50:26
EdgeWalker

2022-12-06 14:17:46
已注销

2022-12-05 22:44:57
佛了

2022-11-14 15:56:19
牛客72330...

2022-09-17 13:05:52

奇数位丢弃

输入描述:

输出描述:

输入

输出

思路：数学推导

问题信息

热门推荐

通过挑战的用户

相关试题