玩家所报数信息以及密码信息,约塞夫问题

作者: 前端  发布:2019-12-09

二、面向过程

算法思想

游戏实现的关键是游戏信息的储存。包括玩家座位信息,玩家所报数信息以及密码信息。我们通过自定义单向循环链表Joeph_list存储结构来实现游戏过程的模拟。链表以结点连接。结点Node存储的信息包括每个人手中的密码、每个人的位置以及下一个结点在计算机中的存储位置,及指向下一个结点的指针。值得注意的是,信息“每个人的位置”是必不可少的,因为他不等同于结点在链表中的位置——但一个玩家被移除之后,链表后的元素位置会“前进”,而我们需要的玩家的位置始终是不变的。玩家的报数,我们通过循环中计数器的递增实现,当顺序递增到链表中最后一个结点,而循环仍没有结束时,我们继续从第一个元素开始递增——及相当于最后一个玩家仍没有报数到m我们就从第一个玩家重头开始报数。直到计数器累加到m,则发现我们要移除的结点,记录并输出移出结点的信息,继续游戏。直到链表中元素被清空,程序结束。算法的关键是将实际游戏场景抽象到链表中的元素的查找和移除上,要掌握清楚哪些数据代表哪些信息,并熟悉程序运行中各种判断的流程。算法流程

9159.com 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; 用以更新密码信息void Jieshu(); 结束游戏

9159.com,项目测试1、游戏开始,初始m为6,从第一个玩家开始自动报数,报到数的人出列

2、以出列人手中的密码为密码继续游戏

9159.com 23、直到所有人出列,游戏结束9159.com 3项目演示9159.com 4(*点击图片可跳转到Youku视频)

代码及资料下载:

分享自xiaowei_cqu。

六、静态链表

其特点是每个数据元素在存储本身的信息之外,还要存储其直接后继的信息

问题描述

约瑟夫问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。

        s->next = p->next;p->next = s;

难怪《美丽心里》里开头就说,是数学家改变了世界

基本要求

利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号

    线性表的顺序存储结构特点是:逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中的任何一个元素。

二、面向对象

    存储空间可以连续也可以不连续。为了表示ai和ai+1的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。它的节点包括两个域:其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。n个节点链接成一个链表,即为线性表:

从 1 号开始报数,报数到 3 号时,3 号就被淘汰,然后由下一人从 1 报数,以此类推

四、定义

虽然能解决问题,但一旦遇到较大的数据量,查询的次数太多,性能太低

typedef struct LNode

{

ElemType data;

struct LNode *next;

} LNode *LinkList;

在吃透了整个游戏规则之后。。。

    例如要插入的元素为x,假设s为指向结点x的指针,则指针修改为

根据循环链表的特性,每个玩家除了存储本身的信息(编号),还需要存储前后的编号

    又因为链表的每个节点中只包含一个指针域,故又称为线性链表或单链表。

最后谁会活下来?

二、链式存储结构

在这个游戏中,可以将玩家抽象成一个对象,然后由玩家组成了一个环

  

于是把题目优化一下,更接近于原本的约塞夫问题

        p->next = p->next->next;

而当这些数据元素构成一个逻辑上的环,任意元素都有一个前驱和后继,这就构成了一个循环链表

    它是另一种形式的链式存储结构。特点是表中最后一个结点的指针指向头结点,整个链表形成一个环。

  

  

function Joseph(sum, value, n) {
    if ( n==1 ) {
        return ( sum + value - 1) % sum;
    } else {
        return ( Joseph( sum - 1, value, n - 1) + value ) % sum;
    }
}

console.log("剩下的人号数为:" + (Joseph(100, 3, 100) + 1))

 

 

八、双向链表

原题目不太明朗(一号到底杀不杀?)

七、循环链表

  

有时候我们在单链表的第一个结点之前附设一个结点,称之为头结点。头结点的数据域不存储任何信息,也可以附加如线性表的长度等类的附加信息,头结点的指针域存储指向第一个结点的指针

在数据结构中,具有链式存储结构的线性表被称为链表

    在单链表中,取得第i个数据元素必须从头指针出发寻找,因此单链表是非随机存取的存储结构。

  1. 如何用 js 快速创建一个 1~100 的数组?

  2. 如果报数到 2 就淘汰,最后剩下谁?

    用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的。换句话说,指针为数据元素之间的逻辑关系的映像,则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻,因此这种存储结构为非顺序映像或者链式映像。

然后分析整个环,除了构造函数之外,还应当具备淘汰玩家、开始游戏的功能

取得第i个元素

 

