怎样用vb实现约瑟夫环算法?
用面向过程的编程方式(C),对某个给定的n=8与m=3,给出被淘汰出列的旅客编号,以及最终的幸存者。
用面向对象的编程风格(C++),重新处理该约瑟夫问题。
谈谈这两种编程风格的优点。
二、用C语言解约瑟夫问题
1、单链表的创建与输出
#include<stdio.h>
#include<malloc.h>
#define NULL 0
struct node{ /*定义结构体*/
int data;
struct node *next;
};
typedef struct node NODE;/*将该结构体设置成自定义类型*/
NODE *head;/*定义一个指向该结构体的头指针*/
NODE *create(int n)/*创建具有n个结点的单链表*/
{
NODE *p;
int i=1;
head=(NODE *)malloc(sizeof(NODE));
head->next=NULL;
while(i<=n)
{
p=(NODE *)malloc(sizeof(NODE));
p->data=n+1-i;
p->next=head->next;
head->next=p;
i++;
}
return(head);
}
void output(NODE *point)/*输出该链表数据域内的值*/
{
NODE *p;
p=point->next;
while(p!=NULL)
{
printf(“%d “,p->data);
p=p->next;
}
printf(“n”);
}
如果我们写一段main()函数
void main()
{
head=create(8);
output(head);
}
便可以完成创建和输出单链表的工作。
如果将上述创建单链表与输出单链表的工作保存为头文件link1.h,那么在今后需要创建输出类似的单链表时,只需写以下主函数即可。
#inlucde “link1.h”
void main()
{
head=create(8);
output(head);
}
2、循环单向链表的创建与输出
明白了带头指针的单向链表的创建与输出,只需作简单修改便可处理循环单向链表的相关问题。这里我们建立一个新的头文件link2.h,它包含以下几段代码。
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
struct node *next;
};
typedef struct node NODE;
NODE *head;
NODE *create(int n)
{
NODE *p;
int i=1;
p=head=(NODE *)malloc(sizeof(NODE));
head->next=head;/*造循环链表时头指针的指针域设置*/
while(i<=n)
{
p->data=n+1-i;
p->next=head->next;
head->next=p;
i++;
p=(NODE *)malloc(sizeof(NODE));
}
return(head);
}
void output(NODE *point,int n) /*n表示欲输出多少个结点,由于该链表是循环的,可输出无穷项*/
{
NODE *p;
int i=1;
p=point->next;
while(i<=n)
{
printf(“%d “,p->data);
p=p->next;
i++;
}
printf(“n”);
}
3、在循环链表中删除结点并输出被删结点的相关信息
在头文件link2.h中增添新函数del(int n,int m),这里的形参n代表起始结点,m代表报数值。
void del(int n,int m)
{
int i;
NODE *p,*q;
p=head;
/*将指针移到起始结点,即第n个结点*/
i=0;
while(i<n)
{
p=p->next;
i++;
}
/*删除满足报数值的结点*/
while(p->next!=p)
{
i=1;
while(i<m)/*找到符合报数值结点的前一个结点,即第m-1个结点*/
{
p=p->next;
i++;
}
/*先输出,后删除*/
q=p->next;
printf(“%d “,q->data);
p->next=q->next;
free(q);
}
printf(“nonly one %d”,p->data);/*输出仅剩的结点*/
}
4、解决约瑟夫问题的主函数
#include <link2.h>
void main()
{
/*number结点个数,item输出结点的个数,location报数的起始位置,callnum报数值*/
int number,item,location,callnum;
printf(“ninput nose number=”);
scanf(“%d”,&number);
printf(“noutput item=”);
scanf(“%d”,&item);
head=create(number);
output(head,item);
printf(“ninput location=”);
scanf(“%d”,&location);
printf(“ninput callnum=”);
scanf(“%d”,&callnum);
del(location,callnum);
}
三、以类作为结点来处理约瑟夫问题(准C++编程风格)
1、以类作结点的链表建立
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head=NULL,*p,*q;
for(int i=1;i<9;i++)
{
p=new Node;
p->SetData(i);
if(head==NULL)
head=p;
else
q->SetNext(p);
q=p;
}
q=head;
do
{
cout<<“该游客编号为:”<<q->GetData()<<endl;
q=q->GetNext();
}while(q!=NULL);
q=head;
do
{
q=q->GetNext();
delete head;
head=q;
}while(q!=NULL);
}
2、以类作结点的循环链表的建立
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=8;i++)
{
p->SetData(i);
p->SetNext(head);
q->SetNext(p);
q=p;
p=new Node;
}
q=head;
i=1;
do
{
cout<<“该游客编号为:”<<q->GetData()<<endl;
q=q->GetNext();
i++;
}while(i<=10);
}
3、解决约瑟夫问题
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=8;i++)
{
p->SetData(i);
p->SetNext(head);
q->SetNext(p);
q=p;
p=new Node;
}//
p=head;
i=1;
while(i<=8)
{
cout<<p->GetData()<<” “<<endl;
p=p->GetNext();
i++;
}//输出
cout<<endl;
p=head;
while(p->GetNext()!=p)
{
i=1;
while(i<2)
{
p=p->GetNext();//将欲删除点的前一个结点
i++;
}
q=p->GetNext();
cout<<q->GetData()<<endl;//删除循环链表上的结点
p->SetNext(q->GetNext());//将q指针域所指结点的地址赋给p的指针域
p=p->GetNext();
delete q;
}//做循环数数出局游戏
cout<<“nLast One “<<p->GetData()<<endl;
}
四、用标准的面向对象编程风格处理约瑟夫问题(C++编程风格)
//#include “stdafx.h”
#include “iostream.h”
//#define NULL 0
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
Node *Create(int n);//创建含n个结点的循环链表
void Output(Node *p,int n);//输出循环链表头结点为p的后n个结点的信息
Node *Move(Node *p,int n);//将头结点指针前移到n
//从头结点为p的循环链开始,所用的计数为n进行约瑟夫实验
void Josephus(Node *p,int n);
};
Node *Node::Create(int n)
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=n;i++)
{
p->data=i;
p->next=head;
q->next=p;
q=p;
p=new Node;
}
return head;
};
void Node::Output(Node *p,int n)
{
int i=1;
while(i<=n)
{
cout<<p->data<<” “;
p=p->next;
i++;
}
};
Node *Node::Move(Node *p,int n)
{
if(n>1)
{
int i=1;
while(i<n)
{
p=p->next;
i++;
}
}
return p;
};
void Node::Josephus(Node *p,int n)
{
Node *q;
while(p->next!=p)
{
p=Move(p,n-1);
q=p->next;
cout<<q->data<<” “;
p->next=q->next;
p=p->next;
delete q;
}
cout<<“nLast One “<<p->data<<endl;
};
void main()
{ Node A,*head;
head=A.Create(8);
cout<<“nCirclist is “;
A.Output(head,10);
head=A.Move(head,1);
cout<<“nJosephus result is “<<endl;
A.Josephus(head,3);
}
五、对两种编程风格的评述
在进行面向过程的程序设计时,一般首先考虑程序所要实现的功能,然后设计为实现这些功能所必须采取的步骤,这些步骤就是过程。如果一个过程比较复杂而不能直接使用已有的抽象进行实现,则对这个过程进行分解,使分解之后的每一步(更低级的过程)能够直接对应着一条语句。通过将分解之后的一系列过程封装在一个函数抽象中,程序员在特定的时刻只关心有限的细节,这个新的函数抽象比其较低级的抽象更接近问题求解的过程,因而,能够很好地映射问题求解中的过程。如果这个过程出现在许多问题求解中,那么,这个函数抽象就可能被重复利用。
函数是面向过程程序设计的基础,按照结构化程序设计的思想,又可将完成某一复杂工作的函数放在一个头文件,便于我们多次复用。
面向过程的程序设计方法与面向对象的程序设计方法的根本区别在于对待数据和函数的关系上。
在面向过程的程序设计中,数据只被看作是一种静态的结构,它只有等待调用函数来对它进行处理。
在面向对象的程序设计中,将数据和对该数据进行合法操作的函数封装在一起作为一个类的定义。另外,封装还提供了一种对数据访问严格控制的机制。因此,数据将被隐藏在封装体中,该封装体通过操作接口与外界交换信息。
面向对象的思想需要在实践中不断摸索和体会,在以后的程序设计中,可主动运用这种思想去实践。
两个人轮流报数1和2原理?
两个人轮流报数1和2的原理可以使用一个简单的算法来描述,这个算法称为“约瑟夫问题”或“约瑟夫环”。
假设有n个人,编号从1到n,两个人轮流报数1和2,报到2的人被淘汰出局,直到只剩下最后一个人为止。
1. 首先,所有人按顺序站成一个环形排列。
2. 从编号为1的人开始报数,报数过程中,每报到2时,当前报数的人被淘汰出局,从环中移除。
3. 下一个人继续从1开始报数,重复第2步,直到只剩下最后一个人。
这个算法的实现可以使用一个循环队列来模拟环形排列,每次报数2时,将当前人出队,再将其放回队尾,然后轮到下一个人继续报数。
这个问题的解决方法有多种,包括递归和迭代两种方式。迭代方法通常更直观和易于理解,可以使用循环结构来实现。
例如,以下是使用Python语言的迭代方式实现的示例代码:
“`python
def josephus(n):
people = list(range(1, n + 1)) # 创建初始人数列表
index = 0 # 当前报数人的索引
while len(people) > 1:
index = (index + 1) % len(people) # 循环队列,计算下一个报数人的索引
del people[index] # 报到2的人被淘汰出局
return people[0] # 返回最后剩下的人的编号
# 示例用法
n = 10 # 10个人进行报数
winner = josephus(n)
print(“最后胜出的人的编号是:”, winner)
“`
以上代码中的`josephus`函数接受一个参数n,表示参与报数的人数,返回最后剩下的人的编号。
这是一个简单的实现示例,实际应用中可能需要根据具体需求进行调整和扩展。
有关约瑟夫环问题的数学公式!求大神指导!
- 用这个数学公式可以算出来:#include stdio.h#includestdlib.h main() { int n, m, i, s=0; printf("N="); scanf("%d", &n); printf("M="); scanf("%d", &m); for(i=2; i=n; i++) s=(s+m)%i;printf("The winner is %dn", s+1); system("pause");}但是题目要求把中间的编号也要输出来这是题目:输入:5 (n个人报数,n=5)3 (报数m=3)输出:No1: 3 (第1个退出圈子的人编号是3)No2: 1 (第2个退出圈子的人编号是1)No3: 5 (第3个退出圈子的人编号是5)No4: 2 (第4个退出圈子的人编号是2)Last No is: 4 (最后一个人的编号是4)求教怎么用这个数学公式可以输出中间的编号?谢谢大神啦!!!!
- 这个公式算不出来
关于C语言用线性表结构解决约瑟夫环问题
- 约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。以下是我自己编写的源代码,我的链表结点是双向的。#include"stdio.h"#include"stdlib.h"#define elem int typedef struct ListNode{ elem data; struct ListNode *prior; struct ListNode *next;}List;List *CreateList(int n)建立初始线性表{ int i; List *list,*head,*ptr; head=(List*)malloc(sizeof(List)); if(!list) { printf("创建失败!");exit(1); } head-data=1; head-next=head; head-prior=NULL; ptr=head; for(i=1;in;i++) { list=(List*)malloc(sizeof(List)); if(!list) { printf("创建失败!");exit(1); } list-data=i+1; list-next=head; list-prior=ptr; ptr-next=list; ptr=ptr-next; } return head;}void ShowList(List *w)输出线性表{ List *ptr=w; do {printf("%3d",ptr-data); ptr=ptr-next; }while(ptr!=w);}List *Kill(List *w,int a,int b)w表示线性表的总人数,a表示从哪里开始报数,b表示每次数数的个数{ int i; List *ptr=w; List *z; for(i=1;ia;i++) { ptr=ptr-next;ptr指向开始报数的那人 } while(ptr-next!=ptr) { for(i=1;ib;i++) { ptr=ptr-next;ptr指向报数后的那人 } z=ptr-next; ptr-next-prior=ptr-prior; ptr-prior-next=ptr-next; free(ptr); ptr=z; } return w;} void main(){ int m,n,c; List *p; printf("请输入要编号的个数:"); scanf("%d",&m); p=CreateList(m); ShowList(p); printf("n请输入要从哪里开始数数和每次报数的个数:"); scanf("%d%d",&n,&c); Kill(p,n,c); printf("n"); ShowList(p);}为什么输出有时出错,自己感觉如果数到第一个链表时就出错(即循环过程中如果数到头指针并删除后,就不能得到最后结果)
- 你改改如下几处1 Kill函数中最后的return语句改为return ptr;2 main主函数中对Kill的调用处改为p = Kill(p, n, c);你试试看,祝好运。
C语言约瑟夫环切西瓜问题
- 如题,求一个c语言源代码,链表或者指针或者数组都行。x个西瓜按顺时针编号,每隔y个西瓜切掉一个,程序最后将最后一个被切西瓜的编号输出来。比如,当西瓜总数为9时,每隔5个西瓜切掉一个西瓜,那么输出应该是6.2.8.5.4.7.1.3.9,则最后一个被切掉的西瓜是第9个情况比较紧急,拜托了
- #includestdio.h#includestdlib.h#includestring.hint main() { int x,i=0,c=0,y,left=0,*arr; printf("x和y:"); scanf("%d %d",&x,&y); y++; arr=(int*)calloc(x,sizeof(int)); memset(arr,0,x*sizeof(int)); while(leftx) { if(0==arr[i]) c++; if(y==c) { arr[i]=1; left++; 不需要打印切掉的西瓜的编号的话, 注释掉这句 printf("%d ",i+1); if(left==x) printf("n最后留下来的西瓜的编号是:%d",i+1); c=0; } if(++i==x) i=0; } free(arr); return 0;}
c++解决约瑟夫问题
- 题目是用户输入让n个小孩数数,数到5的小孩退出,问最后留下的是第几个小孩。要求是程序中必须使用到类和向量
- #include "stdafx.h"#include"iostream.h"const int n=10;class problem{ public :int a[n+1]; void solve(int m,int s)n="人数 m=报数的上界 s=报数开始的位置 { int i,j,s1; for(i=1;i=n;i++) a[i]=i; s1=s; for( i=n;i=2;i–) { s1=(s1+m-1)%i;求出圏的位置 if(s1==0) s1=i; for(j=s1;j=i-1;j++)一个人出圏后,后面的元素前移 a[j]=a[j+1]; } couta[1];最后一个出圈人 } };void main(int argc, char* argv[]){problem p;p.solve(3,1);}
ACM约瑟夫环问题
- 我的代码哪里格式错误了?
- 最后一个不能有空格要直接换行你这样输出有两个空格,题目意思空开一个,你在输出哪里加个判断的语句就可以解决了
求用c#编写的约瑟夫问题窗体程序
- 要求用循环链表,可以任意输入数字并输出要完整程序
- 我有噢
约瑟夫环问题
- #includestdio.h#includestdlib.htypedef struct LNode{int data;struct LNode *next;}LNode;struct LNode *input(){struct LNode *head,*p1,*p2;head=NULL;p1=(struct LNode*)malloc(sizeof(struct LNode));scanf("%d",&p1-data);if(p1-data!=0)head=p1;while(p1-data!=0){p2=p1;p1=(struct LNode*)malloc(sizeof(struct LNode));p2-next=p1;scanf("%d",&p1-data);}p2-next=head;return head;}struct LNode *deleteDeath(struct LNode *head,int n){struct LNode *p1,*p2;p1=head;if(head==NULL)return head;for(int j=0;jn2;j++){for(int i=0;i8;i++){p2=p1;p1=p1-next;}p2=p1;p2-next=p1-next;}return head;}void print(struct LNode *head){struct LNode *p;p=head;printf("%4d",p-data);p=p-next;while(p!=head){printf("%4d",p-data);p=p-next;}printf("n");}void main(){struct LNode *head,*p;head=input();print(head);p=deleteDeath(head,30);print(p);}删除节点的那一步不进入循环结构,求指点
- #define N 10int yuesefu1(int data[],int sum,int k){ int i=0,j=0,count=0; while(count&lt;sum-1) { if(data[i]!=0)&#47;*当前人在圈子里*&#47; j++; if(j==k)&#47;*若该人应该退出圈子*&#47; { data[i]=0;&#47;*0表示不在圈子里*&#47; count++;&#47;*退出的人数加1*&#47; j=0;&#47;*重新数数*&#47; } i++;&#47;*判断下一个人*&#47; if(i==sum)&#47;*围成一圈*&#47; i=0; } for(i=0;i&lt;sum;i++) if(data[i]!=0) return data[i];&#47;*返回最后一个人的编号*&#47;}void main(){ int data[N]; int i,j,total,k; printf(&quot;&#92;nPlease input the number of every people.&#92;n&quot;); for(i=0;i&lt;N;)&#47;*为圈子里的人安排编号*&#47; { int input; scanf(&quot;%d&quot;,&amp;input); if(input==0) break;&#47;*0表示输入结束*&#47; for(j=0;j&lt;i;j++)&#47;*检查编号是否有重复*&#47; if(data[j]==input) break; if(j&gt;=i&amp;&amp;input&gt;0)&#47;*无重复ehlp记录编号ycgk继续输入*&#47; { data[i]=input; i++; } else printf(&quot;&#92;nData error.Re-input:&quot;); } total=i; printf(&quot;&#92;nYou have input:&#92;n&quot;); for(i=0;i&lt;total;i++) { if(i%10==0) printf(&quot;&#92;n&quot;); printf(&quot;%4d&quot;data[i]); } printf(&quot;&#92;nPlease input a number to count:&quot;); scanf(&quot;%d&quot;y&amp;k); printf(&quot;&#92;nThe last one&#39;s number is %d&quot;,yuesefu1(data,total,k));}...余下全文>>
求解约瑟夫环问题算法
- 求解约瑟夫环问题算法多次执行删除操作,每删除一个元素,都必须移动其他若干元素。现在使用新算法:每个元素出环时,并不执行删除操作,而将相应位置元素值设为空,但计数时必须跳过值为空的元素。实现这种算法,并分析算法执行效率。
- 设环长为n,报数m出列。则,n次输出,两次输出间的距离大于等于m。复杂度O(mn)。但常数较大。#includestdio.h#define MAX 101main(){ int n,m,x[MAX],p,cnt,nn; scanf("%d%d",&n,&m); for(p=1;p=n;++p)x[p]=p; p=1,cnt=0,nn=n; while(nn){ if(x[p])cnt++; if(cnt==m){ printf("%d ",x[p]); x[p]=0,nn–; cnt=0; } p++; if(pn)p=1; }}
循环链表约瑟夫环的问题
- 我的思想是:先建立一个带头结点的循环链表,其中尾巴那个指针不指向Head,而是指向 head -next。建立好之后,key码我选的是n,就让i ++,当i 是n的倍数是,q所指向的节点被删除,直到除头结点外只剩下一个节点为止,为什么我free的时候出错啊,不free则正常运行#includestdio.h#includestdlib.hstruct sql{int number;sql *next;};typedef struct sql sql;void main(){sql *head,*p,*q,*temp;head = p = (sql *)malloc(sizeof(sql));head-next = NULL;int n,j,i = 0;printf("此程序中,报号从1开始,遇到与密码相同的人则退出,直到只剩下一个n请输入多少个人n");scanf("%d",&n);while(in){q = (sql *)malloc(sizeof(sql));q-number = ++i;printf("%d,",q-number);p-next = q;p = q;}p-next = head-next;printf("请输入一个报号的密码n");scanf("%d",&j);p = head -next;q = p-next;i = 2;while(p-next != p){if((i++) % j ==0){temp = p-next;p-next = q-next;free(temp);q = q-next;}else{p = q;q = q-next;}}printf("剩下的编号为:%dn",p-number);
- #include&lt;stdio.h&gt;#include&lt;stdlib.h&gt;#define N 9#define OVERFLOW 0#define OK 1int KeyW[N]={4,7,5,9,3,2,6,1,8};typedef struct LNode{int keyword;struct LNode *next;}LNode,*LinkList;void Joseph(LinkList p,int m,int x){LinkList q;int i;if(x==0)return;q=p;m%=x;&#47;*获取头结点*&#47;if(m==0)m=x;&#47;*取余*&#47;for(i=1;i&lt;=m;i++)&#47;*找到下一个结点*&#47;{p=q;q=p-&gt;next;}p-&gt;next=q-&gt;next;&#47;*移动结点*&#47;i=q-&gt;keyword;&#47;*获取编号*&#47;printf(&quot;%d &quot;,q-&gt;keyword);free(q);&#47;*释放结点*&#47;Joseph(p,i,x-1);&#47;*递归调用*&#47;}int main(){int i,m;LinkList Lhead,p,q;Lhead=(LinkList)malloc(sizeof(LNode));&#47;*申请结点空间*&#47;if(!Lhead)return OVERFLOW;Lhead-&gt;keyword=KeyW[0];&#47;*数据域赋值*&#47;Lhead-&gt;next=NULL;p=Lhead;&#47;*指向头结点*&#47;for(i=1;i&lt;9;i++){if(!(q=(LinkList)malloc(sizeof(LNode))))return OVERFLOW;q-&gt;keyword=KeyW[i];&#47;*数据域赋值*&#47;p-&gt;next=q;p=q;&#47;*移动到下一结点*&#47;}p-&gt;next=Lhead;&#47;*尾结点指向头结点,形成循环链表*&#47;printf(&quot;Please input the first recode m:&#92;n&quot;);scanf(&quot;%d&quot;,&amp;m);&#47;*输入起始位置*&#47;printf(&quot;The output alignment is:&#92;n&quot;);Joseph(p,m,N);&#47;*调用函数*&#47;return OK;}约瑟夫环,已加注释
约瑟夫环问题,求吧代码补充完整
- 注释部分,求补充完整,使之可以正常运行 Josehpus.cpp : main project file.#include "stdafx.h"#includeiostreamusing namespace std;struct Node{ int data; 编号 Node *next;};class LinkList{public: LinkList(); void CreatList(int n); void Josephus(int n,int m);private: Node *rear,*first;};LinkList::LinkList(){ rear=first=NULL;}void LinkList::CreatList(int n){ for(int i=0;in;i++) { Node *q=new Node; q-data=i+1; if(i!=0) 非空表情况 { ………. } else { ………. } }}void LinkList::Josephus(int n,int m){ Node *pre,*p; pre=first;p=first-next; int count=2; while(p!=pre) { ………. } coutp-data" "endl; delete p;}void main(){ int m,n; LinkList L; cout"请输入开始的总人数: "endl; cinn; L.CreatList(n); cout"请输入统一密码:"endl; cinm; cout"出列顺序为:"endl; L.Josephus(n,m);}
- 这个是什么啊