约瑟夫问题 解法

计机羊咩咩

我自己也不造写得好不好撒  有疑问或者建议请积极联系我撒  {:1_1:}
希望下列源码能帮助到各位  (最好拉到编译器debug分析  光看代码看不到啥)

约瑟夫问题：

即在M个数内以N的间距开始不断循环，删除第M+(N * A）（A不断加1）个数字

如 1,2,3,4,5,6,7,8,9,10   十个数
从1数起，3号删除，再从4号数起，6号删除，7号数起，9号删除，10号数起，2号删除，在剩下的元素中不断循环删除 (已删除元素不进行循环) ，直至元素个数小于间距为止。

下列为源码：

#include<windows.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
typedef struct List
{
        int Num;
        int Size;
        struct List *Next;
}LIST;

char Command(void);
LIST *CreateList(void);
LIST *Joseph(LIST *Head);
void DestroyList(LIST *Head);
int main(void)
{
        LIST *Head = NULL;

        while (1)
        {
                switch (Command())
                {
                case 'A':
                        if (NULL != Head)
                        {
                                printf("Can not Create again!\n");
                                break;
                        }
                        Head = CreateList();
                        break;

                case 'B':
                        Head = Joseph(Head);
                        break;

                case 'C':
                        DestroyList(Head);
                        return 0;

                default:printf("Bad Command!\n");
                }
                Sleep(5000);
        }
        return 0;
}

char Command(void)
{
        //system("cls");

        char Name[20];
        printf("Function:\n");
        printf("A.Creating_List\n");
        printf("B.Running_Joseph\n");
        printf("C.Exit\n");
        printf("Comfirm your Command Name:");
        scanf("%20s",Name);

        if (!strcmp(Name, "Creating_List"))return 'A';
        else if (!strcmp(Name, "Running_Joseph"))return 'B';
        else if (!strcmp(Name, "Exit"))return 'C';
        else return -1;
}
LIST *CreateList(void)                         //创建环链表
{
        LIST *Head, *Temp;
        int Count = 1,Max = 0;

        printf("Enter Number of member:");
        scanf("%d",&Max);
        srand(time(NULL));
        if (NULL == (Temp = malloc(sizeof(LIST))))
        {
                printf("Creating Failure!\n");
                exit(1);
        }

        Temp->Size = Count++;
        printf("%d ",Temp->Num = (rand() % 100));
        Head = Temp;

        while (Count <= Max)
        {
                if (NULL == (Temp->Next = malloc(sizeof(LIST))))
                {
                        printf("No more memory!\n");
                        exit(1);
                }
                Temp = Temp->Next;

                Temp->Size = Count++;
                printf("%d ",Temp->Num = (rand() % 100));
        }
        Temp->Next = Head;

        printf("\nCreateing Completed!\n");
        return Head;
}

LIST *Joseph(LIST *Head)               //“约瑟夫问题”函数
{
        //system("cls");

        if (NULL == Head)
        {
                printf("List haven't member!\n");
                printf("Please creating list first!\n");
                return NULL;
        }

        int Gap = 0;
        LIST *Left,*Right,*Kill;

        printf("Enter the Gap(Gap > 1):");
        scanf("%d",&Gap);
        if (Gap <= 1)                          //间距不允许为1  实际上间距为1时指针会出现非法引用
        {
                printf("Error Gap!\n");
                exit(1);
        }

        printf("\nDeath Number:\n");
        Left = Kill = Head;
        while (1)
        {
                for (int Count = 1; Count < Gap;Count++)
                {
                        Kill = Kill->Next;
                        if (Count + 1 < Gap)Left = Kill;          //获取“被释放”节点的上一个节点
                }
                Right = Kill->Next;                           //获取“被释放”节点的下一个节点

                printf("%d(%d) ",Kill->Num,Kill->Size);
                Left->Next = Right;
                free(Kill);
                Kill = Right;

                if (Left == Right->Next || Right == Right->Next)break;   //约瑟夫问题最后只会剩下数量少于三个的成员
        }

        LIST *Flag;
        printf("\nSurvival member:\n");

        Flag = Left;
        Left = Left->Next;
        while (Flag != Left)
        {
                printf("%d(%d) ", Left->Num, Left->Size);
                Left = Left->Next;
        }
        printf("%d(%d)",Flag->Num,Flag->Size);
        return Left;
}

void DestroyList(LIST *Head)            //释放环链表  通用函数
{
        LIST *Flag,*Temp;
        
        Flag = Head;
        Temp = Head = Head->Next;           //从“标记”节点的下一个节点开始循环释放

        while (Flag != Head)
        {
                Head = Head->Next;
                free(Temp);
                Temp = Head;
        }
        free(Flag);
        printf("\nRelease completed!\n");
}

小结：
1.建立链表问题
直接Temp = Temp->Next之后再Temp = malloc()，似乎不能建立链表，先Temp->Next = malloc()之后再Temp = Temp->Next反而可以
(应该是Temp = Temp->Next直接把Temp->Next地址赋给Temp，后来malloc有一个新的地址再次赋给Temp，出现地址覆盖)

2. 环链表释放
标记当前节点，从下一节点开始循环释放

3.间距问题
当Gap为1时，debug查看链表发现 “断链” 的现象，出现野指针，原因未明！


以下附约瑟夫问题的变形：

设置一个初始数值，获取循环到该数值的节点的Size并删除该节点

Size作为下次循环的次数，重复以上步骤

直至所有删除到最后一个元素

改版函数源码：

LIST *Joseph(LIST *Head)               //“约瑟夫问题”函数
{
        LIST *Left, *Right, *Kill;
        int Cycles;
        printf("Initialization cycles:");
        scanf("%d",&Cycles);

        printf("\nDeath number:\n");
        Left = Kill = Head;
        while (Left != Left->Next)
        {
                for (int Count = 1; Count < Cycles; Count++)
                {
                        Kill = Kill->Next;
                        if (Count + 1 < Cycles)Left = Kill;
                }
                Right = Kill->Next;
                Left->Next = Right;

                printf("%d(%d) ", Cycles = Kill->Num,Kill->Size);
                free(Kill);
                Kill = Right;
        }

        printf("\nSurvival number:\n");
        printf("%d(%d)\n",Left->Num,Left->Size);
        return Left;
}

此算法结束后  只返回一个节点，且该节点会重新指向自身

安静的渴

正是我要的东西..感谢

vanentu

ThanksFORshare

EntU

辛苦了

EntU

额 我看看学习学习

逆战时代

看看。。。。。。。。。。。。

vanentu

LZ好人。。。。。。。。。