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

Откуда: loopback
Сообщений: 42891
Пятничная экзотическая задачка.

Распечатать прямоугольник цифирками по спирали.

123
654


Или
123
894
765


Реализация - чем экзотичнее - тем лучше. Brainfuck. Машина Тьюринга. Perl. Функциональщина.
Формула мат-лаба. Чистая функция или грязная. SQL-запрос. Конечные-бесконечне автоматы.
Корутины.

Вобщем проявите фантазию. Разумеется параметризация должна быть. 2х3 или 3х3....

Gogo кодить!!!

Самому отличившемуся - респект.

Сообщение было отредактировано: 4 окт 19, 18:40
4 окт 19, 18:37    [21987057]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dima T
Member

Откуда:
Сообщений: 14090
Я тоже на эту тему задумывался :)

Предлагаю чуть упростить задачу: прямоугольник заменяем квадратом, а спираль закручиваем внутрь, т.е.
1 2 3
8 9 4
7 6 5

Так и код будет красивее и студентам списать не получится.
4 окт 19, 18:45    [21987065]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48625
Квадрат это слишком просто. Прямоугольник 7х3 - вот это вызов.
5 окт 19, 13:40    [21987321]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
А что будет сложного в 7:3 ? Или чем сложнее?
5 окт 19, 13:55    [21987329]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Для квадрата размера N. На неком гипотетическом Logo.
выглядело бы так.

Вперед N
Поворот вправо
....
N=N-1
И повтор.

Это будет просто закрашивание. А нам надо добавить еще учет количества.
Тоесть движение черепашки вперед - это еще и закрашивание сиквенсом.
5 окт 19, 16:48    [21987362]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Забавная штука есть Piet. Язык программирования где команды - это цветные квадраты. А растр - это суть исходник.

http://www.dangermouse.net/esoteric/piet/samples.html
5 окт 19, 17:02    [21987367]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dima T
Member

Откуда:
Сообщений: 14090
Я тут подумал что можно попробовать решить другую задачу: имея размер квадрата и координаты ячейки рассчитать ее номер.

Каждый квадрат 2N-2 ячеек, где N размер стороны. Отсюда вычисляем первое число квадрата. Далее надо как-то получить N и на каком месте ячейка
6 окт 19, 09:49    [21987539]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
В топике Тяпничная география
мы решали более интересную задачу. Обход плоскости по кривой Гилберта. Кривая интересна тем что расстояние между
соседними точками всегда 1 в абсолютном эквиваленте. И любые интервалы отложенные вдоль этой кривой всегда
представляют собой композицию квадратов. Причем минимальную. Я обратил внимание тогда что эту кривую часто
используют для графического изображения интервалов IP-blocks.
6 окт 19, 12:20    [21987577]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
mayton,

тему топика вроде обсуждали уже тут:
https://www.sql.ru/forum/1118954-1/obhod-pryamougolnika-po-spirali-poisk-bolee-podhodyashhego-algoritma
6 окт 19, 12:40    [21987582]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Aleksandr Sharahov,

Да это клон. Я создал. Как и обещал но с другим смыслом.
6 окт 19, 12:57    [21987590]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48625
mayton
А что будет сложного в 7:3 ?

Положение числа 1. При раскрутке из центра.
6 окт 19, 13:31    [21987613]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
Dimitry Sibiryakov,

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

Откуда: Москва
Сообщений: 10985
mayton
Распечатать прямоугольник цифирками по спирали.
Никаких проблем, даже кодить неинтересно.
В обработке изображений алгоритм обхода называется цепным кодом Фримена.
Просто идем от верхней левой ячейки и ищем ближайшую пустую по- или против часовой.
6 окт 19, 14:42    [21987632]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10985
Dimitry Sibiryakov
Положение числа 1. При раскрутке из центра.
Строим алгоритм обхода "из угла", потом перенумеровываем в обратном порядке.
6 окт 19, 15:08    [21987637]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
Соколинский Борис,

там нет пустых и не пустых, они не отличаются.

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

Откуда: планета орков, г.Зверополис
Сообщений: 936
не думаю, что алгоритм Фримена поможет распечатать (именно распечатать, а не "обойти изображение") такую спираль
0   1   2   3   4   5   6
21  22  23  24  25  26  7
20  35  36  37  38  27  8
19  34  41  40  39  28  9
18  33  32  31  30  29  10
17  16  15  14  13  12  11

