06月12, 2014

约瑟夫环C语言实现

使用C语言,自己编程实现约瑟夫环。

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

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int data;
    struct Node *next;
}Node,* LinkList;
//初始化
void init(LinkList *list){
    *list=(LinkList)malloc(sizeof(Node));
    (*list)->next=NULL;
}
//根据N个人进行创建
void create(LinkList list,int n){
    int i;
    LinkList node,h=list;
    for(i=0;i<n;i++){
        node=(LinkList)malloc(sizeof(Node));
        node->data=(i+1);
        h->next=node;
        h=node;
    }
    h->next=list->next;
}
//显示链表内容
void show(LinkList list){
    LinkList p=list->next;
    if(!p)return;
    do 
    {
        printf("%d ",p->data);
        p=p->next;
    } while (p!=list->next);
    printf("\n");
}
//计算链表的不为0的个数
int Calculator(LinkList list){
    int i=0;
    LinkList p=list;
    p=list->next;
    while(p){
        if(p->data!=0){
            i++;
        }
        p=p->next;
        if(p==list->next)
            break;

    }
    return i;
}
void execute(LinkList list,int k,int m){
    //从编号为k的人开始报数,
    //  数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;
    LinkList h=list->next;
    int i;
    while(h->data!=k)
        h=h->next;   //找到第K个人
    while(Calculator(list)>1){
        h=h->next;
        for(i=1;i<=m;i++){
            while(h->data==0){
                h=h->next;   //把所有data为0的人都跳过
            }
            if(i==m){
                h->data=0;
            }
            h=h->next;
        }
    }
}
int main()
{
    LinkList list;
    init(&list);
    create(list,3);
    show(list);
    execute(list,2,3);
    show(list);
    printf("%d\n",Calculator(list));
    return 0;
}

本文链接:http://blogs.360.cn/post/约瑟夫环c语言实现.html

-- EOF --

Comments