当前位置: 首页 > 工具软件 > Puzzle Game > 使用案例 >

Joseph‘s Puzzle

穆睿才
2023-12-01
Problem description
Persons, whose number order is from 1 to N, hold a password (the straight integer less than 10000) each person and sit around clockwise.
At first we choose a positive integer factor as the count off number M and start to number clockwise from number one .As we number to M the person who numbers M leaves the rank and whose password will be the new number M. And then start to number again from the person who is sit clockwise next to the person who has been out off the rank just before then. Continue like this, until all people are out off the rank completely. Please design a program of leaving order.
 
Input
There have some groups data. First line of each group data is two integers N, M (0<N, M<100),the second line is N positive integer, separately express every person’s password.The last line contins 0,0 ,which means the end of input data.
 
Output
To each group of data, according to the order which leaves outputs their serial number. Between the numeral separates with a blank space. Each group of data monopolize line of outputs.
 
Sample Input
7 20
3 1 7 2 4 8 4
4 3
1 2 3 4
0 0
Sample Output
6 1 4 7 2 3 5
3 2 1 4
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int n,m;

struct Node {//define node
	int no;
	Node* next;
	Node* pre;
};
int main() {
	while (1) {
		scanf("%d %d",&n,&m);
		if (n == 0 && m == 0) {
			printf("\n");
			break;
		}
//		printf("%d  %d\n", n, m);
		int a[101];
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		Node* head = new Node;//use three nodes to create a circular link
		head->no = 0;
		Node* curr = head;
		Node* next = NULL;
		for (int i = 1; i <= n; i++)
		{
			next = new Node;
			next->no = i;
			next->pre = curr;
			curr->next = next;
			curr = next;
		}
		curr->next = head->next;
		head->next->pre = curr;
		Node* c = head->next;
		while (n) {
			m--;
			m= m % n;//reduce complexity
			for (; m > 0; m--) {
				c = c->next;
			}
			if (n != 1)//avoid presentation error
				printf("%d ", c->no);
			else printf("%d\n", c->no);
			m = a[c->no];
			c->next->pre = c->pre;//remove a node
			c->pre->next = c->next;
			c = c->next;
			n--;
//			for (int i = 0; i < n; i++) {
//				printf("%d ",c->no);
//				c = c->next;
//			}
//			printf("\n%d\n", m);
		}
		/*
		printf("%d\n", c->no);
		c->next->pre = c->pre;
		c->pre->next = c->next;
		c = c->next;
		printf("%d\n", c->no);
		c = c->pre;
		printf("%d\n", c->no);
		printf("%d,%d", n, m);
*/
	}
}

 类似资料:

相关阅读

相关文章

相关问答