约瑟夫问题

莣囨孓love

约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
[基本要求] 　　利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号

怎么可能

#include <cstdlib> #include <ctime> #include <iostream> using namespace std;
struct Person { int secretNumber; int position; int current_position; Person * right; Person * left; };
class Josephu { private: int total; // How many persons total int n; // How many persons current Person * person; int m; // at the begin we set the m value Person * current;; public: Josephu(); void set_the_number_of_persons(); bool createJosephuCircle(); void set_m_value(); Person * bau_shu(int & m); void run_Josephu(); ~Josephu(); };
Josephu::Josephu() { total = 0; n = 0; person = NULL; m = 0; current = NULL; } void Josephu::set_the_number_of_persons() { cout<<"Please enter the number of persons total.\n"; cout<<"The total number of persons is "; cin>>total; n = total; } bool Josephu::createJosephuCircle() { person = new Person[total]; if(person == NULL) return false;
srand( (unsigned)time( NULL ) ); for(int j = 0; j<n; j++) { person[j].secretNumber = rand()+1; person[j].position = person[j].current_position = j; if(j == 0) { current = person; person[j].left = &person[j+1]; person[j].right = &person[n-1]; } else if(j == n-1) { person[j].left = &person[0]; person[j].right = &person[j-1]; } else { person[j].left = &person[j+1]; person[j].right = &person[j-1]; } } return true; } void Josephu::set_m_value() { cout<<"please enter the first m value.\n"; cout<<" m = "; cin>>m; } Person * Josephu::bau_shu(int & m) { Person * aus; Person * temp; Person * next; int offset = (m)%n?(m)%n-1:n-1; temp = current; for(int i = 0; i<offset; i++) { temp = temp->left; } aus = temp; current = aus->left; aus->right->left = aus->left; aus->left->right = aus->right; m = aus->left->secretNumber;
next = aus->left; for(i = current->current_position; i<n; i++) { (next->current_position)--; next = next->left; } cout<<aus->position<<" "; n--; return current; } void Josephu::run_Josephu() { while(n != 1) { bau_shu(m); } } Josephu::~Josephu() { if(person && total>1) delete [] person; else delete person; }
int main() { Josephu aJosephu; aJosephu.set_the_number_of_persons(); aJosephu.createJosephuCircle(); // create a Josephu Circle with 10 member aJosephu.set_m_value(); // set the m value at the begin aJosephu.run_Josephu(); cout<<endl; system("pause"); return 0; }

为爱种菜！

谢谢斑主，我对它进行了一个小修改（主要是报数的函数），又发生错误了，希望指教？？
#include <cstdlib> #include <ctime> #include <iostream> using namespace std;
struct Person { int secretNumber; int position; int current_position; Person * right; Person * left; };
//约瑟夫 类 class Josephu { private: int total; // How many persons total int n; // How many persons current Person * person; int m; // at the begin we set the m value Person * current;
public: Josephu(); void set_the_number_of_persons(); bool createJosephuCircle(); void set_m_value(); Person* bau_shu(int & m); void run_Josephu(); ~Josephu(); }; //构造
Josephu::Josephu() { total = 0; n = 0; person = NULL; m = 0; current = NULL; }
//人的个数 void Josephu::set_the_number_of_persons() { cout<<"Please enter the number of persons total.\n"; cout<<"The total number of persons is "; cin>>total; n = total; }
//构造环 bool Josephu::createJosephuCircle() { person = new Person[total];//声明的一个数组， if(person == NULL) return false;
cout<<"输入每个人的密码"; for(int i = 0; i<n; i++) { cin>>person[i].secretNumber;}
for(int j = 0; j<n; j++) { person[j].position = person[j].current_position = j+1; if(j == 0) { current = person; person[j].left = &person[j+1]; person[j].right = &person[n-1]; } else if(j == n-1) { person[j].left = &person[0]; person[j].right = &person[j-1]; } else { person[j].left = &person[j+1]; person[j].right = &person[j-1]; } } return true; }
//m的值
void Josephu::set_m_value() { cout<<"please enter the first m value.\n"; cout<<" m = "; cin>>m; }
//报数过程 Person* Josephu::bau_shu(int & m) { Person * aus; Person * temp;
temp = current; for(int i = 0; i<m; i++) { temp = temp->left; } current=temp; aus = temp->right;
m=aus->secretNumber;
cout<<aus->position<<" ";
aus->right->left=temp; temp->right=aus->right; delete aus; n--; return current; }
// void Josephu::run_Josephu() { while(n !=0) { bau_shu(m); } } //夕构 Josephu::~Josephu() { if(person && total>1) delete [] person; else delete person; }
int main() { Josephu aJosephu; aJosephu.set_the_number_of_persons(); aJosephu.createJosephuCircle(); // create a Josephu Circle with 10 member aJosephu.set_m_value(); // set the m value at the begin aJosephu.run_Josephu(); cout<<endl; system("pause"); return 0; }

酷aiq兒kuku

将 bao_shu 函数中那个 delete 语句去掉就可以了。
这个程序是通过 指针 来左右连接彼此，当一个人出局之后，就被环上卸除下来，指针重新连接，这样这个出局的人就不在环上了。当程序结束后，调用 析构函数，完整的 delete 整个object.

qz沒愛過mm

感谢！佩服！
但是如果我把析构函数去掉，把bao_shu中的delete语句留下，也就是说一个个的删除节点，为什么不可以呢？
还有我对版主的技术佩服，对你的乐于助人感谢。不知有没方便些的办法联系版主呢。比如QQ，或者我发邮件给你请教问题可以吗？？

青苹果

考虑到 QQ 对中国人民的感情侮辱，我已经退出 QQ , 决不再使用 QQ.
如果有朋友要个人联系我，可以通过 Email 与我联系。Email : kaihua1@yahoo.com
不过，在这里提问题有一个好处，大家都可以看到，这样，别的斑竹，别的朋友都可以及时回答你的问题。别人也可以通过你的问题得到学习。当然，我也会在这里尽量回答大家的问题。
来回答你的那个delete 问题，为什么我们不能随意删除一个连表中的某一个节点，因为这样将破坏整个连表体系。当然要删除一个连表中的某一个节点是有办法的。通过一个 temp 连表，来分段copy 原连表，仅仅漏掉那个要删除的节点，这样我们得到所需要的连表，再将原连表整体删除，再通过 new 创立新的连表，再将 temp 连表 copy 到那个新的连表。最终删除那个起辅助作用的 temp 连表。
在上面的那个问题中没有那个删除某个节点的必要，所以完全不必这样做。

Ｉしovのyou

感谢！
问题1：QQ哪里.对中国人民感情侮辱？
2：这个问题你是用双向链表实现的，可以用单向循环链表实现吗？

※随风飘荡※

问题1： 如果你时常登陆其他网站，对这样的消息就不会陌生了， 比如，如果你在 QQ 使用 钓鱼岛，将被拒绝，而冠之于日本名将被接受。
问题2：可以的。

水清苓

我查了相关的资料，QQ确实有个样的错误，而且很明白是故意将这几个“关键字”屏蔽掉的，真不明白人家国外的软件欺负我们中国人我们没办法，但是一个受众人认可并使用众多的国产软件怎么会这样，难道QQ真的以为中国人没它不行？

小猫钓鱼tp

问版主一个比较垃圾的问题#include <cstdlib>有什么用啊
我把它注释掉了怎么还可以运行啊