帮助：约瑟夫斯之环的问题 [英] Help:the problem of Ring of Josephus

问题描述

我是CPL的初学者。我使用DoubleLinkList数据结构编写了一个关于约瑟夫斯的Ring

问题的程序。 />
我很困惑，我认为我的

代码中确实没有错误。但是，编译器有时会显示一些奇怪的错误，有时可以

在运行时遇到一个未知的麻烦，并且没有

结果。那么，有人可以给我一些帮助吗？非常感谢！

这是我的代码：

------------------------ -------------------------------------------------- ------------------------


#include< stdio.h>

#include< stdlib.h>


typedef struct DuLNode

{

int data;

struct DuLNode * previous;

struct DuLNode * next;

} DuLNode，* DuLinkList;


int ex_16（ int *，int，int）;


int main（int argc，char * argv []）

{

int a [] = {1,2,3,4,5,6,7,8,9,10,11,12，-1}; //使用-1作为

的标志数组的结尾

int n = 8，k = 5;

printf（最后一个数字是％d，ex_16（a，n，k）） ;

返回0;

}


int ex_16（int * a，int n，int k）

{

DuLinkList L;

L =（DuLinkList）malloc（sizeof（DuLNode））;

L->数据= 0; L-> next = L; L-> prior = L; //使用

头节点创建DuLinkList


int * p = a;

while（* p！= - 1）

{

DuLinkList DL ;

DL =（DuLinkList）malloc（sizeof（DuLNode））;

DL-> data = * p;

DL-> ; previous = L-> prior; L-> prior-> next = DL;

DL-> next = L; L-> prior = DL;

L-> data ++; // L->数据是List的长度排除

头节点

p ++;

} //启动DuLinkList


DuLinkList q; int i，temp;


while（1）

{

if（L-> next; = L）

{

q = L;

for（i = 0; i< （n-1）％L->数据; i ++）

{

q = q-> next;

temp = q- >数据;

}

q-> prior-> next = q-> next;

q-> next - > previous = q-> previous;

free（p）;

L-> data - ;

}

其他休息;


如果（L->先前！= L）

{

q = L;

for（i = 0; i<（k-1）％L->数据; i ++）

{

q = q-> previous;

temp = q-> data;

}

q-> prior-> next = q-> next;

q-> next-> prior = q-> previous;

free（p）;

L-> data--;

}

else break;

} //删除位于该点的节点/>

返回temp;

} // ex_16

---------------------------- -------------------------------------------------- ----------------


请告诉我代码中的任何错误或错误习惯。

Hi,
I''m the beginner of the CPL.I write a program about the problem of Ring
of Josephus,using DoubleLinkList data structure.
I''m very confused that I think there is really no error in my
code.But,the compiler sometimes show some strange errors,sometimes can
pass through with an unknown trouble when it is running,and no
result.So,could anyone give me some help? Thank you very much!
Here is my code:
--------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

