По мере эволюции методологии компьютерного программирования появлялись все новые парадигмы. Они придавали программному коду выразительность и элегантность. Чем больше вы узнаете о различных парадигмах, тем лучше будете владеть программированием.
В этой главе мы увидели, как программирование эволюционировало от непосредственного ввода единиц и нулей в память компьютера до написания ассемблерного кода. Затем с внедрением управляющих структур, таких как циклы и переменные, оно стало еще проще. Мы увидели, как использование функций позволило лучше организовать программный код.
Мы познакомились с элементами парадигмы декларативного программирования, которое становится популярным в массовых языках. И, наконец, мы упомянули логическое программирование, которое является предпочтительной парадигмой в некоторых очень специфических контекстах.
Хотелось бы надеяться, что у вас хватит смелости заняться каким-либо новым языком программирования. У них у всех есть что предложить вам. Так что закрывайте книгу — и начинайте программировать!
Полезные материалы
• Основы языков программирования (Essentials of Programming Languages, Friedman, см. https://code.energy/friedman).
• Макконнелл С. Совершенный код. Мастер-класс.
Заключение
Образование в области информатики никого не может сделать хорошим программистом, так же как изучение кистей и красок никого не может сделать хорошим живописцем.
В книге были представлены самые важные темы computer science в очень простой форме. Это абсолютный минимум, который хороший программист должен знать о computer science.
Я надеюсь, что это новое знание вдохновит вас углубиться в темы, которые вам по душе. Вот почему я по ходу изложения в конце каждой главы давал ссылки на лучшие справочные пособия.
Следует отметить, что в этой книге не затронуты некоторые важные темы. Как добиться, чтобы компьютеры в сети, покрывающей всю планету (Интернет), надежно взаимодействовали друг с другом? Как сделать так, чтобы несколько процессоров работали синхронно для ускоренного решения вычислительной задачи? Одна из самых важных парадигм программирования, объектно-ориентированная, также осталась за бортом. Я планирую обратиться к этим недостающим частям в следующей книге.
Кроме того, вам придется заняться написанием программ, чтобы полностью изучить то, с чем вы познакомились. И это хорошо. Разработка программного кода может казаться неблагодарным делом поначалу, когда вы совершаете первые шаги. Как только вы изучите основы, я обещаю, программирование начнет приносить вам огромное удовлетворение. Давайте заканчивайте читать и начинайте программировать.
Напоследок я хотел бы заметить, что это мой первый опыт в написании книги. Я понятия не имею, насколько хорошо у меня получилось. Вот почему ваши отзывы о книге представляют для меня невероятную ценность. Что вам в ней понравилось? Какие части сбили с толку? Как, по вашему мнению, ее можно было бы улучшить? Пишите мне на hi@code.energy.
Приложения
I. Системы счисления
Вычисления сводятся к работе с числами, потому что информация выражается в числах. Если сопоставить числа с буквами, можно будет записывать текст в цифровой форме. Цвета являются комбинацией интенсивности световых потоков красного, синего и зеленого — эту интенсивность можно задать в числовых значениях. Изображения легко представить в виде мозаики из цветных квадратов, так что они тоже выражаются через числа.
Рис. I.1. Число 4321 в разных системах счисления
Архаичные системы счисления (например, римские цифры — I, II, III и т. д.) составляют числа из сумм цифр. Система счисления, которая используется сегодня, тоже опирается на суммы, но значение каждой цифры в позиции i умножается на d в степени i, где d — это некое число. Его называют основанием системы счисления. Мы обычно используем d = 10, потому что у нас десять пальцев, но система работает для любого основания d.
II. Метод Гаусса
Рассказывают, что как-то раз учитель в начальной школе в качестве наказания поставил Гауссу задачу: просуммировать все числа от 1 до 100. К изумлению учителя, Гаусс нашел ответ (5050) в течение нескольких минут. Его прием состоял в том, чтобы манипулировать порядком элементов удвоенной суммы:
= 10 100
Разделив это на 2, мы получим 5050. Мы можем записать так:
.
Следовательно:
В последней строке i отсутствует, поэтому (n + 1) суммируется снова и снова n раз. Следовательно:
III. Множества
Мы используем слово множество для описания группы объектов. Например, мы можем назвать S множеством обезьянок-эмодзи:
S = {, , , }.
Рис. III.1. S1 и S2 есть подмножества S
Подмножества. Множество объектов, содержащихся в другом множестве, называется подмножеством. Например, обезьянки, показывающие лапы и глаза, составляют подмножество S1 = {, }. Все обезьянки в S1 содержатся в S. Мы записываем это так: S1S Мы можем сгруппировать обезьянок с лапками и ртами в другом подмножестве: S2 = {, }.
Объединение. Какие обезьянки принадлежат либо S1, либо S2? Ответ: обезьянки в S3 = {, , }. Новое множество — объединение двух предыдущих. Мы записываем это так: S3 = S1S2.
Пересечение. Какие обезьянки принадлежат и S1, и S2? Ответ: обезьянки в S4 = { }. Новое множество получается путем пересечения двух предыдущих. Мы записываем это так: S4 = S1S2.
Степенные множества. Обратите внимание, что S3 и S4 одновременно являются подмножествами S. Мы также полагаем, что S5 = S и пустое множество S6 = {} являются подмножествами S. Если подсчитать все подмножества S, то вы найдете 24 = 16 подмножеств. Если же рассматривать их все как объекты, то мы можем собрать их в множество. Множество всех подмножеств S называется его степенным множеством:
PS = {S1, S2, S16}.
IV. Алгоритм Кэдейна
В разделе «Полный перебор» главы 3 мы представили задачу «Лучшая сделка».
Лучшая сделка У вас есть список цен на золото по дням за какой-то интервал времени. В этом интервале вы хотите найти такие два дня, чтобы, купив золото, а затем продав его, вы получили бы максимально возможную прибыль.
В разделе «Динамическое программирование» той же главы мы показали алгоритм, который решил эту задачу с временной сложностью O(n) и пространственной сложностью O(n). Когда в 1984 году Джей Кэдейн обнаружил эту задачу, он нашел способ решить ее с O(n) по времени и O(1) по пространству:
function trade_kadane(prices):
····sell_day ← 1
····buy_day ← 1
····best_profit ← 0
····for each s from 2 to prices.length
········if prices[s] < prices[buy_day]
············b ← s
········else
············b ← buy_day
········profit ← prices[s] — prices[b]
········if profit > best_profit
············sell_day ← s
············buy_day ← b
············best_profit ← profit
····return (sell_day, buy_day)
Дело в том, что нам незачем хранить день лучшей покупки для каждого дня на входе. Достаточно сохранить день лучшей покупки относительно дня лучшей продажи, найденной к настоящему моменту.
Предыдущая
Стр. 21 из 21