Практика программирования (Бейсик, Си, Паскаль)
В отличие от Улама мы
В отличие от Улама мы будем нумеровать не клеточки, а узлы целочисленной решетки, начав эту процедуру с нулевого узла в начале системы координат (рис. 2.1).
Рис. 2.1. Нумерация точек на скатерти Улама
Одна из наиболее естественных задач заключается в определении координат точки по ее номеру-ы. Конечно, ее решение можно построить на базе прямого перебора всех точек спирали до узла с заданным номером. При этом движение, начинающееся из точки с номером о, состоит сначала из одного шага вправо (x=x+1) и вверх (у=у+1), затем из двух последовательных шагов влево (x=x-1) и вниз (y=y-l), из трех последовательных шагов вправо и вверх, из четырех последовательных шагов влево и вниз и т. д. Однако при достаточно больших значениях N такая процедура требует слишком много времени.
Гораздо интереснее построить более эффективный алгоритм решения задачи. Одна из идей заключается в определении координат угловой точки, расположенной на общей с нашей точкой горизонтальной или вертикальной ветви спирали. Заметим, что на луче, проведенном из начала координат через узлы с координатами (-п,п), располагаются точки с номерами (2*n)2.
На аналогичном луче, начинающемся из первой точки и проходящем через точки с координатами (n,-n+l), расположены точки с номерами (2*n-1)2. Поэтому нам достаточно обнаружить ближайший к N квадрат числа q, чтобы сообразить, на какой из четырех ветвей "спирали" находится точка с номером N. Если q -- четное, то в зависимости от разности qz-N интересующая нас точка находится на верхней или левой ветви. И для вычисления координат достаточно откорректировать одну из координат угловой точки (-q,q) на величину разности. Если q оказалось нечетным, то ветвь, содержащая точку с номером N, находится либо внизу, либо справа. И тогда коррекции надо подвергнуть одну из координат точки (q, -q+1).
Аналогичная идея может быть использована и для обратного преобразования координат заданной точки (х,у) в ее порядковый номер на спирали. Достаточно определить ближайшую угловую точку с коррдинатами (-q, q) или (q,-q+i) и произвести соответствующую коррекцию номера выбранной угловой точки. Несмотря на кажущуюся простоту идеи, ее реализация требует тщательной проверки многочисленных условий.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий