约瑟夫环的C语言实现

2018-01-29 12:40:10来源:网络收集作者:程序诗人人点击

分享

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


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


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


代码实现:


#define _CRT_SECURE_NO_WARNINGS 1   
#ifndef _JOSEPH_H__  
#define _JOSEPH_H__  
  
#include  
#include  
#include  
  
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


#include


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;


}


最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台