一道习题,求解题的思路.

坦_然

题目如下: 一个旅行社 要从n个旅客中选出一位旅客,为他提供免费的环球旅行服务.旅行社安排这些旅客围成一个圆圈,从帽子中取出一张纸条,用上面的写正整数 m(m<n)作为报数值.游戏进行时,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数,报m的人被淘汰出列,然后从他顺时针方向上的下一个人开始重新报数,如此下去,知道圆圈中只剩下一个人,这个最后的幸存者就是游戏的胜利者,将得到免费旅行的奖励.

流程图 也可 .非常感谢.

故乡的风

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

#define N 10        // 旅客数
#define M 4                // m

typedef struct _Node {
        int num;

        struct _Node *next;
} Node, *PNode, *Ring;

bool InitRing(Ring &r) {
        PNode pr = NULL;
        for (int i = 0; i < N; ++i) {
                // 创建节点
                PNode p = (PNode)malloc(sizeof(Node));
                if (!p) return false;

                if (0 == i) {        // 第一个节点为首节点
                        pr = r = p;
                } else {                // 节点加入链表
                        pr->next = p;
                        pr = pr->next;
                }

                p->num = i + 1;        // 旅客编号
                p->next = r;        // 形成循环链表
        }

        return true;
}

bool DestroyRing(Ring r) {
        if (!r) return false;

        PNode pdel = r;
        PNode pr = NULL;
        do {
                pr = pdel->next;        // 需删除节点的下一个节点
                free(pdel);                        // 删除节点
                pdel = pr;
        } while (pr != r);        // 已删除节点的下一节点若为r，则节点删除完毕

        return true;
}

int GamePlaying(Ring &r) {
        PNode pr = r;
        PNode pdel = r;
        while (pr != pr->next) { // 只有一个节点时，退出循环
                // 找到淘汰者
                for (int i = 0; i < M - 1; ++i) {
                        pr = pdel;
                        pdel = pdel->next;
                        printf("%d\n", pr->num);
                }
                pr->next = pdel->next;
                free(pdel);        // 删除淘汰者节点
                pdel = pr->next;
        }

        r = pr;
        return r->num;
}

int main(int argc, char *argv[]) {
        Ring JosephRing = NULL;
        InitRing(JosephRing);

        int pnum = GamePlaying(JosephRing);
        printf("Game Winner:%4d\n", pnum);

        DestroyRing(JosephRing);

        return 0;
}

只要使用循环的线性表，都可以按游戏描述简单的实现这个问题。这是我使用循环链表写的代码。

SXDA

用循环队列可以不？用一个循环判断队列是否只剩下一个元素。最后打印该元素~~

1187059391

甲鱼的数据结构视频中，讲了一道这样的题

1187059391

记得甲鱼的数据结构视频中，讲了一道这样的题

小亮1201

要求有点高，网上应该有源码吧。自己下去

wangyexin

一、数组模拟
二、数学公式

坦_然

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

int paixu ( int *, int , int ,int ,int *, int * );
int blSZ ( int * ,int  );
 

int main(int argc, char *argv[])
{        
        int i,n,m;
        printf("输入人数和随机数\n");
        scanf ( "%d %d",&n,&m );
        if (m>n)
        {
                printf("输入错误.\n");
                system ("Pause");
                return 0 ;
        }
        int a[n];
        for ( i=0 ;        i<n ;i++ )  //数组置1 ,淘汰则被置 0;
        {
                a[i]= 1;
        }
        paixu ( a , n, m ,0,  a, a); 
        for ( i=0 ;        i<n ;i++ )   
        {
                printf("a[%d]=%d \n",i,a[i]);
        }
        system ( "Pause" );
        return 0;
}





int paixu ( int *P ,int N , int M ,int iJishu, int *iWeizhi,int *iChaxun )
{ 
        if (blSZ( P,N )==1)
        {
                return ;
        }
        else
        {
                // iChaxun指向最后一个数组元素时的处理. 
                if (iChaxun-P==N)
                        {
                        if (iJishu<M)
                                {
                                        if (*iChaxun==0)
                                        {
                                                iChaxun=P;
                                        }
                                        if (*iChaxun==1)
                                        {
                                                iJishu++;
                                        }
                                }
           if (iJishu==M)
                        {
                                *iChaxun=0;
                                 iJishu=0;
                        }
                        //查询起始数组元素位于数组尾时 
                        if (iWeizhi-P==N)
                        {
                                iWeizhi=P;
                                iChaxun=iWeizhi;
                        }
                        else
                        {
                                iChaxun=P;
                        }
        }
/////////////////////////////////////////////
   // 计数 查询 置 0 
        if (iChaxun-P<N)
                {
                        if (*iChaxun==0)
                        {
                                iChaxun++;
                        }
                        if (*iChaxun==1)
                        {
                                iJishu++;
                                if (iJishu==M)
                                {
                                        iJishu=0;
                                        iWeizhi ++;
                                        *iChaxun=0;
                                        iChaxun=iWeizhi;
                                }
                                if (iJishu<M)
                                {
                                        iChaxun ++;
                                }
                
                        }
                }
        }
        return paixu(P, N , M, iJishu ,iWeizhi , iChaxun );
}
 
 
int blSZ ( int *sz ,int n )
{
        int i;
        int temp=0 ;
        for ( i=0 ; i<n ; i++ ) //遍历数组,查看值是否为1,是否只剩下一个人 ;
        {
                temp += *sz++ ;
                 
        }

        if (temp==1)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}

 

坦_然

wangyexin 发表于 2013-3-31 10:03

                               
登录/注册后可看大图

一、数组模拟
二、数学公式

用什么数学公式,能否介绍下.谢谢.

wangyexin

坦_然 发表于 2013-3-31 13:18

                               
登录/注册后可看大图

用什么数学公式,能否介绍下.谢谢.

百度约瑟夫环问题 百度百科里就有

坦_然

故乡的风 发表于 2013-3-30 17:58

                               
登录/注册后可看大图

只要使用循环的线性表，都可以按游戏描述简单的实现这个问题。这是我使用循环链表写的代码。

不太懂,复制保存,留作日后学习.谢谢你的解答.你的付出,我们为之努力.