拔乱返正拔乱返正
2007年04月08日 Sunday , 2,541 次点击

在网上逛的时候,见有些程序写得实在太烂，那谁谁谁不是说过“这不是挖社会主义墙角，hao社会主义羊毛吗！”比如说下面的约瑟夫环问题吧，下面这个从网上摘下来的算法写得惨不忍睹。

约瑟夫问题的算法，精华在于建立链表和节点出列两个方面，而下面的算法在建立链表的时候居然又用了一个数组，本来很简单的问题搞得很复杂，而且还要限定变量范围，大幅度降低了程序的通用性。在节点出列算法中，我看了半天，又是数组又是链表的，愣是没看明白咋回事。于是俺冲冠一怒，自己写一个，作为拨乱反正的第一声呐喊吧。

从网上摘下来的算法：

约瑟夫(Joseph)环
题目描述：编号为1，2，...，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始，
任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报 数，如此下去，
直至所有人全部出列为止。试设计一个程序求出出列顺序。
*需求分析
利用向循环链表存储结构模拟此过程。程序输入、输出值均为正整数（其中人数限?amp;lt;=30），
程序的功能是按照出列的顺序印出各人的编号。
*测试数据：m=20,n=7,7个人的密码为：3，1，7，2，4，8，4；
*测试结果：出列顺序为6，1，4，7，2，3，5.
*附录（源程序）：

PLAIN TEXT
C++:
  1. //约瑟夫(Joseph)环
  2. #include<iostream.h>
  3. #include<conio.h>
  4. //定义单链存储结构
  5. typedef struct LNode{
  6.     int data;
  7.     struct  LNode   *next;
  8. }LNode,*LinkList;
  9. void main()
  10. {
  11.     int m,n,t[30],j(0);     //定义初始报数上限值m、人数n
  12.     cout<<"输入初始报数上限值m(正整数):";
  13.     cin>>m;
  14.     cout<<"输入人数n(正整数，<=30):";
  15.     cin>>n;
  16.     cout<<"输入各人的密码(以空格符为分隔号):"<<endl;
  17.     for(int i=0;i<n;i++)
  18.         cin>>t[i];    
  19.     LinkList p,head;
  20.     head=new LNode;
  21.     head->data=0;
  22.     head->next=0;
  23.     p=head;
  24. //初始化单向循环链表
  25.     for(i=1;i<n;i++)
  26.     {
  27.         struct  LNode *s=new LNode;
  28.         s->data=i;
  29.         //s->next=0;
  30.         p->next=s;
  31.         p=p->next;    
  32.     }
  33.     p->next=head;
  34. //处理出列顺序
  35.     while(p->data!=p->next->next->data&&j<m)
  36.     {
  37.         if(j==m-1){
  38.             int n=p->next->data;  
  39.             m=t[n];
  40.             j=0;
  41.             cout<<n+1<<endl;
  42.             if(p->data==p->next->next->data)
  43.                 break;            
  44.             p->next=p->next->next;    
  45.         }
  46.         if(p->data==p->next->next->data){
  47.             cout<<p->next->data+1<<endl;    //倒数第二个出列者
  48.             break;  }  
  49.         p=p->next;
  50.         j++;      
  51.     }  
  52.     cout<<p->data+1<<endl;  //最后一个出列者
  53. //暂停  
  54.     getch();
  55. }

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
下面是俺的算法，这里给出两个版本，一个增强版，一个简化版，主要区别在于输出详细程度不一样。而且俺给的注释十分详细

增强版

