[BT]Trò chơi xếp vòng, tìm người cuối cùng.

[phantuan_th]

Có 30 người, xếp vòng tròn. Bắt đầu đếm từ vị trí thứ nhất, đến người thứ 7 thì bị loại ra khỏi vòng chơi. Hỏi người cuối cùng còn lại.
Có thể tìm thuật toán chung cho bài toán tổng hợp với n người và đếm đến người thứ m thì loại.

[kidkid]

Uhm Cũng không khó lắm đâu ? Chỉ việc tạo một vào while rồi duyệt cho đến người cuối cùng thôi . Nếu cậu lưu theo danh sách liên kết vòng thì dễ hơn còn nếu lưu theo mảng thì có vẻ hơi vất vả một tí , nhưng bài toán này không có ứng dụng gì cả ? Chẳng hiểu vì sao bạn lại quan tâm ?

[phantuan_th]

Uhm Cũng không khó lắm đâu ? Chỉ việc tạo một vào while rồi duyệt cho đến người cuối cùng thôi . Nếu cậu lưu theo danh sách liên kết vòng thì dễ hơn còn nếu lưu theo mảng thì có vẻ hơi vất vả một tí , nhưng bài toán này không có ứng dụng gì cả ? Chẳng hiểu vì sao bạn lại quan tâm ?

Cậu sai rồi. Không thể duyệt đến người cuối cùng được, vì 30 người đứng vòng tròn cơ mà, sau khi loại người thứ 7 thì bắt đầu đếm từ người thứ 8 mà.

[shinichi_haha]

#include<stdio.h>
#include<stdlib.h>
void init(char *a,int n){
	for(int i=0;i<n;i++)
		a[i]=i+1;
	
}

void process(char *a,int *n){
	int end=*n;
	int target=6;
	while(end>=7){
		for(int i=target;i<end;i++){
			a[i]=a[i+1];
		}
		target=(target+7)%end;
		end--;
	}
	*n=end;
}

int main(){
int n=10;
char *a=(char*)malloc(n*sizeof(char));
init(a,n);
process(a,&n);
for(int i=0;i<n;i++)
	printf("%d ",a[i]);
free(a);
return 0;
}