Определить порядковый номер точки по ее координатам на плоскости N го порядка. Расписать алгоритм решения..
Дискретная математика ( Высшая математика )
Каждое натуральное число обладает очень многими известными и, по-видимому, еще в большем числе неизвестными свойствами. Четные – нечетные, простые – составные, конечные – бесконечные и др. свойства способствуют введению классификации чисел, некоторого порядка в их множестве. Традиционный подход предполагает, что не располагая самим числом (его значением) невозможно определить и его свойства. Но это не совсем так. Ряд полезных свойств для некоторых чисел можно определять не зная их значений, но имея данные об их положении в натуральном ряде чисел (НРЧ). Простыми числами, кроме 2, могут быть только нечетные с флексией ≠ 5, а их положение НРЧ определяется нечетной позицией. Сами эти позиции не все равнозначны. Про некоторые большие нечетные N(x1, x2) числа (разумеется в нечетных позициях в НРЧ) можно, не пользуясь традиционными (вероятностными) и детерминированным (весьма трудоемким) алгоритмами, однозначно утверждать, они не могут быть простыми.
Будем рассматривать связь свойств натуральных чисел и их положения в НРЧ, считая такую связь существующей.
Например, нечетное число, равное четному квадрату (>2) без единицы, всегда составное: х² -1 = (х +1)(х -1). Нечетный квадрат – число составное. Информацию об этом в удобной форме как раз и предоставляет модель НРЧ – спираль Улама, где положение всех квадратов однозначно определено.
Следовательно, описанные диагональные лучи, прижатые к диагоналям квадратов, простых чисел содержать не могут. Кроме упомянутых линий, ниже укажем на другие, обладающие этим же свойством. Это свойство модели ранее ни самим Уламом, ни другими авторами, которые с моделью работали или упоминали ее в публикациях, не отмечалось. Загадки большой в этом нет. Отождествим точку (клетку) с координатами (x1, x2) плоскости спирали и число N(x1, x2) в этой позиции.
Факт существования запретной области для простых чисел в НРЧ установлен из наблюдений спирали, а затем подтвержден (доказан) автором математическими средствами. Полезность этого свойства не очевидна. Но для нечетных чисел, положение клеток (x1, x2) которых в спирали принадлежит области запрета простых чисел, устанавливается не только их не простота, но и факторизуются они без проблем.
На основе этого факта о некоторых нечетных числах N(x1, x2) даже очень большой разрядности можно с достоверностью единица утверждать, что они составные и затем легко их факторизовать.
Система спирали Улама скорее ближе к полярной, чем к декартовой. Роль первой координаты х1 числа N(x1, x2) отведена номеру контура (х1 = k). Вторая координата х2 < L(k), где L(k) — длина контура, определяет удаленность клетки с числом N(x1, x2) от начала контура.
Рисунок 1 -Модель НРЧ и увеличеный фрагмент центральной части спирали
Рис.2 Представление моделью спирали фрагмента (200х200 клеток) натурального ряда с закрашенными клетками для простых чисел.
Примем для удобства обозначения для координат, соответственно, «х» и «у». Определение координат точки по ее номеру N – одна из наиболее естественных задач, как решение противоположной задачи- нахождение порядкового номера по координатам. Решение прямой задачи можно построить на базе прямого перебора всех точек спирали до узла с заданным номером. При этом движение, начинающееся из точки с номером 0, состоит сначала из одного шага вправо (x = x+1) и вверх (y = y+1), затем из двух последовательных шагов влево (x = x-1) и вниз (y = y-1), из трех последовательных шагов вправо и вверх, из четырех последовательных шагов влево и вниз и т.д. Однако при достаточно больших значениях N такая процедура требует слишком много времени и намного интереснее построить алгоритм решения задачи. Рассмотрим теперь задачу обратную, а именно определение по координатам заданной точки (x,y) в ее порядковый номер на спирали Улама (рис.1). Отождествим точку (клетку) с координатами (x, у) плоскости спирали и число N(x, у) в этой позиции (рис.2)
Решение:
Достаточно определить ближайшую угловую точку с координатами (-q,q) или (q, -q+1) и произвести соответствующую коррекцию выбранной угловой точки. При этом обратим внимание на то, что диагональ y = x делит узлы нашей решетки на два множества.
Для всех узлов, расположенныхслева от диагонали, выполняется условие x≥y.
Пусть точка с координатами (x,y) расположена либо на горизонтальном витке спирали, находящемся в левой полуплоскости, либо на вертикальном витке, спускающемся до диагонали.
Разобьем каждый из этих витков на две части и пронумеруем их следующим образом:
Горизонтальный участок от диагонали до оси «y» ;
Горизонтальный участок от оси «y» до угла поворота;
Вертикальный участок от угла поворота до оси «x»;
Вертикальный участок от оси «х» до очередного поворота.
На каждом из этих участков справедливы следующие соотношения, которые и будут представлять АЛГОРИТМ решения поставленной задачи.
1: x≥0, y>0
2: x<0, y>0, y≥|x|
3: x<0, y≥0, y≤|x|
4: x<0, y≤0
Определив принадлежность точки тому или иному участку, мы можем вычислить координаты левого верхнего угла поворота (x0, y0) и найти порядковый номер этого узла N = (2*x0)2.
Затем, в зависимости от номера участка легко можно найти номер точки с координатами (x,y).
Рассуждения аналогичного характера можно повторить и для участков горизонтальной и вертикальной ветвей, принадлежащих правой полуплоскости.
Ниже приводится программа на языке Бейсик, названная coord_to_n реализации этого алгоритма. В ней для обозначения соответствующих четырех частей использованы буквенные обозначения – a, b, c, d.
Для вычисления номера искомой точки, здесь используется правый нижний угол поворота. Отметим, что программа предельно простая. Декларируются переменные, затем используются внутренние циклы IF-END IF в соответствии с выше приведенным алгоритмом.
DECLARE FUNCTION CoordToN! (X&, Y%)
REM Вычисление номера узла по его координатам
INPUT ”Введите координаты узла: ”, X&, Y&
M& = CoordToN (X&, Y&)
PRINT ”Его номер”; M&
END
FUNCTION CoordToN (X&, Y&)
IF X& <=Y& THEN ‘если узел в левой полуплоскости
IF X& >= 0 AND Y& > 0 THEN GOTO m12 ‘случай 1
IF X& < 0 AND Y& >= 0 AND Y& >= ABS (X&) THEN ‘случай 2
’обработка случаев 1 и 2
m12: x0= -Y&: y0 = Y&: N& = (2*x0)^2 ‘координаты и номер угла
CoordToN = N& + x0 – X&: EXIT FUNCTION
ELSE
‘обработка случаев 3 и 4
X0= X&: y0 = – X&: N& = (2*x0)^2
CoordToN = N& + y0 – Y&: EXIT FUNCTION
END IF
END IF
‘если узел в правой полуплоскости
IF X& <= 0 AND Y& < 0 THEN GOTO mab ‘случай a
IF X& >= 0 AND Y& < 0 AND ABS (Y&) >= X& THEN ‘случай b
’обработка случаев a, b
mab: x0= -Y&+1: y0 = -Y&: N& = (2*x0-1)^2
CoordToN = N& – x0 + X&: EXIT FUNCTION
ELSE
‘обработка случаев c, d
X0= X&: y0 = – X&+1: N& = (2*x0-1)^2
CoordToN = N& + Y&- y0
END IF
END FUNCTION