PLAIN TEXT
C++:
  1. //Joseph Ring 2005 Plus! 简体中文正式版
  2. //解决约瑟夫环问题
  3. //CopyRight 2005 09 23 of Empire_Lenin @ USTC EEIS
  4. //预编译命令
  5. #include "iostream.h"//c++程序的标准输入输出头文件
  6. #include "conio.h"//程序最后用到getch();语句，这是它的头文件
  7. //定义单链存储结构
  8. typedef struct LNode{
  9.     unsigned long serial;//各节点序号，用于输出出列顺序
  10.  unsigned long password;//各节点密码
  11.     struct  LNode   *next;//链表指针
  12. }LNode,*LinkList;
  13. //约瑟夫环主程序
  14. void main()
  15. {
  16.     unsigned long m,n,i;     //定义初始报数上限值m、人数n、循环控制变量i为无符号长整型变量
  17.  cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
  18.  cout<<"                   Joseph Ring 2005 Plus! 简体中文正式版"<<endl;
  19.  cout<<"               CopyRight 2005 09 23 of Empire_Lenin @ USTC EEIS"<<endl;
  20.  cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl<<endl;
  21.     cout<<"输入随机数m(正整数):";
  22.     cin>>m;
  23.     cout<<"输入人数n:";
  24.     cin>>n;
  25.     cout<<"输入各人的密码（密码为正整数，回车确认每一个输入,空格亦可）:"<<endl;
  26.  LinkList p,head;//定义指针变量p和头指针head
  27.     head=new LNode;//开辟头结点，本问题亦可不设头结点，此处为了更容易实现本思想，故设之
  28.     head->serial=0;//以下两行对头结点元素赋值，头结点元素值无意义，赋值为了保证程序的健壮
  29.     head->next=0;
  30.     p=head;//定义指针变量p初始为指向头结点
  31.  LinkList s;//定义指针变量s
  32.  //初始化单向循环链表
  33.     for(i=1;i<=n;i++)
  34.     {
  35.         s=new LNode;//开辟新节点，并将新节点的地址赋给LNode型指针变量s
  36.         s->serial=i;//对新开辟的节点的序号元素赋值
  37.   cin>>s->password;//输入新开辟节点的密码
  38.         p->next=s; //新节点链接入链表
  39.         p=p->next; //指针变量p前进
  40.     }
  41.     p->next=head->next;//将表尾节点链接到表头，完成单向循环链表的建立
  42.  //下面六行语句用于检测链表建立是否和法，正式编译程序时可以略去
  43.  unsigned long j=1;//无符号长整型变量虽然耗费存储空间，但为保证程序健壮性起见，仍设之
  44.  cout<<"根据你的输入，该单向循环链表中每个节点的serial number和password分别如下 :"<<endl;
  45.  while(j<=n){
  46.      cout<<"Node No. "<<j<<" 's serial number is : "<<p->next->serial<<"  "<<"password is : "<<p->next->password<<endl;
  47.   p=p->next;
  48.   ++j;
  49.  }//检测完毕，结果在屏幕上输出，若链表建立正确，则若最终结果有误，错误必出在下面while语句。本段程序可删。
  50.  //链表初始化完成，下面输出出列节点序列
  51.     cout<<endl<<"建立链表成功，出列顺序如下 :"<<endl<<endl;
  52.  p=head;//置LNode型指针变量于头结点处
  53.  unsigned long counter1=1;//计数器，用于显示节点出列序号
  54.  //下面程序段以一个while嵌套语句完成按要求寻找节点、删除、返回数据等操作
  55.  //此种写法思路简洁明确，易读性高，完全优于用数组画蛇添足
  56.  while(n!=0){//节点出列完也就是链表长度递减到0之前，一直执行下述循环
  57.   while(m>n) m=m-n;//如果m值大于链表长度，求出在链表长度范围内的m值
  58.   unsigned long counter2=1;//计数器，用于标记和m值匹配的、指针变量p的移动步数
  59.   while(m!=counter2){//找到和m值匹配的节点
  60.    p=p->next;
  61.    ++counter2;
  62.   }
  63. //下面的cout语句较为拉杂，目的是为了更详细的在屏幕上显示每一步结果，在简化版中将会使用直接打印出列序列的语句
  64.   cout<<"第"<<counter1<<"个出列的节点是链表上第"<<p->next->serial<<"个节点。"<<endl;
  65.   m=p->next->password;//在节点删除之前将该节点的密码赋给m，用以执行下次循环
  66.   p->next=p->next->next;//删除该节点
  67.   --n;//链表长度自减一
  68.   ++counter1;//计数器累进
  69.  }//while语句结束，当不满足循环条件时跳出
  70.  //由于是命令行程序，故使用下面语句防止结果显示后程序马上退出造成看不见结果
  71.  cout<<"按任意键退出本程序  :) ";
  72.     getch();//暂停
  73. }//整个程序到此完毕

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
简化版