да и когда там как-то дохрена для студента
тут математикой надо решать
построчный перебор и заполнение каждой строки (вектора) с учётом границ, которые сужаются
6 окт 19, 16:26    [21987651]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 936
*когда = кода
6 окт 19, 16:26    [21987652]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10985
Aleksandr Sharahov
там нет пустых и не пустых, они не отличаются.
Даже не знаю что сказать.
Не могу представить средство разработки в котором невозможно определить, была ли уже заполнена ячейка.
6 окт 19, 16:39    [21987655]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Соколинский Борис
Aleksandr Sharahov
там нет пустых и не пустых, они не отличаются.
Даже не знаю что сказать.
Не могу представить средство разработки в котором невозможно определить, была ли уже заполнена ячейка.

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

Откуда:
Сообщений: 1834
полудух
не думаю, что алгоритм Фримена поможет распечатать (именно распечатать, а не "обойти изображение") такую спираль
0   1   2   3   4   5   6
21  22  23  24  25  26  7
20  35  36  37  38  27  8
19  34  41  40  39  28  9
18  33  32  31  30  29  10
17  16  15  14  13  12  11

да и когда там как-то дохрена для студента тут математикой надо решать
построчный перебор и заполнение каждой строки (вектора) с учётом границ, которые сужаются
Если сделать из центра спираль
(вместо 2-х на 3 цифры по горизонтали)
начиная с 0 и заканчивая 41,
то просто меняем очерёдность с 0 - 41 на 41 - 0.
6 окт 19, 16:49    [21987659]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10985
полудух
не думаю, что алгоритм Фримена поможет распечатать (именно распечатать, а не "обойти изображение") такую спираль
А в чем проблема? Именно так она и построится.
Можно и без Фримена, просто вычеркивать заполненные строки/столбцы и менять направление обхода при завершении линмм
6 окт 19, 16:59    [21987664]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 936
Gennadiy Usov
то просто меняем очерёдность с 0 - 41 на 41 - 0.

и что это будет?
в одной строке всего 7 ячеек, а вы хотите 42 обходить туда-обратно
Соколинский Борис
Можно и без Фримена, просто вычеркивать заполненные строки/столбцы и менять направление обхода при завершении линмм

затык в границах. Они живут своей жизнью. При этом ещё и сокращаются.
6 окт 19, 17:18    [21987668]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
Соколинский Борис
полудух
не думаю, что алгоритм Фримена поможет распечатать (именно распечатать, а не "обойти изображение") такую спираль
А в чем проблема? Именно так она и построится.
Можно и без Фримена, просто вычеркивать заполненные строки/столбцы и менять направление обхода при завершении линмм


Написать функцию f(m,n,i,j), которая при минимальных затратах памяти
возвращает номер присвоенный ячейке [i,j] в матрице m*n.
6 окт 19, 17:19    [21987669]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
полудух
Gennadiy Usov
то просто меняем очерёдность с 0 - 41 на 41 - 0.

и что это будет?
в одной строке всего 7 ячеек, а вы хотите 42 обходить туда-обратно
А если ещё раз взглянуть на картинку (где 42) и подумать.

И поставить вместо 41 - 0, вместо 40 - 1, ...., вместо 0 - 41.
Что получится?

То есть, обход из центра от 0 до 41, а потом меняются цифры в обратном порядке.
6 окт 19, 17:39    [21987674]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Двумерная поверхность по форме напоминающая пирамидку.
6 окт 19, 17:42    [21987676]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Gennadiy Usov
Member

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

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

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

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

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

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

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

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

Прямоугольник из 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Откуда:
Сообщений: 14090
До компа только добрался, немного размышлял на эту тему и пришел к выводу что обычные координаты {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

Откуда:
Сообщений: 1843
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
Сообщений: 42891
полудух
соот-но, по окончании 3го этапа надо сдвигать границу ymin на +1
а по окончании 4го - все остальные границы на -/+1
mayton
Постарайтесь быть оригинальнее.

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

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

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

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

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

Откуда:
Сообщений: 1843
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

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


я имел в виду 21987669

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

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

Откуда: Москва
Сообщений: 10985
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]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
Не, это не экзотично. "Мша и мудведь" интереснее.
6 окт 19, 22:01    [21987807]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 936
если формулу можно вывести, то её место в макросе вообще )
я сразу сказал про математиков
а пока вы предлагаете каждой ячейке вызывать функцию.
6 окт 19, 22:04    [21987808]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
полудух
если формулу можно вывести, то её место в макросе вообще )
я сразу сказал про математиков
а пока вы предлагаете каждой ячейке вызывать функцию.


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

