首页 > 试题广场 >

删数

[编程题]删数
  • 热度指数：66094 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
有一个数组 a[N] 顺序存放 0 ~ N-1 ，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。以 8 个数 (N=7) 为例 :｛ 0，1，2，3，4，5，6，7 ｝，0 -> 1 -> 2 (删除) -> 3 -> 4 -> 5 (删除) -> 6 -> 7 -> 0 (删除),如此循环直到最后一个数被删除。

数据范围：

输入描述:
每组数据为一行一个整数n(小于等于1000)，为数组成员数


输出描述:
一行输出最后一个被删掉的数的原始下标位置。
示例1

输入

8

输出

6
示例2

输入

1

输出

0
算法知识视频讲解
添加回答
明耀头像 明耀
约瑟夫环问题，数学递推公式f（n）=（f（n-1）+m）%n
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Del
{
class Program
{
static void Main(string[] args)
{
string str;
while(!string.IsNullOrEmpty(str=Console.ReadLine()))
{

int n = Convert.ToInt32(str);
int f = 0;
for(int i=2;i<=n;i++)
{
f = (f + 2) % n;
}
Console.WriteLine(f);
}
Console.ReadKey();
}
}
}

编辑于 2017-03-15 18:10:51 回复(0)
苏觅云头像 苏觅云 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()) {
            int n = sc.nextInt();
            int ans = 0;
            for(int i = 2; i <= n; i++) {
                ans = (ans + 3) % i;
            }
            System.out.println(ans);
        }
    }
}

发表于 2022-06-27 22:13:29 回复(0)
陌路人35号头像 陌路人35号 
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();
            Deque<Integer> d = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                d.offerLast(i);
            }
            while (d.size() > 1) {
                d.offerLast(d.pollFirst());
                d.offerLast(d.pollFirst());
                d.pollFirst();
            }
            System.out.println(d.pollFirst());
        }
    }
}

发表于 2022-03-24 20:18:20 回复(0)
Dem1an头像 Dem1an 
#include <bits/stdc++.h>
using namespace std;
int jos(int n, int m) {
    return n==1? 0 : (jos(n - 1, m) + m) % n;
}
int main(){
    int n, m=3;
    while(cin>>n){
        int rtn = jos(n, m);
        cout<<rtn<<endl;
    }
    return 0;
}
约瑟夫环

发表于 2022-03-16 15:48:21 回复(0)
cloudKing头像 cloudKing
#include<bits/stdc++.h>
using namespace std;
int getLastNum(int n,int m)
{
    int lastNum = 0; //N为1时的lastNum
          
    for (int i = 2; i < n+1; i++) 
    { //求出N为n时的lastNum
        lastNum = (lastNum + m + 1) % i;
    }
    return lastNum;
}
int main()
{
    int n;
    while(cin>>n)
    cout<<getLastNum(n,2)<<endl;
    return 0;
}

发表于 2021-04-05 14:35:55 回复(0)
C/C++
思考决定一切头像 思考决定一切
#include <iostream>
#include <vector>
using namespace std;
int main()
{
 int N;
 while (cin >> N)
 {
  vector<int> num;
  for (int i = 0; i < N; i++)
  {
   num.push_back(i);
  }
  int  count = N, m = 0;
  while(1)
  {
   m = (m + 2) % count;
   for (int i = m; i < count-1; i++)
   {
    num[i] = num[i + 1];
   }
   count--;
   if (count == 1) break;
  }
  cout << num[0] << endl;
 }
 return 0;
}
发表于 2021-03-05 23:10:34 回复(0)
pein531头像 pein531
直接用ArrayList进行模拟 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;
        while((strN = br.readLine()) != null){
            int n = Integer.parseInt(strN);
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0; i < n; i++) list.add(i);
            System.out.println(solve(list));
        }
    }
    
    // 模拟删数
    private static int solve(ArrayList<Integer> list) {
        for (int i = 2; list.size() > 1; i = (i + 2) % list.size()) 
            list.remove(i);
        return list.get(0);
    }
}


发表于 2020-11-11 15:43:17 回复(0)
露西恩缇努维尔头像 露西恩缇努维尔
用链表模拟 
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        n=min(n,1000);
        list<int> lis;
        for(int i=0;i<=n;i++)
            lis.push_back(i-1);
        auto it=lis.begin();
        while(lis.size()>2)
        {
            auto ne=next(it,1);        //获取待删除元素的下一个迭代器
            //删除当前元素
            if(it!=lis.begin())    lis.erase(it);
            //
            if(ne==lis.end())
            {
                ne=next(lis.begin(),1);
            }
            ne=next(ne,1);
            if(ne==lis.end())
            {
                ne=next(lis.begin(),1);
            }
            ne=next(ne,1);
            if(ne==lis.end())
            {
                ne=next(lis.begin(),1);
            }
            it=ne;
        }
        cout<<*next(lis.begin(),1)<<endl;
    }
    return 0;
}


