约瑟夫环的问题

Posted on 2010-03-16 09:56 小火球 阅读(925) 评论(2)  编辑 收藏 引用 所属分类: Algorithm
  1/* 约瑟夫环问题(Josephus)
  2原题：
  3 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序。（约瑟夫环问题 Josephus）
  4
  5提示：
  6    由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，
  7    可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，
  8    选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，
  9    链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。
 10    设头指针为p，并根据具体情况移动。
 11    为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。
 12    由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如：int  quit[n];n为一个根据实际问题定义的一个足够大的整数。
 13
 14代码：
 15 purpose: 实现 Josephus 环问题
 16    用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，
 17    直至全部输出。写出C程序。（约瑟夫环问题 Josephus）
 18*********************************************************************/
 19#include <stdio.h>
 20#include <stdlib.h>
 21#include <string.h>
 22#include <malloc.h>
 23
 24/* 结构体和函数声明 */
 25typedef struct _node_t
 26{
 27    int n_num;
 28    struct _node_t *next;
 29} node_t;
 30
 31node_t *node_t_create(int n);
 32node_t *node_t_get(node_t **pn, int m);
 33
 34/* 功能函数实现 */
 35
 36/*
 37 * name: node_t_create
 38 * params:
 39 *   n   [in]  输入要构造的链表的个数
 40 * return:
 41 *   返回构造成功的环形单向链表指针
 42 * notes: 
 43 *   构造节点数量为 n 的环形单向链表
 44 *
 45 * author: A.TNG 2006/06/14 17:56
 46 */
 47node_t *node_t_create(int n)
 48{
 49    node_t *p_ret = NULL;
 50
 51    if (0 != n)
 52    {
 53        int n_idx = 1;
 54        node_t *p_node = NULL;
 55
 56        /* 构造 n 个 node_t */
 57        p_node = (node_t *)malloc(n*sizeof(node_t));
 58        if (NULL == p_node)
 59            return NULL;
 60        else
 61            memset(p_node, 0, n*sizeof(node_t));
 62  
 63        /* 内存空间申请成功 */
 64        p_ret = p_node;
 65        for (; n_idx < n; n_idx++) 
 66        {
 67            p_node->n_num = n_idx;
 68            p_node->next = p_node+1;
 69            p_node = p_node->next;
 70        }
 71        p_node->n_num = n;
 72        p_node->next = p_ret;
 73    }
 74    return p_ret;
 75}
 76
 77/*
 78 * name: main
 79 * params:
 80 *   none
 81 * return:
 82 *   int
 83 * notes: 
 84 *   main function
 85 *
 86 * author: A.TNG 2006/06/14 18:11
 87 */
 88int main()
 89{
 90    int n, m;
 91    node_t *p_list, *p_iter;
 92
 93    n = 20; m = 6;
 94
 95    /* 构造环形单向链表 */
 96    p_list = node_t_create(n);
 97
 98    /* Josephus 循环取数 */
 99    p_iter = p_list;
100    m %= n;
101    while (p_iter != p_iter->next)
102    {
103        int i = 1;
104
105        /* 取到第 m-1 个节点 */
106        for (; i < m-1; i++)
107        {
108            p_iter = p_iter->next;
109        }
110
111        /* 输出第 m 个节点的值 */
112        printf("%d\n", p_iter->next->n_num);
113
114        /* 从链表中删除第 m 个节点 */
115        p_iter->next = p_iter->next->next;
116        p_iter = p_iter->next;
117    }
118    printf("%d\n", p_iter->n_num);
119
120    /* 释放申请的空间 */
121    free(p_list);
122
123    system("PAUSE");
124}
125

Feedback

# re: 约瑟夫环的问题  回复  更多评论   

2012-09-21 20:38 by keen
代码问题，
m %= n;
下面还需要继续更新这个值。

# re: 约瑟夫环的问题  回复  更多评论   

2012-09-22 15:09 by 陈晨
#include<stdio.h>
#include<stdlib.h>
struct Lnode /*定义链表*/
{int number;
int password;
struct Lnode *next;
}Lnode,*p,*q,*head;

int main(void)
{int n; /*n个人*/
int i,j,k,h;
int m; /*初始报数上限值*/
int a[100],r=0;
scanf("%d",&k);
for (h=1;h<=k;h++){
scanf("%d",&n);
scanf("%d",&m);
p=NULL;
q=NULL;
for(i=1;i<=n;i++) /* 建立单链表*/
{if(i==1)
{head=p=(struct Lnode*)malloc(sizeof(struct Lnode));
}
else
{q=(struct Lnode*)malloc(sizeof(struct Lnode));
p->next=q;
p=q;
}
scanf("%d",&(p->password));
p->number=i;
}
p->next=head; /*形成循环链表*/
p=head;
for (j=1;j<=n;j++) /*输出各人的编号*/
{
for(i=1;i<m;i++,p=p->next);
m=p->password;
a[r]=p->number;
r=r+1;
p->number=p->next->number; /*删除报m的节点*/
p->password=p->next->password;
q=p->next;
p->next=p->next->next;
free(q);
}
a[r]=0;
r++;
}
for(i=0;i<r;i++){
if (a[i]!=0)
printf("%d ",a[i]);
else printf("\n");
}
printf("\n\n");
system("pause"); /*等待按任意键退出*/
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 28, comments - 3, trackbacks - 0, articles - 0

Copyright © 小火球