typedef struct DuLNode
{
int data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode,*DuLinkList;

int ex_16(int *,int,int);

int main(int argc, char *argv[])
{
int a[]={1,2,3,4,5,6,7,8,9,10,11,12,-1};//use -1 as the flag of
ending of the array
int n=8,k=5;
printf("The last number is %d",ex_16(a,n,k));
return 0;
}

int ex_16(int *a,int n,int k)
{
DuLinkList L;
L=(DuLinkList)malloc(sizeof(DuLNode));
L->data=0;L->next=L;L->prior=L;//create the DuLinkList with the
head-node

int *p=a;
while(*p!=-1)
{
DuLinkList DL;
DL=(DuLinkList)malloc(sizeof(DuLNode));
DL->data=*p;
DL->prior=L->prior;L->prior->next=DL;
DL->next=L;L->prior=DL;
L->data++; //L->data is the length of the List exclude the
head-node
p++;
}//initiate the DuLinkList

DuLinkList q;int i,temp;

while(1)
{
if(L->next!=L)
{
q=L;
for(i=0;i<(n-1)%L->data;i++)
{
q=q->next;
temp=q->data;
}
q->prior->next=q->next;
q->next->prior=q->prior;
free(p);
L->data--;
}
else break;

if(L->prior!=L)
{
q=L;
for(i=0;i<(k-1)%L->data;i++)
{
q=q->prior;
temp=q->data;
}
q->prior->next=q->next;
q->next->prior=q->prior;
free(p);
L->data--;
}
else break;
}//delete the node which is at the point

return temp;
}//ex_16
----------------------------------------------------------------------------------------------

Please tell any faults or wrong habits in my code.

推荐答案

Yuri CHUANG说：

Yuri CHUANG said:

我是CPL的初学者。我写了一个程序关于Josephus的问题，使用DoubleLinkList数据结构。


那可能是个错误。如果您有少量数据，

阵列就可以了。对于任意数量的数据，Josephus可能更好地用圆形列表而不是线性列表来解决。

#include< stdio.h>
＃ include< stdlib.h>

typedef struct DuLNode
{int int data;
struct DuLNode * prior;
struct DuLNode * next;
} DuLNode，* DuLinkList;


在typedef中隐藏指针总是一个坏主意。我宁愿看到像DuLNode * addnode（）这样的函数比DuLinkList addnode（）还要好......它使得它更加清楚正在发生的事情。
int ex_16（int *，int，int）;

int main（int argc，char * argv []）
{
int a [ ] = {1,2,3,4,5,6,7,8,9,10,11,12，-1}; //使用-1作为数组结尾的标志


或者只是计算数组中元素的数量（它等于数组的

大小除以其中一个成员的大小），然后将这个信息传递给任何需要它的函数。

int n = 8，k = 5;
printf（"最后一个数字是％ d"，ex_16（a，n，k））;
返回0;
}
int ex_16（int * a，int n，int k）
{
DuLinkList L;
L =（DuLinkList）malloc（sizeof（DuLNode））;


演员阵容毫无意义。幸运的是，在你的情况下，它并没有隐瞒

错误 - 但它本可以做到。更简单：L = malloc（sizeof * L）;


如果分配失败，顺便说一句，你的程序将进入超空间
。它不仅仅依赖于分配的成功 -

/假设/分配成功。

L-> data = 0; L- > next = L; L-> prior = L; //使用
头节点创建DuLinkList


第二次，换行使一个你的评论语法的猴子。

老式/ *评论风格* /可能是老式的，但它更坚固。


顺便说一句，0不是你的输入数据的一部分，那你为什么要把它包括在列表中？
？作为一个节点计数器？

从正面来看，你指的是L-> next和L->先前在L，这让我

认为你毕竟决定去循环。

int * p = a;
while（* p！= - 1）
{
DuLinkList DL;
DL =（DuLinkList）malloc（sizeof（DuLNode））;


为什么不只是：DL = malloc（sizeof * DL）;

DL-> data = * p;
DL->先前= L->先前; L->先前 - >下一个= DL;
DL-> next = L; L-> prior = DL;


是的，到目前为止看起来不错。

L-> data ++; // L->数据是List的长度排除
头节点p ++;
} //启动DuLinkList







I，温度;


大概你有一个C99编译器可以理解所有这些混合的

声明/代码和//风格的评论内容？我的编译器只是将它们称为

语法错误。事实上，我所有的编译器都称它们为语法错误。

而（1）


当然你的意思是（我还没有解决约瑟夫斯问题） ）？

{
if（L-> next！= L）


.... ie如果除了头节点之外列表不为空

{
q = L;


....将q指向头节点

for（i = 0; i<（n-1）％L->数据; i ++）
{
q = q-> next;


....数n人围着戒指...

temp = q->数据;
}
q-> prior-> next = q-> next;
q-> next-> prior = q-> prior;
free（p）;

Hi,
I''m the beginner of the CPL.I write a program about the problem of Ring
of Josephus,using DoubleLinkList data structure.
That''s probably a mistake right there. If you have a small amount of data,
an array will be just fine. For arbitrary amounts of data, Josephus is
probably better solved with a circular list rather than a linear one.
#include <stdio.h>
#include <stdlib.h>

typedef struct DuLNode
{
int data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode,*DuLinkList;
Hiding pointers in typedefs is always a bad idea. I''d much rather see a
function like DuLNode *addnode() than DuLinkList addnode() - it makes it
far clearer what''s going on.

int ex_16(int *,int,int);

int main(int argc, char *argv[])
{
int a[]={1,2,3,4,5,6,7,8,9,10,11,12,-1};//use -1 as the flag of
ending of the array
Or simply calculate the number of elements in the array (it''s equal to the
size of the array divided by the size of one member thereof), and then pass
this information to any function that needs it.
int n=8,k=5;
printf("The last number is %d",ex_16(a,n,k));
return 0;
}

int ex_16(int *a,int n,int k)
{
DuLinkList L;
L=(DuLinkList)malloc(sizeof(DuLNode));
The cast is meaningless. Fortunately, in your case, it doesn''t conceal an
error - but it could have done. Much simpler: L = malloc(sizeof *L);

In the event that the allocation fails, by the way, your program heads off
into hyperspace. It doesn''t just rely on the success of the allocation - it
/assumes/ the success of the allocation.
L->data=0;L->next=L;L->prior=L;//create the DuLinkList with the
head-node
For the second time, line-wrap makes a monkey of your comment syntax. The
old-fashioned /* comment style */ may be old-fashioned, but it is more
robust.

By the way, 0 isn''t part of your input data, so why are you including it in
the list? As a node counter?

On the plus side, you''re pointing L->next and L->prior at L, which makes me
think you did after all decide to go for circularity.
int *p=a;
while(*p!=-1)
{
DuLinkList DL;
DL=(DuLinkList)malloc(sizeof(DuLNode));
Why not just: DL = malloc(sizeof *DL);
DL->data=*p;
DL->prior=L->prior;L->prior->next=DL;
DL->next=L;L->prior=DL;
Yeah, that looks good so far.
L->data++; //L->data is the length of the List exclude the
head-node
p++;
}//initiate the DuLinkList

DuLinkList q;int i,temp;
Presumably you have a C99 compiler which understands all this mixed
declarations/code and //-style comment stuff? My compiler just calls them
syntax errors. In fact, all my compilers call them syntax errors.

while(1)
Surely you mean while(I haven''t yet solved the Josephus problem)?
{
if(L->next!=L)
....i.e. if the list is not empty apart from the head node
{
q=L;
....point q to the head node
for(i=0;i<(n-1)%L->data;i++)
{
q=q->next;
....count n people round the ring...
temp=q->data;
}
q->prior->next=q->next;
q->next->prior=q->prior;
free(p);

p只是指向你的数组，你没有malloc。你的意思是免费（q），

我想。


-

Richard Heathfield

Usenet是一个奇怪的地方 - dmr 29/7/1999
http://www.cpax.org.uk

电子邮件：rjh在上面的域名（但显然放弃了www）

p just points to your array, which you didn''t malloc. You meant to free(q),
I think.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

" ; Yuri CHUANG <宇******* @ 126.com>在消息中写道

news：11 ********************** @ i40g2000cwc.googlegr oups.com ...

"Yuri CHUANG" <yu*******@126.com> wrote in message
news:11**********************@i40g2000cwc.googlegr oups.com...

我是CPL的初学者。我使用DoubleLinkList数据结构编写了一个关于Josephus的问题的程序。
我很我认为我的
代码中确实没有错误。但是，编译器有时会显示一些奇怪的错误，有时可能会在运行时遇到未知的麻烦，并且没有
结果。那么，有人可以给我一些帮助吗？非常感谢！
这是我的代码：

Hi,
I''m the beginner of the CPL.I write a program about the problem of Ring
of Josephus,using DoubleLinkList data structure.
I''m very confused that I think there is really no error in my
code.But,the compiler sometimes show some strange errors,sometimes can
pass through with an unknown trouble when it is running,and no
result.So,could anyone give me some help? Thank you very much!
Here is my code:

我从来没有听说过约瑟夫之环。所以我查了一下。


对于实际的约瑟夫之环， n = 13且k = 3。但是，所有戒指都停在

nth元素上。你有n = 8，k = 5。不幸的是，因为第13个元素是-1而不是第8个元素，所以你的戒指不会停留在第8个元素的第b个元素上。此外，你需要

数组中的第n个元素，即n = 13时缺少13个元素。您可能希望将
设置为'a''作为指针，malloc（）为其空间，然后通过n和-1填充1

。

Rod Pemberton

I''d never heard of the "Ring of Josephus." So I looked it up.

For the actual "Ring of Josephus," n=13 and k=3. But, all rings stop on the
nth element. You have n=8, and k=5. Unfortunately, your ring won''t stop on
the 8th element since the 13th element is -1, not the 8th. Also, you need
the nth element in the array, i.e., 13 is missing for n=13. You may want to
setup ''a'' as a pointer, malloc() the space for it, and then fill it with 1
through n and -1.
Rod Pemberton

嗯，这是我在中文书中的问题，也许有翻译了

问题。

所以，我把它描述如下：

从1到m有整数，形成一个圆圈。数字1是

head.Delete第一个数字在一个方向，然后删除第k个数字

在另一个方向，直到只剩下一个数字。打印最后一个数字。

eg n = 12，m = 8，k = 5

1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 9 10 11 12 //删除8

1 2 3 4 5 6 9 10 11 12 //删除7

1 2 3 4 5 6 9 11 12 //删除10（第8位） ）

.....

1 4 6 9 11

4 6 9 11

4 6 9

4 9

4

所以结果是4.

我的代码的关键问题是我无法得到任何答案，甚至

错误一。我认为必须错误使用malloc功能。

请给我一些帮助。

非常感谢。

Well,it''s question in my Chinese book,maybe there are translated
problems.
So,I describe it as follows:
There are integers from 1 to m,forming a circle.The number 1 is the
head.Delete the nth number in one direction,then delete the kth number
in the other,until there is only one number left.Print the last number.
e.g. n=12,m=8,k=5
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 9 10 11 12 //delete 8
1 2 3 4 5 6 9 10 11 12 //delete 7
1 2 3 4 5 6 9 11 12 //delete 10(8th location)
.....
1 4 6 9 11
4 6 9 11
4 6 9
4 9
4
so the result is 4.
The critical problem of my code is that I couldn''t get any answer,even
error one.I think there must be wrong use of malloc function.
Give me some help,please.
Thanks a lot.

这篇关于帮助：约瑟夫斯之环的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！