| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4308 人关注过本帖
标题:约瑟夫环的递归写法 2个铜板买
只看楼主 加入收藏
liyanhong
Rank: 3Rank: 3
来 自:水星
等 级:禁止访问
威 望:8
帖 子:1867
专家分:0
注 册:2008-5-3
收藏
 问题点数:0 回复次数:22 
约瑟夫环的递归写法 2个铜板买
谁有约瑟夫环的递归写法  2个铜板买
实在想不起来

[[it] 本帖最后由 liyanhong 于 2008-5-21 18:07 编辑 [/it]]
搜索更多相关主题的帖子: 约瑟夫 递归 铜板 
2008-05-21 11:49
zjl138
Rank: 1
等 级:新手上路
威 望:1
帖 子:788
专家分:0
注 册:2007-11-12
收藏
得分:0 
为了实现零突破,给你了.
C++写得要不要.

i like linux...
2008-05-21 11:54
zjl138
Rank: 1
等 级:新手上路
威 望:1
帖 子:788
专家分:0
注 册:2007-11-12
收藏
得分:0 
哈哈,不好意思,没仔细看题,我写得是非递归.
你再说一句要就给你了.
收到的鲜花
  • liyanhong2008-05-21 12:01 送鲜花  2朵   附言:精品文章

i like linux...
2008-05-21 11:59
zjl138
Rank: 1
等 级:新手上路
威 望:1
帖 子:788
专家分:0
注 册:2007-11-12
收藏
得分:0 
//工程是大了点,没办法,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]]
收到的鲜花
  • liyanhong2008-05-21 15:22 送鲜花  2朵   附言:果然适合新手 一看就明白。。 ...

i like linux...
2008-05-21 12:12
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
#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]]
收到的鲜花
  • liyanhong2008-05-21 15:23 送鲜花  1朵   附言:精品文章

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2008-05-21 12:33
Q1007665007
Rank: 1
等 级:新手上路
帖 子:58
专家分:0
注 册:2008-5-16
收藏
得分:0 
为什么有优秀算法你不看,就偏要递归?
你觉得递归解这个很合适吗???

[color=white]

QQ1007665007
QQ群61762856
2008-05-21 12:43
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
递推应该是最快的了(不要铜板,那东西没有用)

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2008-05-21 12:49
liyanhong
Rank: 3Rank: 3
来 自:水星
等 级:禁止访问
威 望:8
帖 子:1867
专家分:0
注 册:2008-5-3
收藏
得分:0 
非常感谢
我一点算法都不懂呀
哪个好心人给个递归调用写出来的约瑟夫环
PS:我的机子开机20分钟左右就自动关机   是什么原因呢   无奈

爱上你 是 我的错  可是离 开  又舍不得  听着你为我写的歌     好难过
如果说 我说如果  我们还 能  重新来过   不去计 较 谁对谁错  会怎么做
2008-05-21 14:19
sunkaidong
Rank: 4
来 自:南京师范大学
等 级:贵宾
威 望:12
帖 子:4496
专家分:141
注 册:2006-12-28
收藏
得分:0 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int i=0;
int *p;
int Josephus(int n,int q,int j,int k)
{   
    if(j>n-1)
        return 1;
   
      while(p[i++]==1)
      {
          i=i%n;
      };

      i=(i>n-1?(i-1)%n:i-1);
      k++;
   
    
    if(k%q==0)
     {
      while(p[i++]==1)
      {
          i=i%n;
      };
         i=(i>n-1?(i-1)%n:i-1);
         printf("第%d个元素出队.\n",i);
         p[i]=1;
         j++;        
    }   
    else
        i=(i++)%n;
    if(Josephus(n,q,j,k))
    {   
        return 1;
    };
        return 1;
}
int main()
{
   int n;
   int q;
   printf("请输入队列长度:");
   scanf("%d",&n);
   printf("请输入报数长度:");
   scanf("%d",&q);
   p=new int[n];
   memset(p,0,n);
   Josephus(n,q,0,0);
   delete [] p;
   return 0;
}

[[it] 本帖最后由 sunkaidong 于 2008-5-21 15:52 编辑 [/it]]
收到的鲜花
  • liyanhong2008-05-21 15:43 送鲜花  2朵   附言:我很赞同

学习需要安静。。海盗要重新来过。。
2008-05-21 14:40
qinxinhai
Rank: 1
来 自:湖南长沙
等 级:新手上路
帖 子:237
专家分:0
注 册:2008-4-27
收藏
得分:0 
你不是把自动关机的程序写到任务里面了吧
以前有人给我整了个,10分钟自动关机的
我还以为是木马什么的!整的累死了!
最后才知道是个恶作剧

我秀我自己
2008-05-21 14:41
  • 23
  • 1/3页
  • 1
  • 2
  • 3
快速回复:约瑟夫环的递归写法 2个铜板买
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.044427 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved