Задача 11.
Определим множества K[i] рекуррентно. Пусть K[0] = [0,1]. Разделим сегмент [0,1] на три части точками 1/3 и 2/3 и удалим из него интервал (1/3,2/3). Получим множество K[1], состоящее из двух оставшихся сегментов [0,1/3] и [2/3,1]. Каждый из них разделим на три части (точками 1/9 и 2/9 для первого сегмента, и точками 7/9 и 8/9 - для второго ) и удалим средние интервалы (1/9,2/9) и (7/9,8/9). Таким образом получаем множество K[2], и т.д. Пусть мы построим множество K[i]. Поделим каждый оставшийся сегмент из K[i] на 3 части и удалим из этих сегментов средние интервалы. Получим, таким образом, из K[i] множество K[i+1].
Вводятся 3 целых числа n,a,b.
Необходимо определить, принадлежит ли точка с координатой a/b множеству K[n].
|
Решение задачи 11.
Очевидное решение: При попытке непосредственно вычислять координаты концов сегментов, принадлежащих множеству K[n], и определить, принадлежит ли a/b одному из этих сегментов даже для не слишком больших n за счет потери точности при вычислениях и из-за ограниченного числа знаков в машинном представлении чисел с плавающей точкой данный подход дает неверный ответ для большинства входных данных. При больших n вообще будет наблюдаться потеря значимости: число при делении на 3 станет таким малым, что в машине оно будет представляться нулем.
Рассмотрим другой метод решения этой задачи. Так как мы постоянно должны делить сегменты на три части, то это наталкивает на мысль использовать троичную систему счисления и троичные дроби. В первой из удаленных интервалов (1/3,2/3) попадают только те точки
x=0.a[1] a[2] a[3] ...
в троичном разложении которых a[1]=1, кроме точки 1/3=0.1000... -правого конца сегмента [0,1/3]. Таким образом, в K [1] остаются все те точки, у которых a[1] <>1, либо a[1]=1, a[2] = a[3] = ...= = 0. Аналогично, в множестве K[i], i>=0, содержатся точки, у которых ни одно из чисел a[j], 1<=j<=i, не равно 1, а также точки, удовлетворяющие условию: a[j]=1, j - фиксировано, 1<=j<=i, a[l]<>1, l<j, и a[l] =0 для любого l>j (то есть, в записи троичной дроби только одна позиция равна 1, после нее все остальные позиции нулевые. Эти дроби соответствуют правым концам сегментов из множества K[i]).
Запись алгоритма на Паскале имеет вид:
x:=a; i:=1;
while (i<=n) or (x<>1) or (a<>0) do
begin
a:=a*3 mod b;
x:=a*3 div b;
i:=i+1;
end;
if (x=1) and (a<>0) and (n<>0)
then writeln(' Не принадлежит') else writeln(' Принадлежит');
|
