首页 > 代码库 > 循环链表之约瑟夫问题
循环链表之约瑟夫问题
约瑟夫问题
（上课结束，大家听说第一周没有编程题目，立刻就被鄙视了，为了纠正这个错误，咱们本周就来做点简单题目。本题要求用循环链表实现）
约瑟夫问题是一个经典的问题。已知n个人（不妨分别以编号1，2，3，…，n 代表 ）围坐在一张圆桌周围，从编号为 k 的人开始，从1开始顺时针报数1, 2, 3, ...，顺时针数到m 的那个人，出列并输出。然后从出列的下一个人开始，从1开始继续顺时针报数，数到m的那个人，出列并输出，…依此重复下去，直到圆桌周围的人全部出列。
输入：n, k, m
输出：按照出列的顺序依次输出出列人的编号，编号中间相隔一个空格,每10个编号为一行。
非法输入的对应输出如下
a)
输入：：n、k、m任一个小于1
输出：n,m,k must bigger than 0.
b)
输入：k>n
输出：k should not bigger than n.
例:
输入：9,3,2
输出：4 6 8 1 3 7 2 9 5
#include <stdio.h>#include <stdlib.h>typedef struct node{ int No; struct node * next;}N, *PN;int main(){ int n, k, m, i, j=1; PN head, tmp, p, q; head = (PN)malloc(sizeof(N)); head->next = NULL; scanf("%d",&n); getchar(); scanf("%d",&k); getchar(); scanf("%d",&m); if (n<1 || k<1 || m<1) { printf("n,m,k must bigger than 0.\n"); return 0; } if (k>n) { printf("k should not bigger than n.\n"); return 0; } for (i=0; i<n; i++) { tmp = (PN)malloc(sizeof(N)); if (i==0) q = tmp; tmp->next = head->next; head->next = tmp; tmp->No = n-i; if (tmp->No == k) p = tmp; } q->next = head->next; while (n--) { for (i=1; i<m; i++) { p = p->next; } printf("%d",p->No); p->No = p->next->No; if (n == 0 || ((j++)%10==0)) printf("\n"); else printf(" "); q = p->next; p->next = q->next; free(q); } free(head); return 0;}
循环链表之约瑟夫问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。