Tuyên bố vấn đề
Có N người chơi đang chơi một giải đấu. Chúng tôi cần tìm số trò chơi tối đa mà người chiến thắng có thể chơi. Trong giải đấu này, hai người chơi chỉ được phép đấu với nhau nếu hiệu số giữa các trận đấu của họ không quá một
Ví dụ
Nếu có 3 người chơi thì cần 2 ván để phân định thắng thua như sau -
Trò chơi - 1:người chơi 1 đấu với người chơi 2
Trò chơi - 2:người chơi 2 đấu với người chiến thắng từ Trò chơi - 1
Thuật toán
- Chúng tôi có thể giải quyết vấn đề này bằng cách tính toán số lượng người chơi tối thiểu cần thiết trước tiên để người chiến thắng sẽ chơi x trò chơi. Một khi điều này được tính toán, vấn đề thực tế chỉ là nghịch đảo của điều này. Bây giờ, giả sử rằng dp [i] biểu thị số lượng người chơi tối thiểu cần thiết để người chiến thắng chơi trò chơi của tôi
- Chúng ta có thể viết một quan hệ đệ quy giữa các giá trị dp dưới dạng, dp [i + 1] =dp [i] + dp [i - 1] vì nếu người về nhì đã chơi (i - 1) trò chơi và người chiến thắng đã chơi tôi trò chơi và tất cả những người chơi mà họ đã chơi trong trận đấu là rời rạc, tổng số trò chơi mà người chiến thắng đã chơi sẽ được bổ sung thêm hai nhóm người chơi đó.
- Quan hệ đệ quy ở trên có thể được viết dưới dạng dp [i] =dp [i - 1] + dp [i - 2] Giống như quan hệ chuỗi Fibonacci, vì vậy câu trả lời cuối cùng của chúng tôi sẽ là chỉ số của số Fibonacci tối đa nhỏ hơn hoặc bằng số lượng người chơi nhất định trong đầu vào
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int getMaxGamesToDecideWinner(int n) {
int dp[n];
dp[0] = 1;
dp[1] = 2;
int idx = 2;
do {
dp[idx] = dp[idx - 1] + dp[idx - 2];
} while(dp[idx++] <= n);
return (idx - 2);
}
int main() {
int players = 3;
cout << "Maximum games required to decide winner = " << getMaxGamesToDecideWinner(players) << endl;
return 0;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Maximum games required to decide winner = 2