Я только что закончил готовить слайды для моего нового занятия по вычислительному мышлению, и, поскольку я не хочу начинать ничего нового за полчаса до того, как выйду из офиса, я зашел в твиттер и увидел этот интересный пост. ». Это задача программирования, описанная здесь, с императивным решением и функциональным решением, описанным в первом посте.
Императивное решение довольно сложное и выглядит так:
Функциональное решение более элегантно, но и немного медленнее. Разбитая на три функции, как в сообщении блога, упомянутом выше, это выглядит так:
Что ж, если вы хотите писать быстрый код, вашей первой мыслью должно быть: могу ли я придумать простой алгоритм. Позже вы можете беспокоиться о его реализации.
Здесь у нас есть проблема, которая включает в себя выяснение того, имеет ли стена в любом заданном положении более высокие стены слева и справа, и если да, то какова самая маленькая стена слева или справа. Итак, очень легко мы можем разбить его на сбор списка самых высоких стен, видимых слева и справа от каждой позиции. Это то, что мы можем вычислить с помощью функций аккумулирования и аккумулирования из муррр. После этого мы можем решить задачу, сопоставив эти два вектора и вектор высот стен, и у нас есть трехстрочное решение задачи.
Это решение не только намного проще, но и намного быстрее.
