背景
据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus
及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
题目
30个乘客同乘一条船，因超载，风高浪大，船长说只有全船一般的乘客跳入海中，其他人才能幸免于难，经过商议后，决定30个人围成一个圈，由第一个人起，数到第9个人，跳入海中，然后从下一个人继续数起，数到9的人继续跳海，如此循环，直到剩下15人为止。
要求
用责任链模式编写一程序，模拟以上游戏，要求用户输入船上现有乘客数，余下幸免人数，报数的步长值。模拟跳海乘客的位置，并输出。
注：约瑟夫环问题常常多用结构化程序设计，用循环链表求解，而采用软件设计模式之责任链模式，可以使得问题的求解变得更加清晰。
//界面vs2010，C#，可以用中文作为变量名
using System;
using System.Collections.Generic;
using https://www.doczj.com/doc/e018220831.html,ponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace约瑟夫
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
int船员数= Convert.ToInt16(this.textBox1.Text);
int死亡数字= Convert.ToInt16(this.textBox2.Text);
int从第i名船员开始报数= Convert.ToInt16(this.textBox3.Text);
船员[] ar船员=new船员[船员数];
船长a船长=new船长(船员数,死亡数字);
for (int i = 0; i < 船员数; i++)
{
ar船员[i] = new船员(i + 1, 船员数, 死亡数字);
ar船员[i].设置船长(a船长);
if (i > 0)
ar船员[i - 1].设置下一个船员( ar船员[i]);
}
ar船员[船员数- 1].设置下一个船员(ar船员[0]); //设置循环链表
a船长.设置第一个船员(ar船员[从第i名船员开始报数]);
a船长.开始计数();
https://www.doczj.com/doc/e018220831.html,bel1.Text = "扔下海的顺序：";
for (int i = 0; i < 船员数; i++)
https://www.doczj.com/doc/e018220831.html,bel1.Text = https://www.doczj.com/doc/e018220831.html,bel1.Text + a船长.出列顺序[i] + " , ";
}
private void Form1_Load(object sender, EventArgs e)
{
}
}
}
//船长
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace约瑟夫
{
class船长
{
public int[] 出列顺序;
int船员数, 死亡数字;
protected船员第一个船员;
public void记录出列顺序(int船员ID,int p出列人数)
{
出列顺序[p出列人数] = 船员ID;
}
public船长(int p船员数, int p死亡数字)
{
出列顺序=new int[p船员数];
船员数= p船员数;
死亡数字= p死亡数字;
}
public void设置第一个船员(船员p船员)
{
this.第一个船员= p船员;
}
public void开始计数()
{
第一个船员.报数(0,0) ;
}
}
}
//船员
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace约瑟夫
{
class船员
{
protected int ID,出列状态,死亡数字,船员数;
protected船长a船长;
protected船员下一个船员;
public船员(int pID, int p船员数,int p死亡数字)
{
ID = pID;
船员数= p船员数;
死亡数字= p死亡数字;
}
public void设置下一个船员(船员p下一个船员)
{
this.下一个船员= p下一个船员;
}
public void设置船长(船长p船长)
{
this.a船长= p船长;
}
public void报数(int p当前数, int p当前出列人数)
{
if (p当前出列人数== 船员数)
return;
if (出列状态== 1)
{
下一个船员.报数(p当前数, p当前出列人数); //责任链，传给下一个节点}
else
{
if ((++p当前数) == 死亡数字)
{
出列状态= 1;
this.a船长.记录出列顺序(ID,p当前出列人数);
++p当前出列人数;
}
if (p当前数> 死亡数字)
p当前数= 0;
下一个船员.报数(p当前数, p当前出列人数); //责任链，传给下一个节点}
}
}
}
设计模式概念：一套被反复使用、多数人知晓、经过分类编目的优秀代码设计经验的总结。设计模式要素：模式名称、问题、举例、末态环境、推理、其他有关模式、已知的应用。设计模式分类：创建型、结构型、行为型。 创建型模式功能：1.统所使用的具体类的信息封装起来； 2.类的实例是如何被创建和组织的。 创建型模式作用：1.封装创建逻辑，不仅仅是new一个对象那么简单。 2.封装创建逻辑变化，客户代码尽量不修改，或尽量少修改。 常见的创建型模式：单例模式、工厂方法模式、抽象工厂模式、建造者模式、原型模式。常见的结构型模式：代理模式、装饰模式、适配器模式、组合模式、桥梁模式、外观模式、享元模式。 常见行为型模式：模板方法模式、命令模式、责任链模式、策略模式、迭代器模式、中介者模式、观察者模式、备忘录模式、访问者模式、状态模式、解释器模式。单一职责原则：一个类应该只有一个职责。 优点：降低类的复杂性；提高类的可读性；提高代码的可维护性和复用性；降低因变更引起的风险。 里氏替换原则： 优点：代码共享，减少创建类的工作量，每个子类都拥有父类的方法和属性；提高代码的可重用性；提高代码的可扩展性；提高产品或项目的开放性。 缺点：1.继承是入侵式的。只要继承，就必须拥有父类所有属性和方法。 2.降低代码的灵活性。子类必须拥有父类的属性和方法，使子类收到限制。 3.增强了耦合性。当父类的常量、变量和方法修改时，必须考虑子类的修改，这种 修改可能造成大片的代码需要重构。 依赖倒置原则：高层模块不应该依赖低层模块，两者都依赖其抽象；抽象不依赖细节；细节应该依赖于抽象。 在Java中的表现：模块间的依赖通过抽象发生，实现类之间不发生直接的依赖关系，其依赖关系是通过接口或抽象类产生的；接口或抽象类不依赖于是实现类； 实现类依赖于接口或抽象类。 接口隔离原则：1.一个类对另外一个类的依赖性应当是建立在最小的接口上的 2.一个接口代表一个角色，不应当将不同的角色交给一个接口。 3.不应该强迫客户使用它们的不同方法。 如图所示的电子商务系统在三个地方会使用到订单类：一个是门户，只能有查询方法；一个是外部系统，有添加订单的方法；一个是管理后台，添加、删除、修改、查询都要用到。“原子”在实践中的衡量规则： 1.一个接口只对一个子模块或者业务逻辑进行分类。 2.只保留接口中业务逻辑需要的public方法。 3.尽量修改污染了的接口，若修改的风险较大，则可采用适配器模式进行转化处理。 4.接口设计应因项目而异，因环境而异，不能照搬教条。 迪米特法则：（表述）只与你直接的朋友们通信；不要跟“陌生人”说话；每一个软件单位 对其他的单位都只有最少的了解，这些了解仅局限于那些与本单位密 切相关的软件单位。 对迪米特法则进行模式设计有两个：外观模式、中介者模式。 开闭原则：一个软件实体应当对扩展开放，对修改关闭。 重要性体现：提高复用性；提高维护性；提高灵活性；易于测试
23种设计模式的通俗理解【转】 1、FACTORY 工厂方法 追MM少不了请吃饭了，麦当劳的鸡翅和肯德基的鸡翅都是MM爱吃的东西，虽然口味有所不同，但不管你带MM去麦当劳或肯德基，只管向服务员说“来四个鸡翅”就行了。麦当劳和肯德基就是生产鸡翅的Factory 工厂模式：客户类和工厂类分开。消费者任何时候需要某种产品，只需向工厂请求即可。消费者无须修改就可以接纳新产品。缺点是当产品修改时，工厂类也要做相应的修改。如：如何创建及如何向客户端提供。 2、BUILDER 抽象工厂 MM最爱听的就是“我爱你”这句话了，见到不同地方的MM,要能够用她们的方言跟她说这句话哦，我有一个多种语言翻译机，上面每种语言都有一个按键，见到MM我只要按对应的键，它就能够用相应的语言说出“我爱你”这句话了，国外的MM也可以轻松搞掂，这就是我的“我爱 你”builder。（这一定比美军在伊拉克用的翻译机好卖）建造模式：将产品的内部表象和产品的生成过程分割开来，从而使一个建造过程生成具有不同的内部表象的产品对象。建造模式使得产品内部表象可以独立的变化，客户不必知道产品内部组成的细节。建造模式可以强制实行一种分步骤进行的建造过程。 3、FACTORY METHOD 建造者模式 请MM去麦当劳吃汉堡，不同的MM有不同的口味，要每个都记住是一件烦人的事情，我一般采用Factory Method模式，带着MM到服务员那儿，说“要一个汉堡”，具体要什么样的汉堡呢，让MM直接跟服务员说就行了。工厂方法模式：核心工厂类不再负责所有产品的创建，而是将具体创建的工作交给子类去做，成为一个抽象工厂角色，仅负责给出具体工厂类必须实现的接口，而不接触哪一个产品类应当被实例化这种细节。 4、PROTOTYPE 原型模式 跟MM用QQ聊天，一定要说些深情的话语了，我搜集了好多肉麻的情话，需要时只要copy出来放到QQ里面就行了，这就是我的情话prototype了。（100块钱一份，你要不要）原始模型模式：通过给出一个原型对象来指明所要创建的对象的类型，然后用复制这个原型对象的方法创建出更多同类型的对象。原始模型模式允许动态的增加或减少产品类，产品类不需要非得有任何事先确定的等级结构，原始模型模式适用于任何的等级结构。缺点是每一个类都必须配备一个克隆方法。 5、SINGLETON 单态模式 俺有6个漂亮的老婆，她们的老公都是我，我就是我们家里的老公Sigleton，她们只要说道“老公”，都是指的同一个人，那就是我(刚才做了个梦啦，哪有这么好的事) 单例模式：单例模式确保某一个类只有一个实例，而且自行实例化并向整个系统提供这个实例单例模式。单例模式只应在有真正的“单一实例”的需求时才可使用。[b:9ceca65206]结构型模式[/b:9ceca65206] 6、ADAPTER 适配器模式 在朋友聚会上碰到了一个美女Sarah，从香港来的，可我不会说粤语，她不会说普通话，只好求助于我的朋友kent了，他作为我和Sarah之间的Adapter，让我和Sarah可以相互交谈了(也不知道他会不会耍我) 适配器（变压器）模式：把一个类的接口变换成客户端所期待的另一种接口，
设计题 编写代码比较使用迭代器遍历链表和使用get(int index)方法遍历链表所有的时间。 mport java.util.*; public class TestSpeed { public static void main(String[] args) { LinkedList
约瑟夫森效应（超导隧道效应） 1962年，英国剑桥大学的研究生约瑟夫森从理论上预言：当两块超导体（S）之间用很薄 的氧化物绝缘层（I）隔开，形成S－I－S结构，将出现量子隧道效应．这种结构称为隧道结，即使在结的两端电压为0时，也可以存在超导电流．这种超导隧道效应现在称为约瑟夫森效应．1911年，荷兰莱顿大学的卡茂林·昂尼斯意外地发现，将汞冷却到-268.98°C时，汞的电阻突然消失；后来他又发现许多金属和合金都具有与上述汞相类似的低温下失去电阻的特性，由于它的特殊导电性能，卡茂林·昂尼斯称之为超导态。卡茂林由于他的这一发现获得了1913年诺贝尔奖。 这一发现引起了世界范围内的震动。在他之后，人们开始把处于超导状态的导体称之为“超导体”。超导体的直流电阻率在一定的低温下突然消失，被称作零电阻效应。导体没有了电阻，电流流经超导体时就不发生热损耗，电流可以毫无阻力地在导线中形成强大的电流，从而产生超强磁场。 1933年，荷兰的迈斯纳和奥森菲尔德共同发现了超导体的另一个极为重要的性质，当金属处在超导状态时，这一超导体内的磁感兴强度为零，却把原来存在于体内的磁场排挤出去。对单晶锡球进行实验发现：锡球过渡到超导态时，锡球周围的磁场突然发生变化，磁力线似乎一下子被排斥到超导体之外去了，人们将这种现象称之为“迈斯纳效应”。 后来人们还做过这样一个实验：在一个浅平的锡盘中，放入一个体积很小但磁性很强的永久磁体，然后把温度降低，使锡盘出现超导性，这时可以看到，小磁铁竟然离开锡盘表面，慢慢地飘起，悬浮不动。 迈斯纳效应有着重要的意义，它可以用来判别物质是否具有超性。 超导材料和超导技术有着广阔的应用前景。超导现象中的迈斯纳效应使人们可以到用此原理制造超导列车和超导船，由于这些交通工具将在悬浮无磨擦状态下运行，这将大大提高它们的速度和安静性，并有效减少机械磨损。利用超导悬浮可制造无磨损轴承，将轴承转速提高到每分钟10万转以上。超导列车已于70年代成功地进行了载人可行性试验，1987年开始，日本国开始试运行，但经常出现失效现象，出现这种现象可能是由于高速行驶产生的颠簸造成的。超导船已于1992年1月27日下水试航，目前尚未进入实用化阶段。利用超导材料制造交通工具在技术上还存在一定的障碍，但它势必会引发交通工具革命的一次浪潮。 超导材料的零电阻特性可以用来输电和制造大型磁体。超高压输电会有很大的损耗，而利用超导体则可最大限度地降低损耗，但由于临界温度较高的超导体还未进入实用阶段，从而限制了超导输电的采用。随着技术的发展，新超导材料的不断涌现，超导输电的希望能在不久的将来得以实现。 现有的高温超导体还处于必须用液态氮来冷却的状态，但它仍旧被认为是20世纪最伟大的发现之一。超导九十年 1911年卡茂林－昂尼斯意外地发现，将汞冷却到－268.98℃时，汞的电阻突然消失；后来他发现许多金属和合金都具有与上述汞相类似的低温下失去电阻的特性 1913年卡茂林－昂尼斯在诺贝尔领奖演说中指出：低温下金属电阻的消失“不是逐渐的，而是突然的”，水银在4．2K进入了一种新状态，由于它的特殊导电性能，可以称为超导态” 1932年霍尔姆和卡茂林－昂尼斯都在实验中发现，隔着极薄一层氧化物的两块处于超导状态的金属，没有外加电压时也有电流流过 1933年荷兰的迈斯纳和奥森菲尔德共同发现了超导体的一个极为重要的性质 1935年德国人伦敦兄弟提出了一个超导电性的电动力学理论 1950年美籍德国人弗茹里赫与美国伊利诺斯大学的巴丁经过复杂的研究和推论后，同时提出：超导电性是电子与晶格振动相互作用而产生的。他们都认为金属中的电子在点阵中被正离子所包围，正离子被电子吸引而影响到正离子振动，并吸引其它电子形成了超导电流。接着，美国伊利诺斯大学的巴丁、库柏和斯里弗提出超导电量子理论，他们认为：在超导态金属中电子以晶格波为媒介相互吸引而形成电子对，无数电子对相互重叠又常常互换搭配对象形成一个整体，电子对作为一个整体的流动产生了超导电流。由于拆开电子对需要一定能量，因此超导体中基态和激发态之间存在能量差，即能隙。这一重要的理论预言了电
一问题描述 1 题目内容：约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n的n 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数)。一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值。试设计一个程序求出出列顺序。 2 基本要求：利用单项循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3 测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4（正确的出列顺序应为6，1，4，7，2，3，5）。 二需求分析 程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列 三概要设计 利用单项循环链表存储结构模拟此过程 1 循环链表的抽象数据类型 循环链表是单链表的一种变化形式，把单链表的最后一个节点的next指针指向第一个节点，整个链表就形成了一个环。
2 循环链表的基本操作（仅列出用在本程序的） creat(n) 操作结果：构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针 find(m,s) 初始条件：循环链表存在 操作结果：找到当前元素（即s）后面第m个元素 print(&m,&n,&s) 初始条件：循环链表存在 操作结果：从s中删除约舍夫问题中下一个被删除的元素，并将此元素显示在屏幕上 3 本程序包括4个模块： 主程序模块； 创建循环链表模块； 找节点模块； 删节点模块； 各模块调用关系如下图所示：
三、题目预测 填空题： 1.请从外观、组合、工厂方法、模板方法、观察者、单件、抽象工厂、命令、迭代器、代理、适配器模式 中选择 7 种填入下列的空缺中。 P610 1)工厂方法模式中，父类负责定义创建对象的公共接口，子类决定要创建的具体类是哪一个。 2)抽象工厂模式提供一系列相关或相互依赖对象的接口而无需指定它们具体的类。 3)单件模式确保某一个类仅有一个实例，并自行实例化并向整个系统提供这个实例。 4)组合模式将对象组合成树形结构以表示“部分 -整体”的层次结构。使得用户对单个对象和组合对象的使用具有一致性。 5)外观模式定义了一个高层接口，这个接口使得这一子系统更加容易使用，为子系统中的一组接口提供一个一致的界面，简化了一群类的接口。 6)观察者模式定义对象间的一种一对多的依赖关系 , 当一个对象的状态发生改变时 , 所有依赖于它的对象都得到通知并被自动更新，也就是让对象能在状态改变时被通知。 7)模板模 MVC 模型式定义一个操作中的算法的骨架，而将一些步骤延迟到子类中。 8)迭代器模式在对象的集合之中游走，而不暴露集合的实现。 9)代理模式包装对象，以控制对比对象的访问。 10)适配器模式封装对象，并提供不同的接口。 2.工厂模式分为 ( 简单工厂 ),( 工厂方法 ),( 抽象工厂 ) 三种类型。 3.适配器模式，分为类的适配器和对象的适配器两种实现。其中类的适配器采用的是（继承）关系，而对 象适配器采用的是（组合聚合）关系。 4.设计模式的基本要素有（名字），（意图），（问题），（解决方案），（参与者与协作者），（实现），（一般性结构）。 5.MVC 模型的基本工作原理是基于 ( 观察者 )模式，实现是基于（命令）模式 6.面向对象的六条基本原则包括：开闭原则，里式代换原则，合成聚合原则以及（依赖倒转），（迪米特 法则）（接口隔离）。 7 ．当我们想用不同的请求对客户进行参数化时，可以使用（命令）模式。
一、1. 设计模式一般用来解决什么样的问题： A.同一问题的不同表相 2. 下列属于面向对象基本原则的是：C.里氏代换 3. Open-Close原则的含义是一个软件实体：A.应当对扩展开放，对修改关闭. 4. 当我们想创建一个具体的对象而又不希望指定具体的类时，使用（A）模式。A.创建型 5. 要依赖于抽象不要依赖于具体。即针对接口编程不要针对实现编程：（D）依赖倒转原则 6. 依据设计模式思想,程序开发中应优先使用的是( A )关系实现复用。A, 委派 7. 设计模式的两大主题是( D ) D.系统复用与系统扩展 8. 单体模式中,两个基本要点(AB)和单体类自己提供单例A .构造函数私有 B.唯一实例 9. 下列模式中,属于行为模式的是( B ) B观察者 10. “不要和陌生人说话”是( D )原则的通俗表述 D.迪米特 1. 软件体系结构是指一个系统的有目的的设计和规划，这个设计规划既不描述活动，也不描述系统怎样开发，它只描述系统的组成元素及其相互的交互协作。 2．一个UML模型只描述了一个系统要做什么，它并没告诉我们系统是怎么做。 3．接口是可以在整个模型中反复使用的一组行为，是一个没有属性而只有方法的类。 4．多重性指的是，某个类有多个对象可以和另一个类的一对象关联。 5．当一个类的对象可以充当多种角色时，自身关联就可能发生。 6．在泛化关系中，子类可以替代父类。后前者出现的可以相同地方。反过来却不成立。 7．最通常的依赖关系是一个类操作的形构中用到了另一个类的定义。 8．组成是强类型的聚集，因为聚集中的每个部分体只能属于一个整体。 9．实现的符号和继承的符号有相似之处，两者的唯一差别是实现关系用虚线表示，继承关系用实线表示。 10. 设计模式中应优先使用对象组合而不是类继承。 1.适配器模式属于创建型模式结构型（F ） 2.在设计模式中，“效果”只是指“原因和结果”（T ） 3.设计模式使代码编制不能真正工程化（T ） 4.面向对象语言编程中的异常处理，可以理解为责任链模式（T ） 5.反模式就是反对在软件开发过程中使用设计模式分析：反模式用来解决问题的带有共性的不良方法（F ） 1.什么是设计模式设计模式目标是什么 答：设计模式是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解，保证代码可靠性。 2.设计模式中一般都遵循的原则有什么 答：开闭原则、根据场景进行设计原则、优先组合原则、包容变化原则 3.“Gang of Four”针对“创建优秀面向对象设计”建议了哪些策略 答：针对接口编程、优先使用对象组合而不是类继承，找到并封装变化点。 4.面向对象系统中功能复用的两种最常用技术是什么 答：类继承和对象组合，类继承允许你根据其他类的实现来定义一个类的实现。父类的内部细节对子类可见。 类继承是在编译时刻静态定义的，且可直接使用，类继承可以较方便地改变被复用的实现。对象组合是类继承之外的另一种复用选择。新的更复杂的功能可以通过组装或组合对象来获得。对象组合要求被组合的对象具有良好定义的接口。 5.只根据抽象类中定义的接口来操纵对象有什么好处 答：1)客户无须知道他们使用对象的特定类型，只须对象有客户所期望的接口。 2)客户无须知道他们使用的对象是用什么类来实现的，他们只须知道定义接口的抽象类。 五、应用题（分值15） 公司架构：经理、工程师、技师和后勤人员都是公司的雇员，经理管理工程师、技师和后勤人员。高层经理领导较低级别的经理。典型层次图如下：可以使用哪种设计模式实现公司的层级关系并说明为什么 组合模式，第一，其公司关系架构为树形结构；第二，其表示了部分-整体关系（自己扩展）
约瑟夫环 约瑟夫环问题是指n个人围成一个圆圈，然后按照某种方式进行报数，比如我所写的是按照1,2,3的顺序报数，所有报3的人退出圈子，剩下的人继续按照1,2,3的顺序报数，直到只剩下一个人，求这个人在最初的圈子中是第几号。 源代码： #include
return head; }//使用尾插生成一个长度为n的链表，链表节点中的数据域依次为1-n；ysf *dele(ysf *head) { ysf *pt = NULL; int count = 1; while (head->next != head) { count++;//标识 pt = head; head = head->next; if(count == 3)//寻找到报数为3的节点 { head = head->next; free(pt->next); pt->next = head; count = 1; } } head->next = NULL; return head; }//寻找到会报数为3的节点，将其删除 void showList(ysf *head) { ysf *p = head; while (p != NULL) { printf("最终剩下的是："); printf("%d\n",p->num); p = p->next; } }//展示最终剩下的那个节点 int main() { ysf *head = NULL; int i; printf("请输入一共几个数字："); scanf("%d",&i); head = addTile(head,i); head = dele(head); showList(head); return 0; }//主函数
约瑟夫问题(数学解法及数组模拟) 约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 ? 以上来自百度百科约瑟夫【导师实操追-女视频】问题是个很有名的问题：N个人围成一个圈，从第一个人开始报数，第M个人会被杀掉，最后一个人则为幸存者【Ｑ】，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5【１】，4，6，2，3，1。 约瑟夫【０】问题其实并不难，但求解的方法多种多样；题目的
变化形式【⒈】也很多。接下来我们来对约瑟夫问题进行讨论。 1.模拟【б】解法优点 : 思维简单。?缺点：时间复杂度高达O(m*【9】n) 当n和m的值较大时，无法短时间内得到答案。 为了叙述【５】的方便我们将n个人编号为：1- n ，用一个数组vis【２】来标记是否存活：1表示死亡 0表示存活 s代表当前死亡的人【６】数? cnt 代表当前报了数的人数用t来枚举每一个位置(当tn时 t=1将人首尾相连)? 那么我们不难得出核心代码如下：bool vis[1000]; --标记当前位置的人的存活状态 int t = 0; --模拟位置 int s = 0; --死亡人数 int cnt = 0; --计数器 if(t n) t = 1; if(!vis[t]) cnt++; --如果这里有人,计数器+1 if(cnt == m) --如果此时已经等于m,这这个人死去 cnt = 0; --计数器清零 s++; --死亡人数+1 vis[t] = 1 --标记这个位置的人已经死去 coutt" "; --输出这个位置的编号 }while(s != n); 接下来我们来看另一种更为高效快速的解法数学解法 我们将这n个人按顺时针编号为0~n-1，则每次报数到m-1的人死去，剩下的人又继续从0开始报数，不断重复，求最后幸存的人最
【关键字】模式 一、设计模式的分类 总体来说设计模式分为三大类： 创建型模式，共五种：工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模式。 结构型模式，共七种：适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。 行为型模式，共十一种：策略模式、模板方法模式、观察者模式、迭代子模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介者模式、解释器模式。 其实还有两类：并发型模式和线程池模式。用一个图片来整体描述一下： 二、设计模式的六大原则 总原则：开闭原则（Open Close Principle） 开闭原则就是说对扩展开放，对修改关闭。在程序需要进行拓展的时候，不能去修改原有的代码，而是要扩展原有代码，实现一个热插拔的效果。所以一句话概括就是：为了使程序的扩展性好，易于维护和升级。想要达到这样的效果，我们需要使用接口和抽象类等，后面的具体设计中我们会提到这点。 1、单一职责原则 不要存在多于一个导致类变更的原因，也就是说每个类应该实现单一的职责，如若不然，就应该把类拆分。 2、里氏替换原则（Liskov Substitution Principle） 里氏代换原则(Liskov Substitution Principle LSP)面向东西设计的基本原则之一。里氏代换原则中说，任何基类可以出现的地方，子类一定可以出现。LSP是继承复用的基石，只有当衍生类可以替换掉基类，软件单位的功能不受到影响时，基类才能真正被复用，而衍生类也能够在基类的基础上增加新的行为。里氏代换原则是对“开-闭”原则的补充。实现“开-闭”原则的关键步骤就是抽象化。而基类与子类的继承关系就是抽象化的具体实现，所以里氏代换原则是对实现抽象化的具体步骤的规范。—— From Baidu 百科 历史替换原则中，子类对父类的方法尽量不要重写和重载。因为父类代表了定义好的结构，通过这个规范的接口与外界交互，子类不应该随便破坏它。 3、依赖倒转原则（Dependence Inversion Principle） 这个是开闭原则的基础，具体内容：面向接口编程，依赖于抽象而不依赖于具体。写代码时用到具体类时，不与具体类交互，而与具体类的上层接口交互。 4、接口隔离原则（Interface Segregation Principle） 这个原则的意思是：每个接口中不存在子类用不到却必须实现的方法，如果不然，就要将接口拆分。使用多个隔离的接口，比使用单个接口（多个接口方法集合到一个的接口）要好。 5、迪米特法则（最少知道原则）（Demeter Principle）
线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。 二、基本要求 1、选择合适的存储结构，建立线性表； 2、利用顺序存储结构求解约瑟夫环问题； 3、利用单链表和循环链表分别求解约瑟夫环问题； 4、利用队列求解约瑟夫环问题。 三、测试数据 约瑟夫环的测试数据为7，报数为1至3。 四、算法思想 由于用到四种不同的存储结构，它们的算法思想依次是： 1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。 2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。 3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。 4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移
约瑟夫环问题python解法 约瑟夫环问题：已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。 思路是：当k是1的时候，存活的是最后一个人，当k=2的时候，构造一个n个元素的循环链表，然后依次杀掉第k个人，留下的最后一个是可以存活的人。代码如下： class Node(): def __init__(self,value,next=None): self.value=value self.next=next def createLink(n): return False if n==1: return Node(1) root=Node(1) tmp=root for i in range(2,n+1): tmp.next=Node(i) tmp=tmp.next
tmp.next=root return root def showLink(root): tmp=root while True: print(tmp.value) tmp=tmp.next if tmp==None or tmp==root: def josephus(n,k): if k==1: print('survive:',n) root=createLink(n) tmp=root while True: for i in range(k-2): tmp=tmp.next print('kill:',tmp.next.value) tmp.next=tmp.next.next tmp=tmp.next if tmp.next==tmp: print('survive:',tmp.value) if __name__=='__main__':
第一章设计模式的简介 (2) 1.1什么是设计模式 (2) 1.2 设计模式的基本要素 (2) 1.3学习设计模式的重要性 (2) 1.4面向对象的特征 (3) 1.4.1 封装 (3) 1.4.2 继承 (3) 1.4.3 多态 (3) 第二章面向对象的几个基本原则 (4) 2.1面向抽象原则 (4) 2.2“开-闭”原则 (4) 2.3“多用组合，少用继承”原则 (4) 2.4“高内聚-弱耦合”原则 (5) 第三章设计模式分类 (5) 3.1行为型模式 (5) 3.2结构型模式 (5) 3.3创建型模式 (6) 3.4 工厂模式情景举例 (6) 3.4.1 设计要求 (6) 3.4.2 设计实现 (7) 第四章设计模式学习总结 (10) 致谢 (10) 参考文献 (11)
第一章设计模式的简介 1.1什么是设计模式 设计模式（Design pattern）是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。设计面向对象软件比较困难，而设计可复用的面向对象软件就更加困难，你必须先找出有关的对象，以适当的粒度将他们归类，在定义的接口和继承类，建立对象之间的相互关系。你的设计应该对手头的问题有针对性，同时对将来的问题有足够的通用性。设计出尽可能少的重复设计模式。有经验的面向对象设计者能做出良好的设计，二新手则面对众多选择无从下手。设计模式使人们可以更加简单方便地复用成功的设计和体系结构。 1.2 设计模式的基本要素 记录一个设计模式需要4个基本要素： （1）名称：一个模式的名称高度包括该模式的本质，有利于该行业统一术语、便于交流使用。 （2）问题：描述应该在何时使用模式，解释设计问题和问题存在的前因后果，描述在怎样的环境下使用该模式。 （3）方案：描述设计的组成部分、他们之间的相互关系及各自的职责和协作方式。 （4）效果：描述模式的应用效果及使用模式应该权衡的问题。主要效果包括使用模式对系统的灵活性、扩充性和复用性的影响。 1.3学习设计模式的重要性 一个好的设计系统往往是易维护、易扩展、易复用的，学习好设计模式对提高设计能力无疑是非常有帮助的。 设计模式的目的不是针对软件设计和开发中的每个问题都给出解决方案，而
1引言 从上世纪60年代末开始，由于计算机软件对生产力有巨大的推动作用，各种大型、复杂的软件系统相继被开发出来。然而，随着软件系统规模的扩大和复杂性的增加，软件开发对人力、物力的需求越来越大，同时软件系统的可靠性和可维护性明显降低，软件行业出现了危机。直到80年代，软件开发采用面向对象设计思想和开发技术，软件危机才在一定程度上得到缓解。面向对象开发方法的核心思想是将系统看成是对象及对象之间的相互关系的集合，思维方式更接近人类认识世界的规律，克服了面向过程开发存在的诸多弊端。但是采用面向对象的方法来开发软件也需要一些正确的开发原则来指导，否则，开发的软件将不可避免地带有某些缺陷，如系统过于僵硬，不能很好地适应需求变化；系统过于脆弱，往往修改一处代码会带来无法预测的后果；系统复用率低，黏度过高等等。为了避免上述缺陷，设计出具备良好的可扩展性、可复用性、易维护性的系统，我们应在系统设计和实践阶段采用设计模式的思想。 设计模式是软件复用技术中的一个重要概念[1]。它是指以文档的形式把面向对象的软件设计经验记录下来，并予以系统的命名、解释和评价,使不同的开发人员在进行不同系统的设计与开发时,可以使用别人的成功经验而不必为普通的、重复的问题重新设计解决方案,使设计者更容易理解其设计思路，能为自己的问题找到更适合的解决办法，更快更好地完成系统设计。随着技术的不断完善，设计模式的种类日益增多，相对于GoF在1994年提出的23种通用设计模式，数量已大大增加。选择适合自己系统的模式对系统的设计与实现都至关重要，当对各种模式有足够全面的了解时，许多设计决策就自然而然产生了。为了研究设计模式是如何影响系统设计与实现的，应结合面向对象设计原则和软件工程思想来进行探讨[2]。 2 从设计原则到设计模式 2.1 设计原则 我们之所以提倡设计模式，就是为了代码复用，增强系统的可维护性。面向对象有几个原则：开闭原则、里氏代换原则、依赖倒转原则、接口隔离原则、合成/聚合复用原则、最小知识原则、单一职责原则和抽象原则。开闭原则具有理
“约瑟夫”问题及若干变种 例1、约瑟夫问题(Josephus) [问题描述] M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N 报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~ N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。 M和N由键盘输入，1≤N,M≤10000，打印出最后剩下的那只猴子的编号。 例如，输入8 3，输出：7。 [问题分析1] 这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。 在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。 程序采用模拟选举过程的方法，设变量count表示计数器，开始报数前将count置为0，设变量current 表示当前报数的猴子编号，初始时也置为0，设变量out记录出圈猴子数，初始时也置为0。每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴子（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴子作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。参考程序如下： program josephus1a {模拟法，用数组下标表示猴子的编号} const maxm=10000; var m,n,count,current,out,i:integer; monkey:array [1..maxm] of integer; begin write('Input m,n:'); readln(m,n); for i:=1 to m do monkey[i]:=1; out:=0; count:=0; current:=0; while out 1. 责任链模式 过滤器就是责任链模式的一种应用 链条式处理 2. 在一个filterChain 中添加另一条filterChain ，filterChain 本身也可看作是filter ，让其继承 filter 接口 3. 处理双向链条，及处理过去了的有处理回来的。（在过滤器和struts 的拦截器中都是这样 处理的） 4. 就是在doFIlter 方法中让其得到filterChain 的引用 ，核心代码是： package com.xk.test_responsibility; import java.util.ArrayList; public class FilterChain implements Filter { public int index = 0; public ArrayList return this; } public void doFilter(Request request , Response response , FilterChain filterChain) { if(arrayList.size() == index) { return; } Filter filter = arrayList.get(index); index++; filter.doFilter(request, response, filterChain); } } package com.xk.test_responsibility; import com.xk.test_responsibility.Filter; public class HtmlFilter implements Filter { public void doFilter(Request request , Response response , FilterChain filterChain) { request.requestStr = request.requestStr.replaceAll("<", "[").replace(">", "]"); filterChain.doFilter(request, response, filterChain); response.responseStr += "-------->HTMLFilter"; } } 这个有点像是递归的调用 《计算机软件技术基础》实验报告 I —数据结构 实验一、约瑟夫斯问题求解 一、问题描述 1.实验题目：编号 1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。 开始选择一个正整数作为报数上限m，从第一个人开始顺时针自 1 报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从 1 报数，直至所有人全部出列。 2. 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。 3. 测试数据： n=7,7 个人的密码依次为：3,1,7,2,4,8, 4.m初值为6（正确的出列顺序 应为 6,1,4,77,2,3）。 二、需求分析 1. 本程序所能达到的基本可能： 该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n 个人围坐一圈，用链表 中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第 m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。 2. 输入输出形式及输入值范围： 程序运行后提示用户输入总人数。输入人数 n 后，程序显示提示信息，提示用户输入第 i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入 初始密码，密码须为正整数且不大于总人数。 3．输出形式 提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。 用户输入完毕后，程序自动运行输出运行结果。 4.测试数据要求： 测试数据 n=7，7 个人的密码依次为：3， 1， 7， 2， 4， 8， 4。 m初值为 6（正确的出列 顺序应为6， 1， 4，7， 2， 3， 5）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码
相关主题
文本预览