Откуда: loopback
Сообщений: 42891
Да что там спираль! Давайте сразу функцию которая возвращает кривую Гилберта.
Можно итератор. По сабжу мой вариант - двухпоточный. И это мать ево не круто.

Картинка с другого сайта.

Тематически связано с https://www.sql.ru/forum/1303834/tyapnichnaya-budushhaya-multipotochnost
6 окт 19, 22:38    [21987820]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 936
или с этим? https://www.sql.ru/forum/1146875-3/tyapnichnaya-geografiya?mid=17384728#17384728
7 окт 19, 02:02    [21987870]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
Да что там спираль! Давайте сразу функцию которая возвращает кривую Гилберта.
Можно итератор. По сабжу мой вариант - двухпоточный. И это мать ево не круто.
Я не понял.

Со спиралью разобрались?
7 окт 19, 06:31    [21987883]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dima T
Member

Откуда:
Сообщений: 14090
Написал преобразование обычных координат в спиральные
// Номер ячейки (x,y) на спирали в квадрате n*n
int spiral(int n, int x, int y) {
	// Квадрат на котором расположена ячейка
	int k = std::min(std::min(x, n-x+1), std::min(y, n-y+1)); // Начало квадрата
	int q = n + 2 - 2*k; // Размер стороны
	// Расстояние от начала квадрата
	int r = 0;
	if (y == k) {
		r = x - k + 1;
	} else if (x == k + q - 1) {
		r = y - k + q;
	} else if (y == k + q - 1) {
		r = k - x + q*3 - 2;
	} else {
		r = k - y + q*4 - 3;
	}
	return r + n*n - q*q;
}

// Вывод квадрата n*n
void print(int n) {
	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= n; x++) {
			printf("%3d", spiral(n, x, y));
		}
		printf("\n");
	}
}
7 окт 19, 07:06    [21987886]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Gennadiy Usov
mayton
Да что там спираль! Давайте сразу функцию которая возвращает кривую Гилберта.
Можно итератор. По сабжу мой вариант - двухпоточный. И это мать ево не круто.
Я не понял.

Со спиралью разобрались?

Спираль не особо интересна IMHO.
Так... Для старта беседы.
7 окт 19, 07:41    [21987893]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 936
переформатировал
как лучше?
//##############################################################################
// Номер ячейки (x,y) на спирали в квадрате n*n
int spiral(int n, int x, int y)
{
    // Квадрат на котором расположена ячейка
    int k = min(min(x, n - x + 1), min(y, n - y + 1));  // Начало квадрата
    int q = n + 2 - 2 * k;                              // Размер стороны
    int r = 0;                                          // Расстояние от начала квадрата

    if          (y == k)                {r = x - k + 1;}
    else if     (x == k + q - 1)        {r = y - k + q;}
    else if     (y == k + q - 1)        {r = k - x + q * 3 - 2;}
    else                                {r = k - y + q * 4 - 3;}

    return r + n * n - q * q;
}
//##############################################################################
7 окт 19, 12:53    [21988121]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
полудух
переформатировал
как лучше?
//##############################################################################
// Номер ячейки (x,y) на спирали в квадрате n*n
Это не интересно.

Нужен прямоугольник n * m.21987713
7 окт 19, 13:07    [21988143]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
полудух
переформатировал
как лучше?
    else if     (x == k + q - 1)        {r = y - k + q;}
    else if     (y == k + q - 1)        {r = k - x + q * 3 - 2;}

Это ужасно. Оставь как было.
7 окт 19, 13:20    [21988164]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48625
Соколинский Борис
Строим алгоритм обхода "из угла", потом перенумеровываем в обратном порядке.

Отлично. Но при этом цифра 1 вместо центра внезапно оказывается у правого края матрицы.
7 окт 19, 13:35    [21988186]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dima T
Member

Откуда:
Сообщений: 14090
Dimitry Sibiryakov
Соколинский Борис
Строим алгоритм обхода "из угла", потом перенумеровываем в обратном порядке.

Отлично. Но при этом цифра 1 вместо центра внезапно оказывается у правого края матрицы.

Почему? Вместо 1,2,...,9 сделай 9,8,...,1. Количество чисел заранее известно n*m
7 окт 19, 13:42    [21988203]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
Gennadiy Usov
Это не интересно.

Нужен прямоугольник n * m.21987713


function z(x, y, xSize, ySize: integer): integer;
var
  d, t: integer;
