环形报数

[编程题]环形报数

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

有n个人围成一圈，顺序排号（从1到n）。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的人的标号是多少？

输入描述:

输入一个整数 n 表示起初有 n 个人围成一圈（1<=n<=10000）

输出描述:

输出一个数字 x 表示最后剩下的一个人的标号

示例1

输入

输出

算法知识视频讲解

C/C++

独唱

用链表朴素地挨着报数

#include<stdio.h>
(737)#include<stdlib.h>
typedef struct LinkedNode{
    int no;
    struct LinkedNode* next;
}LinkedNode;

int main(){
    int n,m=3;
    while(scanf("%d",&n)!=EOF){
        LinkedNode* a=(LinkedNode*)malloc(sizeof(LinkedNode)),* p;
        a->no=1;
        a->next=NULL;
        p=a;
        int i=2;
        for(;i<=n;i++){
            p->next=(LinkedNode*)malloc(sizeof(LinkedNode));
            p=p->next;
            p->no=i;
            p->next=NULL;
        }
        if(i-1==n){
            p->next=a;
        }
        LinkedNode *pre=p;
        p=a;
        for(int j=1;p!=(p->next);j++){
            if(j%m==0){
                pre->next=p->next;
                p->next=NULL;
                free(p);
                p=pre->next;
            }else{
                pre=p;
                p=p->next;
            }
            
        }
        printf("%d\n",p->no);
    }
}

发表于 2020-03-24 18:40:01 回复(0)

shyshyshy_

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            list.add(i);
        }
        int n = list.size();
        int begin = 0;
        while (n != 1) {
            int index = (begin + 3) <= n ? begin + 2 : (begin + 3) % n == 0 ? (begin + 3) / n - 1: (begin + 3) % n - 1;
            list.remove(index);
            begin = index == n - 1 ? 0 : index;
            n--;
        }
        System.out.println(list.get(0));
    }
}

发表于 2023-09-18 11:36:10 回复(0)

蓝空已去

#include<stdio.h>
#include<iostream>

using namespace std;

int main(void){
	int n;
	scanf("%d\n",&n);
	
	int arr[n];//存储初始顺序
	for(int i=0;i<n;i++){
		arr[i]=i+1;
	}
	int nzero = n;//数组中非零个数
	int j=1; 
	while(nzero>1){
		for(int i=0;i<n;i++){
			if(j==3 && arr[i]!=0){
				arr[i]=0;//报数至三，arr[i]值为0
				j=1;
				nzero--;
			}
			if(arr[i]!=0 && j!=3){
				j++;
			}
			
		}
	}
	
	for(int i=0;i<n;i++){
		if(arr[i]!=0) printf("%d",i+1);
	}

	return 0;
}

发表于 2021-02-01 20:59:52 回复(0)