首页 » 软件编程 » C语言

C++约瑟夫环问题详解

C语言 2022-01-11

题目如下:

有一家公司,这个公司有一位老板和13名程序员,每天下班前老板都会组织他们玩一次游戏,游戏的胜利者可以不加班,失败者需要加班2小时。游戏规则如下: 一张圆桌共有13个座位,从1到13编号,游戏开始前老板会说出今天开始报数的座位编号start和淘汰序号k。 然后13名程序员开始抢位置,每个位置只能容纳一程序员,每个程序员必须选择一个座位。 座位号为start的程序员从1开始报数,按如图所示方向依次报数。每次报数为k的程序员淘汰并离开座位去加班,其他人继续游戏,直到剩下最后一人潇洒离去。

C++约瑟夫环问题详解

有一位非常聪明的程序员,每次在老板说出start和k的瞬间,就能立即选好座位并且获胜,所以他从来没有加过班,其他程序员都非常羡慕他,问他制胜法宝,只见他缓缓的打开了一个名为IAMGOD的.c文件,大家都露出崇拜的目光。

今天,你就是这个聪明的程序员,请完善IAMGOD.c文件内容

根据提示,在右侧编辑器完善IAMGOD.c文件内容,找到可以不加班的座位号。

输入:start k

输出:所选的座位编号i

示例1-输入:2 3

           输出:13

#include<stdio.h>
#include<malloc.h>
 
//创建结构体 
typedef struct Node{
	int data;
	struct Node* next;
} NODE;
 
//创建新结点和插入结点 
void insert(NODE* head)
{
	int i;
	NODE* tail = head;
	
	//对每一个结点进行编号,依次编号为1、2、3......13
	for(i = 2; i <= 13; i++)
	{
		NODE* newnode;
		newnode = (NODE*)malloc(sizeof(NODE));
		newnode->data = i;
		
		//尾插法连接链表 
		newnode->next = NULL; 
		tail->next =  newnode;
		tail = newnode;
	}
	
	/*
    这段语句用来打印链表,检测链表是否正确连接的 
	NODE* pmove = head; 
	while(pmove != NULL)
	{
	  printf("%d->",pmove->data);
	  pmove = pmove->next;
    } 
    */ 
	 
	 tail->next = head; //将尾结点连接到头结点上,形成一个环 
}
 
void serch(NODE* head)
{
	 int start_data,i,k;
    NODE* start = head;
	scanf("%d%d", &start_data, &k);
	
	//移动到第start_data结点,并将此结点当成1号结点 
	for(i = 2; i <= start_data; i++)
	{
		start = start -> next;
	}
	
	NODE* front; //front表示第k个结点的前一个结点 
	while(start->next != NULL)
	{
	  int j;
	  for(j = 2; j <= k; j++)
	  {
		front = start; //先让front移动到当前结点,然后当前结点往下移动,就形成一前一后的效果 
		start = start->next; //移动结点 
	  }
		
		front->next = start->next; //将第k个结点的上一个结点连接到它的下一个结点上 
		
		free(start);//删除指定结点
		start = front->next;//更新start的位置,也就是1号 
		
		//当第k个仍是本身,即只剩下了一个结点,跳出循环
		if(start->data == (start->next)->data)
		 break;
	}	
	printf("%d",start->data);
}
 
int main()
{
   //创建链表 
	NODE* head;
	head = (NODE*)malloc(sizeof(NODE));
	head->data = 1;
	head->next = NULL;
	
	
	//创建新结点和连接结点 
    insert(head);
    
    //查找第k个结点并且将其删除。 
    serch(head);
	return 0;
} 

到此这篇关于C++约瑟夫环问题详解 的文章就介绍到这了,更多相关C++约瑟夫环内容请搜索www.580doc.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.580doc.com!


上一篇:C++ OpenCV实战之制作九宫格图像下一篇:C++ OpenCV实现图像修复功能
程序园_程序员的世界 Copyright © 2020- www.580doc.com. Some Rights Reserved.