f1101.cpp
资源名称:c.rar [点击查看]
上传用户:puke2000
上传日期:2022-07-25
资源大小:912k
文件大小:2k
源码类别:

C#编程

开发平台:

Visual C++

  1. //=====================================
  2. // f1101.cpp
  3. // josephus problem procedural solving
  4. //=====================================
  5. #include<iostream>
  6. using namespace std;
  7. //-------------------------------------
  8. struct Jose{                   // 小孩结点
  9.   int code;                    // 小孩编号
  10.   Jose* next;                  // 指向下一个小孩结点
  11. };//-----------------------------------
  12. int n, s, m;
  13. Jose *pCur, *pivot;
  14. //-------------------------------------
  15. bool getValue();
  16. Jose* createRing();          // 创建环链表
  17. void countBoy(int m);        // 数m个小孩
  18. void process();               // 排除n-1个小孩
  19. //-------------------------------------
  20. int main(){
  21.   if(!getValue()) return 1;
  22.   Jose* pJose = createRing();
  23.   process();
  24.   cout<<"nThe winner is "<<pCur->code<<"n";
  25.   delete[] pJose;
  26. }//------------------------------------
  27. bool getValue(){
  28.   cout <<"please input boyNumber, startPosition, intervalNumber:n";
  29.   cin>>n>>s>>m;
  30.   if(n>=2 && s>=1 && s<=n && m>=1 && m<=n)  return true;
  31.   cerr<<"failed in bad boyNumber or startPosition or intervalNumber.n";
  32.   return false;
  33. }//------------------------------------
  34. Jose* createRing(){
  35.   Jose* px = new Jose[n];
  36.   for(int i=1; i<=n; ++i){
  37.     px[i-1].next = &px[i%n];
  38.     px[i-1].code = i;
  39.   }//------------------------
  40.   cout<<"There are "<<n<<" boys.nBoys leaved in order:n";
  41.   pivot = &px[n-2];
  42.   pCur = &px[n-1];
  43.   countBoy(s-1);
  44.   return px;
  45. }//------------------------------------
  46. void countBoy(int m){
  47.   for(int i=0; i<m; ++i){
  48.     pivot = pCur;
  49.     pCur = pivot->next;
  50.   }
  51. }//------------------------------------
  52. void process(){
  53.   for(int i=1; i<n; ++i){
  54.     countBoy(m);
  55.     static int line=0;
  56.     cout<<"  "<<pCur->code;
  57.     if(!(++line%10)) cout<<"n";
  58.     pivot->next = pCur->next;       //小孩脱链
  59.     pCur = pivot;
  60.   }
  61. }//====================================
  62.