谁有约瑟夫环的递归写法  2个铜板买
实在想不起来

[[it] 本帖最后由 liyanhong 于 2008-5-21 18:07 编辑 [/it]]

为了实现零突破,给你了.
C++写得要不要.

哈哈,不好意思,没仔细看题,我写得是非递归.
你再说一句要就给你了.

收到的鲜花

• liyanhong 于 2008-05-21 12:01 送鲜花  2朵   附言：精品文章

//工程是大了点,没办法,C++就是这样,当然,也可以写得短小精悍.
//这次写用的是循环链表,效率不高,适合初学者.
//一共三个文件
//////////////////////////////////////////////////////////////////////////////////////////////
//CNode.h

template<typename T>
class CNode
{
private:
    CNode<T> *next;                           //指向下一节点循环指针
public:
    T data;
    CNode();                                  //construct
    CNode(const T & item);

    //更新表的方法
    void InsertAfter(CNode<T> *p);
    CNode<T>*DeleteAfter();

    //保存下一节点的指针
    CNode<T> *NextNode()const;
};
////////////////////////////////////////////////////////////////////
//CNode.cpp

#include "CNode.h"
template<typename T>
CNode<T>::CNode()
{
    next=this;                                                 //下一节点为结点本身
}

//产生空表并初始化数据的构造函数
template<typename T>
CNode<T>::CNode(const T& item)
{
    //将结点指向自身并初始化数据
    next=this;
    data=item;
}

//在当前结点之前插入结点P
template<typename T>
void CNode<T>::InsertAfter(CNode<T> * p)
{
    //p指向当前结点的后继结点，当前结点指向P
    p->next=next;
    next=p;
}

//删除当前结点之后的结点，并返回指向其的指针
template<typename T>
CNode<T>*CNode<T>::DeleteAfter()
{
    //保存指向被删除结点的指针
    CNode<T> *tempPtr=next;
    //若next==this ,表明没有其他结点，返回NULL
    if(next==this)
        return NULL;
    //当前结点指向tempPtr的后继结点。
    next=tempPtr->next;
    //返回指向被删除结点的指针
    return tempPtr;
}
template<typename T>
CNode<T>* CNode<T>::NextNode()const
{
    return next;
}
////////////////////////////////////////////////////////////
#include<iostream>
#include "CNode.h"
using namespace std;
void CreateList(CNode<int> *header,int n)
{
    //开始往头结点插入
    CNode<int>*currPtr=header,*newNodePtr;
    int i;
    //建立起N元循环链表
    for(i=1;i<=n;i++)
    {
        //用数据值i申请结空间
        newNodePtr=new CNode<int>( i);
        
        //往表尾插入结点并将currPtr指针前移到表尾
        currPtr->InsertAfter(newNodePtr);
        currPtr=newNodePtr;
    }
}

//对给定的n 元循环链表，通过每次便使第M个人出局直到最后一个末解决Josephus问题
void Josephus(CNode<int> *list,int n,int m)
{
    CNode<int>*prevPtr=list,*currPtr=list->NextNode();
    CNode<int> *deleteNodePtr;

    //删除表中结点只到最后一个
    for(int i=0;i<n-1;i++)
    {
        //从CURRPTR指向的当前客人开始数人，即指针前移m-1次
        for(int j=0;j<m-1;j++)
        {
            //前移指针
            prevPtr=currPtr;
            currPtr=currPtr->NextNode();
            //若CURRPTR指向表头，再移一次指针
            if(currPtr==list)
            {
                prevPtr=currPtr;
                currPtr=currPtr->NextNode();
            }
        }
        cout<<"Delete person "<<currPtr->data <<endl;
        //记录被删除的结点，并前移currPtr指针
        deleteNodePtr=currPtr;
        currPtr=currPtr->NextNode();
        //从表中删除该结点
        prevPtr->DeleteAfter();
        delete deleteNodePtr;
        //若CURRPTR为头指针，则再移一次
        if(currPtr==list)
        {
            prevPtr=currPtr;
            currPtr=currPtr->NextNode();
        }
    }
    cout<<endl<<"Person"<<currPtr->data<<"Wins the cruise."<<endl;
    //删除表中最后一个结点
    deleteNodePtr=list->DeleteAfter();
    delete deleteNodePtr;
}
int main()
{
    CNode<int> list;
    int n,m;                                       //n为表中人数，M为循环选择因子
    cin>>n;
    CreateList(&list,n);
    cin>>m;
    cout<<"Generated the member"<<m<<endl;
    Josephus(&list,n,m);
    system("pause");
    return 0;
}

[[it] 本帖最后由 zjl138 于 2008-5-21 12:14 编辑 [/it]]

收到的鲜花

• liyanhong 于 2008-05-21 15:22 送鲜花  2朵   附言：果然适合新手 一看就明白。。 ...

#include<stdio.h>
int main(void)
{
  int m,n;
  int i;
  int s;
  scanf("%d%d",&n,&m);
  s=0;
  for(i=2;i<=n;i++) s=(s+m)%i;
  printf("%d\n",s+1);
  return 0;
}
这个是数学方法，我直接在贴中打的，因此可能有点小问题，不过算法就是这样。

[[it] 本帖最后由 卧龙孔明 于 2008-5-21 12:35 编辑 [/it]]

收到的鲜花

• liyanhong 于 2008-05-21 15:23 送鲜花  1朵   附言：精品文章

为什么有优秀算法你不看，就偏要递归？
你觉得递归解这个很合适吗？？？

[color=white]