2 qq 40238743 qq_40238743 于 2017.09.14 12:56 提问

约瑟夫问题,大神们,这个怎么理解啊???

#include
#include

#define n 11
#define m 3

struct node{
int no;
node *next;
};

int main() {
int k = 0;
node p, *q, *r;
p = q = (node
)malloc(sizeof(node));//创建第一个节点
p ->no = 1;
for(int i = 2; i <= n; i++){ //建立链表
r = (node*)malloc(sizeof(node));
r ->no = i;
q ->next = r;
q = r;
}
q->next = p; //构成一个环
q = p;
while(q->next != q){
k++;
if(k == m){
p->next = q->next;
free(q);
q = p->next;
k = 0;
} else {
p = q;
q = q->next;
}
}
printf("最后一个获胜者的编号是:%d\n", q->no);
}

1个回答

jiapengxu
jiapengxu   2017.09.14 13:42

#include
#include
#define n 11
#define m 3
typedef struct _node{
int no;
struct node *next;
}node;

void print(node* front)
{
node* tmp = front->next;
while(tmp != front)
{
printf("%d\t",tmp->no);
tmp = tmp->next;
}
puts("");
}

int main()
{

int k = 0,i=0;
node* p, *q, *r;
p = q = (node*)malloc(sizeof(node));//创建第一个节点
p->no = 1;
for(int i = 2; i <= n; i++)
{ //建立链表 
    r = (node*)malloc(sizeof(node));
    r ->no = i; 
    q ->next = r;
    q = r;
}
q->next = p; //构成一个环 
q = p; 
while(q->next != q)
{
    k++;
    if(k == m)
    {
        printf("%d:",i++);
        print(q);

        p->next = q->next;
        free(q);
        q = p->next;
        k = 0;          
    } 
    else 
    {
        p = q;
        q = q->next;
    }
} 
printf("最后一个获胜者的编号是:%d\n", q->no);  

}

直接运行,可看到整体流程

Csdn user default icon
上传中...
上传图片
插入图片