首页 » C语言 » 约瑟夫环的C语言实现

约瑟夫环的C语言实现

原文 http://blog.csdn.net/zp208151138/article/details/79188542

2018-01-29 02:00:39阅读(554)

  约瑟夫环问题 :已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

对于该问题,众所周知有两种方法,一为循环单链表,一为数组,在这里我们假设均从第一个人开始报数,先讨论循环单链表的实现方法

相较于数组,用循环单链表实现较为简单,主要就是创建循环单链表,插入节点以及循环删除节点模拟人出列的过程

代码实现:

#define _CRT_SECURE_NO_WARNINGS 1   
#ifndef _JOSEPH_H__  
#define _JOSEPH_H__  
  
#include<stdio.h>  
#include<assert.h>  
#include<stdlib.h>  
  
typedef struct Joseph_ring  
{  
    int num;  
    struct Joseph_ring* next;  
}Joseph,*pJoseph;  
  
pJoseph CreateJoseph(int n);  
void joseph_r(pJoseph head, int m);  
  
#endif  




#include"Joseph ring.h"  
  
pJoseph CreateJoseph(int n)  
{  
    int i = 0;  
    pJoseph head = NULL;  
    pJoseph tail = NULL;  
    head = (pJoseph)malloc(sizeof(Joseph));  
    head->next = head;    //先让第一个结点head指向自己形成一个环  
    head->num = 1;  
    tail = head;  
    for (i = 2; i <= n; i++)     //循环向环中插入结点  
    {  
        pJoseph New = (pJoseph)malloc(sizeof(Joseph));  
        New->num = i;  
        New->next = tail->next;  
        tail->next = New;  
        tail = New;  
    }  
    return head;  
}  


void joseph_r(pJoseph head, int m)  
{  
    assert(head);  
    pJoseph cur = NULL;  
    pJoseph prev = NULL;  
    pJoseph del = NULL;  
    cur = head;  
    int i = 0;  
    while (head->next != head)  
    {  
        for (i = 1; i < m - 1; i++)  //找到要出列的人的前一个  
        {  
            cur = cur->next;          
        }                          //cur当前表示要出列的人的前一个  
        del = cur->next;  
        cur->next = del->next;  
        printf("%d ", del->num);  
        if (del == head)  
        {  
            head = del->next;  
         }  
        free(del);  
        cur = cur->next;  
        }  
        printf("%d\n", head->num);  
    }
}  


数组实现 : 用数组实现的一个难点在于,C99标准之前,C语言不接受定义变长数组,但是我们题目中人数n是非固定的,所以我们首先要解决的就是这个问题,在这里我们用int *a,并对a通过malloc分配n长度的空间来实现,然后我们把数组全赋值为0,即0为在场标志。 最后,把a的空间给free掉。

#include<stdio.h>

#include<stdlib.h>

int n;

int length(int *p)

{

 int i, k = 0;

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

{

 if(*(p+i) == 0)

{

 k++;

}

}

return k;

}


int main()

{

 int i, k, j = 0;

int *a;

printf("Please input the number:");

scanf("%d", &n);

printf("Which number go out:");

scanf("%d", &k);

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

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

{

 a[i] = 0;

}

while(length(a) > 1)

{

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

{

 if(a[i] == 0)

{

 j++;

if(j == 3)

{

a[i] = 1;

j = 0;

}

}

}

}

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

{

 if(a[i] == 0)

{

 printf("%d\n", i + 1);

break;

}

}

free(a);

return 0;

}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