发表于 2020-09-08 09:35:12 回复(0)
牛客868677681号头像 牛客868677681号 
while 1:
    try:
        num=int(input())
        if num>1000:
            num=999
        a=[x for x in range(num)]
        deln=2
        while len(a) > 1:
            if deln>=len(a):
                deln=deln-len(a)
            del a[deln]
            deln=deln+2
            if deln>=len(a):
                deln=deln-len(a)
        print(a[0])
    
    except:
        break


发表于 2020-03-11 12:51:42 回复(0)
从零开始学头像 从零开始学 
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int i = sc.nextInt();
            if (i > 1000) {
                i = 1000;
            }
            System.out.println(getLastDeleteElement(i, 2));
        }
        sc.close();
    }
     
    public static int getLastDeleteElement(int count, int step) {
        int[] array = new int[count];
        int remain = count;
        int sum = 0;
        int i = 0;
        int d = 0;
        // 剩余数量大于1
        while (remain > 1) {
            // 有效数字
            if (array[i] == 0) {
                // 距离上一个有效数字的距离为步长
                if (d == step) {
                    // 删除该数字，重置距离
                    sum+= i;
                    array[i]=1;
                    d=0;
                    remain--;
                } else {
                    ++d;
                }
            }
            i = (i + 1) % count;
        }
        return (count - 1) * count / 2 - sum;
    }
}

发表于 2019-11-30 16:07:29 回复(0)
放码过来头像 放码过来 
#include<iostream>
#include<stdlib.h>
#include<vector>
using namespace std;

int main()
{
    int N;
    while(cin>>N)
    {
        vector<int> Vec;
        for(int i=0;i<N;++i)
            Vec.push_back(i);
        
        int cnt = count(Vec.begin(),Vec.end(),-1);
        int i = 0;
        int step = 0;
        while(cnt != N - 1)
        {
            if(Vec[i] != -1)
                ++step;
            if(step > 2)
            {
                Vec[i] = -1;
                ++cnt;
                step = 0;
            }
            i = (i+1) % N;
        }
        for(int j=0;j<Vec.size();j++)
        {
            if(Vec[j]!= -1)
            {
                cout<<j<<endl;
                break;
            }
        }
    }
    return 0;
}

发表于 2019-05-14 18:21:59 回复(0)
Dante2018头像 Dante2018 
// 提供一个新思路！！！
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();
            if(n>1000) n=1000;
            int [] arr = new int[n];
            int inter = 0, size = 0, i = 0;
            while(size<n){
                if(arr[i]!=-1){
                    if(inter==2){
                        arr[i]=-1;
                        size+=1;
                        if(size==n) System.out.println(i);
                        inter = 0;
                    }
                    else inter +=1;                                    
                  }
                i = (i+1)%n;
            }
        }
    }
}

编辑于 2019-04-24 10:42:05 回复(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();
            if(n>1000){
                n=1000;
            }
            int[] array=new int[n];
            int i=-1;int count=n;int step=0;
            while(count>0){
                i++;
                if(i>=n){
                    i=0;
                }
                if(array[i]==-1){
                    continue;
                }
                step++;
                if(step==3){
                    array[i]=-1;
                    step=0;
                    count--;
                }
            }
            System.out.println(i);
    }
    }
}
这道题与剑指Offer中的孩子们的游戏其实是同一原理，用数组来模拟环，需要注意的是在遍历完一遍数组后需要通过判断(i>=n)使得遍历又回到数组开头
发表于 2019-04-02 16:56:49 回复(0)
菩提树叶头像 菩提树叶 

	#include <iostream>





	#include <list>





	usingnamespacestd;





	





	int main() {





	int n;





	while(cin >> n) {





	list<int> li;





	for(inti = 0;i < n;i++) {





	li.push_back(i);





	}





	auto it = li.begin();





	while(li.size() != 1) {





	if(it == li.end()) {





	it = li.begin();





	}





	it++;





	if(it == li.end()) {





	it = li.begin();





	}





	auto del = it;





	del++;





	if(del == li.end()) {





	del = li.begin();





	}





	li.erase(del);





	it++;





	}





	cout << li.front() << endl;





	}





	return0;





	}

编辑于 2019-03-26 21:51:45 回复(0)
C/C++
风笛201809260015282头像 风笛201809260015282
递推思想：
1.递归基：n=1时，只有0本身，返回0；
2.递推公式：f(n)=(f(n-1)+3%n)%n; 
在n-1问题规模下，f（n-1）=0+f(n-1)，0为第一步的起点下标；
在n问题规模下，我们执行一次删除，则数字剩余n-1，问题规模便成了n-1，再将起点下标同步为3%n（跨过三个数的下一个位置），这时我们待求解的问题完全等于n-1的问题了，只需要把0变成3%n,考虑到末尾到开头的循环，将结果再对n取余。 

	#include<iostream>





	using namespace std;





	int f(int n){





	    if(n == 1) return 0;





	    return(f(n - 1) + 3 % n) % n;  //递推公式





	}





	int main(){





	    int n;





	    while(cin >> n){





	        if(n>1000) n = 1000;





	        cout << f(n) << endl;





	    }





	}

