约瑟夫问题 解法
本帖最后由 计机羊咩咩 于 2014-10-12 09:41 编辑我自己也不造写得好不好撒有疑问或者建议请积极联系我撒{: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;
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;
}
此算法结束后只返回一个节点，且该节点会重新指向自身
正是我要的东西..感谢 ThanksFORshare 辛苦了 额 我看看学习学习 看看。。。。。。。。。。。。
LZ好人。。。。。。。。。
页:
[1]