Bài toán cướp biển Somali

[1412446itus (Phạm Khắc Quyền)]

Đề bài

Hải tặc đang ngày càng lộng hành tại vùng biển Somali thuộc Đông Phi, gây ra liên tiếp các
vụ cướp táo tợn. Từ các du thuyền sang trọng, những tàu chở dầu hạng nặng đến các tàu vận
tải chở xe tăng đều trở thành mục tiêu của chúng. Đã một thời gian chúng là thách thức lớn
không những cho các nước trong khu vực mà còn cho tất cả các nước trên toàn thế giới.
Đến một ngày nọ, các nước có hải quân mạnh đã liên kết lại với nhau để tiêu diệt chúng. Biết
không thể kháng cự, bọn chúng quyết định tự sát để chết trong danh dự. Vốn là một sinh viên
thông minh của Khoa CNTT trường ĐH KHTN đã trà trộn vào để chờ thời cơ tiêu diệt bọn
cướp, A đã đề xuất ý kiến sau để có thể cứu mình và đã được tất cả đồng ý:

1. N người ngồi thành một vòng tròn.
2. Một khẩu súng (mỗi lần nạp tối đa k viên đạn) được chuyền theo chiều kim đồng hồ
   bắt đầu từ vị trí số 1 (vị trí 12 giờ).
3. Cứ đến người nào thì người đó tự sát nếu còn đạn. Ngược lại, người đó sẽ nạp đầy đạn
   và chuyền sang người kế bên.
4. Khi có một người tự sát, người kế bên sẽ nhặt súng và tiếp tục chuyền sang người bên
   cạnh cho đến khi chỉ còn lại 1 người sống sót cuối cùng.

Theo bạn, A đã chọn ngồi ở vị trí nào để trở thành người sống sót cuối cùng?

Còn đây là code của mình, mọi người chỉ giáo xem thế nào !!!

#include <stdio.h>
#include <math.h>

bool kiemTra ( int a[], int n );
bool kiemTra ( int a[], int n )//Kiểm tra nếu trong N người chỉ còn  1 người sống ?
{
	int dem = 0;
	for ( int i = 0; i < n; i++ )
	{
		if ( a[i] == 0 )
		{
			dem++;
		}
	}
	if ( dem == 1 )
	{
		return true;
	}
	else
	{
		return false;
	}
}


void cuopBienSomali ( int a[], int n, int k );
void cuopBienSomali ( int a[], int n, int k )
{
	int dan = 0;
	for ( ; kiemTra(a, n) == false; )
	{
		for ( int  i = 0; i < n; i++ )
		{
			if ( a[i] == 1 || a[i-1] == 1)// Nếu người đó đã chết hoặc người trước đó vừa chết
			{
				continue;
			}
			else
			{
				if ( dan == 0 )
				{
					dan = dan + k;//Nếu đạn  = 0 thì nạp vào k viên đạn
				}
				else
				{
					a[i] = 1;
					dan = dan - 1;//Nếu còn đạn thì chuyển giá trị sang 1, giảm 1 viên đạn
				}
			}
		}
	}
	for ( int i = 0; i < n; i ++ )
	{
		if ( a[i] == 0 )
		{
			printf("Vi tri an toan la ghe thu %d !!!\n",i+1);
			break;
		}
	}
}


void main()
{
	int a[100];
	int n;
	int k;
	printf ("Nhap vao so ten cuop: ");
	scanf("%d",&n);
	printf ("Nhap vao so dan moi lan nap: ");
	scanf("%d",&k);
	for ( int i = 0; i < n; i++ )// Đặt giá  trị 0 cho người sống giá  trị 1 cho người đã chết
	{
		a[i] = 0;
	}
	cuopBienSomali(a, n, k);
}

[rogp10]

Bài này có hai cách đều là theta(klogn), một cách mang tính truy hồi.