Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Арифметика >> Номер 12

[Назад]    [Содержание ]    [Вперед]

  


Номер 12


  Условие: Номер 12


Задача 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].

  Решение задачи: Номер 12


Решение задачи 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(' Принадлежит');

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017