begin;
  if (x<0) or (x>=xSize) or (y<0) or (y>=ySize) then Result:=-1
  else begin;
    d:=min(min(min(x,y),xSize-x-1),ySize-y-1);
    t:=xSize*ySize-(xSize-2*d)*(ySize-2*d);
    if d=y then Result:=t+x-d
    else if d=xSize-x-1 then Result:=t+y+xSize-3*d-1
    else if d=ySize-y-1 then Result:=t-x+2*xSize+ySize-5*d-3
    else Result:=t-y+2*xSize+2*ySize-7*d-4;
    end;
  end;
7 окт 19, 15:16    [21988375]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dima T
Member

Откуда:
Сообщений: 14090
Aleksandr Sharahov
  if (x<0) or (x>=xSize) or (y<0) or (y>=ySize) then Result:=-1

Можно проще проверить d >= 0
7 окт 19, 15:19    [21988383]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
Dima T,

точно
7 окт 19, 15:24    [21988393]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
Поскольку ьайтон и Барон посчитали-таки пару доп. диапазонов для 2^2048 и 4096,
(моя оценка для них 140,79 и 17,605, что почти укладывается в дельту sqrt(Ln x), т.е. почти в одну сигму)
то и я подобрел, и отвлёкся от любимых движущихся самолётов и парашютистов.

На МЛ, не шедевр, конечно. Всё же непосредственное вычисление координат удобнее, нежели закраска по спирали. Так что не нужно экзотики. Тем не менее.
Исходник, конечно подводные камни были, закрыл заплатками
+
n= чччч; m= ааааа;
A= zeros(n,m); nc= floor(n/2); mc= floor(m/2); B= [1:n*m]; t=0; 
for k= 1:nc+1  
  hy= n-2*(k-1); hx= m-2*(k-1); 
  if n<=m
	if (2*nc < n) && (k==nc+1) %% нечётное
		A(k, k:end-k)= B(t+1 : t+hx-1); t= t+hx-1; 
		A(k, 1+end-k)= B(t+1); t= t+1;
	end; 
	if 2*k <= n
		A(k, k:end-k)= B(t+1 : t+hx-1); t= t+hx-1; 
		A(k:end-k, end-k+1)= B(t+1 : t+hy-1); t= t+hy-1; 
		A(end-k+1, end-k+1:-1:k+1)= B(t+1 : t+hx-1); t= t+hx-1; 
		A(end-k+1:-1:k+1, k)= B(t+1 : t+hy-1); t= t+hy-1; 
	end; 
  else 
	if 2*k <= m  %% вертик-ный  прям-к
	    A(k, k:end-k)= B(t+1 : t+hx-1); t= t+hx-1; 
		A(k:end-k, end-k+1)= B(t+1 : t+hy-1); t= t+hy-1; 
		A(end-k+1, end-k+1:-1:k+1)= B(t+1 : t+hx-1); t= t+hx-1; 
		A(end-k+1:-1:k+1, k)= B(t+1 : t+hy-1); t= t+hy-1; 
	else  %% вертик-ный столб
	    hx= 2; 
	    if 2*mc < m  %% нечётное
		A(k, mc+1)= B(t+1 : t+hx-1); t= t+hx-1; 
		if 2*k <= n 
		    A(end-k+1, mc+1)= B(t+1 : t+hx-1); t= t+hx-1; 
	    	    if t >= n*m  break, end; 
	    	end; 
	    end; 
	end; 
  end; 
end; [k, t], A

Данные
+

n=5; m=9;
     1     2     3     4     5     6     7     8     9
    24    25    26    27    28    29    30    31    10
    23    40    41    42    43    44    45    32    11
    22    39    38    37    36    35    34    33    12
    21    20    19    18    17    16    15    14    13

n=9; m=5;
     1     2     3     4     5
    24    25    26    27     6
    23    40    41    28     7
    22    39    43    29     8
    21    38    45    30     9
    20    37    44    31    10
    19    36    42    32    11
    18    35    34    33    12
    17    16    15    14    13

n=7; m=6;
     1     2     3     4     5     6
    22    23    24    25    26     7
    21    36    37    38    27     8
    20    35    42    39    28     9
    19    34    41    40    29    10
    18    33    32    31    30    11
    17    16    15    14    13    12

n=6; m=7; 
     1     2     3     4     5     6     7
    22    23    24    25    26    27     8
    21    36    37    38    39    28     9
    20    35    42    41    40    29    10
    19    34    33    32    31    30    11
    18    17    16    15    14    13    12

