C++約瑟夫環(huán)問題詳解

更新時間：2022年01月11日 09:11:02 作者：夏天的峰沒有風

大家好，本篇文章主要講的是C++約瑟夫環(huán)問題詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽

題目如下：

有一家公司，這個公司有一位老板和13名程序員，每天下班前老板都會組織他們玩一次游戲，游戲的勝利者可以不加班，失敗者需要加班2小時。游戲規(guī)則如下：一張圓桌共有13個座位，從1到13編號，游戲開始前老板會說出今天開始報數(shù)的座位編號start和淘汰序號k。然后13名程序員開始搶位置，每個位置只能容納一程序員，每個程序員必須選擇一個座位。座位號為start的程序員從1開始報數(shù)，按如圖所示方向依次報數(shù)。每次報數(shù)為k的程序員淘汰并離開座位去加班，其他人繼續(xù)游戲，直到剩下最后一人瀟灑離去。

有一位非常聰明的程序員，每次在老板說出start和k的瞬間，就能立即選好座位并且獲勝，所以他從來沒有加過班，其他程序員都非常羨慕他，問他制勝法寶，只見他緩緩的打開了一個名為IAMGOD的.c文件，大家都露出崇拜的目光。

今天，你就是這個聰明的程序員，請完善IAMGOD.c文件內容。

根據(jù)提示，在右側編輯器完善IAMGOD.c文件內容，找到可以不加班的座位號。

輸入：start k

輸出：所選的座位編號i

示例1-輸入：2 3

輸出：13

#include<stdio.h>
#include<malloc.h>
 
//創(chuàng)建結構體 
typedef struct Node{
	int data;
	struct Node* next;
} NODE;
 
//創(chuàng)建新結點和插入結點 
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; //將尾結點連接到頭結點上，形成一個環(huán) 
}
 
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號 
		
		//當?shù)趉個仍是本身，即只剩下了一個結點,跳出循環(huán)
		if(start->data == (start->next)->data)
		 break;
	}	
	printf("%d",start->data);
}
 
int main()
{
   //創(chuàng)建鏈表 
	NODE* head;
	head = (NODE*)malloc(sizeof(NODE));
	head->data = 1;
	head->next = NULL;
	
	
	//創(chuàng)建新結點和連接結點 
    insert(head);
    
    //查找第k個結點并且將其刪除。 
    serch(head);
	return 0;
}

到此這篇關于C++約瑟夫環(huán)問題詳解的文章就介紹到這了,更多相關C++約瑟夫環(huán)內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: