Другие языки программирования и технологии

Пожалуйста помогите Прошу

Петя загадал рациональное число (несократимую дробь) больше нуля и меньше единицы, со знаменателем меньшим либо равным N. Вы можете задавать ему вопросы типа "верно ли, что число меньше R?" где вместо R можно подставлять любое рациональное число.
По числу N определите минимальное число вопросов M, которых наверняка хватит, чтобы узнать загаданное Петей число. То есть такое число M, что существует алгоритм задавания вопросов, который при данном N для всех возможных вариантов загаданного числа узнает, чему равно загаданное число меньше либо равно, чем за M вопросов, и алгоритма с меньшим M не существует.
Формат входных данных
Во входном файле записано натуральное число (1 < N < 1000).
Формат выходных данных
Одна строчка, в которой находится натуральное число - минимальное число вопросов, которых наверняка хватит, чтобы угадать загаданное число.

Формат ввода
2

Формат вывода
0
Артём Сапронов
Артём Сапронов
173
Пусть дробь: a / b
a и b - взаимно простые, т. е. НОД (a,b) = 1 т. к. дробь не сократимая
0 < a / b < 1
b <= N
1 < N < 1000
"верно ли, что число меньше R?" - вопрос подразумевает два вариант ответа и ответ на этот вопрос уменьшает неопределенность информации на 1 бит, т. е. в 2 раза.
Значит количество вопросов, вероятно log2(N - 1)
т. к. если знаменатель b <= N, то числитель должен быть меньше знаменателя минимум на 1, чтобы дробь была меньше 1 (по условию), т. е. a <= N - 1

В общем, это первое что пришло на ум. Не уверен в корректности этого решения. Проверь, подумай сам еще.
Hks Hks
Hks Hks
5 124
Лучший ответ
Пусть дробь: a / b
a и b - взаимно простые, т. е. НОД (a,b) = 1 т. к. дробь не сократимая
0 < a / b < 1
b <= N
1 < N < 1000
"верно ли, что число меньше R?" - вопрос подразумевает два вариант ответа и ответ на этот вопрос уменьшает неопределенность информации на 1 бит, т. е. в 2 раза.
Значит количество вопросов, вероятно log2(N - 1)
т. к. если знаменатель b <= N, то числитель должен быть меньше знаменателя минимум на 1, чтобы дробь была меньше 1 (по условию), т. е. a <= N - 1

В общем, это первое что пришло на ум. Не уверен в корректности этого решения. Проверь, подумай сам еще.
Aslan 79
Aslan 79
541

Похожие вопросы