n=5; m=10;
     1     2     3     4     5     6     7     8     9    10
    26    27    28    29    30    31    32    33    34    11
    25    44    45    46    47    48    49    50    35    12
    24    43    42    41    40    39    38    37    36    13
    23    22    21    20    19    18    17    16    15    14

n=10; m=5;
     1     2     3     4     5
    26    27    28    29     6
    25    44    45    30     7
    24    43    47    31     8
    23    42    49    32     9
    22    41    50    33    10
    21    40    48    34    11
    20    39    46    35    12
    19    38    37    36    13
    18    17    16    15    14

n=5; m=11;
     1     2     3     4     5     6     7     8     9    10    11
    28    29    30    31    32    33    34    35    36    37    12
    27    48    49    50    51    52    53    54    55    38    13
    26    47    46    45    44    43    42    41    40    39    14
    25    24    23    22    21    20    19    18    17    16    15

n=11; m=5;
     1     2     3     4     5
    28    29    30    31     6
    27    48    49    32     7
    26    47    51    33     8
    25    46    53    34     9
    24    45    55    35    10
    23    44    54    36    11
    22    43    52    37    12
    21    42    50    38    13
    20    41    40    39    14
    19    18    17    16    15

n=7; m=7;
     1     2     3     4     5     6     7
    24    25    26    27    28    29     8
    23    40    41    42    43    30     9
    22    39    48    49    44    31    10
    21    38    47    46    45    32    11
    20    37    36    35    34    33    12
    19    18    17    16    15    14    13

n=6; m=6;
     1     2     3     4     5     6
    20    21    22    23    24     7
    19    32    33    34    25     8
    18    31    36    35    26     9
    17    30    29    28    27    10
    16    15    14    13    12    11

n=6; m=8;
     1     2     3     4     5     6     7     8
    24    25    26    27    28    29    30     9
    23    40    41    42    43    44    31    10
    22    39    48    47    46    45    32    11
    21    38    37    36    35    34    33    12
    20    19    18    17    16    15    14    13

n=8; m=6;
     1     2     3     4     5     6
    24    25    26    27    28     7
    23    40    41    42    29     8
    22    39    48    43    30     9
    21    38    47    44    31    10
    20    37    46    45    32    11
    19    36    35    34    33    12
    18    17    16    15    14    13

n=6; m=10;
     1     2     3     4     5     6     7     8     9    10
    28    29    30    31    32    33    34    35    36    11
    27    48    49    50    51    52    53    54    37    12
    26    47    60    59    58    57    56    55    38    13
    25    46    45    44    43    42    41    40    39    14
    24    23    22    21    20    19    18    17    16    15

n=10; m=6;
     1     2     3     4     5     6
    28    29    30    31    32     7
    27    48    49    50    33     8
    26    47    60    51    34     9
    25    46    59    52    35    10
    24    45    58    53    36    11
    23    44    57    54    37    12
    22    43    56    55    38    13
    21    42    41    40    39    14
    20    19    18    17    16    15

n=7; m=3;
     1     2     3
    16    17     4
    15    19     5
    14    21     6
    13    20     7
    12    18     8
    11    10     9

n=3; m=7;
     1     2     3
    16    17     4
    15    19     5
    14    21     6
    13    20     7
    12    18     8
    11    10     9


n=3; m=3;
     1     2     3
     8     9     4
     7     6     5

n=3; m=1;
     1
     3
     2

n=1; m=3;
     1     2     3

n=1; m=4;
     1     2     3     4

n=2; m=2;
     1     2
     4     3

n=1; m=1;
     1

n=0; m=1000;
     Ты больной?..

7 окт 19, 18:50    [21988680]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
забыл добавить. Спираль закручивается по часовой от угла А(1,1), при нечётности внутри может остаться строка либо столб. Так вот, если строка, то её заполняю подряд, если столб, то его по псевдоспирали (верх-низ. верх-низ и т.д.). В примерах видно.
7 окт 19, 18:56    [21988685]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
exp98, шикарно.

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

Откуда:
Сообщений: 1834
exp98
На МЛ, не шедевр, конечно. Всё же непосредственное вычисление координат удобнее, нежели закраска по спирали. Так что не нужно экзотики. Тем не менее.
Исходник, конечно подводные камни были, закрыл заплатками
n=9; m=5;
     1     2     3     4     5
    24    25    26    27     6
    23    40    41    28     7
    22    39    43    29     8
    21    38    45    30     9
    20    37    44    31    10
    19    36    42    32    11
    18    35    34    33    12
    17    16    15    14    13
А почему чехарда с цифрами под 40-45?

