Bài toán Josephus

[MaBu (Bụng Bự)]

Em có bài toán nhỏ share cho những bạn đang học về con trỏ áp dụng làm thử. Trên mạng chắc sẽ có nhưng trong DNH thì không. Nếu trùng thì anh Đạt delete giúp em nha.
Bài toán Josephus:
Cho N người đứng thành vòng tròn và chọn 1 con số M bất kì (M < N). Bắt đầu người thứ I (mang số 1) đếm 1, người kế bên phải đếm 2,…cho tới người thứ M sẽ tự động ra khỏi vòng tròn và người bên phải anh ta phải đếm lại là 1, cứ tiếp tục cho đến khi không còn ai. Yêu cầu xuất ra thứ tự đi ra và người cuối cùng đi ra.
Bài này có thể dùng mảng nhưng bạn nào dùng con trỏ thì sẽ hiểu được bản chất con trỏ dùng như thế nào.

[drgnz]

‘3’ DS liên kết phải ko nhể

[MaBu (Bụng Bự)]

híc, bài này dễ quá nên không ai thèm làm hết.

[nguyenchiemminhvu (NCMV)]

Dùng danh sách liên kết vòng. Nối last->next = first;

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

int element = 1;

struct list
{
	int number;
	list *next;
};

list* input()
{
	list *p,*head;
	int n;
	p = NULL;
	head = NULL;
	cout << "Nhap gia tri cho cac phan tu (nhap 0 de dung): ";
	while(true)
	{
		cin >> n;
		if(n==0)
		{
			p->next = head;
			return head;
		}
		if(head == NULL)
		{
			p = new list[1];
			head = p;
		}
		else
		{
			p->next = new list[1];
			p = p->next;
		}
		p->number = n;
		element++;
	}
}

void output(list *head)
{
	list *p;
	p = head;
	int i = 1;
	while(i < element)
	{
		cout<<p->number<<"  ";
		p = p->next;
		i++;
	}
	cout<<endl;
}

int play(list *head)
{
	list *p,*pt;
	p = head;
	while(p->next != p)
	{
	    for(int i = 1; i <= 3; i++)
            p = p->next;

		pt = p; //Cho pt tro den phan tu truoc phan tu bi xoa
		p = p->next;
        pt->next = p->next;
        element--;
		output(head);
		p = p->next;
	}
	return p->number; //Tra ve phan tu con lai sau cung
}

int main()
{
	list *head;
	int last;
	head = input();
	output(head);
	last = play(head);
	cout << "Output: " << last;
	
	system("pause");
	return 0;
}

[hungvp1109 (Phạm Hưng)]

Bạn giải thích hộ mình cả code với. Mình đọc không hiểu

[Hien_Nguyen (Hiển Nguyễn)]

Bài này có công thức tổng quát mà
Với M=2

Thay tất cả các số 2 bởi M là được.
Viết n ở hệ cơ số M. Rồi đảo c.s 1 ở đầu lên cuối

[rogp10]

Bài này có 2 tham số bạn