首页 > 试题广场 >

删数

[编程题]删数
  • 热度指数:64924 时间限制: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)
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)
#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)
#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)
#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)
直接用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)
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)
// 提供一个新思路!!!
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)
递推思想:
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)
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)
//循环链表
#include<bits/stdc++.h>
usingnamespacestd;
structlnode{
    intval;
    lnode* next;
    lnode(intx): val(x),next(NULL){}
};
intmain()
{
    intn;
    while(cin>>n)
    {
        lnode* dummy = newlnode(-1);
        lnode* dummy2 = dummy;
        for(inti=0;i<n;i++)
        {
            lnode* p = newlnode(i);
            dummy->next = p;
            dummy = p;
        }
        lnode* head = dummy2->next;
        dummy->next = head;
        while(head->next != head)
        {
           head = head->next;
            head->next = head->next->next;
            head = head->next;
        }
        cout<<head->val<<endl;
    }
    return0;
}

发表于 2018-08-12 16:14:59 回复(0)
//我这思路超时了 该怎么改哟!
#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)
//强撸型算法,先挖个坑再改进,优点直观,缺点时间复杂度大。
#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)

问题信息

难度:
367条回答 58004浏览

热门推荐

通过挑战的用户

查看代码