Рекурсивная задача для исполнителя Робот
Задача. Требуется закрасить клетку у правой стены и вернуться в исходную клетку.
Маленькая деталь. Нельзя использовать циклы, переменные и присваивание.
Рекурсия нам в помощь.
Если мы уже у правой стены, то просто красим и задача решена.
Иначе сводим задачу к такой же, но меньшего размера:
- делаем шаг вправо
- решаем задачу
- возвращаемся влево
#рекурсия
Задача. Требуется закрасить клетку у правой стены и вернуться в исходную клетку.
Маленькая деталь. Нельзя использовать циклы, переменные и присваивание.
Рекурсия нам в помощь.
Если мы уже у правой стены, то просто красим и задача решена.
Иначе сводим задачу к такой же, но меньшего размера:
- делаем шаг вправо
- решаем задачу
- возвращаемся влево
#рекурсия
Задача, предлагаемая школьникам в рамках изучения темы Словари
Это - одна из задач, иллюстрирующая суть словарей.
В комментариях приветствуются другие задачи на словари.
В качестве идей рассматриваются три направления:
- словарь как набор соответствий (страна - столица)
- словарь как набор пар (ключ, число повторений) - как в данной задаче
- словарь как мультинабор (ключ, список) или (ключ, множество)
Это - одна из задач, иллюстрирующая суть словарей.
В комментариях приветствуются другие задачи на словари.
В качестве идей рассматриваются три направления:
- словарь как набор соответствий (страна - столица)
- словарь как набор пар (ключ, число повторений) - как в данной задаче
- словарь как мультинабор (ключ, список) или (ключ, множество)
О здоровье кода
В программах на PascalABC.NET, встреченных на просторах интернета, до сих пор встречается базовый устаревший Паскаль. Именно из-за его скудных возможностей в школах стали переходить на другие языки.
В оболочке PascalABC.NET использован метод мягкой силы - после компиляции устаревшей программы в правом нижнем углу появляется прямоугольник с процентами плохого здоровья кода. Кликнув на нем мышью, мы получим всю информацию, почему данный код плохой.
Заметим, что те, кто программируют в новом стиле, никогда этого прямоугольника не увидят.
Очень интересно, как каким ухищрениям прибегают некоторые ютуберы чтобы скрыть свой плохой код: они обрезают нижнюю строку или закрывают эту область своим говорящим лицом.
В программах на PascalABC.NET, встреченных на просторах интернета, до сих пор встречается базовый устаревший Паскаль. Именно из-за его скудных возможностей в школах стали переходить на другие языки.
В оболочке PascalABC.NET использован метод мягкой силы - после компиляции устаревшей программы в правом нижнем углу появляется прямоугольник с процентами плохого здоровья кода. Кликнув на нем мышью, мы получим всю информацию, почему данный код плохой.
Заметим, что те, кто программируют в новом стиле, никогда этого прямоугольника не увидят.
Очень интересно, как каким ухищрениям прибегают некоторые ютуберы чтобы скрыть свой плохой код: они обрезают нижнюю строку или закрывают эту область своим говорящим лицом.
Принцип локальности при описании переменных
Локальность означает близость описания переменной к месту своего использования.
Все переменные должны описываться в месте первого присваивания, отдельное описание не нужно. В большинстве случаев типы указывать не следует - они выводятся автоматически.
Такой стиль позволяет легко оформлять отдельные участки кода как независимые функции.
Первый код на слайде содержит еще пару неприятностей: переменная цикла i может быть использована после цикла для других целей, а переменная a имеет непонятное назначение - вероятно оставшееся от старого кода. Кроме того, переменная p инициализируется до ввода и вывода, что смешивает алгоритм и ввод данных.
#начинающим
Локальность означает близость описания переменной к месту своего использования.
Все переменные должны описываться в месте первого присваивания, отдельное описание не нужно. В большинстве случаев типы указывать не следует - они выводятся автоматически.
Такой стиль позволяет легко оформлять отдельные участки кода как независимые функции.
Первый код на слайде содержит еще пару неприятностей: переменная цикла i может быть использована после цикла для других целей, а переменная a имеет непонятное назначение - вероятно оставшееся от старого кода. Кроме того, переменная p инициализируется до ввода и вывода, что смешивает алгоритм и ввод данных.
#начинающим
Forwarded from PascalABC.NET официальный канал
Задача о ханойских башнях
Задача о ханойских башнях - пример, показывающий мощность и краткость использования рекурсии.
Постановка задачи - на слайде. Чтобы переложить пирамиду из n дисков с 1 стержня на 3, перекладываем вначале рекурсивно пирамиду из n-1 диска с 1 стержня на 2, затем перекладываем самый большой диск с 1 на 3 и наконец перекладываем пирамиду их n-1 диска со 2 стержня на 3. Бинго!
Обожаю эту задачу! Мои коллеги из Бостона, зная это, привезли мне в подарок эту головоломку - решаю её прямо сейчас!
Задача о ханойских башнях - пример, показывающий мощность и краткость использования рекурсии.
Постановка задачи - на слайде. Чтобы переложить пирамиду из n дисков с 1 стержня на 3, перекладываем вначале рекурсивно пирамиду из n-1 диска с 1 стержня на 2, затем перекладываем самый большой диск с 1 на 3 и наконец перекладываем пирамиду их n-1 диска со 2 стержня на 3. Бинго!
Обожаю эту задачу! Мои коллеги из Бостона, зная это, привезли мне в подарок эту головоломку - решаю её прямо сейчас!
WPFObjects - создание заготовки игры
Школьное программирование.
На скриншоте - заготовка игры, в которой игрок управляется клавиатурой.
Здесь используются свойства WPF-объектов Direction и Velocity. Анимация на основе кадра позволяет перерисовывать экран в нужный момент когда будет полностью прорисован предыдущий кадр. Параметр dt позволяет определить время между двумя последовательными прорисовками кадра, метод MoveTime(dt) - переместить объект на нужное расстояние при заданной скорости.
Обработчики OnReyDown и OnKeyUp позволяют эффективно начинать и заканчивать перемещение.
Школьное программирование.
На скриншоте - заготовка игры, в которой игрок управляется клавиатурой.
Здесь используются свойства WPF-объектов Direction и Velocity. Анимация на основе кадра позволяет перерисовывать экран в нужный момент когда будет полностью прорисован предыдущий кадр. Параметр dt позволяет определить время между двумя последовательными прорисовками кадра, метод MoveTime(dt) - переместить объект на нужное расстояние при заданной скорости.
Обработчики OnReyDown и OnKeyUp позволяют эффективно начинать и заканчивать перемещение.
CreateVisual и DrawOnVisual - способ нарисовать объект и потом перерисовать его, заменив на другое графическое представление. Не надо объект стирать, поскольку в WPF - нарисованные объекты - это не пиксели на экране, а именно объекты
#графика
#графика
Исключение StackOverflow
При рекурсивном зацикливании стек быстро переполняется, и мы получаем исключение StackOverflow, которое невозможно обработать.
Память под стек выделяется в момент запуска программы и не может быть изменена.
Как следует из эксперимента, в простом рекурсивном вызове с одним параметром достаточно всего лишь 16000 рекурсивных вызовов - и стек переполнится. Поэтому в рекурсивных алгоритмах следует отдавать предпочтение с малой глубиной рекурсии.
#рекурсия
При рекурсивном зацикливании стек быстро переполняется, и мы получаем исключение StackOverflow, которое невозможно обработать.
Память под стек выделяется в момент запуска программы и не может быть изменена.
Как следует из эксперимента, в простом рекурсивном вызове с одним параметром достаточно всего лишь 16000 рекурсивных вызовов - и стек переполнится. Поэтому в рекурсивных алгоритмах следует отдавать предпочтение с малой глубиной рекурсии.
#рекурсия
Forwarded from PascalABC.NET официальный канал
Сортировка деревом
На скрине вы видите одну из самых быстрых сортировок - сортировку с помощью бинарного дерева поиска. Её асимптотическая сложность в среднем - O(n log(n)) - такая же как и у быстрой сортировки Хоара.
Просто добавляем элементы в дерево: если элемент меньше корня, то добавляем в левое поддерево, если больше значения в корне - добавляем в правое поддерево.
И потом печатаем дерево - элементы в нем уже отсортированы.
На скрине вы видите одну из самых быстрых сортировок - сортировку с помощью бинарного дерева поиска. Её асимптотическая сложность в среднем - O(n log(n)) - такая же как и у быстрой сортировки Хоара.
Просто добавляем элементы в дерево: если элемент меньше корня, то добавляем в левое поддерево, если больше значения в корне - добавляем в правое поддерево.
И потом печатаем дерево - элементы в нем уже отсортированы.
Сравнение скорости программ с Where + Select и циклами
Программа, использующая наиболее частые методы Where и Select работает примерно в 2 раза медленнее такой же программы, использующей циклы. Но она короче, понятнее и модифицируемее.
#производительность
Программа, использующая наиболее частые методы Where и Select работает примерно в 2 раза медленнее такой же программы, использующей циклы. Но она короче, понятнее и модифицируемее.
#производительность
Анимация на основе кадра
Именно анимация на основе кадра - лежит в основе игровых движков. Вначале кадр формируется и затем он перерисовывается. Перерисовку имеет смысл проводить с частотой обновления экрана - на обычных мониторах это 60 Гц.
В GraphWPF имеется соответствующее событие onDrawFrame, которое вызывается всякий раз когда пришла пора перерисовать экран.
Параметр dt здесь - время с момента предыдущей перерисовки. Это позволяет задавать перемещение объектов в физических терминах.
На скриншоте - программа движения двух кругов со скоростями 300 и 200 пикселей в секунду. Перерисовка - плавная - без мерцаний и подёргиваний.
# графика
# анимация
Именно анимация на основе кадра - лежит в основе игровых движков. Вначале кадр формируется и затем он перерисовывается. Перерисовку имеет смысл проводить с частотой обновления экрана - на обычных мониторах это 60 Гц.
В GraphWPF имеется соответствующее событие onDrawFrame, которое вызывается всякий раз когда пришла пора перерисовать экран.
Параметр dt здесь - время с момента предыдущей перерисовки. Это позволяет задавать перемещение объектов в физических терминах.
На скриншоте - программа движения двух кругов со скоростями 300 и 200 пикселей в секунду. Перерисовка - плавная - без мерцаний и подёргиваний.
# графика
# анимация
Ускорение вычислений за счет правильного размещения в памяти
Перед нами - три эквивалентных алгоритма умножения матриц. Во втором и третьем случае матрица b транспонируется, в результате данные в самом внутреннем цикле располагаются непрерывно в памяти, что ускоряет вычисления за счет того что рядом стоящие данные попадают в кеш процессора.
Третий пример использует массивы массивов, которые оказываются здесь эффективнее матриц.
Результаты для случайной матрицы размера n = 1000:
Перед нами - три эквивалентных алгоритма умножения матриц. Во втором и третьем случае матрица b транспонируется, в результате данные в самом внутреннем цикле располагаются непрерывно в памяти, что ускоряет вычисления за счет того что рядом стоящие данные попадают в кеш процессора.
Третий пример использует массивы массивов, которые оказываются здесь эффективнее матриц.
Результаты для случайной матрицы размера n = 1000:
алгоритм 1 - 2.7 с
алгоритм 2 - 1.6 с
алгоритм 3 - 0.9 с
PascalABC.NET в английской Википедии
PascalABC.NET представлен в английской Википедии
https://en.wikipedia.org/wiki/PascalABC.NET
Весьма обстоятельная статья с современными примерами, хорошими ссылками на литературные источники, среди которых - книга Александра Осипова "Введение в современное программирование", несколько педагогических статей Дженджера В.О. и др. в научных журналах, несколько научных статей в журналах вычислительной математики, а также несколько качественных ссылок на YouTube-ролики.
Особенно следует отметить выбранный для иллюстрации скриншот интегрированной среды с примером на Pattern Matching по типам.
PascalABC.NET представлен в английской Википедии
https://en.wikipedia.org/wiki/PascalABC.NET
Весьма обстоятельная статья с современными примерами, хорошими ссылками на литературные источники, среди которых - книга Александра Осипова "Введение в современное программирование", несколько педагогических статей Дженджера В.О. и др. в научных журналах, несколько научных статей в журналах вычислительной математики, а также несколько качественных ссылок на YouTube-ролики.
Особенно следует отметить выбранный для иллюстрации скриншот интегрированной среды с примером на Pattern Matching по типам.
Wikipedia
PascalABC.NET
integrated development environment with integrated debugger
Алгоритм генерации случайного лабиринта
В стандартные примеры PascalABC.NET входит программа MazeGen.pas генерации случайного лабиринта.
Алгоритм там неоптимальный, лабиринт получается разреженный.
В комментариях ждем идеи хороших алгоритмов или ссылки на них
В стандартные примеры PascalABC.NET входит программа MazeGen.pas генерации случайного лабиринта.
Алгоритм там неоптимальный, лабиринт получается разреженный.
В комментариях ждем идеи хороших алгоритмов или ссылки на них
Параллельное выполнение задач
С помощью класса Task можно запустить несколько задач одновременно. Выражение t1.Result+t2.Result+t3.Result будет вычислено только тогда когда все задачи завершатся.
На скриншоте хорошо видно, что ускорение по сравнению с последовательным выполнением - в три раза, что означает, что каждая задача выполняется примерно за одно и то же время.
#параллельность
С помощью класса Task можно запустить несколько задач одновременно. Выражение t1.Result+t2.Result+t3.Result будет вычислено только тогда когда все задачи завершатся.
На скриншоте хорошо видно, что ускорение по сравнению с последовательным выполнением - в три раза, что означает, что каждая задача выполняется примерно за одно и то же время.
#параллельность