Bài tập Olympic tin học

#1

Chào các bác, em đang có một bài tập đệ quy muốn tìm cách giải hay nhất:
Một bàn ăn có n người ngồi quanh, người ta dọn cho mỗi người một món ăn, thực đơn chỉ có 3 món A, B, và C. Hãy chỉ ra mọi cách dọn đồ ăn thỏa mãn điều kiện: không có 3 người nào liên tiếp có đồ ăn giống nhau.
Em có làm được một hàm như sau

void in_ra() 
{
	for (int i = 1; i <= n; i ++)
	{
			if ( a[i] == a[i+1])
			{
				if ( a[i] != a[i+2])
				cout << a[i];
			}
			else cout << a[i];
	}
	x++;
		cout<<endl;
}

void sinh(int n)
{
	if (n == 0) 
	{
		in_ra();
	}
	else {
		a[n] = 0; sinh(n-1);
		a[n] = 1; sinh(n-1);
		a[n] = 2; sinh(n-1);
	}
}

Kết quả có vẻ chưa chuẩn lắm, bác nào vào đóng góp ý tưởng cho em với :smiley:

#2

Có phải là không được chứa “AAA”, “BBB”, “CCC” không?

#3

Bắt buộc phải đệ quy hả bạn?

#4

đúng rồi bạn :smiley: aaaaaaaaaaaaaaaaaaâ

#5

đề bài bắt buộc dùng đệ quy :smiley:

#6

Nếu bạn đặt món ăn vào vị trí 1 thì phải kiểm tra vị trí 2 và n xem có món ăn giống vị trí 1 hay không. Tương tự với vị trí n.

Bạn có thể đặt vòng for các khả năng có thể và đặt điều kiện trong vòng for để giảm thiểu số lần đệ quy vô nghĩa.

#7

Thớt tham khảo thuật toán Sawada thử: https://www.semanticscholar.org/paper/A-fast-algorithm-to-generate-necklaces-with-fixed-Sawada/369660a1f7c2a2fd3892a091a709f6b77a367664

3 Likes
#8

Tham khảo.

F(n){
 if (n==1) : return [A, B, C];
 if (n==2) : return [AA, AB, AC, BA, BB, BC, CA, CB, CC];
 F(n-1) nối F(1) rồi CHECK : return nếu thoả mãn.
}
// F là hàm cần tìm.
// F(n-1) nối F(1) ý là nối lần lượt các phần tử return của F(n-1) với F(1) vì vòng tròn nên nối đầu cũng như nối cuối giả sử nối vào vị trí cuối là n.
// CHECK là kiểm tra ba vị trí xung quanh vị trí cuối cùng vừa thêm chỉ cần check 3 cặp các vị trí (n-2, n-1, n), (n-1, n, 1), (n, 1, 2) nếu giống nhau loại. Bắt đầu là 1 không phải 0 như chỉ số array.

P/S: Nếu n chẵn thì nối F(n/2) và F(n/2). Nếu n lẻ nối F((n-1)/2) và F((n-1)/2+1) và CHECK xung quanh 2 điểm nối và sử dụng cache để lưu trữ mỗi lần tính sẽ tối ưu hơn.

#9

duyệt toàn bộ bằng Back_Track có tính là dùng đệ quy ko thớt

#10

Backtrack là đệ quy quay lui mà?

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?