Status GetElem_L(LinkList L,int i,ElemType &e)

{

//L为带头结点的单链表的头指针

//当第i个元素存在时,其值赋给e并返回ok,否则返回error

p = L->next;   //初始化,p指向第一个结点

j=1;   //初始化计数器

while(p && j<i)

{

p = p->next;

++j;

}

if (!p || j>i)  //第i个元素不存在

{

return ERROR;

}

e = p->data;  //取得第i个元素

return OK;

}  //GetElem_L

在上一篇《前端面试 - 算法篇(二分法)》的评论中,有朋友提出了一个“循环杀人游戏”

    用数组描述的链表起名叫静态链表。

 

三、线性链表

/**
 * 面向过程的约塞夫环解决办法
 * @param {Array} peoples 参与游戏的数组
 * @param {Number} kill 淘汰的报数数字
 * @return {Object} 幸存者
 */

function killer(peoples, kill) {

  let flag = 0 // 初始化报数

  while(peoples.length > 1) { // 只剩下一个人时,循环结束

    let len = peoples.length // 剩余人数
    let out = 0 // 已淘汰的人数

    for (let i = 0; i < len; i++) {
      flag++ // 报数+1

      if (kill == flag) { // 当报数到指定数字,淘汰该玩家
        // 淘汰后剩余人数(数组)会发生变化,所以被淘汰玩家下标应为 i-out
        peoples.splice(i-out, 1)

        flag = 0 // 重置报数
        out++ // 淘汰人数+1
      }
    }
  }
  return peoples[0]
}

一、前言

emmmmmmmmmm

   缺点:在作插入删除操作时,需要移动大量元素。

/**
 * 面向对象的约塞夫环解决办法
 * @param {Number} length 玩家总数
 * @param {Number} kill 淘汰的报数数字
 * @return
 */
class Cycle { // 创建循环链表
  constructor (length) {
    this.count = 0; // 玩家总数
    this.start = new Player(1) // 链表起点
    this.end = new Player(length) // 链表终点

    for(let i = 1; i <= length; i++) {
      // 创建玩家
      let player = new Player(i)
      this.count++

      if (this.count <= 1) {
        // 只有一个玩家的时候,起点和终点为同一个玩家
        this.start = this.end = player
      } else {
        // 新创建的玩家一定位于链表终点之后
        this.end.after = player
        player.before = this.end
        // 而该玩家即为新的链表终点
        this.start.before = player
        player.after = this.start
        this.end = player
      }
    }
  }

  delete (player) {
    if (this.count <= 1) { // 错误校验
      this.start = this.end = null
      return
    } else {
      // 将前后的玩家关联起来
      player.before.after = player.after
      player.after.before = player.before
      // 如果处于终点或起点,则修改相关信息
      if (player == this.start) {
        this.start = player.after
      } else if(player == this.end) {
        this.end = player.before
      }
    }
    // 淘汰该玩家
    player = null
    this.count--
  }

  play (kill) {
    let flag = 0 // 初始化报数
    let k = this.start // 从起点开始游戏
    while (this.count > 1) { // 只剩一个玩家,循环结束
      flag++
      if (flag == kill) { // 报数到目标数字,淘汰玩家
        flag = 0
        this.delete(k)
      }
      // 无论淘汰与否,让下一个玩家报数
      k = k.after
    }
    return `幸存者:${k.index}`
  }
}

new Cycle(100).play(3)

    概念:它不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去顺序表可随机存取的优点。

为了保证环的完整,需要一个起点和一个终点,这两个点在逻辑上是相邻的

    若要删除元素,则需要

四、问题拓展

    (a1,a2,…..,an)

 

五、元素的插入和删除

就在我为之苦恼的时候,一位同事在我身旁经过,突然说了一句:“咦,这不是约塞夫问题吗?”

 

最开始我按照自己的思路,模拟了整个过程

    克服了单向性缺电,双向链表的结点中有两个指针域,其一指向直接后继,另一个指向直接前驱。 

一、面试题

数据元素之间不要求在存储空间中连续

在整个游戏过程中,我们只需要关心环的完整(起点、终点、玩家的前驱与后继)就可以了

9159.com 5

 

假设有100人,分别编号 1~100

三、递归算法 

class Player { // 创建玩家
  constructor(n) {
    this.index = n; // 玩家编号
    this.before = {}; // 前一个玩家
    this.after = {}; // 后一个玩家
  }
}

不过这种方法最容易理解

本文由9159.com发布于前端,转载请注明出处:玩家所报数信息以及密码信息,约塞夫问题

关键词: