首页 > 试题广场 >

删数

[编程题]删数

热度指数：67006 时间限制：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 (删除),如此循环直到最后一个数被删除。

数据范围： $1 \le n \le 1000 \$

输入描述:

每组数据为一行一个整数n(小于等于1000)，为数组成员数

输出描述:

一行输出最后一个被删掉的数的原始下标位置。

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

苏觅云

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)

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

#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)

露西恩缇努维尔

用链表模拟

#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号

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

// 提供一个新思路！！！
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

递推思想：
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

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

//强撸型算法，先挖个坑再改进，优点直观，缺点时间复杂度大。
#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)

南邮陈丹伟

//写一个***一点的吧，实质和队列差不多
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
        	int n = scanner.nextInt();
        	ArrayList<Node> list = new ArrayList<Node>();
        	for(int i=0;i<n;i++)
        		list.add(new Node(i));
        	int index = 0;
        	while(list.size()>0){
        		if(list.size() == 1){
        			System.out.println(list.get(0).originIndex);
        			list.remove(0);
        			break;
        		}
        		int size = list.size();
        		
        		int place = index+2;
        		if(place > size -1)
        			place= place % size;
        		list.remove(place);
        		index = place;
        	}
        	
        }
        scanner.close();
    }
    
    static class Node{
    	public int originIndex;
    	public Node(int originIdex){
    		this.originIndex = originIdex;
    	}
    }
  
}

发表于 2017-02-11 13:31:24 回复(0)

jionggu88


	#include<iostream>



	using namespace std;



	 



	struct node{



	    intval;



	    node *next;



	};



	 



	intmain(){



	    intn, i, j, k, result;



	    while(cin >> n){



	        if(n == 1){



	        cout << 0<< endl;



	        return0;



	    }



	    node *head, *rear, *p, *s;



	    head = newnode;



	    head -> val = 0;



	    p = head;



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



	        s = newnode;



	        s -> val = i;



	        p -> next = s;



	        p = s;



	    }



	    p -> next = head;



	     



	    p = head;



	    while(p->next!=p) {



	        p = p -> next;



	        s = p -> next;



	        p -> next = s -> next;



	        p = p -> next;



	        delete s;



	        result = p->val;



	    }



	    cout << result << endl;



	    }



	     



	     



	    return0;



	}



	



	利用循环链表，可以很清晰地解决

发表于 2016-03-17 11:32:37 回复(0)

Shield_W

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 = 999;
            }
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < n; i++) {
                list.add(i);
            }
            int i = 0;
            while (list.size() > 1) {
                i = (i + 2) % list.size();
                list.remove(i);
            }
            System.out.println(list.get(0));
        }
    }
}

发表于 2016-08-12 16:54:49 回复(35)

Sdankle

用队列模拟，队首取数，用一个计数器计数，隔2个删一个，其他的重新放到队尾 #include<iostream>
#include<queue>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        queue<int> q;
        for(int i=0;i<n;i++)
        {
            q.push(i);
        }
        int count=0;
        while(q.size()!=1)
        {
            if(count!=2)
            {
                int b=q.front();
                q.pop();
                q.push(b);
                count++;
            }
            else
            {
                q.pop();
                count=0;
            }
        }
        int c=q.front();
        cout<<c<<endl;
    }
    return 0;
}

发表于 2016-03-10 11:22:22 回复(27)

提交观点

问题信息

数组模拟

来自：华为2016研发工程师编程题

难度：

373条回答 1233收藏 61174浏览

通过挑战的用户

查看代码

牛客79715...

2023-03-08 22:26:14
花生油

2023-03-07 18:00:59
1234_

2023-02-20 19:37:40
追太阳的黑子

2023-01-12 10:57:29
长余佩之陆离

2022-11-29 19:03:55

删数

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题