C语言 报数游戏

Python019

C语言 报数游戏,第1张

main()

{

int a[22]

int i,j

for(i=0i<21i++)a[i]=1

a[0]=0//这样，a[]的下标就是编号

j=0

int f,s

int n

scanf("%d",&n)

for(i=1i++)

{

NA:

j++

if(j==22)j=1//j的值是1～21

if(a[j]==0)goto NA

if(i==n)

{

a[j]=0

printf("j=%d\n",j)

s=0

for(f=0f<22f++)

{

s+=a[f]

}

if(s==1)break

i=0

}

}

for(f=0f<22f++)

{

if(a[f]==1)

printf("%d\n",f)

}

}

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<strings.h>

void c()//清空输入缓冲函数

{

    char c

    while((c=getchar())!=EOF&&c!='\n')

}

int main()

{

    int n,m

    printf("输入人数:")

    scanf("%d",&n)

    c()

    printf("输入报数:")

    scanf("%d",&m)

    c()

    char *arry=(char *)malloc(sizeof(char)*n)//建立动态数组

    bzero(arry,0)//置零

    int next=-1,num=n,j=0//next表示下标,从next+1开始报数,num表示还剩多少人,j是计数器表示报数到多少了,从0开始

    while(1)

    {

        if(num==1)//还剩一个

            break

        while(j<m)//报数到了退出

        {

            next=(next+1)%n

            if(arry[next]==0)//0表示这个人没有退出

                j++

        }

        j=0

        arry[next]=1//1表示人已退出

        printf("%4d",next+1)

        num--

    }

    printf("\n")

    for(j=0j++)

    {

        if(arry[j]==0)

            break

    }

    printf("第%4dwin\n",j+1)

}

此题可用数学方法求解。

设有n个人（编号0~(n-1)），从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数    （用数学方法解的时候需要注意应当从0开始编号，因为取余会取到0解。）

实质是一个递推，n个人中最终留下来的序号与n-1个人中留下来的人的序号有一个递推关系式。

假设除去第k个人，则

0, 1, 2, 3, ..., k-2, k-1, k, ..., n-1　         // 原始序列　(1)

0, 1, 2, 3, ..., k-2,      , k, ..., n-1      // 除去第k人，即除去序号为k-1的人   (2)

k, k+1, ..., n-1,    0,    1,        ..., k-2// 以序号k为起始，从k开始报0  (3)

0, 1,     ..., n-k-1, n-k, n-k+1, ..., n-2　  // 作编号转换，此时队列为n-1人　 (4)

变换后就完完全全成为了(n-1)个人报数的子问题，注意(1)式和(4)式，是同一个问题，不同的仅仅是人数。比较(4)和(3)，不难看出，0+k=k, 1+k=k+1, ... ，(3)式中'0'后面的数字，

（(n-3)+k）%n=k-3,（(n-2)+k）%n=k-2, 对于(3)式中'0'前面的数字，由于比n小，也可看作(0+k)%n=k,  (1+k)%n=k+1,  故可得出规律：

设(3)中某一数为x' , (4)中对应的数为x，则有：x'=(x+k)%n.

设x为最终留下的人序号时，队列只剩下1人时，显然x=0此时可向前回溯至2人时x对应的序号，3人时x对应的序号……直至n人时x的序号，即为所求。

#include <stdio.h>

const int M = 3

int main()

{

    int n, s = 0

    scanf("%d", &n)

    for (int i = 2 i <= n ++i)

        s = (s+M)%i

    printf("%d\n", s+1)

    return 0

}