围圈报数

[编程题]围圈报数

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

N 个人围成一圈顺序编号，从1 号开始按1、2、3 顺序报数，报3 者退出圈外，其余的人再从1、2、3 开始报数，报3 的人再退出圈外，依次类推。请按退出顺序输出每个退出人的原序号。要求使用环行链表编程。

输入描述:

输入第一行为整数m表示有m组测试数据，接下来m行每行一个整数N，N不超过50。

输出描述:

输出m行，每行表示题目所求，用空格隔开。

示例1

输入

1
4

输出

3 2 4 1

算法知识视频讲解

Java

azzz1112

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()) {
			int m = scanner.nextInt();
			for (int i = 0; i < m; i++) {
				
				int n = scanner.nextInt();
				
				//按照输入顺序排序
				List<Integer> myList = new LinkedList<Integer>();
				for (int j = 1; j <= n; j++) {
					myList.add(j);
				}
				
				while(!myList.isEmpty()) {
					
					if(myList.size() >= 3) {
						System.out.print(myList.get(2)+" ");
						reSort(myList);
						continue;
					}else {
						System.out.print(myList.remove(0)+" ");
					}
					
				}
				
				//换行输出
				System.out.println();
				
			}
		}
	}
	
	public static void reSort(List<Integer> myList) {
        //重排List：实现将List的前两个元素插入到最后得到一个新的List
		if (myList.size() >= 3) {
			int list1 = myList.remove(0);
			int list2 = myList.remove(0);
			
            //删除原来List中第3个元素
			myList.remove(0);
			
			myList.add(list1);
			myList.add(list2);
		}
	}
}

编辑于 2024-03-21 15:27:26 回复(0)

Java

浅笑_0657

用java模拟实现：

关键：每次循环记录当前报数人并寻找下次报数人，报3（bs%3==0）的人从list删除，直到list为空

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n-->0){
            int a = scanner.nextInt();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < a; i++) list.add(i+1);//将所有人抽象成Integer，用list模拟圈
            int bs = 1;
            Integer cbsr;//当前报数人
            Integer nextbsr = list.get(0);//下一个报数人
            while (list.size() != 0) {
                cbsr = nextbsr;
                nextbsr = list.get((list.indexOf(cbsr) + 1) % list.size());//关键 每次在移除报3的人之前找下一个报数人
                if (bs % 3 == 0) {
                    list.remove(cbsr);//当前报数人退出
                    System.out.print(cbsr+(list.size()==0?"":" "));//并输出
                }
                bs++;
            }
            System.out.println();
        }
    }
}

编辑于 2020-07-09 12:19:36 回复(0)

Java

LHC0512

Java

package nowcoder05.demo30;

import java.util.Scanner;

public class Main {
    static class Node{
        int value;
        Node next;
        public Node(int value) {
            this.value = value;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            int n = scanner.nextInt();
            Node head = new Node(1);
            Node p = head;
            for (int j = 2; j <= n; j++) {
                Node node = new Node(j);
                p.next=node;
                p=node;
            }
            p.next=head;
            p=head;
            while (p.next!=p){
                Node pre  = p.next;
                System.out.print(pre.next.value+" ");
                pre.next= pre.next.next;
                p= pre.next;
            }
            System.out.println(p.value);
        }
    }
}

发表于 2020-03-20 19:56:20 回复(0)

Java

我在清华玩泥巴

import java.util.*;
public class Main {
static int i =1;//全局计数器，用于数3
static int m;//用例数
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();//圈内人数的集合
List<Integer> list2 = new LinkedList<>();//挑出的人的集合
List<Integer> group = new LinkedList<>();//用例（人数）集合
Iterator<Integer> it = list.iterator();//实例一个迭代器
Scanner sc = new Scanner(System.in);
m = sc.nextInt();//用户输入用例数
for(int a=0;a<m;a++) {//对用例数（圈数）循环
group.add(sc.nextInt());//向用例集合输入用例
for(int j =0;j<group.get(a);j++) {//读取用例，将序号添加进list
list.add(j+1);
}
for(;it.hasNext();){//只要圈内还有人就执行下一轮循环
int x=list.size();
for(int q=0,b=0,c=0;c<x;q++,i++,c++) {//这个循环只对一轮内的人挑出数3的人的序号
if(i==3) {//当数到3时
list2.add(list.get(q-b));//向list2添加当前数到3的人的序号
i=0;//初始化计数器
list.remove(q-b);//将原圈里数到3的人移除
b++;//记录移除的人数
}
}
}
for(int p=0;p<list2.size();p++) {//输出被挑出的人序号
System.out.print(list2.get(p)+" ");
}
System.out.print("\n");
for(;0<list2.size();) {//输出完后移除list2的所有元素
list2.remove(0);
}
}
}
}

//JAVA入门菜鸟，苦苦想了一整天

发表于 2019-04-11 14:09:40 回复(0)