Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4   вперед  Ctrl      все
 Re: Ну что... с пятницей чтоли  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
А далее - обычный алгоритм:

первая линейка цифр по горизонтали (вертикали),
несколько обходов этой горизонтали(вертикали),
и остановиться в любое время, если образовался прямоугольник нужного размера.

Первая линейка может быть произвольной длины.

Если кому-то нужно сделать обратный порядок, то нет проблем.
6 окт 19, 17:51    [21987678]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 942
лучше 1 раз увидеть
6 окт 19, 18:39    [21987692]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Постарайтесь быть оригинальнее.

Классическая имплементации обсуждается в родительском топике.
6 окт 19, 19:19    [21987705]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Алгоритм:

Прямоугольник из 4-х точек: xmin и xmax, ymin и ymax
Для начальной линейки ymin = ymax

Работаем на плоскости.
Координаты очередной точки x, y

1 этап – x растёт от xmin.
Если x > xmax, то xmax +=1 и переходим на y

2 этап - y уменьшается от ymin
Если y < ymin, то ymin -=1 и переходим на x

3 этап - x уменьшается от xmax
Если x < xmin, то xmin -=1 и переходим на y

4 этап - y растёт от ymin
Если y > ymax, то ymax +=1 и переходим на x

Далее этап 1 и т.д.

Если x или y «останавливаются» на минимальных или максимальных значениях,
то получается прямоугольник.

Можно сделать и обратный обход.

Можно потом поменять порядок точек, чтобы попасть в "центр" прямоугольника.
6 окт 19, 19:27    [21987713]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1846
mayton
Постарайтесь быть оригинальнее.
Критерии? что такое экзотика?
Потому что, если "не помнит состояния доски", то что она помнит? свои ходы сал быть тоже не помнит, своё положение тоже не должна помнить. Мутная формулировка, сэр.

Или, например минимум, чево она помнит. Например только своё положение, но тогда заранее рассчитывается и зашивается в код. Для экзотики лично я сделал бы по Соколинскому, виток за витком, для экзотики можно с рекурсией, помнятся только текущие размеры прям-ка. Ну и направление во внутрьили наружу. Но время на это тратить неохота. Я бы понял бы ещё, если б это что-то моделировало ...
6 окт 19, 20:00    [21987726]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1846
Кстати, вот как раз для экзотики начальную точку можно выбрать не угол и не центр. И даже не периметр.
6 окт 19, 20:03    [21987732]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Главное забыл:

для точки с координатами (x, y) ставится число, равное порядковому изменению значений (x, y).

Можно начинать с 0, можно начинать с 1.

Если нужно, потом переворачиваем всю цепочку чисел.
6 окт 19, 20:05    [21987734]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 942
соот-но, по окончании 3го этапа надо сдвигать границу ymin на +1
а по окончании 4го - все остальные границы на -/+1
mayton
Постарайтесь быть оригинальнее.

Классическая имплементации обсуждается в родительском топике.

без математиков разве что проц грузить
6 окт 19, 20:06    [21987735]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
полудух
соот-но, по окончании 3го этапа надо сдвигать границу ymin на +1
а по окончании 4го - все остальные границы на -/+1
Попробуйте на простых числах и поймёте.

Поиск минимума - это уменьшение!

Каждый этап заканчивается только одним изменением, а не двумя.
6 окт 19, 20:10    [21987736]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1846
один здесь математик, и тот - Usov
6 окт 19, 20:10    [21987737]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dima T
Member

Откуда:
Сообщений: 14096
exp98
один здесь математик, и тот - Usov

Остальные в школу не ходили? Математика тут уровня средней школы.
6 окт 19, 20:14    [21987739]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1846
В принципе для экзотики можно по мере прохождения удалять путь из массива. А выход по исключению)) Ну то есть полудух прав, гонять байты туда-сюда.
6 окт 19, 20:16    [21987740]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1846
Dima T, я не про задачу, про программистов. Оч часто оказывается, что не не ходили.
6 окт 19, 20:20    [21987741]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dima T
Member

