首页 > 代码库 > 九度OJ—题目1188：约瑟夫环

九度OJ—题目1188：约瑟夫环

2024-08-09 06:51:21   221人阅读

题目描述：

    N个人围成一圈顺序编号，从1号开始按1、2、3......顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。
    请按退出顺序输出每个退出人的原序号。

输入：

包括一个整数N(1<=N<=3000)及一个整数p。

输出：

测试数据可能有多组，对于每一组数据，
按退出顺序输出每个退出人的原序号。

样例输入： 
7 3
样例输出： 
3 6 2 7 5 1 4
来源：
2003-2005年华中科技大学计算机研究生机试真题
答疑：
解题遇到问题?分享解题心得?讨论本题请访问：http://t.jobdu.com/thread-7911-1-1.html


基本思路：数组存储，剔除的位置赋值为0.每次遍历完整个数组，

                   index=(index+1)%n,

                   求模继续从第一个位置开始,遇0跳过


#include<stdio.h>
 
int del(int a[],int b,int n)
{
    int index=0,i=1,x=0;
    while(i<=n){
        if(a[index]!=0){
            x++;
            if(x==b){            
                if(i==1) printf("%d",a[index]);
                else printf(" %d",a[index]);
                a[index]=0; 
                i++;
                x=0;
            }
        }                
        index=(index+1)%n;       
    }
    return 0;   
}
int main()
{
    int a[3001],i,b,n;
    while(scanf("%d%d",&n,&b)!=EOF){
        for(i=0;i<n;i++)
            a[i]=i+1;
        del(a,b,n);    
        printf("\n");
    }
    return 0;
}
/**************************************************************
    Problem: 1188
    User: vhreal
    Language: C
    Result: Accepted
    Time:370 ms
    Memory:912 kb
****************************************************************/


九度OJ—题目1188：约瑟夫环


联系
我们