约瑟夫环的两种设计——结构化设计与OOP | 学习记录
周末赶了一个关于程序设计的作业，题目让我们分别用结构化设计与基于面向对象的设计思路来完成约瑟夫环的问题，刚好顺便复习下链表，以下是一点过程记录。
约瑟夫环的实现
结构化设计
这一块网络上的资料也很多，我这里提供一种方法。总的思路就是使用累加器来记录报数，到指定人数后将对应的人“杀死”，一直循环直至剩下一人，返回存活人的号码。
#include <iostream>
using namespace std;
int main()
{
int nrOfPeople = 100; // 总人数
int nrOfDead = 0; // 死亡人数
int M; // 题目所指定的M，报数报到M即死亡
int index = 0; // 第index个人
int number = 0; // 当前报数
bool survival[nrOfPeople + 1]; // 记录第n个人是否死亡
cout << "Input M ";
cin >> M;
// 初始化，全部人一开始都活着
for (int i = 1; i <= nrOfPeople; i++)
{
survival[i] = true;
}
// 开始筛选
cout << "Dead: ";
do
{
index++;
if (index > nrOfPeople)
index = 1;
if (survival[index])
number++;
if (number == M)
{
number = 0;
cout << index << " ";
survival[index] = false;
nrOfDead++;
}
} while (nrOfDead != nrOfPeople - 1); // 筛选至只剩一人结束
cout << endl;
// 输出幸存的人所处位置
cout << "Left one: ";
for (int i = 1; i <=nrOfPeople; i++)
{
if(survival[i])
{
cout << i << endl;
break;
}
}
return 0;
}
基于面向对象（OOP）
根据我目前对OOP的理解，就是将问题分为许多个小问题，再将其封装成类，一个类解决一个问题。在这个约瑟夫环问题中，我分了三类：
- 整个约瑟夫环的过程（JosephusProblem）
- 约瑟夫环中的人（PeopleInJos）
- 报数器（Number)
和结构化设计解决约瑟夫环的思路类似，将不同的内容分类塞入这三类里。JosephusProblem中，我们要控制游戏的过程，所以相应的初始化，以及需要的变量，包括调用其他两个类的两个变量，总人数、死亡人数，以及一个指向队首的指针（因为我使用了循环链表来存储人）。PeopleInJos中，存放每个人所必须的信息，在这里只有两个，存活与否（isSurvival)和他对应的号码（index），当然，因为类要封装，都必须设置相应的方法来调用到这些私有变量。Number中很简单，就是累加，到点了就返回相应的提示并重置，这个我集成在同一个方法（bool out()）里了。以下是具体代码：
// JosephusProblemOOP.cpp:
#include <iostream>
#include "JosephusProblem.cpp"
using namespace std;
int main()
{
JosephusProblem j(3, 41);
j.initializa();
cout << j.start() << endl;
return 0;
}
// JosephusProblem.cpp:
#pragma once
#include "PeopleInJos.cpp"
#include "Number.cpp"
using namespace std;
class JosephusProblem
{
public:
JosephusProblem()
{
}
JosephusProblem(int M, int N)
{
head = new PeopleInJos(1);
num = new Number(M);
this->nrOfPeople = N;
this->nrOfDead = 0;
}
void initializa()
{
PeopleInJos* temp = head;
for(int i = 2; i <= nrOfPeople; i++)
{
temp->setNext(new PeopleInJos(i));
temp = temp->getNext();
}
temp->setNext(head);
}
int start()
{
int tempI = 0;
currentP = head;
do
{
if (currentP->survival())
{
if(num->out())
{
currentP->kill();
nrOfDead++;
}
}
currentP = currentP->getNext();
} while (nrOfDead != nrOfPeople - 1);
currentP = head;
for (int i = 1; i <= nrOfPeople; i++)
{
if(currentP->survival())
{
return i;
}
currentP = currentP->getNext();
}
return -1;
}
private:
Number* num;
PeopleInJos* head;
PeopleInJos* currentP;
int nrOfPeople;
int nrOfDead;
};
// Number.cpp:
#pragma once
using namespace std;
class Number
{
public:
Number()
{
}
Number(int M)
{
this->currentN = 0;
this->setM = M;
}
bool out()
{
currentN++;
if (currentN >= setM)
{
currentN = 0;
return true;
}
else
{
return false;
}
}
private:
int currentN;
int setM;
};
// PeopleInJos.cpp:
# pragma once
using namespace std;
class PeopleInJos
{
public:
PeopleInJos()
{
}
PeopleInJos(int i)
{
this->isSurvival = true;
this->index = i;
}
PeopleInJos* getNext()
{
return this->next;
}
void setNext(PeopleInJos* next)
{
this->next = next;
}
bool survival()
{
return this->isSurvival;
}
void kill()
{
this->isSurvival = false;
}
private:
PeopleInJos* next;
bool isSurvival;
int index;
};
一些想法
毕竟是开学初，刚开始系统的学习OOP设计思路，也许上面的类划分不够细致，不过程序跑起来后，感觉还是不错的，代码个人看着也还是比较清晰的。当然基于OOP设计的程序还是有点问题的，使用了指针却没有手动内存释放，会导致内存泄漏等。这些就留待下次有空完成吧~