大约瑟夫环Joeph问题。【算法设计】约瑟夫环。

问题讲述

盖瑟夫(Joeph)问题之同一栽描述是:编号也1,2,…,n的n个人如约顺时针方向绕为同一环绕,每人有一个密码(正整数)。一开始任选一个刚好整数作为报数上限值m,从第一私房开始按顺时针方向从1从头逐项报数,报到m时停止报数。报m的丁出列,将他的密码作为新的m值,从外以顺时针方向直达之产一个人数开始又打1报数,如此下来,直至所有人周生列为止。试设计一个次要来出列顺序。

本科系列课程参见:《软件学院那些课》

基本要求

动用单向循环链表存储结构模拟此过程,按照有列的依次印出各人的号子

题材讲述

大体瑟夫(Joeph)问题的相同栽描述是:编号吧1,2,…,n的n个人按照顺时针方向绕为同一缠,每人有一个密码(正整数)。一开始任选一个恰巧整数作为报数上限值m,从第一私房开始按顺时针方向从1始挨家挨户报数,报到m时停止报数。报m的食指出列,将他的密码作为新的m值,从外以顺时针方向达成的下一个人数起更于1报数,如此下来,直至所有人数全有列为止。试设计一个序要出出列顺序。

中心要求

应用单向循环链表存储结构模拟此过程,按照有列的逐条印出各人的编号

算法思想

游玩实现之主要是娱乐信息的积存。包括玩家座位信息,玩家所报数信息和密码信息。我们通过从定义单为循环链表Joeph_list存储结构来促成休闲游经过的模拟。链表以结点连接。结点Node存储的音信包括每个人手中的密码、每个人的岗位及下一个结点在处理器中之囤位置,及针对下一个结点的指针。值得注意的是,信息“每个人之位置”是必要的,因为他无均等于结点于链表中的职务——但一个玩家被移除之后,链表后底要素位置会“前进”,而我们用的玩家的位置一直是未转移的。玩家的报数,我们通过轮回中计数器的与日俱增实现,当顺序递增到链表中最后一个结点,而循环仍尚未了时,我们延续于第一单要素开始递增——及相当给最后一个玩家仍没有报数到m我们就是于第一独玩家重头开始报数。直到计数器累加到m,则发现我们要移除的结点,记录并出口移出结点的信息,继续打。直到链表中元素被清空,程序结束。算法的要紧是将实际游戏场景抽象到链表中的要素的摸索和移除上,要控了解如何数据代表如何信息,并熟悉程序运行中各种判断的流水线。
算法流程

数据结构
于这游乐受,假定每个人且是一个节点,这样有利于程序的晓。

template <class List_entry>  
struct Node{  
    List_entry code;             // 存储每个人手中   密码  
    List_entry iposition;        // 存储每个人所处的 位置  
    Node<List_entry> *next;  

    Node();  
    Node(List_entry a, List_entry b, Node<List_entry> *link=NULL);  
};  

template <class List_entry>  
class Joeph_list{  
    public:  
        Joeph_list();  
        int size() const;  
        bool empty() const;  
        void clear();  

        Error_code retrieve(int position, List_entry &x, List_entry &y) const;  
        Error_code replace(int position, const List_entry &x, const List_entry &y);  
        Error_code remove(int position, List_entry &x, List_entry &y);  
        Error_code insert(int position, const List_entry &x, const List_entry &y);  

        ~Joeph_list();  
    protected:  
        int count;  
        void Init();                              // 初始化线性表  
        Node<List_entry> *head;  
        Node<List_entry> *set_position(int position) const;         
 // 返回指向第position个结点的指针  
};  

Node结构:表示实现Joeph_list以及List表的结点
Joeph_list类:储存游戏中玩家座位、密码等信息的数据结构
List类:以链表的不二法门囤图片等数据结构
全局对象game:SimpleWidow的窗口输出游戏经过
List<BitMap>tu;List<BitMap>shu;List<BitMap>people;分别存储游戏参与者报数、所持密码、和娱乐参与者的图纸。
全局函数:

