约瑟夫环问题~C语言初学者

约瑟夫环问题~C语言初学者

问题描述:设有n个小朋友围坐一圈玩丢手绢(用编号1,2,……n代表玩游戏的人),从第k(k大于等于1并且小于等于n)个小朋友开始报数,数到m的那个人出列。他的下一位继续从1开始报数,数到m的人出列,依此类推,直到所有人都出列为止。

输入:三个整数n k m,其中n表示玩游戏的人数,k表示从第k个人开始玩,m表示报数的值。

输出:n个整数,分别对应依次输出游戏的小朋友的编号。

例如: 输入13 2 3

输出结果为4 7 10 13 3 8 12 5 11 6 2 9 1

代码如下:

#include <stdio.h>

int main()

{

void f(int n,int m,int a[]);

int i,n,k,m,a[1000],t,j;

scanf("%d %d %d",&n,&k,&m);

t=k;

for(i=1;i<=n-(k-1);i++,t++)

a[i]=t;

for(i=n-k+1+1,j=1;i<=n;i++,j++)

a[i]=j; //把k放到了数组元素下标为1处,按题目给出的示例,完成到这里,a[1]=2,a[2]=3以此类推,到a[13]=1。

f(n,m,a); // 调用函数

}

void f(int n,int m,int a[])

{

int i,j,total=0; //j作为记录,有多少个人参与报数了,以便用此判断是不是该报数了,是不是m的整数倍。

for(i=1,j=0 ;total!=n; i++)

{

if(i>n) i=i-n;

if(a[i]!=0) //以及下面的把零赋值给a[i] 都是为了让每一次输出的其所在数组的那个元素变成零 这样可以有效避免这个元素对下面的产生干扰

{ j++;

if(j%m==0) { printf("%d ",a[i]); a[i]=0; total++; }

}

}

}