let x = 0
let y = 0
let d = 1
let m = 1
while true
while 2 * x * d < m
print(x, y)
x = x + d
while 2 * y * d < m
print(x, y)
y = y + d
d = -1 * d
m = m + 1
Было предложено множество решений этой проблемы, написанных на разных языках программирования, однако все они, похоже, основаны на одном и том же запутанном подходе. Я собираюсь рассмотреть более общую проблему вычисления спирали, которую можно кратко выразить с помощью индукции.
Базовый случай: начните с (0, 0), переместитесь на 1 квадрат вперед, поверните налево, переместитесь на 1 квадрат вперед, поверните налево. Индуктивный шаг: пройдите вперед n + 1 квадратик, поверните налево, пройдите вперед n + 1 квадратик, поверните налево.
Математическая элегантность выражения этой проблемы настоятельно предполагает, что должен быть простой алгоритм для вычисления решения. Помня об абстракции, я решил реализовать алгоритм не на конкретном языке программирования, а скорее в виде псевдокода.
Сначала я рассмотрю алгоритм для вычисления всего 2 итераций спирали с использованием 4 пар циклов while. Структура каждой пары похожа, но различна сама по себе. Сначала это может показаться безумием (некоторые циклы выполняются только один раз), но шаг за шагом я буду делать преобразования, пока мы не получим 4 пары циклов, которые идентичны и, следовательно, могут быть заменены одной парой, помещенной внутри другого цикла. Это даст нам общее решение вычисления n итераций без использования каких-либо условных выражений.
let x = 0
let y = 0
//RIGHT, UP
while x < 1
print(x, y)
x = x + 1
while y < 1
print(x, y)
y = y + 1
//LEFT, LEFT, DOWN, DOWN
while x > -1
print(x, y)
x = x - 1
while y > -1
print(x, y)
y = y - 1
//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x < 2
print(x, y)
x = x + 1
while y < 2
print(x, y)
y = y + 1
//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x > -2
print(x, y)
x = x - 1
while y > -2
print(x, y)
y = y - 1
Первое преобразование, которое мы сделаем, - это введение новой переменной d для направления, которая содержит либо значение +1, либо -1. Направление переключается после каждой пары петель. Поскольку мы знаем значение d во всех точках, мы можем умножить на него каждую сторону каждого неравенства, соответствующим образом скорректировать направление неравенства и упростить любое умножение d на константу до другой константы. Это оставляет нам следующее.
let x = 0
let y = 0
let d = 1
//RIGHT, UP
while x * d < 1
print(x, y)
x = x + d
while y * d < 1
print(x, y)
y = y + d
d = -1 * d
//LEFT, LEFT, DOWN, DOWN
while x * d < 1
print(x, y)
x = x + d
while y * d < 1
print(x, y)
y = y + d
d = -1 * d
//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < 2
print(x, y)
x = x + d
while y * d < 2
print(x, y)
y = y + d
d = -1 * d
//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < 2
print(x, y)
x = x + d
while y * d < 2
print(x, y)
y = y + d
Теперь отметим, что и x * d, и правая часть являются целыми числами, поэтому мы можем вычесть любое действительное значение от 0 до 1 из правой части, не влияя на результат неравенства. Мы решили вычесть 0,5 из неравенств каждой другой пары циклов while, чтобы установить больше закономерности.
let x = 0
let y = 0
let d = 1
//RIGHT, UP
while x * d < 0.5
print(x, y)
x = x + d
while y * d < 0.5
print(x, y)
y = y + d
d = -1 * d
//LEFT, LEFT, DOWN, DOWN
while x * d < 1
print(x, y)
x = x + d
while y * d < 1
print(x, y)
y = y + d
d = -1 * d
//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < 1.5
print(x, y)
x = x + d
while y * d < 1.5
print(x, y)
y = y + d
d = -1 * d
//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < 2
print(x, y)
x = x + d
while y * d < 2
print(x, y)
y = y + d
Теперь мы можем ввести другую переменную m для количества шагов, которые мы делаем в каждой паре циклов while.
let x = 0
let y = 0
let d = 1
let m = 0.5
//RIGHT, UP
while x * d < m
print(x, y)
x = x + d
while y * d < m
print(x, y)
y = y + d
d = -1 * d
m = m + 0.5
//LEFT, LEFT, DOWN, DOWN
while x * d < m
print(x, y)
x = x + d
while y * d < m
print(x, y)
y = y + d
d = -1 * d
m = m + 0.5
//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < m
print(x, y)
x = x + d
while y * d < m
print(x, y)
y = y + d
d = -1 * d
m = m + 0.5
//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < m
print(x, y)
x = x + d
while y * d < m
print(x, y)
y = y + d
Наконец, мы видим, что структура каждой пары циклов while идентична и может быть сведена к одному циклу, помещенному внутри другого цикла. Кроме того, чтобы не использовать действительные числа, я умножил начальное значение m; значение m увеличивается на; и обе части каждого неравенства на 2.
Это приводит к решению, показанному в начале этого ответа.
person
Mike
schedule
10.11.2015
