约瑟夫问题c 代码链表（有一堆人排成一圈,喊到一个数就出局,最后剩下的人,用c语言用动态链表编程）

本文目录

• 有一堆人排成一圈,喊到一个数就出局,最后剩下的人,用c语言用动态链表编程
• 请教C++约瑟夫问题代码
• 求个约瑟夫循环链表的C++程序
• 约瑟夫问题，怎么用C语言写
• （C语言）用静态链表求解约瑟夫问题
• C++单链表做约瑟夫环
• 约瑟夫环问题的C++算法,求用链表和递归两种方法,尽量详细!

有一堆人排成一圈,喊到一个数就出局,最后剩下的人,用c语言用动态链表编程

这个问题是有名的约瑟夫问题。

假设有n个人参加报数，依次编号1~n。从编号1开始依次报数，从1报到m，报到m的人出列，剩下来的人重新开始报数，报到m的人出列，如此重复直到所有人都出列为止。最后出列的人原来的编号是多少？

链表程序如下：

#include 《stdio.h》
#include《stdlib.h》
struct node
{
int num;
struct node *next;
};
struct node *create(int n)
{
int i;
struct node *p,*head=NULL,*rear;
for(i=0;i《n;i++)
{
p=(struct node *)malloc(sizeof(struct node));
p-》num=i+1;
if(head==NULL)
{
head=p;
rear=p;
}
else
{
rear-》next=p;
rear=p;
}
}
rear-》next=head;
return head;
}
void Del(struct node *head,int n,int m)
{
int i,j;
    struct node *p,*q=head,*front=head;
while(q-》next!=head)
q=q-》next;
for(j=0;j《n;j++)
{
for(i=1;i《m;i++)
{
q=front;
front=front-》next;
}
        printf("%d\t",front-》num);
p=front;
q-》next=front-》next;
front=front-》next;
free(p);
}
}
void main()
{
int m,n;
    struct node *head;
printf("输入报到人数n:");
    scanf("%d",&n);
printf("输入报数终值m:");
    scanf("%d",&m);
head=create(n);
    if(n》0 && m》0)
{
Del(head,n,m);
head=0;
}
}

运行结果：

假设10个人参加报数，报到3的人出列，则出列顺序为

最后出列的是原来编号为4的人。

请教C++约瑟夫问题代码

#include
《iostream.h》
#include《malloc.h》
#include《string.h》
struct
person//定义结构体变量person
{
int
num;//编号
struct
person
*next;//指向自身类型的指针
};
int
main()
{
int
i;
int
m,n;
struct
person
*p1,*p2,*head;
cout《《"请输入总人数n：";
cin》》n;
while(n《1){
cout《《"Input
error!Enter
again:"《《endl;
cin》》n;
}
cout《《"请输入报数m值：";
cin》》m;
p1=(struct
person*)malloc(sizeof(struct
person));//申请首元结点空间
head=p1;
//用head保留链表首元结点地址
p1-》num=1;
p2=p1;
for(i=2;i《=n;)
{
p1=(struct
person*)malloc(sizeof(struct
person));//申请新结点空间
p1-》num=i;
p2-》next=p1;//新结点插入链表尾部
p2=p1;
i++;
}
p1-》next=head;//尾结点的next指向首元结点，形成单循环链表
cout《《"\n\n*****************************\n";
cout《《"出队顺序为：\n";
p1=head;//从首元结点开始访问链表
int
winner;
while(n》=1)//链表不为空
{
for(i=1;i《m;i++)
{
p2=p1;
p1=p1-》next;
}
cout《《p1-》num《《"
";//喊到m的人出列
winner
=
p1-》num;
p2-》next=p1-》next;//链表不断链
free(p1);//释放已删除结点空间
p1=p2-》next;
n=n-1;
}
cout《《"\n\n*****************************\n";
cout《《"得胜者是："《《winner《《endl《《endl;
return
0;
}

求个约瑟夫循环链表的C++程序

