|
Информационные технологии
:: Математика и алгоритмы
|
|
| ||
Kassern 26.12.20 - 13:02 | Добрый день форумчане. Вам скучно и одиноко, тогда у меня есть задачка для вас! Время от времени прохожу задачки на codewars на питоне/джаве чисто ради интереса.
Нашел вот такую задачку, кому интересно может попробовать решить в 1с. Хотелось бы увидеть красивый, читаемый код без лишних циклов/переменных. Дан n x n массив, верните элементы массива, расположенные от самых внешних элементов к среднему элементу, перемещаясь по часовой стрелке. Наглядный пример https://www.haan.lu/files/2513/8347/2456/snail.png Массив= [[1,2,3], [8,9,4], [7,6,5]] Результат = Массив [1,2,3,4,5,6,7,8,9] Проще говоря надо написать функцию ПолучитьМассивПоЗмейке(ДвумерныйМассив) которая вернет одномерный массив с элементами в нужном порядке. | ||
acht 1 - 26.12.20 - 13:11 | (0) Вам скучно и одиноко
Не, чувак, это тебе - скучно и одиноко. Все кончится опять твоим вяленьким "вечерком сравню по времени выполнения", как в Оптимальное решение задачки | ||
Ненавижу 1С 2 - 26.12.20 - 13:15 | (0) в случае четного n почему начало отсчёта берётся так как на рисунке? | ||
Ненавижу 1С 3 - 26.12.20 - 13:17 | (2) а не... Там наоборот внутрь идут | ||
Kassern 4 - 26.12.20 - 13:19 | (1) Только что проверил ваш код, немного замотался на наделе, при большом массиве покупателей ответ ваш код дает не верный и выполняется дольше. Отпишусь в том посте о результатах. | ||
Вафель 5 - 26.12.20 - 13:20 | вообще по идее можно в 1 цикле сделать | ||
Kassern 6 - 26.12.20 - 13:20 | (3) совершенно верно с внешних элементов во внутрь по часовой стрелке | ||
Kassern 7 - 26.12.20 - 13:21 | (5) хотелось бы увидеть этот один цикл) у меня так не получилось | ||
Ненавижу 1С 8 - 26.12.20 - 13:23 | Ну короче, там всё время два прохода одной длины. Потом длина уменьшается на 1. Между проходами поворот. В первый раз три прохода. | ||
acht 9 - 26.12.20 - 13:26 | (4) > при большом массиве покупателей
О. А давай-ка ты и для этой задачи, превентивно, какие-нибудь условия озвучишь. | ||
Kassern 10 - 26.12.20 - 13:31 | (9) Лучше это писать в той ветке. По существу " Ваша задача - написать функцию для расчета общего времени, необходимого для обслуживания всех клиентов! " ваш код при данном массиве покупателей и касс дал не верный результат. Пример с 6тью кассами и заданным порядком покупателей я написал лишь для лучшего понимания задачи подсчета времени, не более того. | ||
Kassern 11 - 26.12.20 - 13:33 | (10) так же и здесь пример написан лишь для понимания задачки, матрица может быть и 10на10 | ||
acht 12 - 26.12.20 - 13:38 | (11) Не пойдет. Я сейчас напишу тебе красивое и быстрое решение на каких-нибудь битовых операциях и услышу в ответ нудятину "а вот оно на больших размерностях..." | ||
acht 13 - 26.12.20 - 13:40 | (7) https://www.haikson.com/programmirovanie/zapolnenie-dvumernoj-matritsyi-po-spirali/
Заменяешь присвоение a[i][j] = k; на вывод этого a[i][j] и все | ||
Kassern 14 - 26.12.20 - 13:42 | (13) А если не гуглить, а самому попытаться найти решение? Это ведь задачки, как раз развивать мышление. | ||
Kassern 15 - 26.12.20 - 13:44 | (14) я когда ее прорешивал у меня вот такой код получился, он и близко не идеальный, но рабочий:
def snail(snail_map): result=[]; array_len=len(snail_map); if array_len==0 or len(snail_map[0])==0: return result; array_vektor=[]; for i in range(array_len): if i==0: array_vektor.append(array_len); else: array_vektor.append(array_len-i); array_vektor.append(array_len-i); index=0; left_index=0; right_index=array_len-1; for v in array_vektor: if index==0: array=snail_map[left_index]; for i in range(v): k=i+left_index; result.append(array[k]); if index==1: for i in range(v): k=i+1+left_index; array=snail_map[k]; result.append(array[array_len-1-left_index]); if index==2: array=snail_map[right_index]; for i in range(v): k=array_len-i-2-left_index; result.append(array[k]); if index==3: for i in range(v): k=array_len-i-2-left_index; array=snail_map[k]; result.append(array[0+left_index]); index+=1; if index>3: index=0; left_index+=1; right_index-=1; return result; | ||
Kassern 16 - 26.12.20 - 13:46 | (15) я более чем уверен что можно в 1с куда красивее это дело решить | ||
Salimbek 17 - 26.12.20 - 13:47 | инициализируем
delta=1 x=-1 y=0 lxy=n крутим цикл while (lxy>0){ for(i=0;i<lxy;i++){ x+=delta print Массив[x,y] } lxy-- if(lxy>0){ for(i=0;i<lxy;i++){ y+=delta print Массив[x,y] } } delta=-delta } | ||
Salimbek 18 - 26.12.20 - 13:50 | +(17) Хотя if не нужен, все равно в цикл не зайдет | ||
RomanYS 19 - 26.12.20 - 14:19 | Запрос = Новый Запрос;
Запрос.Текст = "ВЫБРАТЬ 1 КАК x, 0 КАК y |ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ 0, 1 |ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ -1, 0 |ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ 0, -1"; Векторы = Запрос.Выполнить().Выгрузить(); Слоев = Цел(N/2); НомерЯчейки = 0; Для Слой = 1 По Слоев Цикл Тек = Новый Структура("x,y", Слой, Слой); Для каждого Направление Из Векторы Цикл Для инд = 1 По N+1-2*Слой Цикл НомерЯчейки = НомерЯчейки + 1; ТД.Область(тек.y, тек.x).Текст = НомерЯчейки; тек.x = тек.x + Направление.x; тек.y = тек.y + Направление.y; КонецЦикла; КонецЦикла; КонецЦикла; Если N%2=1 Тогда НомерЯчейки = НомерЯчейки + 1; ТД.Область((N+1)/2, (N+1)/2).Текст = НомерЯчейки; КонецЕсли; | ||
Kassern 20 - 26.12.20 - 14:33 | (19) прикольное решение, рисует в табличном документе числа в виде змейки. Только вот нужно обратное, уже готовый вложенный массив обойти и получить числа в нужном порядке в виде массива. Скорее всего нужно немного подправить ваш код и он это сделает. Например заполнить табдок начальными массивами, а потом в массив получить текст из ячеек в вашем цикле. | ||
RomanYS 21 - 26.12.20 - 14:38 | (20) Да, конечно нужно одну строку поменять
ТД.Область(тек.y, тек.x).Текст = НомерЯчейки; на МассивЛинейный[НомерЯчейки-1] = МассивКвадратный[тек.y-1][тек.x-1];//вомзожно x и y нужно поменять местами Хотелось без "если" обойтись, но не получилось) | ||
ДедМорроз 22 - 26.12.20 - 14:55 | Самый простой вариант - создаём массив битов,равный нашему массиву.
Когда проходим точку,то устанавливаем бит. Далее,определяем смещение по x и y для перехода в следующую точку. Прежде чем шагнуть,проверяем,а не занята ли она,если занята,то меняем вектор смещения поворотом по часовой стрелке. Когда сразу после поворота снова будет занято,то мы прошли весь массив. | ||
Конструктор1С 23 - 26.12.20 - 15:20 | (15) вот зачем писать такой стрёмный код? Хотя бы разбей метод на подметоды | ||
Kassern 24 - 26.12.20 - 15:25 | (23) Писал на время и не особо парился за красоту, сам принцип был интересен. Да и питон для меня в новинку, только начал изучать. | ||
Kassern 25 - 26.12.20 - 15:27 | (23) вот тебе красивый код:
def snail(array): ret = [] if array and array[0]: size = len(array) for n in xrange((size + 1) // 2): for x in xrange(n, size - n): ret.append(array[n][x]) for y in xrange(1 + n, size - n): ret.append(array[y][-1 - n]) for x in xrange(2 + n, size - n + 1): ret.append(array[-1 - n][-x]) for y in xrange(2 + n, size - n): ret.append(array[-y][n]) return ret | ||
Конструктор1С 26 - 26.12.20 - 16:48 | (25) код стал короче, но не стал понятнее. Низачот | ||
Вафель 27 - 26.12.20 - 18:35 | тут 4 цикла по ребрам и 1 общий цикл по числу кругов | ||
Garykom 28 - 26.12.20 - 18:40 | (0) Простейший КА же | ||
Garykom 29 - 26.12.20 - 18:46 | (28)+ Две переменные нужны номер шага и направление исполнителя и текущие координаты x, y
Изначально шаг = 0, направление 1 (принимаем что 0 - вверх, 1 вправо, 2 вниз, 3 влево), координаты 0,0 левый верхний угол Далее на каждом шагу считываем текущее значение x,y из массива, если можно то перемещаемся на 1 шаг в текущем направлении, пройденную ячейку массива помечаем как то (можно новым массив NxN завести или в текущий нечто писать) Если упираемся в "стену" (границы массива или уже пройденное значение) то сначала поворот на 90 по часовой а затем уже шаг перед, если и там стена то снова поворот Как уже некуда идти после поворотов то стоп | ||
Cthulhu 30 - 27.12.20 - 02:16 | [1с]
// хехе... вариант вообще без циклов ))) Функция ПолучитьМассивПоЗмейке( ДвуМерныйМассив , Знач ТекНомерКруга = -1, Знач ТекСтрока = -1, Знач ТекСтолбец = -1 , ТекущийСписокЗначений = Неопределено ) Если ТекНомерКруга < 0 Тогда ТекущийСписокЗначений = Новый СписокЗначений; Возврат ПолучитьМассивПоЗмейке(ДвуМерныйМассив,0,0,0,ТекущийСписокЗначений); КонецЕсли; ТекИндексМин = ТекНомерКруга; ТекИндексМакс = ДвуМерныйМассив.ВГраница()-ТекИндексМин; ТекущийСписокЗначений.Добавить( ДвуМерныйМассив[ТекСтрока][ТекСтолбец] ); Если ТекНомерКруга < ДвуМерныйМассив.ВГраница()/2 Тогда Если ТекСтрока = ТекИндексМин Тогда Если ТекСтолбец < ТекИндексМакс Тогда ТекСтолбец = ТекСтолбец + 1; Иначе ТекСтрока = ТекСтрока + 1; КонецЕсли; ИначеЕсли ТекСтолбец = ТекИндексМакс Тогда Если ТекСтрока < ТекИндексМакс Тогда ТекСтрока = ТекСтрока + 1; Иначе ТекСтолбец = ТекСтолбец - 1; КонецЕсли; ИначеЕсли ТекСтрока = ТекИндексМакс Тогда Если ТекСтолбец > ТекИндексМин Тогда ТекСтолбец = ТекСтолбец - 1; ИначеЕсли ТекСтрока - 1 >ТекИндексМин Тогда ТекСтрока = ТекСтрока - 1; Иначе Возврат ТекущийСписокЗначений.ВыгрузитьЗначения(); КонецЕсли; ИначеЕсли ТекСтолбец = ТекИндексМин Тогда Если ТекСтрока > ТекИндексМин + 1 Тогда ТекСтрока = ТекСтрока - 1; ИначеЕсли ТекНомерКруга < ДвуМерныйМассив.ВГраница()/2 Тогда ТекНомерКруга = ТекНомерКруга + 1; ТекСтрока = ТекНомерКруга; ТекСтолбец = ТекНомерКруга; Иначе Возврат ТекущийСписокЗначений.ВыгрузитьЗначения(); КонецЕсли; КонецЕсли; Возврат ПолучитьМассивПоЗмейке( ДвуМерныйМассив , ТекНомерКруга , ТекСтрока, ТекСтолбец, ТекущийСписокЗначений); КонецЕсли; Возврат ТекущийСписокЗначений.ВыгрузитьЗначения(); КонецФункции //ПолучитьМассивПоЗмейке [/1с] Рекламное место пустует | ||
Конструктор1С 31 - 27.12.20 - 05:16 | (30) эм... Хуже такого кода разве что вот такой:
https://www.govnokod.ru/1777 и мозг сломаешь, пытаясь понять логику работы кода, и для трудновыявляемых ошибок благодатная среда | ||
Документовед 32 - 27.12.20 - 08:07 | Процедура ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник)
Для НомВысота = 1 по ВысотаМасива Цикл ТекСтрока = ""; Для НомДлина = 1 по ДлинаМасива Цикл ТекЗначСтр = СокрЛП(МассивИсточник[НомДлина - 1][НомВысота - 1]); ТекСтрока = ТекСтрока + ЛЕв(" ", 5 - СтрДлина(ТекЗначСтр))+ ТекЗначСтр +"; "; КонецЦикла; Сообщить(ТекСтрока); КонецЦикла; КонецПроцедуры Процедура ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат) ТекСтрока = ""; Для НомДлина = 1 по ДлинаМасива*ВысотаМасива Цикл ТекЗначСтр = СокрЛП(МассивРезультат[НомДлина - 1]); ТекСтрока = ТекСтрока + ЛЕв(" ", 5 - СтрДлина(ТекЗначСтр))+ ТекЗначСтр +"; "; КонецЦикла; Сообщить(ТекСтрока); КонецПроцедуры ДлинаМасива = 5; ВысотаМасива = 5; МассивИсточник = Новый Массив(ДлинаМасива, ВысотаМасива); МассивРезультат = Новый Массив(ДлинаМасива * ВысотаМасива); НаправлениеДвиженияГоризнотальное = Истина; ТекСтолбец = 0; ТекСтрока = 1; НаправлениеДвиженияПоДлине = 1; НаправлениеДвиженияПоВысоте = 1; ПройденоКолец = 0; Для НомПП = 1 По ДлинаМасива * ВысотаМасива Цикл Если НаправлениеДвиженияГоризнотальное Тогда ТекСтолбец = ТекСтолбец + НаправлениеДвиженияПоДлине; Если (НаправлениеДвиженияПоДлине > 0 и ТекСтолбец = ДлинаМасива - ПройденоКолец ) или (НаправлениеДвиженияПоДлине < 0 и ТекСтолбец = 1 + ПройденоКолец) Тогда НаправлениеДвиженияГоризнотальное = не НаправлениеДвиженияГоризнотальное; НаправлениеДвиженияПоДлине = - НаправлениеДвиженияПоДлине; Если НаправлениеДвиженияПоДлине >0 ТОгда ПройденоКолец = ПройденоКолец +1; КонецЕСли; КонецЕСли; Иначе ТекСтрока = ТекСтрока + НаправлениеДвиженияПоВысоте; Если (НаправлениеДвиженияПоВысоте > 0 и ТекСтрока = ВысотаМасива - ПройденоКолец ) или (НаправлениеДвиженияПоВысоте < 0 и ТекСтрока = 1 + ПройденоКолец) Тогда НаправлениеДвиженияГоризнотальное = не НаправлениеДвиженияГоризнотальное; НаправлениеДвиженияПоВысоте = - НаправлениеДвиженияПоВысоте; КонецЕСли; КонецЕСли; МассивИсточник[ТекСтолбец - 1][ТекСтрока - 1] = НомПП; МассивРезультат[ДлинаМасива * ВысотаМасива - НомПП] = НомПП; КонецЦикла; ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник); Сообщить(" "); ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат); | ||
Доктор Манхэттен 33 - 27.12.20 - 09:29 | (0) Решение на JS. Проверка граничных условий получилась довольно длинная, вынес в отдельные функции checkX и checkY:
function snail(a) { let x = -1, y = dy = 0, dx = 1, res = [], n = a.length; const checkX = () => dx === 0 || x + dx !== (dx > 0 ? n - y : n - y - 2); const checkY = () => dy === 0 || y + dy !== (dy > 0 ? x + 1 : x); do { do { res.push(a[y += dy][x += dx]); } while(checkX() && checkY()); [dy, dx] = [dx, -dy]; } while (checkX() && checkY()) return res; } | ||
Доктор Манхэттен 34 - 27.12.20 - 09:37 | +(33) Заметьте, без каких-либо счетчиков циклов. Чистая логика. Сам себе решил усложнить задачу, иначе слишком легко и не интересно | ||
Документовед 35 - 27.12.20 - 09:57 | С рекурсией
Процедура ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник) Для НомВысота = 1 по ВысотаМасива Цикл ТекСтрока = ""; Для НомДлина = 1 по ДлинаМасива Цикл ТекЗначСтр = СокрЛП(МассивИсточник[НомДлина - 1][НомВысота - 1]); ТекСтрока = ТекСтрока + ЛЕв(" ", 5 - СтрДлина(ТекЗначСтр))+ ТекЗначСтр +"; "; КонецЦикла; Сообщить(ТекСтрока); КонецЦикла; КонецПроцедуры Процедура ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат) ТекСтрока = ""; Для НомДлина = 1 по ДлинаМасива*ВысотаМасива Цикл ТекЗначСтр = СокрЛП(МассивРезультат[НомДлина - 1]); ТекСтрока = ТекСтрока + ЛЕв(" ", 5 - СтрДлина(ТекЗначСтр))+ ТекЗначСтр +"; "; КонецЦикла; Сообщить(ТекСтрока); КонецПроцедуры Процедура ЗаполнитьПолниМассив(МассивИсточник, МассивРезультат = Неопределено, НомПП = 0, струкДвижения = Неопределено, ПройденоКолец = 0, ИмяТекКоординаты = "ТекСтолбец", ИмяТекГраницы = "ДлинаМасива", НаправлениеДвижения = 1) Если НомПП > струкДвижения.ВысотаМасива * струкДвижения.ДлинаМасива Тогда Возврат; КонецЕСли; струкДвижения[ИмяТекКоординаты] = струкДвижения[ИмяТекКоординаты] + НаправлениеДвижения; Если (НаправлениеДвижения > 0 и струкДвижения[ИмяТекКоординаты] = струкДвижения[ИмяТекГраницы] - ПройденоКолец ) или (НаправлениеДвижения < 0 и струкДвижения[ИмяТекКоординаты] = 1 + ПройденоКолец) Тогда Если ИмяТекКоординаты = "ТекСтрока" Тогда НаправлениеДвижения = - НаправлениеДвижения; Если НаправлениеДвижения > 0 Тогда ПройденоКолец = ПройденоКолец +1; струкДвижения.ТекСтолбец = струкДвижения.ТекСтолбец + 1; струкДвижения.ТекСтрока = струкДвижения.ТекСтрока + 1; КонецЕСли; КонецЕСли; ИмяТекКоординаты = ?(ИмяТекКоординаты = "ТекСтолбец", "ТекСтрока", "ТекСтолбец" ); ИмяТекГраницы = ?(ИмяТекГраницы = "ДлинаМасива", "ВысотаМасива", "ДлинаМасива" ); КонецЕСли; МассивИсточник[струкДвижения.ТекСтолбец - 1][струкДвижения.ТекСтрока - 1] = НомПП; МассивРезультат[струкДвижения.ДлинаМасива * струкДвижения.ВысотаМасива - НомПП] = МассивИсточник[струкДвижения.ТекСтолбец - 1][струкДвижения.ТекСтрока - 1]; ЗаполнитьПолниМассив(МассивИсточник, МассивРезультат, НомПП+ 1, струкДвижения, ПройденоКолец, ИмяТекКоординаты, ИмяТекГраницы, НаправлениеДвижения) КонецПроцедуры Функция ПолучитьМассивПоЗмейке(МассивИсточник) струкДвижения = Новый Структура; струкДвижения.Вставить("ТекСтолбец", 0); струкДвижения.Вставить("ТекСтрока", 1); струкДвижения.Вставить("ВысотаМасива", 0); струкДвижения.Вставить("ДлинаМасива", 0); Попытка струкДвижения.ВысотаМасива = МассивИсточник.Количество(); струкДвижения.ДлинаМасива = МассивИсточник[0].Количество(); Исключение Сообщить("Чёт, не похоже на двумерный массив."); Возврат Новый Массив(1); КонецПопытки; МассивРезультат = Новый Массив(струкДвижения.ДлинаМасива * струкДвижения.ВысотаМасива); НомПП = 1; ЗаполнитьПолниМассив(МассивИсточник, МассивРезультат, 1, струкДвижения, 0, "ТекСтолбец", "ДлинаМасива", 1); Возврат МассивРезультат; КонецФункции ДлинаМасива = 5; ВысотаМасива = 5; МассивИсточник = Новый Массив(ДлинаМасива, ВысотаМасива); МассивРезультат = ПолучитьМассивПоЗмейке(МассивИсточник); ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник); Сообщить(" "); ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат); | ||
Документовед 36 - 27.12.20 - 10:08 | (35) Поправка
струкДвижения.ДлинаМасива = МассивИсточник.Количество(); струкДвижения.ВысотаМасива = МассивИсточник[0].Количество(); | ||
DrHiHi 37 - 27.12.20 - 14:08 | еще вариант автокода))
Массив = ПолучитьМассив(); // задаваемый массив хмакс = Массив.ВГраница(); умакс = хмакс; хмин = 0; умин = 0; угол = 0; х = 0; у = 0; МассивРезультат = Новый Массив; Пока Истина Цикл МассивРезультат.Добавить(Массив[у][х]); Если угол = 0 Тогда Если х = хмакс Тогда угол = 1; умин = умин + 1; у = умин; Иначе х = х + 1; КонецЕсли; ИначеЕсли угол = 1 Тогда Если у = умакс Тогда угол = 2; хмакс = хмакс - 1; х = хмакс; Иначе у = у + 1; КонецЕсли; ИначеЕсли угол = 2 Тогда Если х = хмин Тогда угол = 3; умакс = умакс - 1; у = умакс; Иначе х = х - 1; КонецЕсли; ИначеЕсли угол = 3 Тогда Если у = умин Тогда угол = 0; хмин = хмин + 1; х = хмин; Иначе у = у - 1; КонецЕсли; КонецЕсли; Если умин > умакс Или хмин > хмакс Тогда Прервать; КонецЕсли; КонецЦикла; | ||
Cthulhu 38 - 27.12.20 - 14:11 | (31) спасибо ваше мнение очень важно для нас (с) lol
если мозгов не хватает понять обычную рекурсию и элементарную арифметику - так работайте над собой а не нойте про говнокод. ))) | ||
Конструктор1С 39 - 27.12.20 - 19:09 | (38) 一个小气的财主叫他的仆人去买酒,但是没有给他钱。仆人说:“老爷,没有钱怎么能够买酒呢?”财主生气地说:“用钱买酒谁不会?不用钱买到酒才算真的能干呢!”
过了一会儿,仆人拿着空瓶子回来了。主人大骂:“你叫我喝什么?”仆人说:“瓶子里没有酒,谁不会喝!要是能从空瓶子里喝出酒来,那才算真的能干呢!” если мозгов нет понять иероглифы, так работайте над собой. Код пишется для людей, а не для компилятора. Хороший код должен быть максимально линейным и понятным. А не состоять из шарад в виде рекурсий | ||
Конструктор1С 40 - 27.12.20 - 19:15 | Всё просто. Допустим, написал ты 100 строк кода. Другому программисту нужно внести небольшие изменения в этот код:
- если программист за 2 минуты понял всю логику кода и сразу же нашел место правки - у тебя хороший код - если программисту понадобилось полчаса ползать с отладчиком по твоему коду - у тебя дрянной код | ||
bolder 41 - 27.12.20 - 19:18 | |||
Salimbek 42 - 27.12.20 - 20:46 | |||
Cthulhu 43 - 27.12.20 - 20:58 | |||
bolder 44 - 27.12.20 - 21:21 | |||
acht 45 - 27.12.20 - 21:33 | (0) Это вот то самое, что ты хотел добиться - локального срачика? | ||
bolder 46 - 27.12.20 - 22:14 | |||
Salimbek 47 - 28.12.20 - 00:42 | (46) А... ясно, Массив[x,y] - неправильно, надо везде поменять на Массив[y,x] - первым идет номер слоя (т.е. координата y), а вторым - позиция элемента в этом слое (т.е. координата x) | ||
Доктор Манхэттен 48 - 28.12.20 - 02:19 | |||
Доктор Манхэттен 49 - 28.12.20 - 05:51 | Немного оптимизировал по времени выполнения
Максимальный размер массива получился 46340 х 46340, выборал исходя из размера занимаемой памяти, чтобы входной и выходной массивы были примерно по 2 гигабайта. Браузер не дает выделять больше памяти. На тестовом массиве функция выполняется за пол минуты в Microsoft Edge. В хроме не пробовал, лень устанавливать. Проверьте у кого есть. function snail(a) { let x = -1, y = dy = resIndex = 0, dx = 1; const n = a.length; const res = new Uint8Array(n * n); for (let l = n - .5; l; l -= .5) { for (let i = 0; i < l; i++) res[resIndex++] = a[y += dy][x += dx]; [dy, dx] = [dx, -dy]; }; return res; } | ||
Kassern 50 - 28.12.20 - 09:06 | (45) Я лишь хотел поделиться интересной на мой взгляд задачкой, не более. Я вообще удивлен, что столько людей так же заинтересовались и попробовали решить. Всем спасибо | ||
mikecool 51 - 28.12.20 - 09:12 | » | ||
mikecool 52 - 28.12.20 - 09:13 | +51 ограничение - память 65535, время - 1000мс | ||
Доктор Манхэттен 53 - 28.12.20 - 09:42 | (52) >> количество селений (1 <= n <= 100000)
>> ограничение - память 65535 >> Для хранения ответа используйте список, где индекс будет номером селения Что-то тут не сходится... | ||
mikecool 54 - 28.12.20 - 10:01 | (53) вот тут я хз, но мое решение работает, только по времени исполнения ошибку выдает... | ||
Salimbek 55 - 28.12.20 - 15:13 | (51) А как делал?
Если идти по подсказке, то: 1) сортируем список селений и бомбоубежищ 2) Допустим мы рассмотрели селение i, и для него нашли ближайшее убежище j. Теперь берем следующее селение i+1 и для него надо быстро найти ближайшее бомбоубежище. Оно будет либо полученное на предыдущем шаге (j), либо какое-то из последующих (j...n) 3) Используем Метод половинного деления, т.е. берем середину нашего отрезка k=(j+n)/2 и смотрим - селение находится ближе или дальше этой середины. Если ближе, то рассматриваем диапазон (j...k), если дальше, то диапазон (k...n). P.S. Мне лениво разбираться, когда остается 1-2 элемента, поэтому если в выборке осталось менее 5 элементов, то я делаю просто полный перебор, все равно это выгоднее, чем перебирать все 100000 элементов. | ||
fisher 56 - 28.12.20 - 16:40 | |||
bolder 57 - 28.12.20 - 18:51 | (48) Хм..Как то тоже слабовато.Массив 100000x 100000 ( 10 в 10 степени ячеек) основное время - заполнение первоначального массива. Сама процедура, без вывода результата ;-) - мгновенно.
Полное время 1 минута 47 с. А сколько времени в браeзере занимает вывод массива 40000x40000? | ||
Доктор Манхэттен 58 - 29.12.20 - 00:00 | (56) 0.5 мне тоже не очень, можно было заменить на какой-то флаг и добавить пару условий и дополнительных действий, но это мало влияет, так что не стал. | ||
Доктор Манхэттен 59 - 29.12.20 - 00:06 | (57) Странно. У меня первоначальный массив заполнялся гораздо быстрее чем основная процедура. Ты как заполнял?
Вывод массива в браузер не происходит, не стал это оформлять в какой-то формат или HTML. Результат выполнения функции возвращается в консоль, его можно посмотреть в виде массива в удобном виде. | ||
Доктор Манхэттен 60 - 29.12.20 - 00:06 | 100000x100000 - мгновенно? Не верю что-то. Рекламное место пустует | ||
_DAle_ 61 - 29.12.20 - 00:10 | (55) В третьем пункте не нужен двоичный поиск. Нужно просто для каждого селения i двигать вправо j пока расстояние между селением i и бомбоубежищем j уменьшается. | ||
Доктор Манхэттен 62 - 29.12.20 - 01:43 | (61) В самой задаче уже все расписано как ее делать. Так не интересно. | ||
Salimbek 63 - 29.12.20 - 07:58 | |||
Доктор Манхэттен 64 - 29.12.20 - 08:36 | (63) Проверил этот алгоритм на JS в браузере, результат вполне быстрый, ~200 миллисекунд на максимальных размерах массивов:
function bomb(cities, vaults) { const [ sortedCities, sortedVaults ] = [ cities, vaults ].map(coords => Object.entries(coords).sort((a, b) => a[1] - b[1])) let vaultIndex = 0; const vaultsCount = vaults.length; const ret = new Uint32Array(cities.length); sortedCities.map(city => { const cityCoord = city[1]; let closestDisd = Math.abs(cityCoord - sortedVaults[vaultIndex][1]); let nextDist; while (vaultIndex + 1 < vaultsCount && (nextDist = Math.abs(cityCoord - sortedVaults[vaultIndex + 1][1])) < closestDisd) { vaultIndex++; closestDisd = nextDist; } ret[city[0]] = +sortedVaults[vaultIndex][0] + 1; }); return ret; } Причем самая долгая операция - это сортировка в самой первой строке: ~180 миллисекунд. Основной цикл выполняется в среднем за 20-25 миллисекунд. | ||
Доктор Манхэттен 65 - 29.12.20 - 08:41 | Как я понимаю, суть задачи - это написать свою более быструю функцию сортировки. В ней как раз узкое место. Но мы, конечно, этого делать не будем, потому что это уже делали на лабораторных работах в ВУЗе, ничего интересного, все уже давно придумано. | ||
_DAle_ 66 - 29.12.20 - 10:51 | (63) Да, но судя по всему у него как-то не так реализован последний шаг, потому что и вариант с двоичным поиском, и вариант с просто продвижением второго указателя (который практически полностью описан в самом условии) должны быть достаточны для такого размера входных данных. Более того с этими двумя вариантами самым затратным шагом будет все равно является сортировка.
Почему я сказал, что двоичный поиск не нужен. Смотрите, если мы делаем двоичный поиск для каждого селения, то сложность этой части алгоритма в худшем случае (а при решении таких задачек нас ведь интересует именно худший случай в отличие от реальной жизни) будет O(n*log(m)), сложность варианта с продвижением второго указателя - O(n+m), так как мы идем всегда только вправо и за весь внешний цикл в худшем случае просто пройдем весь массив бомбоубежищ. Второй вариант при данных ограничениях будет быстрее. Вариант с двоичным поиском имеет, конечно, право на существование, когда m на порядки больше n, тогда мы исключаем линейную зависимость от количества бомбоубежищ. Но все это довольно бесполезно анализировать, когда у нас первый шаг - это сортировка обоих массивов, которая уже сама по себе будет иметь сложность O(n*log(n) + m*log(m)), что и будет являться самой затратной по времени частью алгоритма. Вообще, эта задачка - достаточно классический пример two pointers technique. И ее основной смысл обычно в демонстрации этой незамысловатой техники. |
|
Список тем форума |