发表于 2019-03-20 14:41:01 回复(1)
kestars头像 kestars 
import java.util.*;

class Node{
    int val;
    Node next;
}
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            Node root=new Node();
            root.val=0;
            Node curr=root;
            for(int i=1;i<n;i++){
                Node node=new Node();
                node.val=i;
                curr.next=node;
                curr=node;
            }
            if(curr.val!=root.val){
                curr.next=root;
            }
            while(curr.next.val!=curr.val){
                curr=curr.next;
                curr=curr.next;
                curr.next=curr.next.next;
            }
            System.out.println(curr.val);
        }
    }
}

发表于 2018-10-10 19:20:26 回复(0)
打工不可能打工的头像 打工不可能打工的
加了一个节点结构创建循环链表。 

	importjava.util.*;





	 





	public class Main {





	     





	    public static class Node {





	        Node next;





	        intval;





	         





	        publicNode(intval) {





	            this.val = val;





	        }





	    }





	     





	    public static void main(String[] args) {





	        Scanner scan = newScanner(System.in);





	        while(scan.hasNext()) {





	            intn = scan.nextInt();





	            Node cur = newNode(0);





	            Node head = cur;





	            for(inti = 1; i < n; i++) {





	                cur.next = newNode(i);





	                cur = cur.next;





	            }





	            cur.next = head;        





	            cur = head;





	            Node pre = null;





	            while(n > 1) {





	                for(inti = 2; i > 0; i--) {





	                    pre = cur;





	                    cur = cur.next;





	                }





	                pre.next = cur.next;





	                cur = cur.next;





	                n--;





	            }





	            System.out.println(pre.val);





	        }





	    }





	}

发表于 2018-08-28 14:36:06 回复(0)
C/C++
杨九天头像 杨九天 
//我这思路超时了 该怎么改哟！
#include<iostream>

using namespace std;

int main(){
    int n;
    cin>>n;
    if(n>1000){
    	n=1000;
    }
	int a[1000];
	
	//给a[1000]赋值 多余的部分赋值为1000；
	for(int i=n;i<1000;i++){
		a[i]=1000;
	}
	for(int i=0;i<n;i++){
		a[i]=i;
	}
	
	//把要剔除的数字也赋值为1000	
	int j=-1;
	for(int i=0;i<n-1;i++){
		j+=3;
		
		if(j>=n){
			j=j%n;
		}
		while(a[j]==1000){
			if(j>=n){
				j=j%n;
			}			
			j++;
		}
		
//		cout<<j<<":"<<a[j]<<" ";
		a[j]=1000;
		
	//使j跳过值为1000的数字 
		int m=0,k=j;
		while(m<2){
			k++;
			if(k>n){
				k=k%n;
			}
			if(a[k]!=1000){
				m++;
//				cout<<"m:"<<m<<endl;
			}else
				j++;
		}
	}
	
	for(int i=0;i<n;i++){
		if(a[i]!=1000){
			cout<<a[i];
		}
	}
    return 0;
}

发表于 2017-08-19 12:58:03 回复(0)
C/C++
cycleof头像 cycleof 
//强撸型算法，先挖个坑再改进，优点直观，缺点时间复杂度大。
#include<iostream>
using namespace std;
int main(){
    int n;
    while(cin >> n){
        int a[1001],i,j,count =0;
        if(n>1000)
            n = 999;
        for(i=0;i<n;i++)
            a[i] = i;
        for(i=0;i<20;i++){
            int x = 0,xx;
            for(j=0;j<n;j++){
                if(a[j] != -1){
                    count ++;
                	x ++;
                	xx = a[j];
                }
                if(count == 3){
                    a[j] = -1;
                    count = 0;
                }
            }
            if( x == 1 ){
                cout << xx <<endl;
                break;
            }
        }
    }
}

发表于 2017-06-25 10:42:20 回复(0)
冷色探戈头像 冷色探戈 
	/**
	 * 约瑟夫环(链表模拟)
	 * @param args
	 */
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			n = n > 1000 ? 999 : n;
			LinkedList<Integer> ll = new LinkedList<Integer>();
			for (int i=0; i<n; i++) {
				ll.add(i);
			}
			int ind = 0;
			int step = 3;
			while (ll.size() > 1) {
				int next = ind + step - 1;
				ind = (ind+next) % ll.size();
				ll.remove(ind);
			}
			System.out.println(ll.getFirst());
		}

		sc.close();
	}
编辑于 2017-03-30 11:24:08 回复(0)
提交观点

问题信息

数组 模拟
来自：华为2016研发工程师编程题
难度：
371条回答 58968浏览

热门推荐

通过挑战的用户

查看代码

相关试题

删数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号