Think of the following games:
Suppose the alphabet 'A' to 'Z' is the whole set and one subset is given.This is called the answer.
Players can make the following inquiries once per turn.
Inquiry: One set of alphabets 'A' to 'Z' is input, and whether or not the product set of answers and inputs is an empty set is returned with Yes/No.
Now we will compete for the number of turns until the answer is confirmed.
What is the player's best strategy?
Also, what is the worst number of turns when the player takes the best strategy?
The strategy with the lowest average number of turns is called the best strategy.
algorithm
If it is optional how many alphabets are included, the solution is 2**26, and under this condition, it is difficult to order, so dichotomous search is not possible.So the best strategy on the part of the player, or the only strategy, is to search every single character, or
You will be able to reach the correct answer in 26 queries (worst = best = average).
As long as the correct answer contains any number of characters, if you query non-single characters (for example, AB and AC and ADE), it is unclear whether A is included.If so, it is useless to query more than two characters.
In my own conclusion, it's best to check each letter.
The initial state is 2**26 candidate solutions.
And every time I make an inquiry, yes/no is returned, so the execution process is shown as a two-minute tree.
And when you have one candidate solution, it becomes a leaf.
The most efficient binary tree is a complete binary tree, but the strategy for examining each character is a complete binary tree.
Therefore, it would be best to check each letter.
© 2024 OneMinuteCode. All rights reserved.