Откуда:
Сообщений: 14096
До компа только добрался, немного размышлял на эту тему и пришел к выводу что обычные координаты {x,y} легко преобразуются в номер ячейки спирали. Функция попозже.
6 окт 19, 20:26    [21987744]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
программисту тут массив не нужен
6 окт 19, 20:28    [21987749]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
booby
Member

Откуда:
Сообщений: 1683
Aleksandr Sharahov
программисту тут массив не нужен

это если он yield-ами программирует.
Но задача вполне может быть сформулирована и в терминах перестановки элементов массива.
Так, чтобы при принятом в языке соглашении о "сначала строках" или "сначала столбцах",
переставленный массив "естественным образом" отобразился в прямоугольнике необходимым образом.
6 окт 19, 20:33    [21987751]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1846
Aleksandr Sharahov
программисту тут массив не нужен
Вот-вот, проверяет пусть тестировщик.
6 окт 19, 20:38    [21987756]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
exp98
Aleksandr Sharahov
программисту тут массив не нужен
Вот-вот, проверяет пусть тестировщик.


я имел в виду 21987669
6 окт 19, 20:44    [21987763]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
полудух
соот-но, по окончании 3го этапа надо сдвигать границу ymin на +1
а по окончании 4го - все остальные границы на -/+1
mayton
Постарайтесь быть оригинальнее.

Классическая имплементации обсуждается в родительском топике.

без математиков разве что проц грузить

Ай.. ты просто не в курсе наших пятничных традиций...
6 окт 19, 20:45    [21987765]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1846
Кста, вот ещё вариант реализации.
Ходы(ф-ции): шаг вправо-влево, шаг вниз-вверх
Входной массив: указатели на ф-цию в нужной послед-сти.

"бэктрекинг" перестановок, с выполнением условий правильности перест-ки. На 40 эл-тов я наверное не возьмусь.
6 окт 19, 20:49    [21987769]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1846
Aleksandr Sharahov
я имел в виду 21987669
Ну вот и реализуй, с поправкой на то, что после каждого ххода меняется нумерация (если конечно есть желание).

Кста, ещё 2-поточный вариант: 2 потока делают ходы (т.е. 2 ф-ции) поочерёдно. Но каждому надо проверять, правильный ли ход у "коллеги".
6 окт 19, 20:58    [21987776]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
exp98
Aleksandr Sharahov
я имел в виду 21987669
Ну вот и реализуй, с поправкой на то, что после каждого ххода меняется нумерация (если конечно есть желание).

Кста, ещё 2-поточный вариант: 2 потока делают ходы (т.е. 2 ф-ции) поочерёдно. Но каждому надо проверять, правильный ли ход у "коллеги".


ну и реализовал несколькими способами в предыдущем топике )
6 окт 19, 21:14    [21987785]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 942
Aleksandr Sharahov
exp98
пропущено...
Вот-вот, проверяет пусть тестировщик.


я имел в виду 21987669

это ж оверхед
правильно внутри ф-и делать цикл
вектор это те же переменные, вы же не предлагаете от переменных отказываться
mayton
Ай.. ты просто не в курсе наших пятничных традиций...

да в курсе я ваших пятничных страданий )
взять всё, да и... написать на STL!
чтобы .rotate(), .reverse(), sets, sorting и прочие heaps
6 окт 19, 21:20    [21987787]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10988
Aleksandr Sharahov
Написать функцию f(m,n,i,j), которая при минимальных затратах памяти
возвращает номер присвоенный ячейке [i,j] в матрице m*n.
Можно и так.
1. Определяем номер слоя как мин. расстояние до границы.
2. Определяем грань (В П Н Л).
3. Тривиально считаем номер.
6 окт 19, 21:20    [21987789]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
полудух
Aleksandr Sharahov
я имел в виду 21987669

это ж оверхед
правильно внутри ф-и делать цикл


Зависит от задачи: если не нумеруем, а только считаем до нужной ячейки, то как раз не оверхед.
Кстати, там и циклы не нужны. Можно вывести формулу.
6 окт 19, 21:48    [21987801]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4   вперед  Ctrl      все
Все форумы / Программирование Ответить