华剑缘
一切都在这个过程中获得,将那些目标埋藏于心中
posts - 19,comments - 20,trackbacks - 0

实验一、Joseph问题

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

这是我们数据结构第一个实验题目。大部分都用C语言写。我用C++写的,写到一半编译通过了,run的时候出了问题。还没有写完,只把用用到的类写了出来。第一次这样写,不知道那里除了问题。

代码:

  1 #include  " iostream.h "
  2 // #include "String.h"
  3
  4
  5
  6 class  PersonList;
  7 class  Joseph;
  8
  9 class  Person {
 10 // friend PersonList;
 11 private :
 12     char  num;
 13     int  value;
 14    //  Person *next;
 15 public :
 16  Person  * next;
 17  Person();
 18     Person( char , int );
 19     Person(Person   & A);
 20 }
;
 21
 22 Person::Person( char  A, int  Val)
 23 {
 24     num = A;
 25     value = Val;
 26
 27 }

 28 Person::Person(Person  & B)
 29 {
 30     num = B.num;
 31     value = B.value;
 32     next = B.next;
 33 }

 34 class  PersonList {
 35 friend Joseph;
 36 public :
 37     Person  * head, * tail;
 38   int  sum;
 39 public :
 40     PersonList();
 41      ~ PersonList();
 42      void  initialPL();
 43      void  insertPl(PersonList  & Pl,Person x);
 44      void  DeleteBlPerson(Person y);
 45      bool  NEmpty();
 46 }
;
 47
 48 PersonList::PersonList()
 49 {
 50  Person  * head = new  Person;
 51  Person  * tail = head;
 52
 53 }

 54
 55 void  PersonList::insertPl(PersonList  & PL,Person x)
 56 {
 57     Person  * p = new  Person(x);
 58     PL.tail -> next = p;
 59     PL.tail = p;
 60     PL.tail -> next = head;
 61
 62 }

 63 void  PersonList::DeleteBlPerson(Person y)
 64 {
 65     Person p =* y.next;
 66  y.next = y.next -> next;
 67
 68 }

 69
 70
 71 class  Joseph {
 72 private :
 73  PersonList List;
 74
 75 public :
 76   char   * JosephList;   //用来存放输出序列
 77  Joseph();
 78
 79
 80 }
;
 81
 82 Joseph::Joseph()
 83 {
 84  PersonList P;
 85  P.initialPL();
 86  cout << " 人数 : " << endl;
 87  cin >> P.sum;
 88   for ( int  i = P.sum;i > 0 ;i -- )
 89   {
 90   cout << " 代号 " << endl;
 91    char  a;
 92   cin >> a;
 93   cout << " " << endl;
 94    int  x;
 95   cin >> x;
 96   Person Z(x,a);
 97   P.insertPl(P,Z);
 98  }

 99
100
101 }

102
103
104
105 int  main()
106 {
107     Joseph B;
108     cout << " 输入 " ;
109
110
111      return   0 ;
112 }

113



 

posted on 2006-12-12 22:59 华剑缘 阅读(310) 评论(3)  编辑 收藏 引用

FeedBack:
# re: 关于约瑟夫环的问题,编不下去了,那位帮忙看看
2006-12-12 23:10 | Dain
今晚不想了
明天写个来  回复  更多评论
  
# re: 关于约瑟夫环的问题,编不下去了,那位帮忙看看
2006-12-13 09:20 | 华剑缘
@Dain
十分感谢  回复  更多评论
  
# re: 关于约瑟夫环的问题,编不下去了,那位帮忙看看
2006-12-13 14:45 | Dain
sorry,没有采用你用的那种结构

#include <iostream>

using namespace std;

void Josephus(int *Child,int n,int m)
{
int i = -1,j = 0,k = 1;
while(1)
{
for(j = 0;j < m;)
{
i = (i + 1) % n;
if(Child[i] != -1)
j++;
}

if(k == n)
break;
cout << Child[i] << "\t";
m = Child[i];
Child[i] = -1;
k++;
}
cout << Child[i] << endl; // the last
}

int main()
{
int *allChild,j,k,l;
cout << "Person Number and Password:" << endl << "\t";
cin >> j >> k;

if((allChild= new int[j])!=NULL)
{
for(l = 0;l < j;l++)
{
cout << l + 1 << "\t";
allChild[l] = l + 1;
}
cout << endl;
}

Josephus(allChild,j,k);

return 0;
}  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理