Олимпиадный тренинг

Задача . Рациональный бинарный поиск. Реализация


Задача

Темы:
На одном из ЕГЭ по профильной математике был вопрос
"Существуют ли двузначные натуральные числа m и n такие, что \(|\frac{m}{n} - \sqrt2| \leq \frac{1}{100}\)"
Зададимся вопросом как найти "лучшее" приближение \(\sqrt n\) с помощью рациональной дроби
с "некоторыми ограничениями на числитель и знаменатель дроби.
Условие задание
Найдите "лучшее представление" \(\sqrt 2\) с помощью рациональной дроби со знаменателем, 
не превосходящим K
Ниже представлена программа, реализующая данную программу методом "бинарный поиск", 
путем деления отрезка [1;2] в отношении [n:m] с ограничением на (n+m)
В самом деле, искомое значение лежит в [1;2] и если точка T делит отрезок [A;B] в отношении
AT:TB = n:m, то T = (A*m +B*n)/(n+m) = (m + 2n)/(m+n) = 1 + n/(m+n)

Ваша задача написать функцию check((n,m)), которая должна возвращать
  • True  - если разбиение определяет точку не меньшую \(\sqrt 2\)
  • False - в противном случае

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python16
Комментарий учителя

Ваш ответ

Python
Напишите программу ниже 
K = int(input()) #ограничение на знаменатель дроби
L, R = (0,1), (1,0)
while sum(L) + sum (R) < K :
    M = (L[0] + R[0], L[1] + R[1])
    if check2(M) : R = M
    else : L = M
print( R[1] + 2* R[0], R[1] + R[0])
     

Загруженные файлы
Нет