Уже совсем скоро – 10 января гранд-мастеру программирования исполнится 84 года, а он считает, что для окончания основного труда его жизни "Искусства программирования" ему необходимо еще 25 лет. Дай бог ему здоровья, сил и ясный ум, а со всем остальным он точно справится сам. Кстати, рост у него не как у мастера Йоды – 190 см, вот здесь хорошо видно по плечам, хотя он, конечно, сильно сутулится.
На Хабре писали про Кнута предостаточно, потому ограничусь здесь моими любимыми цитатами и одной замечательной историей из его жизни, про которую здесь почему-то еще не упоминали.
Именно ее я поведал своим ученикам на самых первых уроках программирования лет 20 назад (да, был такой период, когда я преподавал в техническом лицее в маленьком провинциальном городке у полярного круга). Зачем же я ее рассказал? Чтобы объяснить, какие именно качества необходимы будущему программисту, хотя в нашей истории нет ни единого слова ни о программировании, ни о компьютерах.
"Дональд Кнут был младше вас, сидящих здесь в классе, ему едва ли исполнилось 14 лет, когда он услышал, как по ТВ объявили о конкурсе местной кондитерской компании: предлагалось из букв использованных в названии нового шоколадного батончика "Гигантские батончики Циглера" ("Ziegler's Giant Bar") составить наибольшее количество слов. Приз для победителя держали в тайне, но как обещали, он точно должен быть весьма ценным. Игры в слова, настолки типа скрэббла, до сих популярны в США и являются традиционным семейным досугом. Потому многие любители настольных игр, конечно же, тут же подписались на участие в конкурсе.
Поразмыслив Дональд тоже решил принять участие. Что он мог противопоставить компании (семье) из 5-6 друзей заядлых игроков- "монстров скрэббла", которые за считанные минуты могли составить десятки слов, а за один только вечер уж точно не менее нескольких сотен слов в сумме?
Если на короткой дистанции в 2-3 дня у него точно нет ни единого шанса, то на длинной – в две недели он вполне может победить, просто потому что примерно знал, как именно его соперники будут действовать. Каждый из игроков станет составлять список слов самостоятельно в течение определенного времени, затем они соберутся в одной большой комнате и начнут по очереди их зачитывать, при этом каждый игрок будет вычеркивать у себя уже прозвучавшие слова. В конце все полученные незачеркнутые слова будут занесены (переписаны) в основной список. На второй и третий день количество таких слов уменьшится в разы. При этом все больше времени станет уходить на сверку новых слов с предыдущим списком. Очевидно, что скорость роста основного списка будет неуклонно и быстро падать с каждым днем.
Так каким же образом Дональд мог обогнать целую команду таких игроков?
Только если выберет иной путь к достижению цели. И он делает это: зачем составлять слова из данного набора букв, когда можно проверять готовый список слов на наличие в нем этих самых букв?!
Если взять достаточно полный словарь английского языка, то база для поиска слов будет просто огромной, а, следовательно, итоговый результат должен быть заметно лучше чем у "монстров скрэббла". Тем более, что такой словарь у Дональда, а точнее у его отца – владельца типографии, был: New Standard Unabridged Dictionary of the English Language, Funk & Wagnalls. Замечательный двухтомник — всего навсего на две тысячи страниц.
Что же такое словарь? Это, по сути, список всех слов в алфавитном порядке. Значит, отпадает одна из главных проблем – проверка найденных слов на уникальность, поскольку в словаре изначально нет повторов. Скорость поиска слов таким методом хоть изначально не слишком высока, но будет практически постоянной все две недели, не снижаясь к концу срока.
Идея использовать словарь, конечно же, замечательная, но как ее осуществить? Каким образом перебрать более 50 тысяч слов на наличие в них определенного набора букв за столь короткий срок? Кнут в воспоминаниях не описывает своего алгоритма, но, уверен, мы сами сможем восстановить его, используя его упоминания про закладки и карточки.
Для начала Дональд аккуратно выписывает буквы из фразы "Ziegler's Giant Bar", удаляя повторы и размещая их в алфавитном порядке (11 букв). На втором листе он выписывает все буквы невходящие в эту фразу так же в алфавитном порядке (15 букв). Затем вносит закладки в словарь по начальным буквам, которых нет в ключевой фразе. На этом этапе таким образом он исключает для будущего анализа, не менее 30 тысяч слов. Потом приступает к делу, составляя карточки с сочетаниями первых и вторых букв, пропуская ровно так же слова, у которых вторые буквы не входят в ключевую фразу. Уже на этом этапе у него остается всего около 10 тысяч слов. Поскольку словарь, напоминаю, упорядочен по алфавиту, натыкаясь, например, на третью букву невходящую в список, он листает словарь, пока эта или предыдущие по порядку буквы в словах не сменятся.
Тем не менее, такой кропотливый труд требует много времени, и с началом второй недели до окончания конкурса, понимая, что он катастрофически не успевает закончить перебор всех слов, Дональд отпрашивается с уроков на неделю, сославшись на сильные боли в животе, и запирается дома в подвале на восемь часов в день и больше, анализируя и выписывая полученные слова.
Итог его работы за две недели – четыре с половиной тысячи слов!
Ни один из других участников не составил более двух тысяч слов, у самих судей на руках изначально – список всего из двух с половиной тысяч. Такого результата от долговязого 13-летнего школьника не ожидал никто. Его пригласили на телепередачу, где торжественно вручили главный приз – телевизор и большую коробку шоколадных батончиков. Телевизор достался школе, а батончики он раздал своим одноклассникам".
Так какие же качества будущего программиста продемонстрировал Дональд Кнут в данной истории?
Первое: умение выполнить постановку задачи. То, чему в школе, да зачастую и в университетах не учат в принципе. Вспомните формулировки задач в учебниках: вот вам необходимые и достаточные данные для решения, а теперь решайте задачу и получите ответ. В жизни так не бывает. Ты получаешь задание, а вот постановку задачи ты должен сделать сам, как, впрочем, определить и найти нужные данные для ее решения. В нашем случае задание: "Составить как можно больше слов из данного набора букв", он свел к очень конкретно поставленной задаче: "Найти все слова в словаре Funk&Wagnalls, полностью состоящих из данного набора букв".
Второе: вместо того, чтобы действовать и сразу же приступить к поиску этих слов в словаре, он сначала разработал алгоритм отсеивания слов, неподходящих к требованиям задачи. К сожалению, у многих программистов умение остановиться и подумать, прежде чем начать стучать по клавиатуре, напрочь отстутствует, они предпочитают, как я это называю, "думать руками" – кодят сразу: "Хрен ли здесь думать – прыгать надо!" И это, уж извините, очень плохо.
Третье: хотя постановка задачи и разработка алгоритма решения задачи весьма интересны и очень важны, но занимают они в самом лучшем случае лишь 5% от затраченного времени и сил в процессе решения той или иной задачи. Остальное – рутина: реализация алгоритма с учетом особенностей языка программирования, доводка программы до рабочего состояния, затем тестирование, бесконечное вылавливание блох (исправление багов) в программе. Без огромного упорства и концентрации на предмете в программировании абсолютно точно нечего делать. Именно эти свойства и продемонстрировал нам тринадцатилетней подросток, работая без выходных две недели в подвале своего дома, просто потому что решил довести дело, за которое взялся, до конца. Увы, если у вас "шило в заднице" — программирование не для вас, каким бы острым и быстрым умом вы не обладаете.
После знакомства с основными понятиями и операторами языка программирования, давал ученикам эту задачу, как одну из начальных после освоения азов, причем исходный словарь они должны были найти сами. При желании можете раскрыть спойлер и посмотреть.
Ziegler's Giant Bar
20 лет назад я использовал Турбо-Паскаль для обучения программированию, но здесь приведу образцы программ на Python. В файле-словаре Wordbook.txt все слова записаны в одну колонку без пробелов в начале и в конце слов.
with open("c:\wordbook.txt", "r") as file1:
mn_zgbar=set("zieglersgiantbar")
i=0
# итерация по строкам словаря
for line in file1:
if line[len(line)-1]=='\n':
line=line[:len(line)-1]
#line = line.replace('\n','')
mn_line=set(line)
if mn_zgbar >= mn_line: # проверка вхождения букв слова в ключевую фразу
i+=1
print(i,' ', line)Но использовать операции с множествами, конечно же, нечестно, ведь программа должна быть написана учениками, еще не знакомыми с ними.
Вот вам такой вариант:
with open("c:\wordbook.txt", "r") as file1:
zgbar="abegilnrstz"
i=0
# итерация по строкам словаря
for line in file1:
if line[len(line)-1]=='\n':
line=line[:len(line)-1]
k=0
flag=False
while k<len(line):
m=0
# Проверка букв слова на совпадение
while m<len(zgbar):
if line[k]== zgbar[m]:
flag=True
break
else:
flag=False
m+=1
k+=1
if flag == False:
break
# Вывод полученных слов
if flag:
i+=1
print(i,' ',line)Ну и на закуску мои любимые цитаты Дональда Кнута. Добавляйте в комментариях свои!
Остерегайтесь ошибок в приведенном выше коде; я только доказал его правильность, но не проверял его.
Случайные числа не должны генерироваться случайным образом выбранным методом.
Наука - это знание, которое мы так хорошо понимаем, что можем обучить ему компьютер; а если мы не понимаем до конца, как с этим справляться - это искусство.
В этом смысле мы должны постоянно стремиться превратить каждое искусство в науку: в процессе этого мы продвигаем дальше искусство.
Давайте изменим наше традиционное отношение к построению программ: вместо того, чтобы воображать, что наша основная задача - указывать компьютеру, что ему делать, давайте сосредоточимся на объяснении людям того, что мы хотим, чтобы компьютер делал.
Я предполагаю, что Бог существует, и рад, что это невозможно доказать. [Потому что] я бы проверил доказательство один раз, а потом тут же его забыл бы, ведь иначе я никогда не смог бы рассуждать о духовных вещах и тайнах. И, думаю, моя жизнь была бы очень неполной.
@LKamrad
Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.