void Baoshu(int p,int s); 用以显示游戏参与者报数的效果
void Yizou(int p,int m); 用以移走报到数的游戏参与者
void Code(int m);  用以更新密码信息
void Jieshu(); 结束游戏

类测试
1、游戏开始,初始m为6,从第一个玩家开始自行报数,报及数的人数出列

2、以发列人手中的密码也密码(不殊让6)继续玩

3、直到有人数出列,游戏结束

花色示范

(*点击图片但超反到Youku视频)

代码和材料下载:http://download.csdn.net/detail/xiaowei\_cqu/5068425

分享自xiaowei_cqu。

算法思想

玩耍实现之严重性是耍信息的积存。包括玩家座位信息,玩家所报数信息以及密码信息。我们通过从定义单为循环链表Joeph_list存储结构来兑现游戏过程的套。链表以结点连接。结点Node存储的音讯包括每个人手中的密码、每个人之职位与生一个结点在电脑被的存储位置,及针对下一个结点的指针。值得注意的是,信息“每个人的岗位”是必需的,因为他莫雷同于结点当链表中的位置——但一个玩家被移除之后,链表后的因素位置会“前进”,而我辈要之玩家的岗位一直是不更换的。
玩家的报数,我们由此巡回中计数器的与日俱增实现,当顺序递增到链表中最后一个结点,而循环仍没有完时,我们继承打第一独元素开始递增——及相当给最后一个玩家仍没报数到m我们即便从第一只玩家重头开始报数。直到计数器累加到m,则发现我们若移除的结点,记录并出口移有结点的消息,继续玩乐。直到链表中元素被清空,程序结束。
算法的严重性是以实际游戏场景抽象到链表中之要素的探寻和移除上,要控了解如何数据意味着如何信息,并熟悉程序运行中各种判断的流水线。

竟法流程

图片 1

数据结构

以斯玩受,假定每个人且是一个节点,这样方便程序的晓。

template <class List_entry>
struct Node{
    List_entry code;             // 存储每个人手中   密码
    List_entry iposition;        // 存储每个人所处的 位置
    Node<List_entry> *next;

    Node();
    Node(List_entry a, List_entry b, Node<List_entry> *link=NULL);
};

template <class List_entry>
class Joeph_list{
    public:
        Joeph_list();
        int size() const;
        bool empty() const;
        void clear();

        Error_code retrieve(int position, List_entry &x, List_entry &y) const;
        Error_code replace(int position, const List_entry &x, const List_entry &y);
        Error_code remove(int position, List_entry &x, List_entry &y);
        Error_code insert(int position, const List_entry &x, const List_entry &y);

        ~Joeph_list();
    protected:
        int count;
        void Init();                              // 初始化线性表
        Node<List_entry> *head;
        Node<List_entry> *set_position(int position) const;       
 // 返回指向第position个结点的指针
};

Node结构:表示实现Joeph_list以及List表的结点

Joeph_list类:储存游戏中玩家座位、密码等消息的数据结构

List类:以链表的计囤图片等数据结构

全局对象game:SimpleWidow的窗口输出游戏经过

List<BitMap>tu;List<BitMap>shu;List<BitMap>people;分别存储游戏参与者报数、所持密码、和娱乐参与者的图样。

全局函数:

void Baoshu(int p,int s); 用以显示游戏参与者报数的力量

void Yizou(int p,int m); 用以换走报至数之游玩参与者

void Code(int m);  用以更新密码信息

void Jieshu(); 结束游戏

品种测试

1、游戏开始,初始m为6,从第一独玩家开始活动报数,报及数之总人口出列

2、以发出列人手中的密码吗密码(不很叫6)继续打

图片 2

3、直到所有人出列,游戏结束

图片 3

种类示范

图片 4

(*点击图片但跨反至Youku视频)

代码和资料下载:http://download.csdn.net/detail/xiaowei_cqu/5068425

(转载请注明作者与出处:http://blog.csdn.net/xiaowei_cqu 未经允许请无用于商业用途)

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注