Подгонка?
7 окт 19, 19:53    [21988729]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
Здесь объяснено.
exp98
внутри может остаться строка либо столб. Так вот, если строка, то её заполняю подряд, если столб, то его по псевдоспирали (верх-низ. верх-низ и т.д.).
В даном случае столб [41 43 45 44 42]'.
7 окт 19, 20:04    [21988739]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
exp98
Здесь объяснено.
exp98
внутри может остаться строка либо столб. Так вот, если строка, то её заполняю подряд, если столб, то его по псевдоспирали (верх-низ. верх-низ и т.д.).
В даном случае столб [41 43 45 44 42]'.
То что "верх-низ. верх-низ" к математике мало имеет отношение.
Это несколько иное.

Чехарда невозможна.

По условию задачи должно быть плавное заполнение последнего участка.
7 окт 19, 20:09    [21988744]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
Gennadiy Usov, это не чехарда, это, сказано выше уже, псевдоспираль.
Я не читал про плавное заполнение, очень нужно если, возьми вторую половину проги (после else ), и переделай в ней вторую половину сам. Потом напишешь статью про плавное заполнение вертикальных участков.
7 окт 19, 20:52    [21988818]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
exp98
Gennadiy Usov, это не чехарда, это, сказано выше уже, псевдоспираль.
Я не читал про плавное заполнение, очень нужно если, возьми вторую половину проги (после else ), и переделай в ней вторую половину сам. Потом напишешь статью про плавное заполнение вертикальных участков.
Почему горизонтальный участок заполняется нормально,
а вертикальный участок заполняется через Ж(вверх-вниз)?
7 окт 19, 21:03    [21988832]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
Gennadiy Usov, здесь объяснено В случае возникновения вопросов см. данный пост.
7 окт 19, 21:35    [21988874]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
Вариант проще, без экзотики.
Исходник
+
%% по спирали, начиная с А(1,1), по часовой стрелке, 
%% по принципу левой руки в лабиринте: Ползти червяком прямо,
%% пока ползётся, затем повернуть направо и снова прямо.
clear all; n= 7; m= 5; ...
A= zeros(n,m); t=1; x2= 1; y2= 1; A(1,1)= t; x0=x2; y0=y2; ...
while t<n*m
      x0= x2; y0= y2;
      for x= x0+1:m 
        if A(y0,x)==0 t= t+1; A(y0,x)= t; x2= x; else  break,  end; 
      end; ...   
  
      x0= x2; y0= y2;
      for y= y0+1:n 
        if A(y,x0)==0 t= t+1; A(y,x0)= t; y2= y; else  break,  end;
      end; ...   
        
      x0= x2; y0= y2;
      for x= x0-1:-1:1 
        if A(y0,x)==0 t= t+1; A(y0,x)= t; x2= x; else  break, end;
      end; ...   
         
      x0= x2; y0= y2;
      for y= y0-1:-1:1
        if A(y,x0)==0 t= t+1; A(y,x0)= t; y2= y; else  break, end;
      end; ...   
end; [n, m], A, t
Данные
+
[n, m] =
     7     5
A =
     1     2     3     4     5
    20    21    22    23     6
    19    32    33    24     7
    18    31    34    25     8
    17    30    35    26     9
    16    29    28    27    10
    15    14    13    12    11
t =   35
8 окт 19, 09:49    [21989119]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48625
Dima T
Почему? Вместо 1,2,...,9 сделай 9,8,...,1.

Потому что в такой матрице невозможно раскрутить спираль от центра без разрывов.
8 окт 19, 13:58    [21989413]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 936
mayton
полудух
переформатировал
как лучше?
    else if     (x == k + q - 1)        {r = y - k + q;}
    else if     (y == k + q - 1)        {r = k - x + q * 3 - 2;}


Это ужасно. Оставь как было.

это ты щас выступил против главного фундамента баз данных - табличной структуры
ни много, ни мало
смело Картинка с другого сайта.
8 окт 19, 14:12    [21989429]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dima T
Member

Откуда:
Сообщений: 14090
Dimitry Sibiryakov
Dima T
Почему? Вместо 1,2,...,9 сделай 9,8,...,1.

Потому что в такой матрице невозможно раскрутить спираль от центра без разрывов.

Почему? Например сторона 7.
Было
  1  2  3  4  5  6  7
24 25 26 27 28 29 8
23 40 41 42 43 30 9
22 39 48 49 44 31 10
21 38 47 46 45 32 11
20 37 36 35 34 33 12
19 18 17 16 15 14 13
стало
 49 48 47 46 45 44 43
