01/10/2018, 12:15

Bài tập Olympic tin học

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

rogp10 viết 14:27 ngày 01/10/2018

không có 3 người nào liên tiếp có đồ ăn giống nhau

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

Trần Hoàn viết 14:32 ngày 01/10/2018

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

Quyết Tiến Trịnh viết 14:20 ngày 01/10/2018

đúng rồi bạn aaaaaaaaaaaaaaaaaaâ

Quyết Tiến Trịnh viết 14:30 ngày 01/10/2018

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

HK boy viết 14:19 ngày 01/10/2018

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.

rogp10 viết 14:30 ngày 01/10/2018

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

Phuc Phan viết 14:20 ngày 01/10/2018

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.

Nchau viết 14:32 ngày 01/10/2018

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

HK boy viết 14:31 ngày 01/10/2018

Backtrack là đệ quy quay lui mà?

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Quyết Tiến Trịnh

0 chủ đề

0 bài viết

Tác giả nổi bật