本文主要是介绍寒假第二天--线性表--约瑟夫问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
约瑟夫问题
Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^
题目描述
n个人想玩残酷的死亡游戏,游戏规则如下:
n个人进行编号,分别从1到n,排成一个圈,顺时针从1开始数到m,数到m的人被杀,剩下的人继续游戏,活到最后的一个人是胜利者。
请输出最后一个人的编号。
n个人进行编号,分别从1到n,排成一个圈,顺时针从1开始数到m,数到m的人被杀,剩下的人继续游戏,活到最后的一个人是胜利者。
请输出最后一个人的编号。
输入
输入n和m值。
输出
输出胜利者的编号。
示例输入
5 3
示例输出
4
提示
第一轮:3被杀第二轮:1被杀第三轮:5被杀第四轮:2被杀
在这个题中,和前面的不同的一点就是将最后的q->next = head ->next ; 是整个链表循环起来,其中数到m时将那个人杀死,因为删除时用的是将当前指向的后面的数删掉,所以我从最后一个开始循环,这样就可以做到当count为指定值时,就将那个数删除
#include <stdio.h>
#include <stdlib.h>
struct node{ int data ; struct node *next ;
};
int main()
{ int i , n , a , b ; struct node *head = NULL, *p = NULL, *q = NULL ; head = (struct node *)malloc(sizeof(struct node)); head->next = NULL ; q = head ; scanf("%d", &n); for(i = 1 ; i <= n ; i++) { scanf("%d", &a); p = (struct node *)malloc(sizeof(struct node)); p->data = a ; q->next = p ; q = p ; } scanf("%d", &b); q->next = NULL ; p = head->next ; printf("%d\n", n); while(p) { printf("%d", p->data); if(p->next != NULL) printf(" "); p = p->next ; } printf("\n"); p = head ; while(p->next != NULL) { if(p->next->data==b) { q = p->next ; p->next = q->next; free(q); n--; } else p = p->next ; } printf("%d\n", n); p = head->next; while(p) { printf("%d", p->data); if(p->next != NULL) printf(" "); p = p->next ; } printf("\n");
}
这篇关于寒假第二天--线性表--约瑟夫问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!