好玩的約瑟夫環(huán):有M個人迅矛,編號分別為1到M妨猩,玩約瑟夫環(huán)游戲,最初時按編號順序排成隊列秽褒;每遍游戲開始時壶硅,有一個正整數(shù)報數(shù)密碼N,隊列中人依次圍坐成一圈震嫉,從隊首的人開始報數(shù)森瘪,報到N的人出列,然后再從出列的下一人開始重新報數(shù)票堵,報到N的人出列扼睬;重復這一過程,直至所有人出列悴势,完成一遍游戲窗宇,所有出列的人形成新隊列;游戲可能玩很多遍特纤,每遍有新報數(shù)密碼军俊。求若干遍游戲完成后隊列次序。題目輸入包括若干個正整數(shù)(至少1個)捧存,第一個正整數(shù)為玩游戲人數(shù)M粪躬,后續(xù)每個正整數(shù)為每遍游戲報數(shù)密碼担败,報數(shù)密碼可能為1,題目要求按出隊列順序輸出他們的編號镰官。
輸入格式:
正整數(shù)M和后面的若干個正整數(shù)報數(shù)提前。
輸出格式:
每個測試用例結(jié)果占一行,每個編號占4位泳唠。
輸入樣例: | 10 3 5 2 |
---|---|
輸出樣例: | 4 6 5 2 9 1 3 7 8 10 |
作者 | 李衛(wèi)明 |
---|---|
單位 | 杭州電子科技大學 |
代碼長度限制 | 16 KB |
時間限制 | 400 ms |
內(nèi)存限制 | 64 MB |
C語言版本:
#include <stdio.h>
#include<string.h>
typedef int bool;
#define true 1
#define false 0
typedef struct Node{
int data;
struct Node *next;
} Node;
Node* create_Yuesefu_List(int m){
Node *head, *node,*end;//定義頭節(jié)點狈网,普通節(jié)點,尾部節(jié)點笨腥;
head = (Node*)malloc(sizeof(Node));//分配地址
head->data = 1;
end = head; //若是空鏈表則頭尾節(jié)點一樣
for (int i = 1; i < m; i++) {
node = (Node*)malloc(sizeof(Node));
node->data = (i+1);
head->next = node;
head = head->next;
}
head->next = end;
return end;
}
Node* yuesefu_Problem(Node* head,int n){
int counter = 1;
bool is_First_Out = true;
Node *node_new,*h,*node;
node_new = (Node*)malloc(sizeof(Node));
h=node_new;
while(head!=NULL)
{
if(n!=1)counter++;
else {
if(is_First_Out==true){
node_new->data = head->data;
is_First_Out=false;
}else{
node = (Node*)malloc(sizeof(Node));
node->data = head->next->data;//賦值操作
node_new->next=node;
head->next = head->next->next;
node_new = node_new->next;
if(head==head->next){
node_new->next=h;
return h;
}
}
}
if(counter==n && n!=1){
if(is_First_Out==true){
node_new->data = head->next->data;
is_First_Out=false;
}else{
node = (Node*)malloc(sizeof(Node));
node->data = head->next->data;
node_new->next = node;
//上面三句話 相當于1句話 node_new.next = new Node(head.next.value);
node_new=node_new->next;
}
head->next = head->next->next;
counter = 0;
}else if(counter!=n&&n!=1){
head = head->next;
if(head == head->next){
node = (Node*)malloc(sizeof(Node));
node->data = head->data;
node_new->next = node;
node_new->next->next = h;
break;
}
}
}
return h;
}
Node* input_LinkedList(){
char str[1024];
char *delim = " ";
scanf("%[^\n]", str);
Node* head = (Node*)malloc(sizeof(Node));
Node * end = head;
Node * node;
int count=0;
char *p = strtok(str, delim);
head->data = atoi(p);
// printf("%s \n", p);
count++;
while((p = strtok(NULL, delim))){
node = (Node*)malloc(sizeof(Node));
node->data = atoi(p);
head->next = node;
head = head->next;
// printf("%s \n", p);
count++;
}
return end;
}
void print_LinkedList(Node* head,int count){
while(head->next != NULL && count !=0){
printf("%4d",head->data);
head = head->next;
count--;
}
printf("\n");
}
int main(void) {
Node* head = input_LinkedList();
int m = head->data;
head = head->next;
Node* h = create_Yuesefu_List(m);
while(head!=NULL){
h = yuesefu_Problem(h,head->data);
head = head->next;
}
print_LinkedList(h, m);
}