26 25 24 23 22 21 42
27 10 9 8 7 20 41
28 11 2 1 6 19 40
29 12 3 4 5 18 39
30 13 14 15 16 17 38
31 32 33 34 35 36 37

Или разговор о чем-то другом?
+ Исходник
Исходник тут 21987886, для обратной выдачи сменить вывод на
printf("%3d", n*n+1 - spiral(n, x, y));
8 окт 19, 14:17    [21989436]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
полудух
mayton
пропущено...

Это ужасно. Оставь как было.

это ты щас выступил против главного фундамента баз данных - табличной структуры
ни много, ни мало
смело Картинка с другого сайта.

Нет. Я следовал конвенциям от Google/Oracle.
8 окт 19, 14:18    [21989441]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48625
Dima T
Почему? Например сторона 7.

В оригинальном топике речь шла о неквадратных матрицах.
В твоём примере было

1 2 3 4 5 6 7
16 17 18 19 20 21 8
15 14 13 12 11 10 9
стало

21 20 19 18 17 16 15
6 5 4 3 2 1 14
7 8 9 10 11 12 13
9 окт 19, 13:50    [21990393]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
Мож уже и было.
То же самое в браузере, с выводом на экран, просто побаловаться. Я не умею в динамике управлять шириной кнопок в браузере, это надо наверное через стили.

charset="windows-1251"

жать в след-щем порядке:
[N,M] - много не переварит
*new
[start]
*F5

P.S поля отмеченные * обязательны,
остальные необязательны - если, конечно, не интересно.
Дважды *new можно только, если клетки не вывелись на экран.

К сообщению приложен файл (4-spiral.html - 5Kb) cкачать
10 окт 19, 20:15    [21991695]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Интересный видос про кривые Гилберта-Пеано.

+
12 окт 19, 21:36    [21992920]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Мысли.

1. Универсальная формула перехода от многомерных координат одномерным. С сохранением
относительной стационарности точек.

2. Связь с частотным пространством (Frequency Space) я не очень понял. Но интересно было-бы понять.


3.

Прочее. Практические смыслы которые я знал до этого видоса. Кривая гилберта может быть использована
для архивации картинок. Есть интересное свойство. Любые две соседние точки отличаются не более чем на 1
в на растянутой кривой и в разложении ее на 2 -3 -4 и более мерные пространства. Грубо говоря расстояние
Манхеттена между двумя соседями - всегда равно единице.

Еще один смысл - аллокация диапазонов IP адресов и даже IPv6 которые трудно визуально нарисовать зигзагом
или спиралью. Но в Гилберт укладывается хорошо. Это практический смысл из топика Географии линк на который
я приводил.

Есть какая-то связь с кодом Грея. По крайней мере в разности соседних точек гилбертова пространства.
12 окт 19, 21:45    [21992921]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Вот печально известная мадам Лизавета оцифрована мной и обрезана где-то на квадрат 256 на 256 пикселов.
Здесь кратность степени двойки нужна для Гильберта.

К сообщению приложен файл. Размер - 138Kb
12 окт 19, 23:45    [21992942]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Некий концептуальный код для перехода от растра к одной длинной линии.
        BufferedImage src = ImageIO.read(new FileInputStream("Mona-Lisa-crop-256x256.png"));

        BufferedImage dest = new BufferedImage(src.getWidth(), src.getHeight(), src.getType());

        IPixIterator iPixIterator = new GilbertPixelIterator(256);

        IPixIterator destIterator = new LinearPixIterator(256, 256);

        while(iPixIterator.next()) {
            destIterator.next();
            int x = iPixIterator.getX();
            int y = iPixIterator.getY();
            int pixel = src.getRGB(x,y);
            dest.setRGB(destIterator.getX(), destIterator.getY(), pixel);
        }

Линия завёрнута в обычный обход слева направо сверху вниз чтоб опять-же иметь возможность ее видеть.

К сообщению приложен файл. Размер - 74Kb
12 окт 19, 23:47    [21992943]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
mayton
Грубо говоря расстояние Манхеттена между двумя соседями - всегда равно единице.