#include《iostream》
using namespace std;
//链表结点类number为这个人的编号,key为密码
struct person
{
unsigned int number;
unsigned int key;
person *next;
};
//约瑟夫环类,此类包含多个person类,并控制输入输出.
class joseph_ring
{
private:
unsigned int n;//用于存放人数
unsigned int m;//用于存放初始密码
person *head;//链表的头结点
public:
joseph_ring(){m=0;n=0;head=NULL;}//构造函数,把成员变量赋初值
void create();//建立环的成员函数
void show();//运算并输出的成员函数
};
void joseph_ring::create()
{
cout《《"请输入人数:";
cin》》n;
cout《《"请输入m的初值:";
cin》》m;
//定义2个临时指针
person *p1,*p2;
//for循环中用于初始化环
for(int i=1;i《=n;i++)
{
p1=new person;//新实例化一个"人"的对象
p1-》number=i;//给这个"人"编个号
cout《《"请输入第 "《《i《《"个人对应密码:";
cin》》p1-》key;//给这个"人"一密码
//如果当前链表为空,头结点指向第一个"人"
if(i==1)
{
head=p1;
p2=p1;
}
//否则,p2永远指向尾结点,新建的结点都接到p2之后
else
{
p2-》next=p1;
p2=p1;
}
}
p2-》next=head;//把链表连成一个循环链表(就是一个环)
}
void joseph_ring::show()
{
person *p1,*p2,*p;
p1=head;
//有n个人,所以执行n次循环
for(int i=1;i《=n;i++)
{
int count=1;
//用count定位到第m个出圈人,循环后,p1指向这个出圈人,p2指向这个出圈人的上一个人
while(count++《m)
{
p2=p1;
p1=p1-》next;
}
cout《《p1-》number《《"\t";//输入当前出圈人的编号
m=p1-》key;//把当前出圈人的密码作为指向下一个出圈人所要经过的人数
p=p1;//p指向当前这个出圈人
p2-》next=p1-》next;//把出圈人前的人和出圈人后的人连上.
p1=p1-》next;//下次从当前出圈人的下一个人开始数
delete p;//把出圈人毙掉(就是释放这块内存)
}
cout《《endl;
cin》》m;
}
int main()
{
joseph_ring j;
j.create();
j.show();
return 0;
}

约瑟夫问题，怎么用C语言写

#include《stdio.h》
#include《malloc.h》
typedef struct LNode
{
int number;
int password;
struct LNode *next;
}LNode,*LinkList;
void CreatLink(LinkList &tail,int n) //尾插法建立不带头结点单向循环链表，返回尾指针
{
LNode *head,*p;
for(int i=1;i《=n;i++) //依次输入n个人的密码，建立单向循环链表
{
p=(LNode*)malloc(sizeof(LNode));
p-》number=i;
printf("请输入第%d个人的密码：",i);
scanf("%d",&(p-》password));
if(i==1) //建立第一个结点
{
head=p; tail=p; tail-》next=head;
} //第2-n个结点，插入表尾
tail-》next=p; tail=p; tail-》next=head;
}
/* p=head; //输出链表
while(p-》next!=head)
{
printf("%d ",p-》password);
p=p-》next;
}
printf("%d ",p-》password);*/
}
void joseph(LinkList &tail)
{
int m;
printf("\n请输入一个正整数作为初始报数上限值：");
scanf("%d",&m);
int i=1;
LNode *p=tail-》next,*pre=tail;
printf("\n出圈顺序依次为：");
while(p-》next!=p) //圈中多于1个人时
{
while(i《m) //报数
{
pre=p; p=p-》next; i++;
}
printf(" %d ",p-》number); //报数为m的人数列
m=p-》password;
pre-》next=p-》next;
free(p);
i=1; //从下一个人开始重新报数
p=pre-》next;
}
printf(" %d \n",p-》number); //最后一个人出列
free(p);
}
void main()
{
int n;
printf("\n请输入圈中人数：");
scanf("%d",&n);
LinkList tail;
CreatLink(tail,n);
joseph(tail);
}
额，不知道你看不看的懂

（C语言）用静态链表求解约瑟夫问题

