Question

C语言中用数组解约瑟夫问题

数组a[]中N个人围绕桌子坐一圈，从1开始报数，报到m的人出局，依次输出出局人的序号

Answer 1

#include<stdio.h>

#include<stdlib.h>

void main()

{

int y(int n,int m);

int p,q,r;

printf("请输入参选人的个数p和开始的位置q：\n");

scanf("%d%d",&p,&q);

r=y(p,q);

printf("最后那个人的初始位置是：%d\n",r);

}

int y(int n,int m)

{

int i,j=0,s=0,l;

int *a=(int *)malloc(sizeof(int));

int *b=(int *)malloc(sizeof(int));

for(i=0;i<n;i++)

{

a[i]=i+1;

}

a[n]=-1;

for(i=0;j!=n;i++)

{

if(a[i]==-1) 

i=0;

if(a[i]!=0 && a[i]!=-1)

s++;

if(s==m)

{

b[j]=a[i];

a[i]=0;

j++;

s=0;

}    

}

for(i=0;i<n;i++)

{

printf("%5d",b[i]);

}

printf("\n");

l=b[n-1];

return l;

}

扩展资料：

大体思路如下：

①、read(a)

②、b:=1,c:=1{b为某一组的元素个数，c为累计所加到的数}

③、while c<a do (b:=b*2,c:=b+c){超过目标时停止加数}

⑥、c:=c-b{退到前一组}

⑦、x:=a-c{算出目标为所在组的第几个元素}

⑧、ans:=x*2-1{求出该元素}

⑨、write(ans)

参考资料：百度百科-约瑟夫问题

Answer 2

#include <stdio.h>

int main()
{
	// 假设k=3为报到计数单位量
	int i,k,m,n,num[50],*p;
	printf("输入人的数量：n=");
	scanf("%d",&n);
	p=num;
	
	for(i=0;i<n;i++)
		*(p+i)=i+1;//以1至n为序给每个人编号
	i=0;//i为每次循环时计数变量
	k=0;//k为按1,2,3报数时的计数变量
	m=0;//m为退出人数
	while (m<n-1)//当退出人数比n-1少时执行循环体
	{
		if(*(p+i)!=0) k++;
		if (k==3)
		{
			printf("出局人序号:%d\n",*(p+i));
		 *(p+i)=0;//将退出的人的编号置为0
		k=0;//k报到3后,重置为0
		m++;//退出的人数+1
		}
		i++;
		if (i==n) i=0;//报数到尾后,i恢复为0
	}
	while (*p==0) p++;//如果p所指向的值等于0.那么就执行p++让它指向下一个元素，直到不为0.
    printf("最后留下的人的编号是:%d\n",*p);//经过上面的循环后,*p的指向的编号就是最后留下的人
	
	return 1;
}

Answer 3

可以用另一个数组b[]来标记数组a里的元素是否出局，初始化b[]=0,出局者标记为1，报数计数标记为0的元素，到了数组尾端，再从开始

Answer 4

这个问题不算复杂，可以在数组a中进行就地处理，具体代码如下

#include <stdio.h>
#include <stdlib.h>

int main(){
    int *A;
    int n, m, i, j, k;
    while(scanf("%d%d%d", &n, &k, &m) == 3){
        A = (int *)malloc(sizeof(int) * n);
        for(i = 0; i < n; i++)
            A[i] = i + 1;
        i = j = n;
        --k;
        while(i > 0){
            k = (m + k - 1) % i;
            j = A[k];
            memmove(&A[1], &A[0], sizeof(int) * k);
            A[0] = A[i - 1];
            A[i - 1] = j;
            i--;
            k++;
        }
        for(i = n - 1; i >= 0; i--){
            printf("%d", A[i]);
            if(i > 0)
                printf(" ");
            else
                printf("\n");
        }
    }
}

测试用例为
3 2 20

9 1 5

输出结果为

3 2 1

5 1 7 4 3 6 9 2 8