UniLecs #143_1. Пирамида - 2
UniLecsЗадача: снова строим пирамиду, на этот раз порядок следующий: нужно укладывать блоки по спирали против часовой стрелки, начиная с левого нижнего угла. Верхний ярус пирамиды состоит из 1 го блока, каждый след.ярус на 2 блока больше предыдущего.
Необходимо написать программу, ктр формирует схему укладки блоков.
Входные данные: height - высота пирамиды, ктр необходимо построить, где height - натуральное число от 1 до 100.
Вывод: схема укладки блоков пирамиды:
- в 1-й строчке номер при укладке верхнего блока;
- во 2й строке - номера блоков след.яруса
и т.д.
Пример: height = 3
Answer:
7
8 9 6
1 2 3 4 5
Реализация:
- @akolosov364, JS: 1.3 балла
Идея состоит в том, что для того чтобы нарисовать спиральную пирамиду стоит учесть 3 направления движения, то есть по всем трём сторонам треугольнка. Вначале отрисовывается пустой скелет, который будет заполнен пустым местом для красивой отрисовки и иницилизируются начальные направления. Как только одно из направлений заканчивается - выбирается следующее. Как только будет отрисовано число равное height * height цикл заканчивается.
https://gist.github.com/KolosovAO/d291950891cce323d9bb0279552d526d
Test: https://repl.it/@AlieksieiKoloso/task143
Визуализация: https://kolosovao.github.io/pyramid.html
2. @jinxonik, Python, C++, Ruby: (1 + 2*0.5 за 2 доп.метода + 0.1 доп.оптимизацию + 0.3 за визуализацию + 2*0.1 за 2 доп.ЯП) = 2.6 балла
МЕТОД 1. Заполнение треугольниками (с созданием массивов). Создаём вектор векторов, последовательно заполняя значениями каждый треугольник (нижнюю грань слева направо, правую грань снизу вверх и левую грань сверху вниз).
МЕТОД 2. Движением по спирали (с созданием массивов). Принимаем в качестве начальных координат точку чуть левее той, что будет содержать число 1. Далее задаём направление движения с помощью дельта-значений dx и dy (сначала вправо, затем вверх влево, а затем вниз – на картинке это будет вниз влево, но по координатам ровно вниз), кол-во перемещений и изменение кол-ва перемещений каждый раз после записи последовательности чисел в одном направлении (эти значения задаются также для всех 3-х направлений). Индекс текущего перемещения (0 = вправо, 1 = вверх влево, 2 = вниз) выставляем в 0. После этого начинаем двигаться в направлении, соответствующем текущему индексу, делая кол-во перемещений, соответствующее текущему индексу, после чего уменьшаем это кол-во на значение, соответствующее текущему индексу :), а затем увеличиваем и сам индекс (по модулю 3). Весь процесс повторяем до тех пор, пока текущее кол-во перемещений не станет меньшим или равным нулю.
МЕТОД 3. Вычисление значений в ячейках по координатам (без создания массивов). Функция возвращает значение в строке row столбце col для пирамиды высотой height. Приведённые ниже формулы являются упрощением рекурсий и эмпирически выведенных громоздких формул :)
МЕТОД 3B. Вычисление значений в ячейках по координатам (без создания массивов). Функция возвращает значение в строке row столбце col для пирамиды высотой height. Приведённые ниже формулы получены эмпирически + здесь использована рекурсия (собственно, метод 3 является оптимизированной версией метода 3B без рекурсии).
https://gist.github.com/jin-x/bb740a722190c44a0a46a28b44eec1f3
Test C++: https://repl.it/@jin_x/UniLecs-143-spiroidpyramid3cpp
Test Ruby: https://repl.it/@jin_x/UniLecs-143-spiroidpyramidrb
Визуализация:
Download visualization on Delphi from here: http://xk8.ru/f/spiroid_pyramid_lemmings.zip
Либо смотрите видео в нашем чате:
https://t.me/unilecs_chat/25248
3. Andrew Bystrov, Java: 1 балл
Смотри подробный разбор по ссылке ниже:
https://gist.github.com/AndrewBystrov/b265f3c24a228ccf9723a897b5461973
4. @kirillmotrichkin, Python, Java: (1 + 2*0.5 за 2 доп.метода + 0.1 за доп.ЯП) = 2.1 балла
Первый способ - поклеточный обход. Пройдём по массиву в нужно порядке от первого до последнего числа. Для этого начнём движение от левого нижнего угла и будем менять направление движения, когда встретим препятствие.
Второй способ - построчное вычисление. На основе предыдущей строки и местоположения в массиве будем вычислять следующую строку. Для каждой клетки будем смотреть, в какую сторону в ней происходит движение и на основе этого вычислять элемент. Вывод по мере вычисления строки. Много формул.
Третий способ - манипуляция с простой пирамидой. Сделаем обычную пирамиду, поменяем местами строки, поменяем направление некоторых строк, сплющим получим нужную пирамиду.
https://gist.github.com/superkiria/418e2ee7d053f0e61e29d24a6e54c6d6
Test Java: https://repl.it/@superkiria/unilecs1431
Test Python 1: https://repl.it/@superkiria/unilecs1432
Test Python 2: https://repl.it/@superkiria/unilecs1433
5. @LostInKadath, Python: 1 балл
Создаем пустую матрицу. Выставляем границы. А дальше - внимательная игра с индексами. Для удобства основание пирамиды совпадает с верхней границей матрицы. Три цикла счетчика - по основанию матрицы, по правой границе и по диагонали. Для печати выполнена процедура, выдающая на печать только ненулевые элементы матрицы.
https://gist.github.com/LostInKadath/dc9c398bb91de390f98412f16f43a97b
6. @IegorT, JS: 1 балл
Детали реализации смотри по ссылке ниже:
https://gist.github.com/IegorT/d55175604a20c1ac37be23f2186ef434
7. Антон, Rust: 1 балл
Подробный разбор смотрите по ссылке ниже!
https://gist.github.com/AnthonyMikh/4253172062919cd10c9ee73c1ee6f63d
Test: https://play.rust-lang.org/?gist=829b938aedbd3b0da206c44262809759
8. @egormasharskii, C++: 2 балла
Метод 1.Собственно поэлементно рисуем раскладку в порядке увеличения номеров блоков. Для этого используем простенькую state-machine, где состояние отвечает за рисование одной линии. Двигаемся по одному элементу за раз.
Метод 2. На задачу можно посмореть так, сначала рисуем "оболочку" пирамиды, потом решаем аналогичную задачу рисования пирамиды внутри пирамиды и т.д. DrawPyramid рисует пирамиду без внутренностей.
Метод 3. У предыдущих алгоритмов есть один фатальный недостаток. Они используют дополниельную память. Алгоритм ниже этого не делает, для заданных коодинат он возвращает либо номер блока пирамиды , либо ноль если блок с коордигатами к пирамиде не относится.
https://gist.github.com/myegor/65587dc7f20f3ff389f56c5ab590c9d6
9. @R4PAAA, С++: 1 балл
Эта задача решается в лоб. Мы честно идём сначала по нижней строке вправо, затем по диагонали влево вверх, потом влево вних. И так до самого центра. Вся магия в пределах циклов и в пересчёте индексов в координаты. Используется два индекса. Индекс низа - номер строки при движении вправо и предел при движении влево вниз. Индекс верх - предел при движении влево вверх. Его же можно рассмитривать как номер вложенного треугольника. Заполнение треугольников продолжается до тех пор, пока индексы верха и низа не достигнут друг друга.