PLAIN TEXT
C++:
  1. //Joseph Ring 2005 Lite! 简体中文正式版
  2. //解决约瑟夫环问题
  3. //CopyRight 2005 09 23 of Empire_Lenin @ USTC EEIS
  4. //预编译命令
  5. #include "iostream.h"//c++程序的标准输入输出头文件
  6. #include "conio.h"//程序最后用到getch();语句，这是它的头文件
  7. //定义单链存储结构
  8. typedef struct LNode{
  9.     unsigned long serial;//各节点序号，用于输出出列顺序
  10.  unsigned long password;//各节点密码
  11.     struct  LNode   *next;//链表指针
  12. }LNode,*LinkList;
  13. //约瑟夫环主程序
  14. void main()
  15. {
  16.     unsigned long m,n,i;     //定义初始报数上限值m、人数n、循环控制变量i为无符号长整型变量
  17.  cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
  18.  cout<<"                   Joseph Ring 2005 Lite! 简体中文正式版"<<endl;
  19.  cout<<"               CopyRight 2005 09 23 of Empire_Lenin @ USTC EEIS"<<endl;
  20.  cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl<<endl;
  21.     cout<<"输入随机数m(正整数):";
  22.     cin>>m;
  23.     cout<<"输入人数n:";
  24.     cin>>n;
  25.     cout<<"输入各人的密码（密码为正整数，回车确认每一个输入,空格亦可）:"<<endl;
  26.  LinkList p,head;//定义指针变量p和头指针head
  27.     head=new LNode;//开辟头结点，本问题亦可不设头结点，此处为了更容易实现本思想，故设之
  28.     head->serial=0;//以下两行对头结点元素赋值，头结点元素值无意义，赋值为了保证程序的健壮
  29.     head->next=0;
  30.     p=head;//定义指针变量p初始为指向头结点
  31.  LinkList s;//定义指针变量s
  32.  //初始化单向循环链表
  33.     for(i=1;i<=n;i++)
  34.     {
  35.         s=new LNode;//开辟新节点，并将新节点的地址赋给LNode型指针变量s
  36.         s->serial=i;//对新开辟的节点的序号元素赋值
  37.   cin>>s->password;//输入新开辟节点的密码
  38.         p->next=s; //新节点链接入链表
  39.         p=p->next; //指针变量p前进
  40.     }
  41.     p->next=head->next;//将表尾节点链接到表头，完成单向循环链表的建立
  42.  //链表初始化完成，下面输出出列节点序列
  43.     cout<<endl<<"建立链表成功，出列顺序如下 :"<<endl<<endl;
  44.  p=head;//置LNode型指针变量于头结点处
  45.  unsigned long counter1=1;//计数器，用于显示节点出列序号
  46.  //下面程序段以一个while嵌套语句完成按要求寻找节点、删除、返回数据等操作
  47.  //此种写法思路简洁明确，易读性高，完全优于用数组画蛇添足
  48.  while(n!=0){//节点出列完也就是链表长度递减到0之前，一直执行下述循环
  49.   while(m>n) m=m-n;//如果m值大于链表长度，求出在链表长度范围内的m值
  50.   unsigned long counter2=1;//计数器，用于标记和m值匹配的、指针变量p的移动步数
  51.   while(m!=counter2){//找到和m值匹配的节点
  52.    p=p->next;
  53.    ++counter2;
  54.   }
  55. //此为简化版，使用直接打印出列序列的语句
  56.   if(counter1>=10&&counter1%10==0) cout<<endl;//每输出十个节点换行
  57.   else cout<<p->next->serial<<"    ";//输出出列节点序号
  58.   m=p->next->password;//在节点删除之前将该节点的密码赋给m，用以执行下次循环
  59.   p->next=p->next->next;//删除该节点
  60.   --n;//链表长度自减一
  61.   ++counter1;//计数器累进
  62.  }//while语句结束，当不满足循环条件时跳出
  63.  //由于是命令行程序，故使用下面语句防止结果显示后程序马上退出造成看不见结果
  64.  cout<<endl<<"按任意键退出本程序  :) ";
  65.     getch();//暂停
  66. }//整个程序到此完毕

下面是俺给出的一个验证素数的程序

PLAIN TEXT
C++:
  1. //CopyRight 2005 09 22 of Empire_Lenin @ USTC EEIS
  2. //检验一个数是不是素数
  3. //素数是除了0和1及其自身外不能被别的任何正数整除的数
  4. #include "conio.h"
  5. #include "math.h"
  6. #include "iostream.h"
  7. void main()
  8. {
  9.  unsigned long n;
  10.  unsigned long i;
  11.  cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl<<endl;
  12.  cout<<"              本程序用于判断一个数是不是素数\n";
  13.  cout<<"        CopyRight 2005 09 22 of Empire_Lenin @ USTC EEIS\n\n";
  14.  cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl<<endl;
  15.  cout<<"请输入一个正整数：";
  16.  cin>>n;
  17.  cout<<endl;
  18.  for(i=2;i<=sqrt(n);++i){
  19.   if(n%i!=0) continue;
  20.   else cout<<"这个数不是素数.\n\n"<<"原因是  "<<i<<"*"<<n/i<<"="<<n<<endl<<endl;break;
  21.  }
  22.  if(i>sqrt(n)) cout<<"这是个素数.\n\n";
  23.  getch();
  24. }

Tags :

随机日志

來留言吧!


Please copy the string e0oAZ9 to the field below:

*
To prove you're a person (not a spam script), type the security word shown in the picture. Click on the picture to hear an audio file of the word.
Click to hear an audio file of the anti-spam word

尚未有留言

尚未有留言

留言板RSS 引用 URI

來留言吧!


»