小生今天做课程实验,上机期间倍感无聊,老师就让我们写一个约瑟夫环,那就写吧。

首先我来介绍一下约瑟夫环,参考百度文献:约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后 结果+1即为原问题的解。

我在机房是没有网的,我记得老师当时讲的也就是那么个意思吧。然后我就开始写吧,

这里我把k设计为1,m设计为4,也就是从第一个人报数,数到4的那个人出列。

首先解决问题。

第一步:我想应该要有一个循环链表

说实话,我一直没写过循环链表,我一直都是在脑子中想,这突然让我写,我还真有点无从下手,然后我拿了笔和纸,终于还是让我写了出来;

for(int i=1;i<=count;i++)
{
    p->date=i;
    p->pNext = (Note *)malloc(sizeof(Note));
    if(i==count)
    {
        free(p->pNext);
        break;
    }
    p = p->pNext;    
}
p->pNext = head;

其实很简单的,(让我觉得有点难度的还是链表的逆序(其实也不难,以后有空也发表出来分享一下))

第二步:就该判断啥时候出来一个数了。

根据我的k和m,我给出了我的算法,如下

    for(i=1;1;i++)
{
    p = p->pNext;

    if(i==3)
    {
        pt1 = p;
        p = p->pNext;
        printf("%d\n",p->date);
        ptem=p->pNext;
        pt1->pNext = ptem;
        i=0;
        count--;
        if(count==0)
            break;
    }

}

到这里,老师让我们做的这个问题,也就解决了,我的代码写的比较差劲,而且,我还没有释放内存,下面的事情就交给想去研究这个问题的同学去完善吧,(其实是我懒,不想去完善(这点我要改))。 完整代码(编译就可以用的如下)

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

struct Note
{
    int date;
    Note *pNext;
};
Note *head;
int main()
{
    int count=0;
    printf("请输入有多少个数:\n");
    scanf("%d",&count);
    head=(Note *)malloc(sizeof(Note));
    Note *p=head;
    Note *ptem,*pt1;
    for(int i=1;i<=count;i++)
    {
        p->date=i;
        p->pNext = (Note *)malloc(sizeof(Note));
        if(i==count)
        {
            free(p->pNext);
            break;
        }
    p = p->pNext;    
    }
p->pNext = head;
for(i=1;1;i++)
{
    p = p->pNext;

    if(i==3)
    {
        pt1 = p;
        p = p->pNext;
        printf("%d\n",p->date);
        ptem=p->pNext;
        pt1->pNext = ptem;
        i=0;
        count--;
        if(count==0)
            break;
    }

}
system("pause");
return 0;

}

好了,有问题大家可以去优化,在这里我想说,代码这东西,要多练,才能有感觉,我要加强练习。千万不能眼高手低。切记切记多练。

2016年12月20日星期二