точнее так: между последовательными соседями
13 окт 19, 12:18    [21993025]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
Мысли лучше выражать не так вяло. Я всё ждал, когда мэйтон после намеков перейдёт к жипегу. От себя могу сказать. В инете написано (можно поискать), что жипеговские квадратики они (ж-эксперты) линеаризовали диагональным зиг-загом, ожидая, возможно справведливо, что так близкие на плоскости точки чаще будут рядом на прямой, чем когда построчно. И значит будут более коррелированы (стоит читать как более плавные), значит будет меньше скачков, меньше ультракоротких волн в разложении Ф., будет выше сжатие блока при том же качестве.
Но у меня есть сомнения в районе диагонали блоков. Ещё есть "блочный эффект" на границах и маленький размер блока (возможно не только по этим 2-м причинам).
Возможно (судя только по "мыслям"), в ролике имелось ввиду это. Теперь скорости позволяют.
13 окт 19, 13:55    [21993046]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Я не планировал обсуждать JPEG в этом топике. Да и что в нем обсуждать. Это старая лошадь и мне
было-бы интереснее обсуждать его замены.
13 окт 19, 14:11    [21993051]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
Тем не менее, связь с волнами для сжатия имхо такая. И, кстати, м.б. одинаково применима для 1-мерного Ф (например, как в жипеге) и для 2-мерного Ф. А то что-то 2-мерное до сих пор в загоне у всех.
13 окт 19, 14:23    [21993054]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
JPEG - это lossy.

Я на хабре где-то видел статью где с помощью нейрос-сети прогнозируется цвет пиксела
на основе его соседей сверху и слева. При этом ошибка прогноза кодируется отдельно как слой
и сжимается. Интересный подход. Я не помню его эффективность и вряд-ли он превышает
PNG. Но сами идея интересна.

На заре изучения этих методов когда я еще учился в универе у меня была идея - рассматривать
lossy сжатие так. Берем картинку и гоним по ней очень грубый ФНЧ с периодом типа половина
размера картинки. Детектируем локальный всплеск. Создаем гладкую функцию типа Гаусса
(колокольчик) которая должна дать компенсацию для этого всплеска. Накладываем на оригинал.
Далее гоним ФНЧ с более высокой частотой. И так далее.

Картинка раскладывается на суперпозицию "колокольчиков". Сжатие останавливаем тогда, когда
сами решим что детальность изображения достаточна для восприятия или мы не превысили некий
коэффциниент полезного соотношения размеров оригинала и вектора колокольчиков.
13 окт 19, 21:13    [21993247]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
exp98
Member

Откуда:
Сообщений: 1843
Да ни чуть не лучше прогнозирует, чем Байесовы вероятности. Конечно, если сетка не вычисляет что-нить типа "градиентов освещённости". Зато 100пудов тормозиловей. А если градиенты, то и область применимости ограничена естественными сценами.

А пока ты Гауссов мучал, перешли на вейвлеты - в принципе, те же "пачки" Ф. или гладкий Хаар. Всё уже давно придумано за нас. К тому же у Ф. одна из самых быстрых скорость сходимости.

Автоматические показатели качества изображения - отдельная и нелёгкая задача. Хорошо, когда есть оригинал.
13 окт 19, 23:27    [21993289]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Я когда думал о колокольчиках - про вейвлеты и слыхом ни слыхал. Да и был это кажется 1996 год.
А первый работающий кодек от LuraWave был анонсирован где-то в 2000х.
13 окт 19, 23:36    [21993292]     Ответить | Цитировать Сообщить модератору
 Re: Ну что... с пятницей чтоли  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Вот. Чисто случайно нашел пример из книги

THE FIRST 10
PROLOG PROGRAMMING
CONTESTS


По заданию - рисует спираль. Сорян за плохое форматирование. Из PDF не удается грамотно скопировать
в clipboard.

:- use_module(contestlib, [writeN/2, for/3, int_width/2, write_int/2]).
spiral(N,M) :-
NM is N*M,
int_width(NM,Width),
Width1 is Width + 1,
for(I,1,N),
nl,
for(J,1,M),
distance(N,M,I,J,Distance),
write_int(Distance,Width1),
fail.
spiral(_,_).
distance(_,_,1,J,D) :- !, D is J -
distance(_,M,I,M,D) :- !, D is M +
distance(N,M,N,J,D) :- !, D is N +
distance(N,M,I,1,D) :- !, D is 2*N
distance(N,M,I,J,D) :-
N1 is N - 2,
M1 is M - 2,
I1 is I - 1,
J1 is J - 1,
distance(N1,M1,I1,J1,D1),
D is 2*N + 2*M + D1 - 4.
1 + 1.
I - 2 + 1.
2*M - J - 2 + 1.
+ 2*M - I - 3 + 1.
2 ноя 19, 09:45    [22008610]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4      [все]
Все форумы / Программирование Ответить