#include
"stdio.h"
//
#include
"conio.h"
#include
"stdlib.h"
#define
MAX
100
typedef
struct
nodes
{
int
data;
nodes*
next;
}Lnode;
/*静态链表节点结构体定义
*/
//
typedef
struct
list
//
{
//
Lnode
node;
//
int
head;
//
}List,*PList;
void
InitList(Lnode*
pHead,int
n)/*n为节点数
*/
{
pHead-》data
=
0;
Lnode*
pPre
=
pHead;
for(int
i=1;
i《n;
++i)
{
Lnode
*pTemp
=
(Lnode*)malloc(sizeof(Lnode));
pTemp-》data
=
i;
pPre-》next
=
pTemp;
pPre
=
pTemp;
if
(i
==
n-1)
{
pTemp
-》next
=
pHead;
}
}
}
void
Searchnode(Lnode
*pHead,
int
n)/*m为报数，n为节点数,start为初始报数序号*/
{
Lnode*
pNext
=
pHead;
Lnode*
pPreNode
=
NULL;
while
(1)
{
for(int
i=0;
i《
n;
++i)
{
pPreNode
=
pNext;
pNext
=
pNext-》next;
}
printf("delete:
%d
",pNext-》data);
if
(pPreNode-》next
==
pNext-》next)
{
break;
}
pPreNode-》next
=
pNext-》next;
free((void
*)pNext);
pNext
=
pPreNode-》next;
}
}
void
main()
{
int
i;
int
n=10,start=1;
Lnode*
pHeadNode
=
(Lnode*)malloc(sizeof(Lnode));
InitList(pHeadNode,
n);
Lnode*
pNext
=
pHeadNode;
for
(i=0;i《10;
++i)
{
printf("%d
",
pNext-》data);
pNext
=
pNext-》next;
}
printf("请输入一个数
");
scanf("%d",
&n);
n
%=
10;
Searchnode(pHeadNode,
n);
getchar();
//
printf("Hello,
world
");
}

C++单链表做约瑟夫环

#include《iostream》
#include《cstdio》
#include《cstring》
using namespace std;
int a;
struct LNode{
    int num;
    LNode *next;
};
LNode *p, *r, *list;
/*利用单向循环链表实现*/
void joseph(int n, int m){//n：总人数；m：报数上限
    printf("\n%d个人报数，上限为%d \n", n, m);
    int i;
    //创建链表
    for (i = 1; i 《= n; i++){
        p = new LNode;
        p-》num = i;
        if (list == NULL)
            list = p;
        else
            r-》next = p;
        r = p;
    }
    p-》next = list;//使链表循环
    p = list;//p指向头结点
    r = p;
    //x循环删除队列中的结点，即出列
    printf("出列者序列：");
    while (p-》next != p){
        for (i = 1; i《m; i++){
            r = p;
            p = p-》next;
        }
        r-》next = p-》next;
        printf("%d ", p-》num);
        free(p);
        p = r-》next;
    }
    printf("\n最后留下的人是：%d\n", p-》num);
}
int main(){
    for (int m, n; cin 》》 m 》》 n;)
        joseph(m, n);
    return 0;
}
/*
* n的初值为10，m为2，则出列顺序为 2 4 6 8 10 3 7 1 9，最后留下者是 5.
* n的初值为20，m为5，则出列顺序为 5 10 15 20 6 12 18 4 13 1 9 19 11 3 17 16 2 8 14，最后留下者是 7.
*/

约瑟夫环问题的C++算法,求用链表和递归两种方法,尽量详细!

#include 《iostream.h》
typedef struct node {  //结点类型定义，每个结点表示一个孩子
    int data;   //用于存放结点（孩子）编号
    node *next;
    node(int _data = 0, node *_next = NULL)  //带缺省参数的结点构造函数

        : data(_data),next(_next)

    {}
}*PNode, Node, *JosephusCycle;

void InitJCycle(JosephusCycle &last, int n) {

//初始化一个含有n个孩子的约瑟夫环，用带尾指针last的单循环链表表示，建表时采用首插法。
    last = new Node(n);  //last指针始终指向表尾结点，先创建表尾结点
    last-》next = last;  //先初始化只含一个结点的环。
    for(int i = n - 1; i 》 0; i--)
        last-》next = new Node(i, last-》next); //将新结点插入到表头(即循环链表表尾的下一个)之前
}

int GetWinner(JosephusCycle &last, int k) { //第一种方法，返回剩下的最后这个孩子的编号
    if(last == NULL) return -1;  //如果为空环，则返回-1表示失败
    int sum; //报数器
    PNode prior = last, current = prior-》next;//current表示当前报数结点，prior为当前结点的前驱
    while(prior != current) {//如果prior==current则意味着环中剩下一个孩子
        sum = 1; //报数开始
        while(sum 《 k) {  //进行报数，报数时，current指针与prior指针需同时移动
            prior = current;
            current = prior-》next;
            sum++;
        }
        cout 《《 current-》data 《《 "\t"; //将报到k的孩子的序号输出。接下来的两行是该孩子删除出环
        prior-》next = current-》next;
        delete current;
        current = prior-》next; //重新定位当前孩子
    }  //end while，结束循环时，环中只剩最后一个孩子
    last = current;  //将环尾指针指向最后这个孩子
    return last-》data;
}

int GetWinner(JosephusCycle &last, int n, int k) {

//方法二，递归，参数last是环尾指针，n表示环中孩子个数，k为报数的目标数
    if(n == 1) return last-》data;  //如果环中只有一个孩子，则结束，并返回这个孩子的编号
    int sum = 1; //否则，则开始报数
    while(sum 《 k) {  //进行报数
        last = last-》next;
        sum++;
    }  //结束while时，last-》next即为报到k的孩子结点
    PNode p = last-》next;//本行及后续3行是输出该孩子并删除该孩子
    cout 《《 p-》data 《《 "\t";
    last-》next = p-》next;
    delete p;
    GetWinner(last, n - 1, k); //在剩下的n-1个孩子的环中继续找优胜者
}

void main( ) {
    JosephusCycle cycle;
    int m, k, winner;
    cin 》》 m 》》 k;

    cout 《《 "方法一的出圈序列为：\n";
    InitJCycle(cycle, m);
    winner = GetWinner(cycle, k);
    cout 《《 "\n优胜者：" 《《 winner 《《 endl;

    delete cycle;

    cout 《《 "\n方法二的出圈序列为：\n";
    InitJCycle(cycle, m);
    winner = GetWinner(cycle, m, k);
    cout 《《 "\n优胜者：" 《《 winner 《《 endl;
}