1. 首页
  2. IT资讯

Josephus问题解决方法四(循环数组)

前几篇都是运用了循环单链表的知识解决该问题(http://blog.itpub.net/29876893/viewspace-1815055/http://blog.itpub.net/29876893/viewspace-1850077/http://blog.itpub.net/29876893/viewspace-1851818/),下面用循环数组来解决该问题。运用的解题思路和第三篇类似,给元素设置标识,退出循环的条件就是被标识的元素总数=学生总数。下面给出代码:

点击(此处)折叠或打开

  1. #include<iostream>
  2. #define MAX_SIZE 10
  3. using namespace std;
  4. int j,flag,q,sizeA;
  5. char lastone;
  6. void searchnote(char *,int);
  7. void searchnote(char *A, int n) {
  8.     cout << “出队的顺序依次是:” << endl;
  9.     for (int i = 0;i<=sizeA;i++){ //扫描数组
  10.         
  11.         if (i == sizeA) { //如果循环整个数组后,则取余,构成循环数组
  12.             i%=sizeA;
  13.         }
  14.         if(A[i] == NULL) {
  15.                 continue;
  16.             }
  17.          q++;
  18.             if (q == n) { //若q等于间隔数n,则此时A[i]就是被标识的元素,且q置为0
  19.                 cout << A[i]<< ” “;
  20.                 flag++;
  21.                 if (flag == sizeA) { //该步骤是为了打印最后一个同学编号,否则最后一个同学别标识为NULL
  22.                     lastone = A[i];
  23.                  }
  24.                 A[i] = NULL;
  25.                 q = 0;
  26.             }
  27.             if (flag == sizeA) { //循环退出条件
  28.                 cout << endl;
  29.                 cout << “获胜的同学是:” << endl;
  30.                 cout << lastone;
  31.                 break;
  32.             }
  33.     }
  34. }
  35. int main() {
  36.     cout << “请输入同学的编号:” << endl;
  37.     char note[MAX_SIZE];
  38.     for (char ch; cin >>ch, j++) { //构建数组
  39.         note[j] = ch;
  40.         cout << note[j] << ” “;
  41.         sizeA++;
  42.     }
  43.     cout << endl;
  44.     searchnote(note, 4);
  45.     cout << endl;
  46. }

运行结果:
Josephus问题解决方法四(循环数组)
上面给出的只是解题思路,希望有抛砖引玉的作用,相信读者还有更好的算法。当然该程序有更多的功能可以完善,其中涉及到一些细节给出了简单的注释。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29876893/viewspace-1853008/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:℅傍ㄖ免沦陷dε鬼,转转请注明出处:http://www.cxybcw.com/191816.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code