Л ю б о е и с п о л ь з о в а н и е д а н н о г о ф а й л а о з н а ч а е т в а ш е согласие с у с л о в и я м и л и ц е н з и и (см. след. стр.) Т е к с т в д а н н о м
ф а й л е п о л н о с т ь ю с о о т в е т с т в у е т п е ч а т н о й версии к н и г и .
Э л е к т р о н н ы е версии э т о й и д р у г и х к н и г а в т о р а в ы м о ж е т е
п о л у ч и т ь на с а й т е http://www.stolyarov.info
ПУБЛИЧНАЯ ЛИЦЕНЗИЯ
Учебное пособие Андрея Викторовича С т о л я р о в а «Программирование: введение в профессию. З а д а ч и и этюды», опубликованное в издательстве М А К С Пресс в 2022 году, называемое далее «Произведением», защищено действующим российским и м е ж д у н а р о д н ы м
авторско-правовым законодательством. Все п р а в а на Произведение, предусмотренные законом, как имущественные, т а к и неимущественные, п р и н а д л е ж а т его автору.
Н а с т о я щ а я Лицензия устанавливает способы использования электронной версии Произведения, право на которые предоставлено автором и правообладателем неограниченному
кругу лиц, при условии безоговорочного п р и н я т и я этими лицами всех условий данной Лицензии. Любое использование Произведения, не соответствующее условиям данной Лиценции, а равно и использование Произведения лицами, не согласными с условиями Лицензии,
возможно т о л ь к о при наличии письменного р а з р е ш е н и я автора и правообладателя, а при
отсутствии такого р а з р е ш е н и я я в л я е т с я противозаконным и преследуется в р а м к а х г р а ж данского, административного и уголовного права.
Автор и правообладатель настоящим р а з р е ш а е т следующие виды использования данного ф а й л а , являющегося э л е к т р о н н ы м представлением Произведения, без уведомления правообладателя и без в ы п л а т ы авторского в о з н а г р а ж д е н и я :
1) воспроизведение Произведения (полностью или частично) на бумаге путём распечатки с
помощью принтера в одном э к з е м п л я р е д л я удовлетворения л и ч н ы х бытовых или учебных потребностей, без п р а в а передачи воспроизведённого э к з е м п л я р а д р у г и м л и ц а м ;
2) копирование и распространение данного ф а й л а в электронном виде, в т о м числе путём
записи на ф и з и ч е с к и е носители и путём передачи по компьютерным сетям, с соблюдением следующих условий: (1) в с е в о с п р о и з в е д ё н н ы е и п е р е д а в а е м ы е л ю б ы м
лицам экземпляры файла являются точными копиями оригинального файл а в ф о р м а т е P D F , при копировании не производится н и к а к и х и з ъ я т и й , сокращений,
дополнений, искажений и любых д р у г и х изменений, в к л ю ч а я изменение ф о р м а т а представления ф а й л а ; (2) р а с п р о с т р а н е н и е и п е р е д а ч а к о п и й д р у г и м л и ц а м п р о и з в о д и т с я и с к л ю ч и т е л ь н о бесплатно,
то есть при передаче не взимается никакое
в о з н а г р а ж д е н и е н и в к а к о й ф о р м е , в том числе в ф о р м е просмотра р е к л а м ы , в ф о р ме п л а т ы за носитель или за сам а к т копирования и передачи, д а ж е если т а к а я п л а т а
оказывается значительно меньше ф а к т и ч е с к о й стоимости или себестоимости носителя,
а к т а копирования и т. п.
Л ю б ы е другие способы распространения данного ф а й л а при отсутствии письменного разрешения автора запрещены. В частности, з а п р е щ а е т с я : внесение каких-либо изменений в
д а н н ы й ф а й л , создание и распространение и с к а ж ё н н ы х экземпляров, в том числе экземпляров, содержащих какую-либо часть произведения; распространение данного ф а й л а в
Сети Интернет через веб-сайты, о к а з ы в а ю щ и е п л а т н ы е услуги, через сайты коммерческих
компаний и и н д и в и д у а л ь н ы х предпринимателей (включая файлообменные и любые другие
сервисы, организованные в Сети Интернет коммерческими компаниями, в т о м числе бесплатные), а т а к ж е ч е р е з с а й т ы , с о д е р ж а щ и е р е к л а м у л ю б о г о р о д а ; п р о д а ж а и обмен
физических носителей, содержащих д а н н ы й ф а й л , д а ж е если в о з н а г р а ж д е н и е значительно
меньше себестоимости носителя; включение данного ф а й л а в состав каких-либо и н ф о р м а ционных и иных продуктов; распространение данного ф а й л а в составе какой-либо платной
услуги или в дополнение к такой услуге. С другой стороны, р а з р е ш а е т с я дарение (бесп л а т н а я передача) носителей, содержащих д а н н ы й ф а й л , бесплатная запись данного ф а й л а
на носители, п р и н а д л е ж а щ и е д р у г и м пользователям, распространение данного ф а й л а через бесплатные децентрализованные файлообменные P2P-сети и т . п . С с ы л к и на э к з е м п л я р
ф а й л а , расположенный на о ф и ц и а л ь н о м сайте автора, р а з р е ш е н ы без ограничений.
А . В . С т о л я р о в .запрещает
Российскому авторскому обществу и любым другим о р г а н и з а ц и я м производить любого рода л и ц е н з и р о в а н и е л ю б ы х его произведений и о с у щ е с т в л я т ь в интересах автора к а к у ю бы то ни б ы л о и н у ю с в я з а н н у ю
с а в т о р с к и м и п р а в а м и д е я т е л ь н о с т ь без его письменного р а з р е ш е н и я .
А.В.СТОЛЯРОВ
ПРОГРАММИРОВАНИЕ
ВВЕДЕНИЕ В ПРОФЕССИЮ
задачи и этюды
Москва - 2022
У Д К 519.683+004.2+004.45
Б Б К 32.97
С81
С81
Столяров, Андрей Викторович.
П р о г р а м м и р о в а н и е : введение в профессию. З а д а ч и и
э т ю д ы / А. В. С т о л я р о в . - М о с к в а : М А К С Пресс, 2022. - 156 с.
ISBN 978-5-317-06732-8
Сборник содержит задачи, упражнения и практические задания S поддержку учебника «Программироsание: введение S профессию».
Д л я школьников, студeнтоs, прeподаsатeлeй и всех, кто интересуется программироsаниeм.
У Д К 519.683+004.2+004.45
Б Б К 32.97
Задачи
К части
К части
К части
К части
К части
К части
К части
К части
К части
К части
К части
К части
1 «предварительные сведения»
2 «язык Паскаль и начала программирования» . .
3 «возможности процессора и язык ассемблера» . .
4 «программирование на языке Си»
5 «объекты и услуги операционной системы» . . . .
6 «сети и протоколы»
7 «параллельные программы и разделяемые данные»
8 «ядро системы: взгляд за кулисы»
9 «парадигмы в мышлении программиста»
10 «язык С и + + , О О П и АТД»
11 «неразрушающие парадигмы»
12 «компиляция, интерпретация, скриптинг» . . . .
7
8
17
36
48
59
74
82
84
86
89
100
113
Указания
К части
К части
К части
К части
К части
К части
К части
К части
К части
К части
К части
1
2
3
4
5
6
7
8
10
11
12
115
116
118
120
123
127
138
142
142
142
143
144
Ответы
145
От автора
Вы держите в руках задачник в поддержку курса изучения программирования, изложенного в моей книге «Программирование: введение в профессию»; этот ф а к т довольно примечателен сам по себе,
поскольку изначально я совершенно не планировал никаких задачников и вообще задач. Сам я, изучая программирование в начале
1990-х, никогда не нуждался в том, чтобы кто-то ставил мне задачи
или подсказывал этюды; напротив, идей, что бы такого ещё запрограммировать, у меня всегда было (и до сих пор есть) намного больше, чем имеется на это времени. Признаюсь, я грешным делом был
уверен, что это у всех так, а у кого не так, те мою к н и ж к у читать не
станут; но я ошибался.
Интересоваться, как там насчёт задач «для закрепления материала» или «для самопроверки», публика начала сразу после выхода
первого тома первого издания «Введения в профессию». Конечно, поначалу я крепился, отбивался, держал марку и всё такое прочее, но в
какой-то момент мою оборону всё-таки прорвали. В конце концов, по
большей части материала книги я так или иначе вёл или семинары,
или частные уроки, и у меня, естественно, успел накопиться запас
наработанных задач, заданий и прочих заморочек; почему бы всем
этим добром не поделиться с публикой, раз у ж так хотят.
Есть только одна очень в а ж н а я вещь, которую я хотел бы озвучить, прежде чем вы приметесь за собранные в этой книжке задачи. Е с л и у вас в о з н и к л а и д е я , к о т о р у ю х о ч е т с я р е а л и з о в а т ь
в в и д е п р о г р а м м ы — н е м е д л е н н о б р о с а й т е з а д а ч н и к , хоть
этот, хоть л ю б о й д р у г о й , и в о п л о щ а й т е с в о ю и д е ю . Толку
от этого будет заведомо больше. Вообще учиться программировать
намного эффективнее, когда вы заставляете компьютер делать то,
чего от него хотите сами, а не то, что вам предписано каким-нибудь
очередным добрым дядей. Не беспокойтесь, работа на идиотов-заказчиков от вас никуда не денется, всё впереди; так что, пока есть возможность, занимайтесь программированием как искусством, а программирование как ремесло пусть пока подождёт.
Сказанное, впрочем, не относится к задачам в поддержку первой
(вводной) части «Введения в профессию», где в основном математика; задачи, не предполагающие написания программ, встречаются и
в других частях, но такого тут, прямо скажем, немного.
Стоит сказать несколько слов о том, как пользоваться этой книжкой. В тексте задачника встречаются ссылки на «главы» и «параграфы»; во всех таких случаях имеются в виду главы и параграфы
трёхтомника «Программирование: введение в профессию», в той их
нумерации, которая сложилась во втором издании. К сожалению,
От автора
5
нумерация глав и параграфов первого издания (того, в котором было четыре тома) несколько отличается. Впрочем, задачник можно
использовать и с первым изданием тоже, найти нужный п а р а г р а ф
обычно не так сложно, а если совсем не получается — воспользуйтесь
электронной версией второго издания. К а к можно заметить из оглавления, задачник снабжён рубриками «указания» и «ответы». Скажу
сразу, ответами снабжены все задачи, к р о м е тех, которые подразумевают написание программы или её фрагмента; решение таких
задач по понятным причинам всё равно невозможно «сверить с ответом», а проверить, правильно вы всё сделали или нет, проще будет
обычным тестированием написанной программы. Д л я многих (но,
опять же, не всех) задач в разделе «Указания» можно найти дополнительные подсказки. Иногда подсказки содержатся прямо в тексте
задачи — это означает, что мне как автору задачника показалось
бессмысленным тратить время читателя на самостоятельный поиск
нужной информации или нужного подхода; но если подсказка вынесена в раздел указаний, то сначала стоит попробовать обойтись без
неё, это может оказаться полезно. Подсказку, впрочем, стоит прочитать, даже если вы уже решили задачу — может оказаться, что
решить её можно проще или в каком-нибудь смысле «правильнее».
Ну и ещё один момент, который, возможно, разочарует моих
коллег-преподавателей. Большинство сборников задач, какому бы
предмету их ни посвящали, включают огромные массивы всевозможных примеров, часто однотипных, что позволяет организовать
работу в классе или аудитории, предлагая подопечным одну задачу
за другой до полного «освоения» (в действительности тут было бы
уместно совсем другое слово) очередной темы, а потом ещё и провести контрольную работу, используя тот же задачник. Увы, на такое
меня не хватило, да простят меня те, кто чего-то подобного ожидал.
Сборник упражнений, который вы держите в руках, рассчитан на
человека, осваивающего предмет самостоятельно в гордом одиночестве, «запасных» и похожих друг на друга задач тут, за небольшими
исключениями, нет.
Издание этого задачника благополучно завершает проект, растянувшийся на семь лет. Пользуясь случаем, ещё раз благодарю всех
тех, кто поддержал проект своими пожертвованиями; ниже приведён
актуальный на 11 января 2022 г. список всех, кто присылал пожертвования, кроме тех, кто предпочёл сохранить инкогнито.
Gremlin, Grigoriy Kraynov, Ш е р Арсений Владимирович, Таранов Василий, Сергей
Сетченков, Валерия Шакирзянова, Катерина Галкина, Илья Лобанов, Сюзана
Тевдорадзе, Иванова Оксана, Куликова Юлия, Соколов Кирилл Владимирович,
jeckep, К у л ё в а А н н а Сергеевна, Е р м а к о в а М а р и н а А л е к с а н д р о в н а , Переведенцев
Максим Олегович, Костарев Иван Сергеевич, Донцов Евгений, Олег Французов,
С т е п а н Х о л о п к и н , П о п о в А р т ё м С е р г е е в и ч , А л е к с а н д р Б ы к о в , Б е л о б о р о д о в И. Б . ,
Ким Максим, artyrian, Игорь Эльман, И л ю ш к и н Никита, Кальсин Сергей
А л е к с а н д р о в и ч , Евгений Земцов, Ш р а м о в Георгий, В л а д и м и р Л а з а р е в , eupharina,
6
Н и к о л а й К о р о л е в , Г о р о ш е в с к и й А л е к с е й В а л е р ь е в и ч , Л е м е н к о в Д . Д . , F o r e s t e r , say42,
А н я « c a n j a » Ф., С е р г е й , b i g _ f e l l o w , В о л к а н о в Д м и т р и й Ю р ь е в и ч , Т а н е ч к а , Т а т ь я н а
'Vikora' Алпатова, Б е л я е в Андрей, Л о ш к и н ы (Александр и Д а р ь я ) , К и р и л л
Алексеев, kopish32, Е к а т е р и н а Глазкова, О л е г « b u r u n d u k 3 » Д а в ы д о в , Д м и т р и й
Кронберг, yobibyte, Михаил Аграновский, Александр Шепелев, G.Nerc=Y.uR,
В а с и л и й Артемьев, С м и р н о в Денис, Pavel Korzhenko, Р у с л а н Степаненко, Т е р е ш к о
Г р и г о р и й Ю р ь е в и ч 1 5 e 6 5 d 3 d , L o t h l o r i e n , v a s i l i a n d e t s , М а к с и м Ф и л и п п о в , Глеб
С е м е н о в , П а в е л , u n D E F E R , kilolife, А р б и ч е в , Р я б и н и н С е р г е й А н а т о л ь е в и ч , N i k o l a y
K s e n e v , К у ч и н В а д и м , М а р и я Т р о ф и м о в а , igneus, А л е к с а н д р Ч е р н о в , R o m a n
Kurynin, Власов Андрей, Дергачев Борис Николаевич, Алексей Алексеевич, Георгий
Мошкин, Владимир Руцкий, Федулов Роман Сергеевич, Ш а д р и н Денис, Панферов
А н т о н А л е к с а н д р о в и ч , os80, З у б к о в И в а н , А р х и п е н к о К о н с т а н т и н В л а д и м и р о в и ч ,
А с и р я н А л е к с а н д р , Д м и т р и й С. Г у с ь к о в , Т о й г и л ь д и н В л а д и с л а в , M a s u t a c u , D . A . X . ,
К а г а н о в В л а д и с л а в , А н а с т а с и я Н а з а р о в а , Гена И в а н Е в г е н ь е в и ч , Л и н а р а А д ы л о в а ,
А л е к с а н д р , izin, Н и к о л а й П о д о н и н , Ю л и я К о р у х о в а , К у з ь м е н к о в а Е в г е н и я
Анатольевна, Сергей «GDM» Иванов, Андрей Шестимеров, vap, Грацианова Т а т ь я н а
Ю р ь е в н а , М е н ь ш о в Ю р и й Н и к о л а е в и ч , nvasil, В . К р а с н ы х , О г р ы з к о в С т а н и с л а в
А н а т о л ь е в и ч , Б у з о в Д е н и с Николаевич, capgelka, В о л к о в и ч Максим Сергеевич,
Владимир Ермоленко, Горячая Илона Владимировна, Полякова Ирина Николаевна,
Антон Хван, Иван К., Сальников Алексей, Щеславский Алексей Владимирович,
Золотарев Роман Евгеньевич, Константин Глазков, Сергей Черевков, Андрей
Л и т в и н о в , Ш у б и н М. В . , С ы щ е н к о А л е к с е й , Н и к о л а й К у р т о , К о в р и г и н Д м и т р и й
Анатольевич, Андрей Кабанец, Юрий Скурский, Дмитрий Беляев, Баранов Виталий,
Новиков Сергей Михайлович, maxon86, mishamm, Спиридонов Сергей Вячеславович,
Сергей Черевков, Кирилл Филатов, Чаплыгин Андрей, Виктор Николаевич
Остроухов, Николай Богданов, Б а е в Ален, Плосков Александр, Сергей Матвеев a.k.a.
s t a r g r a v e , И л ь я , a y k a r , О л е г Б а р т у н о в , m i c k y _ m a d f r e e , А л е к с е й К у р о ч к и н a k a kaa37,
Н и к о л а й С м о л и н , I, J D Z a b , К р а в ч и к Р о м а н , Д м и т р и й М а ч н е в , b e r g e n t r o l l ,
И в а н А . Ф р о л о в , А л е к с а н д р Ч а щ и н , М у с л и м о в Я . В., S e d a r , М а к с и м С а д о в н и к о в ,
Я к о в л е в С. Д . , Р у с т а м К а д ы р о в , Н а б и е в М а р а т , П о к р о в с к и й Д м и т р и й Е в г е н ь е в и ч ,
Заворин Александр, Павлочев Сергей Ю р ь е в и ч , Рустам Юсупов, Noko A n n a , Андрей
Воронов, Лисица Владимир, Алексей Ковура, Ч а й к а Леонид Николаевич, Коробань
Д м и т р и й , Алексей Вересов, suhorez, Ольга Сергеевна Цаун, Б о б о р ы к и н Сергей
Владимирович, Олохтонов Владимир, Александр Смирницкий, Максим Клочков,
Анисимов Сергей, Вадим Вадимович Чемодуров, rumiantcev, babera, Артем
Коротченко, Евгений Шевкунов, Александр Смирницкий, Артем Шутов, Засеев
Заурбек, Konstantin Slobodnyuk, Yan Zaripov, В и т а л и й Бодренков, А л е к с а н д р
Сергиенко, Денис Кузаков, Пушистый Шмель, Сергей Спивак, suuuumcaa, Гагарин,
В а л е р и й Г а й н у л л и н , А л е к с а н д р М а х а е в ( m a n k m s ) , V D , А. Б . Л и х а ч е в , C o l _ K u r t z ,
E s p a n k a , Д м и т р и й Сергеевич Х., А н а т о л и й К а м ч а т н о в , Табакаев Е в г е н и й
Владимирович, Александр Трошенков, Малюга Андрей, Сорокин Андрей, Б у р к и н
И в а н , А л е к с а н д р Л о г у н о в , m o y a _ b b f 3 , V i l n u r _ S h , К и п н и с А л е к с а н д р , Oleg G . G e i e r ,
В л а д и м и р Исаев (fBSD), Филимонов Сергей Владимирович, vsudakou, AniMath,
Д а н и л о в Е в г е н и й , В о р о б ь е в В. С., m o c h a l o v , К а м ч а т с к а я L U G , Л о г и н о в С е р г е й
Владимирович, Чистяков Артем Андреевич, А&А Сулимовы, Денисов Денис
Юрьевич, Сутупов Андрей Михайлович, kuddai, Озерицкий Алексей Владимирович,
alexz, В л а д и м и р Цой, В л а д и м и р Б е р д о в щ и к о в , Сергей Д м и т р и ч е н к о , И в а н ц о в Д а н и л
Игоревич, З а м ы с л о в Д. А., В л а д и м и р Х а л я м и н , Максим К а р а с е в (begs),
E r r a t i c L u n a t i c , А. Е. А р т е м ь е в , FriendlyElk, Алексей С п а с ю к , А н д р и е в с к и й
Константин Андреевич, Сукачев Владислав Вячеславович, Артем Абрамов, maxon86,
С о к о л о в П а в е л А н д р е е в и ч , А л е к с е й Н, Н и к и т а Г у л я е в , Б о д ю л ь Е в г е н и й , r e b u s _ x ,
Рачинский Максим Юрьевич, Мезенцев Андрей Владимирович, И ж м я к о в Павел
Андреевич, Д е н и с К., У м н о в а Н а т а л ь я Евгеньевна, А р т е м Ж и л е е в , Л е г о ц к и й
Николай Евгеньевич, Виталий Саган, Александр Д., Иванов Павел Николаевич,
Роман Викторович Щербинин, Константин Хомутов, barsik, Чистяков Сергей,
Д м и т р и й Н у р и с л а м о в , Е в г е н и й lipklim К л и м о в , А з а р о в В л а д и м и р , И в а н о в В и т а л и й
Сергеевич, Бичекуев Аслан Расулович, Владимир Бахтин, Иванцов Д а н и л Игоревич,
С м и р н о в И в а н , lexizz19, С о д н о м о в А л е к с е й Э р д э н и - Б а и р о в и ч , y s h a w n , А в д е е н к о в
Василий, Андрей, Игорь, Денис Николаевич Ж . , Aglaro, aoratos, Ш а р а п о в К и р и л л
Владимирович, Александр, Нестеренко Владислав Валерьевич, Рябчиков Дмитрий
Александрович, Андрей Александрович Герман, pashak, Морозов Михаил Павлович,
Тихонов Руслан Владимирович, Копкин Максим, ЛАГ-5891, Евгений Феликсович
Н а б о к о в , П л о т н и к о в С е р г е й , Х у д я е в Глеб, М а к с и м Ш а т а л и н , П е т р З а х а р о в , М и х а и л ,
Тимофей Дубский, Андрей Анатольевич Бородин, gunpi, Зеленин Андрей,
П л а к с и ц к а я Н а т а л и я , e n o e l i a , Ю р и й С и д о р о в , Dizzy, Д м и т р и й С е р е г и н , М и х а и л К . ,
П а в е л Е г о р о в , Д а н и и л Ш е л е п а н о в , Д ь я к о н о в О л е г , Д а н и л о в Р о м а н В и к т о р о в и ч , le34,
Константин Плахетка, Илья Денисов, Вадим Марченко, Ратников Сергей
Валерьевич, Илья Алексеевич Белоусов, К у з ь м и н Ринат, savtog, Валеев Эдуард
Накипович, paq1311, e _ m a t v e e v , Е ф р е м о в Артур, братишка, Иван Михайлович
Пузырев, Jamezzz, Мелкумян Завен, Игорь Романович Шульга, Сергей Спивак,
В а с и л и й Дзюбенко, sadsnake, И г о р ь Середов, Pavel Heiden
З А Д А Ч И
К части 1 «предварительные
сведения»
Командная строка Unix
1.01. Мы находимся в директории / o p t / l i g h t / f o o , т. е. она является для нас текущей; известно, что на одном уровне с директорией
f o o находится директория bar, а в ней есть файл f l . t x t . К а к будет
выглядеть абсолютное имя этого файла? Каково кратчайшее относительное (т. е. отсчитываемое от текущей директории) имя для обращения к этому файлу?
1.02. Пользователь дал следующие команды:
mkdir t e t r i s
ср t e t r i s . p a s
cd t e t r i s
Is
tetris
Все команды отработали успешно. Что напечатала последняя из них?
1.03. К а к а я директория стала текущей после команд
cd
cd
cd
/usr/local/bin/hunter
../../lib
hunter/run
если известно, что все команды отработали успешно?
1.04. К а к а я директория станет текущей, если дать команды
cd
cd
cd
cd
cd
..
../..
../john
work/tetris/src
..
и все они отработают успешно, а текущей изначально была директория / h o m e / l i z z i e / w o r k / p a s / t e t r i s ?
К части «предварительные сведения»
9
1.05. Почему в условиях задачи 1.03 не указано, какая директория была текущей изначально?
1.06. Что означают права доступа к обычному файлу, заданные
следующими числами?
а) 0700
Ь) 0440
с) 0511
d) 0660
е) 0644
f) 0555
1.07*. Что означают права доступа к обычному файлу, заданные
следующими числами?
а) 04711
Ь) 06751
с) 02550
1.08. Что означают права доступа к директории, заданные следующими числами? Имеет ли смысл устанавливать такие права, а если
нет, то какие права доступа следовало бы поставить вместо них?
а) 0700
Ь) 0711
с) 0751
d) 0733
е) 0744
f) 0660
1.09*. Что означают права доступа к директории, заданные следующими числами? В каких ситуациях такие права доступа могут
потребоваться?
а) 01770
Ь) 03777
Следующие задачи посвящены с к р и п т о в о м у п р о г р а м м и р о ванию на я з ы к е к о м а н д н о г о интерпретатора (Bourne Shell);
для их решения потребуется владение материалом, к о т о р ы й
в к н и г е объявлен к а к « н е о б я з а т е л ь н ы й » (см. § 1.2.15 1 ) — набран у м е н ь ш е н н ы м ш р и ф т о м и предваряется к о м м е н т а р и ем о п р и ч и н а х . П о в т о р и м эту м ы с л ь здесь: начинать изучение п р о г р а м м и р о в а н и я с я з ы к а Bourne Shell — идея крайне
неудачная, поэтому, если вы раньше ни на к а к и х я з ы к а х не
п р о г р а м м и р о в а л и , правильнее будет п р о п у с т и т ь и сами эти
задачи, и н у ж н ы й для них ф р а г м е н т к н и г и , и вернуться к
ним позднее, когда у вас у ж е будет о п ы т п р о г р а м м и р о в а н и я ,
путь д а ж е небольшой.
1.10. Напишите скрипт на Bourne Shell, принимающий ровно два
аргумента командной строки, которые д о л ж н ы быть целыми числами (назовём их N и М ) . Скрипт должен выдать на печать М натуральных чисел подряд, начиная с числа N ; числа д о л ж н ы быть
напечатаны через пробел, а в конце следует выдать перевод строки.
Например, если заданы числа 15 и 5, ваш скрипт должен напечатать:
15 16 17 18 19
1.11. Напишите скрипт на Bourne Shell, который выдаёт (в одну
строку) столько символов « у С Д Н Ф состоит всего из одного «слагаемого»: ху. Обратите внимание, что в к а ж д ы й член входят (с отрицанием или без)
обе переменные х и у; для функции от трёх переменных х, у и z в
к а ж д ы й член СДНФ входили бы все эти три переменные.
В общем случае (для произвольной функции) СДНФ состоит из
стольки членов, сколько единиц в правой части её таблице истинности; к а ж д ы й такой член формируется, исходя из левой части соответствующей строки таблицы истинности: переменные, которые
в этой строке равны единице, входят в конъюнкт сами по себе,
а те, что равны нулю, берутся с отрицанием. Например, функция
К части «предварительные сведения»
15
h(x, у, z) = z(x ф у) будет истинна (равна единице) на двух наборах:
(0,1,1) и (1,0,1); следовательно, её СДНФ будет состоять из двух
членов: xyz V xyz.
Постройте таблицы истинности для следующих выражений и
представьте их в совершенной дизъюнктивной нормальной форме:
а) (х ^ у) ф (х ^ z)
b) (х V у)(х ^ (yz))
1.50. Имеется 500 логических (булевых) переменных, обозначенных х\, Х2, хз,..., Ж500. Сколько решений имеет каждая из следующих систем уравнений ?
<
Х\
ф
х2
= 1
Х2
ф
хз
= 1
Хз
ф
Х4
= 1
, Ж499 ф
Х500
Х\ ф
Х2
Х2 ф хз
=0
= 0
< хз ф Х4 = 0
=
1
, Ж499 ф
Х500
=
0
Какие это решения?
1.51*. Логическая функция называется существенно aasucpwfiZ
от переменной х, если существует хотя бы одна такая пара наборов
значений всех переменных, что функция на этих наборах принимает противоположные значения, а сами наборы различаются только
значением переменной х, все остальные переменные в этих наборах
имеют одинаковые значения. Так, конъюнкция и дизъюнкция существенно зависят от обеих своих переменных, функция f (х,у) = х
существенно зависит только от х, а константы не являются существенно зависимыми ни от одной переменной. Сколько существует
логических функций от двух переменных, существенно зависящих
от каждой своей переменной? А сколько таких функций от трёх переменных?
Количество информации
1.52. В некоторой игре, чтобы сделать ход, игрок должен бросить три игральные кости (обычные кубики, грани которых помечены числами от 1 до 6), причём правилами игры установлено, что
учитываются только выпавшие единицы и двойки, а кости, упавшие
вверх гранями от 3 до 6, дают ноль очков. Какова информационная
ценность сообщений, что игрок в результате своего броска:
a)
b)
c)
d)
получил
получил
получил
получил
ноль очков;
ненулевое количество очков;
шесть очков;
одно очко?
16
Задачи
1.53. Игральная кость для некоторой настольной игры выполнена
в виде додекаэдра — правильного 12-гранника, каждая грань которого представляет собой правильный пятиугольник; считается, что
падения этой кости любой из её граней вверх равновероятны. В связи
с особенностями правил игры три из 12 граней пусты (считается, что
их выпадение соответствует нулю очков), остальные грани помечены числами от 1 до 9. Какова информационная ценность сообщения
«результат броска кости — ноль очков»?
1.54. Бросив игральную кость, описанную в предыдущей задаче,
игрок получил больше трёх очков. Какова информационная ценность
сообщения об этом?
1.55. Устроители благотворительной лотереи выпустили миллион билетов и сообщили, что будет разыграно 15625 призов (каждый
билет может выиграть один приз или не выиграть ни одного). Зная
это, Сергей купил два билета. Через некоторое время ему сообщили,
что оба его билета выиграли. Сколько бит информации он при этом
получил?
1.56. На участие в забеге на 10000 метров заявились 27 спортсменов, среди них был Виктор, за которого болели Маша и Оля. Оля
не смогла прийти на соревнования, поэтому Маша сообщала ей о
происходящем, посылая SMS-сообщения. Сначала Маша сообщила,
что 13 спортсменов из числа заявившихся не вышли на старт, но
Виктор благополучно стартовал. Когда забег был в самом разгаре,
от Маши пришло сообщение, что на дистанции один из спортсменов
сделал другому подножку, так что тот второй упал и вынужден был
сойти с дистанции, а виновника происшествия судьи дисквалифицировали. Ещё через какое-то время Маша написала, что ещё шестеро
спортсменов сошли с дистанции по разным причинам, а Виктор благополучно добежал до финиша, но табло на стадионе сломалось и
зрители не знают, кто с каким результатом финишировал, так что
придётся ждать награждения.
Какова информационная ценность заключительной SMS-ки от
Маши, в которой сообщалось, что Виктора, увы, нет на пьедестале,
если никакой информации об исходном уровне подготовки спортсменов Оля не получала?
1.57. В турнире участвовали восемь шахматистов, имеющих примерно одинаковый рейтинг. Один из зрителей после подведения итогов записал на бумажке фамилии участников турнира, занявших
три призовых места. Сколько информации получит его знакомый,
для которого предназначается бумажка, если список всех участников, сформированный до начала турнира, у него уже есть?
К части 2 «язык Паскаль и
начала программирования»
Закрепление базовых понятий
2.01. Д л я каждого из следующих выражений определите его значение и тип:
а) 2+3
Ь) 2+3*10
с) 5 - 1 6 - 7 )
d) 18/6
e) 15/6
f) 18 d i v 6
g) 18 mod 6 h) 17 d i v 3 i) 17 mod 3 j) 4 mod 7
k) 2 / 1 + 3 / 1 l) 3 < 4
m) 2 = 1 . 0 + 1 . 0
n) 3 4 - 1
2.02. Какие значения будут в переменных a и b, имеющих тип
i n t e g e r , после выполнения следующих присваиваний?
a := 3 ;
b := 5 ;
a := b ;
b := a ;
2.03. Что напечатает следующая программа?
program demol;
var
x, у, z: i n t e g e r ;
begin
x := 5 ;
У := 1 0 ;
z := x 4 у ;
x := z 3 3 ;
writeln(x)
end.
2.04. Переменная x, имеющая тип i n t e g e r , содержит число 7;
какое число она будет содержать после выполнения следующих присваиваний?
Задачи
18
х := х 4 3 ;
х := 100 - х ;
х := 10 3 х 4 х ;
2.05. Что будет напечатано в результате выполнения следующих
фрагментов программы?
а)
i := 0 ;
w h i l e i < 10 d o
begin
writeln('Hello');
i := i 4 1
end
Ь)
с)
i := 1 5 ;
w h i l e i < 27 d o
begin
writeln('abrakadabra');
i := i 4 1
end
d)
i := 4 0 ;
w h i l e i > 25 do
begin
writeln('foobar');
i := i - 1
end
е)
i := 5 ;
w h i l e i < 104 do
begin
w r i t e l n ( ' J o h n n y be
i := i 4 10
end
f)
i := 1 2 ;
w h i l e i > 22 do
begin
writeln('abcdefgh');
i := i 4 1
end
good!');
i := 1;
w h i l e i < 20 do
begin
writeln('Good
i := i 4 1
end
Bye');
2.06. Что будет напечатано в результате выполнения следующих
фрагментов программы?
а)
с)
i := 0 ;
repeat
writeln('Hello');
i := i 4 1
u n t i l i > 10;
Ь)
i := 1 2 ;
repeat
writeln('abrakadabra');
i := i - 1
u n t i l i > 0;
d)
i := 1;
repeat
writeln('Good
i := i 4 1
u n t i l i > 20;
Bye');
i := 1 2 ;
repeat
writeln('abcdefgh');
i := i 4 1
u n t i l i < 100;
Сравните ваши результаты с результатами предыдущей задачи.
2.07*. Переменную, которая меняет своё значение на каждой итерации цикла и на основании значения которой принимается решение, продолжать цикл или прекратить, часто называют
счётчиком
К части « я з ы к П а с к а л ь и н а ч а л а программирования»
19
цикла. К а к вы считаете, в каких примерах из задач 2.05 и 2.06 переменную i можно с полным на то основанием называть «счётчиком»
и что конкретно она считает?
2.08. Вернитесь к задаче 2.05 и те примеры, которые это позволяют, перепишите с использованием цикла f o r так, чтобы переменная
цикла пробегала те же самые значения. Какие из примеров не допускают такого переписывания и почему?
Побитовые операции
2.09. Каковы значения следующих выражений?
а) 99 and 78 Ь) 99 or 78
с) 99 xor 78 d) not 0
е) not - 1 3
f) not 177
f) 1 s h l 7
g) 7 s h l 2
h) 255 shr 4 i) 240 shr 3 j) 42 shr 3
1) - 2 s h l 2
2.10. Переменные x и у имеют тип longword (32-битное беззнаковое целое). Какие в них будут значения после выполнения следующих
операторов?
х
у
х
у
:=
:=
:=
:=
$abcdef57;
$12346891;
( ( х s h r 8) and $ f f f f 0 0 0 0 ) o r ( ( у s h l 8) and $ f f f f ) ;
( ( у and $ f f 0 0 0 0 ) s h r 16) o r ( ( у and $ f f ) s h l 8 ) ;
Напомним, знак «4» в Паскале означает шестнадцатеричную систему
счисления; ответ дайте также в виде шестнадцатеричных чисел.
2.11. Напишите функцию, которая принимает параметром число типа l o n g i n t и возвращает целое число — количество единиц в
двоичном представлении параметра.
З а д а ч и на ц и к л ы и п р о ц е д у р ы
Последующие задачи стоит пробовать решать не раньше,
чем вы справитесь с содержанием главы 2.3, рассказывающей о подпрограммах, или хотя бы с первым параграфом
из неё. Обязательно применяйте процедуры при решении
задач, исключая дублирование кода и упрощая структуру
программы, иначе эти задачи окажутся практически бесполезны.
2.12. Задействовав процедуру PrintChars, разобранную в §2.3.1
в качестве одного из примеров, напишите две программы, по смыслу аналогичные программе DiamondProc (эта программа разобрана в
том же параграфе чуть раньше) и точно так же, как она, использующие построчный вывод, но немного отличающиеся от неё: пусть одна
Задачи
20
из них печатает «ромбик», он же «алмаз», .заполненный звёздочками,
а вторая — «алмаз» из пробелов на фоне, заполненном звёздочками.
Так, если пользователь введёт число 5, ваши программы д о л ж н ы
напечатать следующее:
(слева показан вывод первой программы, справа — второй). Обязательно убедитесь, что в вашей программе нет одинаковых фрагментов кода, если они есть — вынесите их в процедуры.
2.13. Напишите программу, запрашивающую у пользователя два
числа: высоту «алмаза» и желаемое количество «алмазов», и выдающая (построчно!) фигуру из звёздочек, содержащую заданное число
алмазов заданной высоты, расположенных горизонтально и отстоящих друг от друга на один пробел. Так, если пользователь ввёл числа
7 и 6, получиться должно следующее:
2.14. Напишите программу, выдающую состоящую из «звёздочек» букву Z с горизонтальной поперечиной, имеющую заданную
(введённую пользователем) высоту (и такую же ширину). Например,
для введённого числа 7 результат должен быть таким:
3
3
3
Если пользователь пытается ввести чётное число или число меньше пяти, выдавайте сообщение об ошибке и просите пользователя
повторить ввод.
2.15*. Усовершенствуйте программу из задачи 2.14, чтобы она
запрашивала два числа (высоту буквы и количество таких букв) и
печатала нужное количество букв Z заданной высоты, причём кажд а я следующая буква Z д о л ж н а отстоять от предыдущей на один
К части «язык Паскаль и начала программирования»
21
пробел по горизонтали и на половину высоты буквы по вертикали.
Например, для чисел 7 и 3 картина д о л ж н а получиться такая:
3
3
3
3
3
3
3
3
3
3
3
3
Символы
2.16. Напишите программу, которая читает из стандартного потока ввода строку (используйте переменную типа s t r i n g и оператор
readln) и печатает те непробелъные символы из этой строки, которые в ней встречаются больше одного раза. К а ж д ы й такой символ
должен быть напечатан ровно один раз; печатать их следует в том порядке, в котором они S nepsuZ раз встречаются во введённой строке.
Не забудьте про перевод строки в конце вашего вывода. Например,
работа программы может выглядеть так:
lizzie abra "schwabra kadabra" "foo
[abra]
[schwabra kadabra]
[foo
bar]
> abra schw"abra ka"dab"ra"
[abra]
[schwabra kadabra]
[foo
bar]
> abra schwabra kadabra"
E r r o r : unmatched quotes
> abraschwabrakadabra
[abraschwabrakadabra]
> ~D
kadabra
bar"
foo"
"bar
foo bar
user /dev/null
Сразу после этого ваша программа (в нашем примере её исполняемый файл называется s h e l l 1 ) появится в верхних строчках списка,
выдаваемого программой top в соседнем окне; подождите несколько
58
Задачи
секунд, и если за это время числа, показывающие количество занимаемой вашей программой памяти (в особенности число в колонке VIRT), не начнут плавно расти, то всё, скорее всего, в порядке;
если же они действительно стали расти, немедленно прибейте ваш
конвейер нажатием Ctrl-C (иначе ваша программа запросто может
сожрать всю доступную память и «повесить» систему) и приступайте к поиску — где-то в вашей программе память выделяется, но не
освобождается.
4.37. Доработайте решение задачи 4.36 так, чтобы в слово можно
было включить символ двойной кавычки. Д л я этого предусмотрите
ещё один «специальный» символ — «\», который будет «экранировать» символ, стоящий следом за ним; таких «экранируемых» символов следует предусмотреть два: символ двойной кавычки и сам
символ «\», ведь его тоже может потребоваться ввести в слово. К а к
реагировать, если следом за «\» в строке располагается какой-то ещё
символ — придумайте сами, только не завершайте при этом работу
программы (увы, приходится об этом напоминать).
4.38. Снабдите решение задачи 4.36 возможностью сформировать пустое слово. Обозначением пустого слова считайте два символа
двойных кавычек, встреченные подряд sHe c\os, то есть когда накопленное слово пусто, а сразу после закрывающей кавычки идёт либо
пробельный символ, либо конец строки.
К части 5 «объекты и услуги
операционной системы»
Ф а й л ы и п о т о к и (уровень с и с т е м н ы х в ы з о в о в )
5.01. Напишите программу, которая получает аргументом командной строки имя ф а й л а и, открыв его на чтение, с помощью
системного вызова l s e e k 6 4 определяет (и печатает) его длину в байтах. Обязательно проверьте корректность работы вашей программы
на разных файлах.
Конечно, S реальной задаче следует для определения размера файла воспользоваться вызовом s t a t , тогда файл не придётся открывать, а узнать размер можно будет даже для такого файла, к которому нет доступа на чтение.
Всему своё время!
5.02. Используя для чтения и записи только системные вызовы
(read и write), напишите программу, которая копирует свой поток
стандартного ввода в поток стандартного вывода, т. е. ведёт себя как
хорошо известная команда cat без параметров. Чтение и запись производите блоками (например, чтение запрашивайте по 1024 или 4096
байт; записывайте всегда столько, сколько прочитано). Проверьте
корректность работы вашей программы как с терминалом, так и с
различными комбинациями перенаправлений; особое внимание обратите на сохранение размера файла, когда перенаправлены и ввод, и
вывод.
5.03. Напишите на Си программы, соответствующие условиям задач 2.53 и 2.54 (см. стр. 32), адаптированным к терминологии Си (термин «типизированный файл» замените термином «бинарный файл»).
Д л я работы с бинарными файлами используйте системные вызовы,
для работы с текстовыми — высокоуровневый ввод-вывод.
5.04. Используя для чтения файла только системные вызовы,
напишите программу, которая получает через параметр командной
60
Задачи
строки имя файла и (в предположении, что файл текстовый) подсчитывает в нём количество строк. Чтение всегда запрашивайте блоками
(например, по 4096 байт). Полученное количество строк напечатайте
(используйте обычный p r i n t f ) .
5.05. Напишите программу, которая получает четыре параметра
командной строки: имя файла, начальную позицию, длину и значение байта; указанный файл открывает на запись и, начиная с заданной позиции, заполняет в этом файле отрезок нужной длины указанным байтом. Запись организуйте так, чтобы, если указанная длина отрезка превышает 4096 байт, вывод производился блоками по
4096 байт, и лишь один (последний) вызов w r i t e записывал меньше (сколько ещё осталось). Проверить корректность работы вашей
программы можно с помощью утилиты hexdump.
5.06. Известен очень простой (и совершенно не стойкий к взлому,
но сейчас это не так важно) способ зашифровать данные, используя
секретный ключ: просто применить к данным и указанному ключу
операцию «исключающее или» (xor). Напомним на всякий случай,
что в языке Си эта операция обозначается символом «~».
Напишите программу, которая получает два параметра командной строки: имя файла и ключ (ключ рассматривается как 32-битное
беззнаковое целое число), и прямо па месте (не создавая никаких
дополнительных файлов) «зашифровывает» заданный ф а й л заданным ключом. Насколько это возможно, работу производите блоками
по 4096 байт. Учтите, что длина файла может оказаться не кратна
четырём байтам. Длина файла, естественно, не должна измениться
в результате зашифровки; если всё сделать правильно, это никак не
усложнит вашу программу.
Поскольку х ф а ф а = х для любых х и а, расшифровка производится точно так же, как и зашифровка, то есть нужно второй
раз прогнать вашу программу с тем же самым ключом. Это позволяет проверить корректность программы: возьмите какой-нибудь
файл более-менее серьёзного размера (например, фотографию или
музыкальный трек), создайте его копию, «зашифруйте» её, убедитесь, что содержимое файла теперь не имеет ничего общего с оригиналом, повторно запустите вашу программу и теперь (например, с
помощью d i f f или md5sum) убедитесь, что результат расшифровки
тождественно (байт в байт) совпадает с оригинальным файлом.
5.07. Вернитесь к условиям задач 2.55-2.57 (см. стр. 32) и напишите аналогичные программы на Си с использованием файловых системных вызовов. Текст условия задачи 2.55 адаптируйте к реалиям
Си — за неимением аналога паскалевского типа s t r i n g используйте
К части «объекты и услуги операционной системы»
61
массив из 60 элементов типа char, предполагающий нулевой байт на
конце.
5.08. Напишите программу, которая получает через аргумент командной строки имя файла и, используя библиотечные функции
opendir, readdir и c l o s e d i r , находит в текущей директории и во
всех её поддиректориях ф а й л ы с заданным именем. Д л я каждого
найденного файла напечатайте его относительное имя, отсчитываемое от текущей директории.
5.09. Напишите программу, которая получает через аргумент командной строки имя файла и, используя вызовы s t a t и l s t a t , выдаёт (в виде текста на английском языке) все свойства этого файла,
какие только возможно, начиная с типа файла; для символических
ссылок печатайте информацию как по самой ссылке, так и по файлу, на который она ссылается (если, конечно, таковой есть; если его
нет — напечатайте слово dangling).
Управление процессами
5.10. Что может напечатать следующая программа, если вызов
fork и все операции вывода пройдут успешно? Перечислите все варианты. Считайте, что вывод идёт на терминал, так что выдача символа перевода строки приводит в вытеснению буфера вывода.
#include
#include
i n t main()
K
int pid;
printf("start\n");
pid = fork();
i f ( p i d == 0) {
printf("child\n");
M else {
printf("parent\n");
M
printf("finish\n");
r e t u r n 0;
M
5.11. В некоторой программе содержится описание локальной переменной:
int
^status;
а позже в тексте — такой вызов:
Задачи
62
wait(status);
Больше переменная s t a t u s в программе нигде не упоминается. В чём
состоит ошибка программиста, писавшего эту программу? На всякий
случай подчеркнём, что ошибка здесь совершенно фатальная и выдаёт глубочайшее непонимание происходящего, но при этом программа
пройдёт компиляцию и даже будет делать вид, что «работает», хотя,
конечно, работать будет неправильно.
К а к следует исправить эту программу?
5.12. Напишите программу, которая принимает произвольное количество (не менее одного) аргументов командной строки и рассматривает их как имя и аргументы для запуска внешней программы;
например, если ваша программа называется prog и пользователь запустил её командой
./prog ls
-l
-R
— то ваша программа д о л ж н а запустить программу l s с аргументами
- l -R. Сделайте так, чтобы в зависимости от того, как запущенная
программа завершится, ваша программа печатала либо слово e x i t e d
и код завершения, либо слово k i l l e d и номер сигнала, которым запущенная программа была убита.
5.13. Напишите программу, которая через аргументы командной
строки получает имена и аргументы д л я запуска внешних программ
(произвольное их количество), разделённые параметром, состоящим
из двух символов «; »; чтобы при запуске командный интерпретатор
не считал параметр « ; ; » имеющим особый смысл, заключайте его в
апострофы, например:
./prog ls
-l /
';;'
s l e e p 10 ' ; ; '
cat
file1.txt
file2.txt
Ваша программа д о л ж н а запустить на одновременное (параллельное) исполнение все указанные программы с заданными аргументами и напечатать и м е н а тех из них, которые завершились успешно,
то есть вызовом _ e x i t с параметром 0. Печатать имена следует по
мере завершения запущенных программ. Закончить работу следует
сразу после завершения последней из запущенных программ, но не
раньше.
5.14. Допустим, в вашей программе запускается много дополнительных процессов, и вы знаете, что некоторые из них уже могли
завершиться (и превратиться в зомби), но не все. Нужно убрать всех
«готовых» зомби, но при этом не блокироваться в ожидании тех, кто
ещё не завершился. Каким фрагментом кода это можно сделать?
К части «объекты и услуги операционной системы»
63
5 . 1 5 ( s h e l l - I I ) . Вернитесь к программе, которую вы писали, решая задачи 4.36-4.38, и модифицируйте её так, чтобы введённые
пользователем команды не печатались, а выполнялись, то есть чтобы
ваша программа, прочитав очередную команду, запускала внешнюю
программу, имя которой задано первым словом, а остальные слова
представляют собой аргументы командной строки.
Поскольку процесс в ОС Unix не может изменить текущую директорию другому процессу, а только себе, команду cd (то есть —
буквально — ситуацию, когда первое слово введённой команды состоит из двух символов — «c» и «d») придётся рассматривать как
особый случай. Запуск внешней программы здесь бесполезен; вместо этого проверьте. что задан ровно один параметр (т.е.введённая
команда состоит ровно из двух слов: собственно «cd» и имени директории), и смените текущую директорию с помощью системного
вызова chdir.
5.16. Доработайте программу, написанную при решении предыдущей задачи, так, чтобы команду cd можно было дать без параметров, и она при этом, как и в «настоящем» командном интерпретаторе,
устанавливала в качестве текущей домашнюю директорию пользователя.
5 . 1 7 ( s h e l l - I I I ) . Когда речь идёт о разборе текста на формальном языке, в большинстве случаев первой стадией такого разбора
становится лексический анализ, то есть разбиение текста на лексемы
или токены; решение задачи 4.36 можно рассматривать как простейший лексический анализатор, а токенами здесь выступают те самые
слова, на которые наша программа делит введённую пользователем
строку.
В языках программирования некоторые символы или определённые последовательности символов (как правило, короткие — в два
символа, очень редко в три) выделяются в отдельные лексемы, д а ж е
если их не отделить от остального текста пробелами. Таковы обычно
всевозможные скобки, пунктуационные символы вроде «;», « , » или
«:», обозначения арифметических операций — такие как «+», «/»,
и т. п. Примерами разделителей, состоящих более чем из одного символа, служат обозначения некоторых операций языка Си: +=, &&, ->,
а, скажем, = — это тот самый редкий случай разделителя
из трёх символов. Отметим, что обозначения операций не обязаны
быть разделителями: так, в Паскале слова div, mod, and, or или not
разделителями не являются, ведь если написать, к примеру, aandb —
это будет совсем не то же самое, что a and b (тогда как в Си a&feb
и a && b — совершенно одно и то же, поскольку здесь конъюнкция
обозначена разделителем &&).
64
Задачи
Существуют свои разделители и во входном языке командного
интерпретатора. В нашем упрощённом интерпретаторе можно ограничиться небольшим количеством разделителей, но совсем без них
обойтись невозможно.
Начнём мы с того, что снабдим наш командный интерпретатор
возможностью запуска процессов в фоновом режиме, а для этого нам
потребуется символ «&» (амперсанд), и его нужно оформить как разделитель. Говоря более конкретно, нужно, чтобы ваша программа,
встретив этот символ sne кasычек, рассматривала его как «отдельное слово» вне всякой зависимости от того, есть вокруг него пробелы
или нет, причём это должно быть некое «хитрое» слово, отличающееся от простого слова из одного амперсанда (такое можно получить,
если заключить амперсанд в кавычки, а вокруг кавычек поставить
пробелы).
Амперсанд означает, что команду следует выполнить «в фоновом режиме», то есть, попросту говоря, пе ждатъ её зaseршenия —
запустить и «забыть», продолжая читать команды с клавиатуры и
выполнять их. Нужно будет только не забыть вовремя убрать зомби, когда такая фоновая команда всё-таки завершится. Настоящие
командные интерпретаторы позволяют ввести сразу несколько команд, разделив их амперсандами, при этом все команды, кроме последней, будут выполняться в фоновом режиме; но эта возможность
всё равно применяется очень редко, так что мы поступим проще: будем считать, что амперсанд должен располагаться в конце строки,
т. е. если после него есть ещё что-то, кроме пробелов, будем выдавать
ошибку.
Если пользователь ввёл всё правильно, то есть амперсанд, встреченный вне кавычек, является в строке последним значащим символом, то ваша программа должна введённую команду исполнить как
фоновую (сам амперсанд, конечно, в такую команду не входит, используются только настоящие слова, расположенные до него). Само
по себе это д а ж е проще, чем обычное выполнение — просто не делать wait, и всё; но сам ф а к т возможности существования фоновых
процессов означает, что выполнение команд в обычпом режиме, не
фоновом, становится несколько сложнее, хотя и не сильно. Попробуйте сами сообразить, в чём тут проблема и как с ней справиться, если
же сразу не догадаетесь — воспользуйтесь указаниями на стр. 129.
На всякий случай отметим, что S последующих задачах, посвящённых командному интерпретатору, потребуются ещё разделители >, E, >>, I, ; , (, ) , &&
и I I . Если вы планируете довести эту программу до конца — возможно, имеет смысл предусмотреть все разделительные лексемы прямо сейчас, вместе
с одиночным амперсандом, чтобы больше не переделывать ваш анализатор
строки; пока соответствующие возможности не реализованы, при появлении
К части «объекты и услуги операционной системы»
65
S пользовательском вводе любого из этих разделителей следует фиксировать
ошибку с диагностикой вроде « F e a t u r e n o t i m p l e m e n t e d y e t » .
Перенаправление ввода-вывода
5.18. Напишите программу, которая принимает не менее двух аргументов командной строки и рассматривает первый аргумент — как
имя файла, остальные — как имя и аргументы для запуска внешней программы; например, если ваша программа называется prog и
пользователь запустил её командой
./prog f i l e l . t x t
ls
-l
-R
— то здесь имеется в виду файл f i l e 1 . t x t , внешняя программа l s и
аргументы - l -R. Запустите указанную внешнюю программу с указанными аргументами так, чтобы:
a) её стандартный вывод был перенаправлен в указанный файл (если
такого файла нет, он должен быть создан, если он уже есть —
перезаписан; если открыть файл не удалось, д о л ж н а быть выдана
диагностика, соответствующая возникшей ситуации);
b) её стандартный ввод шёл из указанного файла (если такого файла
нет, д о л ж н а быть зафиксирована ошибка и выдана соответствующая диагностика);
c) стандартный вывод был перенаправлен в указанный файл на до6as\enue S конец (если файла нет, создайте его, но если он есть,
новое содержимое должно быть добавлено к старому);
d) стандартный вывод был перенаправлен в указанный файл на добавление в конец, причём если такого файла нет, должна быть
зафиксирована ошибка.
5 . 1 9 ( s h e l l - I V ) . Возьмите за основу программу, написанную в
соответствии с условиями задачи 5.17; если вы ещё не решали её,
можно начать с версии программы, написанной в качестве решения
задачи 5.15, а к фоновым процессам вернуться позднее. Условия задачи 5.17 стоит хотя бы прочитать и понять, о чём там идёт речь,
поскольку повторять рассуждения о лексическом анализе и разделительных лексемах мы здесь не будем.
Модифицируйте ваш анализатор строки так, чтобы он воспримнимал в качестве разделителей, наряду с уже имеющимся токеном
«&», также токены «>», «>». Обратите внимание, что любые из
этих символов д о л ж н ы иметь специальный смысл только Sне Kasiчек, тогда как внутри кавычек любой символ, кроме собственно кавычки, считается просто символом. Таким образом, например, ">>"
Задачи
66
и просто >> — это совершенно не одно и то же. Кроме того, » — это
не то же самое, что два отдельно стоящих символа >.
Модифицируйте остальную часть программы так, чтобы любой
из этих токенов, если после него поставить обычное слово (предполагается, что это слово — имя файла), производил соответствующее
перенаправление: знак < означает перенаправление стандартного потока ввода на чтение из заданного файла, знак > — перенаправление
стандартного вывода на запись в заданный файл (если файла нет, он
должен быть создан, если он есть — перезаписан с нуля), знак >> —
перенаправление стандартного вывода на добавление в конец заданного файла (если ф а й л а нет, он должен быть создан).
Фиксируйте ошибки в случаях, если:
• пользователь пытается перенаправить один и тот же поток два
и более раза — д в а ж д ы встречается один и тот же символ перенаправления или в одной команде сочетаются > и >>;
• следующий токен после любого из токенов или >> не является простым словом (т.е. является разделителем);
• после специальных токенов наблюдаются какие-то ещё простые
слова, кроме ожидаемых (имён файлов сразу после или >>).
Сочетания перенаправлений с символом фонового режима (который
по-прежнему должен быть последним во введённой строке), а также
и между собой, если они осмысленны (одно перенаправление на ввод,
другое на вывод) д о л ж н ы нормально работать.
Сигналы
5.20. Напишите программу, которая после запуска выдаёт сообщение «Press Ctrl-C t o quit» и после этого ничего не делает, но и
не завершается; при нажатии Ctrl-C выдаёт сообщение «Good bye» и
завершается. Обязательно убедитесь с помощью программы top, что
ваша программа во время своего «ничегонеделания» не потребляет
процессорное время.
5.21. Напишите программу, которая после запуска ничего видимого не делает, но и не завершается, в том числе и при нажатии
Ctrl-C; при получении сигнала SIGUSR1 выдаёт в поток стандартного вывода число, сколько раз к текущему моменту пользователь
успел нажать Ctrl-C (на самом деле — сколько раз приходил сигнал
SIGINT).
Д л я завершения работы программы используйте C t r l - \ или
убейте её из другого терминального окна.
К части «объекты и услуги операционной системы»
67
5.22. Напишите программу, которая один раз в секунду печатает
(без перевода строки) некоторый символ, причём сразу после запуска
это символ «+», после нажатия Ctrl-C (то есть по сигналу SIGINT)
печатаемый символ меняется на «-», после нажатия C t r l - \ (то есть
по SIGQUIT) — меняется обратно на «+», причём в обоих случаях соответствующий символ печатается немедленно после нажатия комбинации клавиш, и очередная секунда отсчитывается с этого момента. При нажатии Ctrl-C д в а ж д ы с интервалом менее одной секунды
программа завершает работу, двойное нажатие с боольшим интервалом никакого эффекта не оказывает. Д л я отслеживания секундного
интервала используйте системный вызов alarm и сигнал SIGALRM.
5.23. Напишите программу, которая ожидает пользовательского ввода, причём если пользователь ничего не вводит в течение пяти секунд, спрашивает пользователя, не заснул ли он (конкретный
текст вопроса можете придумать сами). При нажатии Ctrl-C (сигнал SIGINT) выдаёт информацию о том, сколько строк и символов
успел к настоящему моменту ввести пользователь (если пользователь дальше ничего не вводит, пять секунд до очередного вопроса
отсчитывается от момента нажатия Ctrl-C). При повторном нажатии Ctrl-C менее чем в течение пяти секунд программа завершает
работу. Д л я отслеживания пятисекундного интервала используйте
системный вызов alarm и сигнал SIGALRM.
5.24. Вернитесь к задаче 5.19 (если её ещё не решали — то к задаче 5.17) и перенесите цикл «очистки от зомби» в обработчик сигнала
SIGCHLD, как это, собственно говоря, и положено делать. Учтите, что
этот цикл помешает работе цикла обычных wait'ов, который выполняется при ожидании завершения нефоновой команды, так что на
время этого цикла следует возвращать для сигнала SIGCHLD диспозицию по умолчанию.
К а н а л ы и конвейеры
5.25. Напишите программу, в которой порождается дополнительный процесс, связанный неименованным каналом (pipe) с родительским процессом; родительский процесс читает информацию из канала, пока она не кончится, и всё прочитанное тут же выдаёт в
свой стандартный вывод; порождённый процесс записывает в канал
несколько текстовых строк (например, какое-нибудь стихотворение)
и завершается. Родительский процесс должен, дочитав всё из канала, дождаться завершения порождённого процесса (на самом деле
порождённый, скорее всего, уже завершился, но wait сделать всё
68
Задачи
равно стоит) и закончить работу. Если всё сделать правильно, строки, которые порождённый процесс передавал в канал, окажутся в
итоге выведенными на экран (родительским процессом), после чего
программа завершит работу.
Эта задача может показаться бессмысленной, но она позволит,
как говорится, «опробовать инструмент» (в данном случае — pipe).
Если что-то пошло не так, обратитесь к указаниям на стр. 132.
Д л я большей наглядности добавьте в вашу программу сразу после вызова pipe простой p r i n t f , который напечатает численные значения обоих дескрипторов созданного канала. Если вам придёт в
голову какой-нибудь ещё эксперимент — обязательно сделайте его,
компьютер не взорвётся; осознать, что это за сущность такая — «канал», — очень важно для дальнейшего развития.
5.26. Напишите программу, которая через аргументы командной
строки получает имена и аргументы для запуска д в у х внешних программ, разделённые параметром, состоящим из двух символов «;»,
как в задаче 5.13, и запускает эти программы на одновременное (параллельное) выполнение, связав их конвейером, т. е. стандартный вывод первой программы должен идти на стандартный ввод второй
программы.
5.27. Напишите программу, которая получает через аргументы
командной строки имя и аргументы для запуска внешней программы
(так же, как это было сделано в задаче 5.12). Запустите эту внешнюю
программу, подав ей на стандартный ввод ч е р е з н е и м е н о в а н н ы й
к а н а л текстовое представление чисел 1, 2, 3 и т.д. до 1000000, по
одному числу в строке. После исчерпания чисел закройте свой конец
канала, чтобы показать партнёру, что здесь больше ничего не ожидается. Ваша программа должна работать (т. е. не должна завершаться) до завершения внешней программы; после такового напечатать
информацию об обстоятельствах её завершения (код завершения при
самостоятельном завершении, номер сигнала при завершении по сигналу). Ситуация с досрочным завершением внешней программы (когда цикл записи чисел в канал ещё крутится) должна быть обработана корректно.
5.28. Напишите программу, которая получает через аргументы
командной строки имя и аргументы д л я запуска внешней программы (как в предыдущей задаче). Запустите эту внешнюю программу,
перехватив её поток стандартного вывода и напечатав:
а) только первые 10 строк выведенной ею информации (при этом
внешней программе следует дать возможность доработать до конца, продолжая чтение из канала, но не выдавая прочитанное);
К части «объекты и услуги операционной системы»
69
b) только те из выданных ею строк, которые начинаются с пробела
или табуляции;
c) первые 20 символов каждой выданной ею строки (если строка
короче, печатать её целиком; символ перевода строки печатать в
любом случае);
d) первое слово каждой строки.
5.29. Модифицируйте решение задачи 5.27 так, чтобы стандартный вывод запускаемой внешней программы тоже перехватывался,
а после завершения работы на экран было выведено количество символов и количество строк, выданных внешней программой за время
работы.
5.30. Напишите программу, которая через аргументы командной
строки получает имена и аргументы для запуска д в у х внешних программ, разделённые параметром, состоящим из двух символов «;»,
как в задаче 5.26, и запускает эти программы на одновременное (параллельное) выполнение, причём на стандартный ввод второй программе подаётся:
a) к а ж д а я вторая строка из выданных первой программой;
b) текст, составленный из тех строк, выданных первой программой,
которые начинаются с пробела или табуляции;
c) первые 10 символов каждой строки, выданной первой программой
(если очередная строка короче 10 символов, её следует подать целиком; части разных строк следует разделять переводом строки).
5 . 3 1 ( s h e l l - V - s i m p l e ) . Возьмите за основу решение задачи 5.19,
или более позднюю её модификацию (например, полученную при решении задачи 5.24). Доработайте анализатор строки, добавив в этот
раз в качестве разделителя символ « I ». Остальную часть программы
модифицируйте так, чтобы этот символ рассматривался как обозначение конвейера. Пока можете считать, что больше одного такого
символа во введённой команде быть не может, т. е. ваш конвейер не
может состоять более чем из двух элементов; если такое ограничение кажется вам ненужным, можете сразу же решать задачу 5.32,
которая отличается только отсутствием ограничения на количество
элементов конвейера.
Если во введённой команде присутствует символ конвейера, следует сформировать две отдельные командные строки для первой команды и для второй; символ фонового режима по-прежнему допускается только последним во всей строке, что касается символов перенаправления ввода-вывода, то вы можете сами для себя решить,
удобнее вам допускать их непосредственно перед знаком конвейера
Задачи
70
или же тоже только в конце всей строки. В обоих случаях перенаправление ввода должно относиться к первому элементу конвейера,
перенаправление вывода — к последнему.
Программы, запускаемые в составе конвейера, д о л ж н ы работать
одновременно, то есть нельзя сначала дожидаться завершения первой из них, и только потом запускать вторую — объём буфера канала ограничен, и если первая программа будет выдавать достаточно
большой объём данных в свой стандартный вывод, а читать эти данные будет некому, ваша система процессов просто повиснет. Моментом завершения конвейера считается момент завершения последнего
из составляющих его процессов, причём «последнего» в хронологическом смысле; так, если второй элемент конвейера уже завершился, а
первый всё ещё работает, конвейер следует считать продолжающим
работу.
5.32* ( s h e l l - V ) . Переделайте решение задачи 5.31, убрав ограничение на количество элементов конвейера.
Терминал
5.33. Напишите программу, которая получает ровно один аргумент командной строки — имя текстового файла, первая строка которого содержит некий пароль, т. е. паролем считаются символы от начала файла до перевода строки, не включая его; программа должна
запросить у пользователя ввод пароля, перепрограммировать терминал так, чтобы вводимые символы не отображались на экране,
считать вводимый пользователем пароль и проверить, совпадает ли
он с находящимся в файле. Если пароль совпал — завершить работу
«успешно», ничего не печатая, если не совпал — выдать в диагностический поток сообщение i n c o r r e c t password и завершиться с кодом
неуспеха. Не забудьте сразу после ввода пароля вернуть настройки
терминала в исходное состояние!
В случае, если ввод идёт не с терминала (перенаправлен), откажитесь работать.
5.34*. Напишите программу, которая позволяет вводить текст
(строчка за строчкой) и записывать его в заданный файл, при этом в
каком-то другом файле имеется словарь слов (простое их перечисление по одному в строке); когда пользователь нажимает клавишу Tab,
программа проверяет вводимое слово и, если введённые буквы, относящиеся к текущему слову, представляют собой префикс какого-то
одного слова из словаря — дописывает это слово во вводимой строке,
как если бы пользователь ввёл его целиком; если на момент нажатия Tab введённые символы окажутся префиксом нескольких слов —
К части «объекты и услуги операционной системы»
71
следует поступить так же, как поступает, например, командный интерпретатор: перевести строку, показать все подходящие слова из
словаря, затем снова напечатать ту часть строки, которую пользователь уже ввёл, и позволить пользователю продолжить ввод.
Программа д о л ж н а получать два аргумента командной строки:
файл словаря и тот файл, куда будет записываться результат пользовательского ввода.
5.35*. Дополните решение предыдущей задачи возможностью редактировать вводимую строку с помощью стрелок влево и вправо,
Backspace, Del и (желательно) комбинации Ctrl-W для удаления последнего слова (до ближайшего пробельного символа).
5.36* ( s h e l l - e d i t ) . Возьмите какую-то из версий вашего командного интерпретатора (лучше всего, конечно, самую последнюю)
и оснастите её возможностями редактирования вводимой команды
(как в задаче 5.35) и дописывания имён команд и файлов (как в задаче 5.34, только без словаря). Во всех словах, кроме первого в строке,
пытайтесь «дописать» имя файла, найдя на диске соответствующий
файл или все подходящие ф а й л ы (напомним, имена файлов бывают
абсолютные и относительные, здесь это важно), а в первом слове,
если в нём пока нет ни одного слэша, следует дописывать имена исполняемых файлов из директорий, содержащихся в переменной PATH.
Эта задача не входит в основной набор этапов создания командного интерпретатора, поскольку всё остальное там можно сделать и без
этого, а трудоёмкость этой задачи довольно высока; но опыт, который вам даст решение этой задачи, определённо стоит потраченного
времени.
5 . 3 7 (daemon). Напишите программу-демона (daemon, см. §5.4.5).
Пусть ваш демон «просыпается» один раз в пять минут и дописывает
в некий файл (лучше всего — расположенный в директории /tmp,
запись туда разрешена всем) строку с указанием того, кто он такой,
каков его pid, сколько времени, по его сведениям, он уже работает и
сколько за время работы получил сигналов SIGUSR1; при получении
такого сигнала стоит аналогичную строку в тот же файл записать
немедленно, не дожидаясь очередных пяти минут.
5 . 3 8 (daemon-logging). Дополните решение предыдущей задачи
выдачей диагностических сообщений через системную журнализацию. Такое сообщение стоит выдать при старте, а также дублировать
журнальными сообщениями информацию, выводимую в файл.
5 . 3 9 ( s h e l l - V I ) . Дополните ваш командный интерпретатор (любой степени готовности, начиная от второго этапа, где просто выполнялись команды) правильно организованной работой с группами
Задачи
72
процессов. Процессы, запускаемые для исполнения очередной введённой команды, д о л ж н ы образовывать отдельную группу, новую
для каждой команды; если д л я выполнения одной команды нужно
породить больше одного процесса (например, при выполнении команды, содержащей конвейер), все эти процессы д о л ж н ы быть в одной
группе, отличной от группы, в которой находится сам командный интерпретатор, и от групп, в которых выполняются запущенные ранее
фоновые команды (у каждой из них, заметим, тоже должна быть
своя группа). При выполнении HeiftoHosoZ команды интерпретатор
должен на время её выполнения объявить её группу процессов текущей в сеансе, а после окончания её выполнения снова сделать текущей группой свою собственную.
Если всё сделать правильно, то, в частности, при нажатии Ctrl-C
во время работы программы, запущенной в ответ на очередную команду, будет убиваться только эта программа, а сам ваш командный
интерпретатор сигнала SIGINT не получит и продолжит работу. Собственно говоря, так и должно быть.
Дополнение
5.40* ( s h e l l - V I I ) . Возьмите командный интерпретатор в той версии, которая описана в задаче 5.32 (возможно, с дополнениями из
задач 5.39 и / и л и 5.36, они никоим образом не помешают). Дополните анализатор вводимой строки, чтобы он обрабатывал ещё пять
токенов-разделителей: «(», «)», «;», «II» и «&&». Реализуйте CSPSKU
команд: команды, связанные точкой с запятой, выполняются последовательно, сначала первая, потом вторая, вне зависимости от результатов; в связке && выполняется сначала первая команда, а вторая
выполняется лишь в случае, если первая завершилась успешно; связка II работает аналогично, только вторая команда выполняется при
неуспехе первой. Связки и скобки рассмотрены в §1.2.15; возможно,
есть смысл перечитать тот параграф, а ещё — поэкспериментировать
со связками в настоящем командном интерпретаторе, чтобы понять,
как выглядит их работа.
Круглые скобки реализуются порождением отдельного процесса,
который и выполнит (проинтерпретирует) все те команды и связки,
которые указаны в скобках; мы ведь помним, что процесс порождается как копия текущего, в данном случае — копия командного
интерпретатора? Этот дополнительный процесс (вместе со всеми теми, кого он будет порождать при выполнении содержимого скобок),
очевидно, имеет свои стандартные потоки, которые могут быть перенаправлены; как следствие, группа команд, заключённых в скобки,
может (как целое) выступать элементом конвейера, для неё может
К части «объекты и услуги операционной системы»
73
быть выполнено перенаправление стандартных потоков (в файлы и
из файлов), она может быть как правым, так и левым элементом
любой из связок.
Ещё работа над этой задачей — прекрасный повод превратить, наконец, амперсанд «&» из флажка, которым мы его сделали, в то, чем
он должен быть на самом деле — в связку, в которой левый элемент
выполняется как фоновый процесс, а правый — как обычный процесс
(нефоновый, завершения выполнения которого дожидаются).
К части 6 «сети и протоколы»
1Р-адреса
6.01. Что из этого н е я в л я е т с я валидной записью ip-адреса и
почему?
195.42.170.128
198.260.101.15
127.0.0.1
6.02. Определите, н е п о д г л я д ы в а я в т а б л и ц ы и п р о ч и е м а т е р и а л ы , как будет выглядеть маска подсети при указанной длине
префикса:
а) / 2 4
Ь) / 1 6
с) / 8
d) / 3 2
е) / 3 0
f) / 2 5
g) / 2 3
h) / 2 0
6.03. К а к а я
255.240.0.0?
длина
префикса
соответствует
маске
подсети
6.04. Перечислите (с указанием адреса сети и длины префикса)
все подсети, в которые входит ip-адрес 1 9 5 . 4 2 . 1 7 0 . 1 2 9 .
6.05. Напишите (на Си или даже на Паскале, здесь это неважно)
программу, которая решает предыдущую задачу для произвольного ip-адреса: принимает десятичную запись ip-адреса через аргумент
командной строки и печатает (через запятую, через пробел или просто на отдельных строках) все ip-подсети, в которые он входит.
П р о с т е й ш е е в з а и м о д е й с т в и е по сети
Задачи этого и п о с л е д у ю щ и х параграфов предполагают написание п р о г р а м м
на я з ы к е Си. Решение задач,
л а г а ю щ и х связь по к о м п ь ю т е р н о й сети, м о ж н о
на локальной
вера
машине,
127.0.0.1
указывая
или просто 0,
в качестве
предпо-
проверить
адреса
сер-
но если у вас есть хоть
какая-то в о з м о ж н о с т ь разнести в з а и м о д е й с т в у ю щ и е процессы по разным к о м п ь ю т е р а м — обязательно сделайте это.
К части «сети и протоколы»
75
Сложность программ при этом никак не изменится (им, собственно, всё равно, как работать), а вот наглядность происходящего (лично для вас!) сильно возрастёт, и скорее всего — вместе с вашей самооценкой.
6.06. Напишите две программы — для передачи дейтаграмм и
для их получения. Первая программа получает три аргумента командной строки: ip-адрес, номер порта и произвольную строку; указанную строку (без ограничивающего нуля!) она д о л ж н а отправить
в виде дейтаграммы на заданные адрес и порт. Вторая программа
получает через командную строку один аргумент — номер порта; на
этом порту (и на всех адресах, имеющихся на локальной машине)
она должна ожидать прихода дейтаграмм. Получив очередную дейтаграмму, программа должна напечатать адрес и порт отправителя,
а содержание дейтаграммы воспроизвести посимвольно, заменяя вопросительными знаками те символы, которые не могут быть напечатаны (не входят в диапазон 32-126 и не являются ни переводом
строки, ни табуляцией).
6.07. Напишите простой UDP-сервер — программу, которая подсчитывает количество полученных дейтаграмм и их общий объём, и
в ответ на каждую полученную дейтаграмму отправляет (также в
виде дейтаграммы) текстовое представление обоих счётчиков. Д л я
проверки работоспособности вашей программы придётся написать
также клиент — программу, которая отправляет на заданный адрес/порт дейтаграмму заданной длины, дожидается ответа и распечатывает его, если же ответ не поступает в течение 15 секунд (или
какого-то другого интервала времени) — сообщает об этом и завершается.
Обе программы д о л ж н ы всю необходимую информацию получать
через аргументы командной строки; программа-сервер д о л ж н а после
запуска «демонизироваться» (см. §5.4.5).
6.08. Напишите простой TCP-сервер, который сразу после получения очередного запроса на соединение принимает его, отправляет
клиенту (в текстовом виде) текущие дату и время, а также ip-адрес и
порт клиента. Это, заметим, имеет самый прямой смысл: если клиент находится за МАТ'ом, он может не знать, с какого — реального,
а не «внутреннего» — ip-адреса он работает. Сразу после отправки
данных сервер разрывает соединение.
Клиентскую программу писать не обязательно, можно воспользоваться программой t e l n e t ; если вдруг выяснится, что в вашей системе её нет — установите её, она ещё не раз потребуется.
В этой задаче можно не беспокоиться относительно проблемы очерёдности действий: вся передаваемая вашим сервером информация
Задачи
76
«уляжется» в один ip-пакет, сам он ж д а т ь данных от клиента не
будет, так что никаких блокировок не произойдёт и отвалиться по
тайм-ауту никто не успеет. Учтите, что этот случай — исключение,
а не правило.
Системный вызов select
Задачи этого параграфа не имеют прямого отношения к
компьютерным сетям; они призваны помочь понять, как работает и для чего нужен вызов s e l e c t , без которого при
создании сетевых программ придётся туго.
6.09. Напишите программу, которая задаёт пользователю вопрос «What i s your name, p l e a s e ? » и, дождавшись ответа, выдаёт вежливое «Nice t o meet you, dear (имя)1.»; если пользователь
не вводит имя в течение 15 секунд, программа заявляет «Sorry, I'm
t e r r i b l y busy. » и завершается. Д л я отслеживания времени используйте вызов s e l e c t .
6.10. Вернитесь к задаче 5.23 и напишите программу, удовлетворяющую её условиям, без применения сигнала SIGALRM. Д л я отслеживания интервала используйте s e l e c t .
6.11. Напишите программу, которая получает через аргументы
командной строки имена двух файлов (предполагается, что это именованные каналы, т.е. ф а й л ы типа FIFO), первый из них использует
для приёма информации, и всё, что принято, тут же выводит в свой
стандартный вывод, а во второй ф а й л передаёт то, что будет введено
через стандартный ввод.
Если всё сделать правильно, можно будет с помощью m k f i f o создать два файла нужного типа, например, f 1 и f 2 , а затем в разных терминалах запустить два экземпляра вашей программы, указав
им созданные каналы «крест-накрест» — например, . / p r o g f 1 f 2 и
. / p r o g f 2 f1; получится «чат»: всё, что набирается на клавиатуре в одном окошке терминала, после нажатия Enter появляется во
втором, и наоборот. Не забудьте обработать конец файла на обоих
потоках ввода: если «кончился» стандартный ввод, можно просто
выйти, а если канал — желательно сначала сообщить пользователю,
что наш партнёр по чату нас покинул.
В этой задаче есть одна хитрость; если с ходу ничего не работает, прочитайте указания к задаче на стр. 139, но лучше сначала
попробуйте сами догадаться, что происходит; если воспользоваться
дебаггером и выяснить, где всё повисло, а ещё (до или после) перечитать п а р а г р а ф про каналы (§5.3.15), то понять, что к чему, будет
не так у ж сложно.
К части «сети и протоколы»
77
ТСР-сервера
Задачи этого параграфа предполагают использование вызова s e l e c t . Условия некоторых задач позволяют применить
решение с обслуживающими процессами, но так делать следует разве что с ознакомительными целями; после обязательно перепишите ваши программы через мультиплексирование ввода-ввода.
В роли клиентской программы можно использовать утилиту
t e l n e t , если условиями задачи не подразумевается что-то
другое.
6.12. Напишите TCP-сервер, который принимает от каждого клиента произвольный текст и отвечает на к а ж д у ю присланную строку
отправкой сообщения «Ок». Единственное ограничение на количество
обслуживаемых клиентов может быть обусловлено предельным числом одновременно открытых в процессе дескрипторов, сама ваша
программа никаких ограничений вводить не должна.
6.13. Усовершенствуйте программу, написанную при решении
предыдущей задачи: снабдите ваш сервер одной на всех клиентов целочисленной переменной, изначально равной нулю, а пришедшие от
клиента строки анализируйте. Если полученная от клиента строка
содержит слово «ир» (возможно, с пробельными символами спереди и сзади), значение переменной увеличьте на единицу, если слово
«down» — наоборот, уменьшите на единицу; клиенту в обоих случаях
отправьте сообщение «Ок». Если полученная строка содержит слово
«show» — отправьте клиенту строку текста, содержащую десятичное представление текущего значения переменной. Если прочитана
строка, в которой есть непробельные символы, но она после отбрасывания пробелов совпадает ни с одной из трёх команд ир, down
и show, отправьте клиенту сообщение об ошибке, что-нибудь вроде
«textttunknown command». Обязательно проверьте, что сервер ведёт
себя корректно при массовых подключениях и отключениях клиентов.
6.14. Придумайте подходящий протокол и напишите серверную
и клиентскую программы, реализующие функциональность BBS
(bulletin board system,). При старте программа должна через аргументы командной строки получить имя рабочей директории; в ней
д о л ж н ы содержаться файл заставки (текстовый), файл учётных записей (имён и паролей пользователей), а также файлы, доступные
пользователям для скачивания, и к каждому из них — служебный
78
Задачи
файл, содержащий описание и права доступа (кому из пользователей этот файл можно скачивать; обязательно нужно предусмотреть
вариант «всем», в том числе незарегистрированным).
Учётные записи пользователей должно быть возможно пометить
особым образом; такая отметка должна позволять пользователю не
только скачивать файлы, но и размещать на BBS новые файлы, указав к ним описание и права доступа. Кроме того, стоит предусмотреть «привилегированных» пользователей, которые могут удалять
файлы, изменять их описания и права, а также добавлять новых
пользователей.
Клиентская программа после установления связи д о л ж н а продемонстрировать пользователю содержимое заставки, позволить ввести логин и пароль (либо при желании продолжить работу как незарегистрированный пользователь), просмотреть описания к доступным для скачивания файлам и, конечно, скачать любой из них, а
также (при наличии полномочий) закачать новые файлы, изменить
описания и права к имеющимся файлам, удалить файлы. Очень желательно предусмотреть возможность оставить сообщение для владельца системы.
6.15*. Напишите серверную программу, принимающую электронную почту по протоколу SMTP и складывающую все принятые письма в виде файлов в указанную (например, через параметр командной строки) директорию. Д л я проверки вашей программы возьмите
какой-нибудь существующий клиент электронной почты, такой как
Sylpheed, Thunderbird или любой другой, и настройте его на отправку почты через smtp-сервер, расположенный на локальной машине
(ip-адрес 1 2 7 . 0 . 0 . 1 ) и порт, соответствующий порту, используемому вашей программой. Отправьте несколько писем и убедитесь, что
ваша программа их получила и сложила куда следует.
Обязательно убедитесь, что ваша программа способна без ограничений одновременно обслуживать несколько сеансов работы с клиентами. Д л я этого, запустив программу, подключитесь к ней из
нескольких терминальных окон с помощью утилиты t e l n e t , в каждом из подключений начните сеанс взаимодействия, бросьте эти сеансы на разных стадиях (не завершая их), после чего попробуйте
отправить почту из вашего клиента; если всё в порядке, вернитесь к
брошенным сеансам и доведите к а ж д ы й из них до отправки письма.
6.16. Напишите серверную программу, отдающую клиентам заданный файл в формате HTML по протоколу h t t p 1.1; для проверки работы программы воспользуйтесь браузером.
6.17*. Напишите сервер, позволяющий нескольким людям (пользователям) сыграть друг с другом в хорошо известного подкидного
К части «сети и протоколы»
79
дурачка, используя текстовый режим. Чтобы играть могло больше
людей, используйте «полную» колоду (включающую карты каждой
масти от двойки до туза, всего 52 карты; джокеры в игре в дурачка
задействовать проблематично); тогда в игре могут участвовать до
восьми человек. Сервер должен начинать игру, когда к нему присоединилось не меньше двух игроков и один из них н а ж а л Enter (прислал пустую строку), либо к игре присоединилось восемь человек —
в этом случае нажатия Enter ж д а т ь уже бессмысленно.
Сервер должен «перетасовать» колоду, т. е. расположить её карты
в случайно выбранном порядке, «сдать» каждому игроку по шесть
карт, одну из оставшихся карт «открыть», показав, какая масть в
этой игре будет козырной. Д л я обозначения старшинства карт можно использовать ц и ф р ы от 2 до 9, десятку так и обозначать «10»,
вальта, даму, короля и туза — латинскими буквами J, Q, К и A (jack,
queen, king, ace); для обозначения мастей можно воспользоваться,
например, символами #, % ~ v или какими-то ещё (здесь можно проявить фантазию).
Игрок должен видеть «состояние стола» и «свою руку». Пока не
начался очередной ход, «состояние стола» представляет собой количество карт у каждого из остальных игроков, карту, показывающую
козырную масть, и количество оставшихся карт в колоде; «свою руку» — список карт, имеющихся в настоящий момент у игрока — лучше показать, снабдив к а ж д у ю карту меткой, причём, чтобы не путались между собой «номера» карт и их достоинства, правильнее будет
использовать в роли меток строчные латинские буквы. Вывести всё
это можно в две строки, например
< 6 > < 6 > < 6 >
a : 10"
Ъ: J #
с : 2%
J"
d:
Qv
e:
7"
f:
[ 2 7 ]
9#
будет означать, что у игрока есть три противника, у каждого из
них в руках по шесть карт, козыря показывает валет пик, в колоде (прикупе) ещё 27 карт, а на руке у игрока десятка пик, валет
бубей, двойка крестей, дама червей, семёрка пик и девятка бубей.
Ситуация, когда латинских букв не хватит для нумерации карт на
руке, маловероятна, но теоретически возможна; в этом случае следует, например, привлечь заглавные латинские буквы (это вроде бы
не очень хорошо, поскольку некоторые из них игрок может перепутать со старшинством карт, но ситуация эта настолько редка, что на
мелкие неудобства при её возникновении можно не обращать внимания). Тому игроку, чей сейчас ход, следует вывести приглашение
и (желательно) список возможных ходов; например, к вышеприведённым строчкам, если сейчас ход этого игрока, следует добавить
строку
Задачи
80
abcdef >
После начала хода к «состоянию стола» добавляются сыгранные на
этом ходу карты, выглядеть всё вместе может, например, так:
< 4 > < 6 > < 6 >
2% e
J%
e
Q#
J#
a : 10"
b>
b:
Qv
c: 7"
J"
d:
[ 2 7 ]
9#
Здесь игрок зашёл с двойки крестей, партнёр покрыл её вальтом,
атакующий подбросил вальта бубей, валет был покрыт дамой, теперь
атакующему выдано приглашение, показывающее, что он может подбросить ещё даму пик. Игрок может набрать букву b и нажать Enter,
либо просто нажать Enter, отказавшись от дальнейшего подбрасывания.
Приглашение для «отбивающегося» игрока должно выглядеть
как-то иначе, например, можно перечислить метки тех карт его руки,
которыми он может покрыть последнюю сыгранную карту, и к этому добавить какие-то ещё символы; получится, например, «be =>».
Все игроки, которые на текущем состоянии хода могут «подбросить»
отбивающемуся ещё карты, д о л ж н ы своевременно получить соответствующее приглашение. Отбивающийся игрок может отказаться от
дальнейшей защиты, даже если у него есть подходящие карты — для
этого он отправляет пустую строку (нажимает Enter). В этом случае
все карты, сыгранные на данном ходу, передаются ему на руку. Если
у отбивающегося нет подходящих карт для обороны, такое завершение хода должно происходить автоматически. Если у остальных
игроков имеются карты, подходящие для подбрасывания, и пока ещё
не достигнут лимит на количество карт при атаке (этот лимит равен числу карт на руке у отбивающегося в на момент начала хода),
им должно быть выдано приглашение с указанием подходящих карт
(«добавки»); ход считается завершённым, когда ни у кого нет больше
подходящих карт или все игроки отказались от «добавления», нажав
Enter.
При любом изменении в игре все игроки д о л ж н ы получить обновлённую «картинку», проще всего это сделать, передав 25 символов
перевода строки. что при традиционной высоте терминала приведёт
к очистке экрана, после чего передать строки состояния стола, руки
и приглашения.
К части «сети и протоколы»
81
В наше время при игре в подкидного дурака обычно устанавливается очерёдность «подкидывания», но классические правила этой игры такой очерёдности не подразумевали: действовало правило «кто
успел, тот молодец». Именно такая реализация, когда игроки, имеющие подходящие карты, могут посоревноваться в скорости реакции,
интереснее в качестве этюда. Проблема разве что в том, что наличие на столе одновременно нескольких непокрытых карт приводит к
некоторой неопределённости: какую из них отбивающийся пытается
покрыть очередным своим ходом? Проще всего решить эту проблему,
не допуская на стол больше одной непокрытой карты; сервер может
принять и запомнить, какие карты игроки пытаются подбросить, но
показывать их на столе по одной, либо показывать все, но игроку
предлагать крыть в каждый момент только одну из них.
6.18*. Усовершенствуйте свой сервер для игры в дурачка так,
чтобы он позволял одновременно проводить несколько игр, а пользователей и их результаты запоминал. При входе на сервер у пользователя следует спросить его имя; если такого пользователя пока
нет, спросить, желает ли пользователь завести новую учётную запись и если да, то запросить пароль; если пользователь с таким именем уже известен — спросить и проверить пароль. После успешного
входа на сервер пользователь оказывается в общем чате, где можно
договориться об игре с другими игроками, создать игру или присоединиться к созданной, но ещё не начавшейся игре. В режиме игры
теперь должны показываться имена игроков; следует предусмотреть
возможность чата между игроками в ходе игры.
6.19*. Придумайте свою текстовую многопользовательскую игру
и реализуйте сервер для неё.
6.20*. Реализуйте сервер для многопользовательских игр
(см. условия задачи 6.18), позволяющий одновременно проводить игры различных видов.
К части 7 «параллельные
программы и разделяемые
данные»
7.01. В неправильно спроектированной системе имеется сегмент
разделяемой памяти, в котором содержится массив целых чисел (как
положительных, так и отрицательных), общая сумма которых равна
нулю. Некая программа из числа входящих в систему начала подсчёт
суммы элементов массива. В это же самое время другая программа
каким-то неизвестным способом выбрала три элемента массива, первый из них уменьшила на 100, второй уменьшила на 200, третий
увеличила на 300, так что общая сумма элементов осталась нулевой.
Какими могут оказаться результаты подсчёта, выполняемогопервой
программой, если известно, что каждая отдельно взятая операция
извлечения элемента из массива и записи элемента в массив выполняется атомарно, но никакого взаимоисключения в обеих работающих программах не предусмотрено? Перечислите все возможные варианты. Номера элементов, выбранных второй программой, а также
конкретная последовательность, в которой первая программа суммирует элементы, неизвестны (могут быть любыми).
7.02. В разделяемой памяти расположен массив из трёх элементов типа int, причём исходно первый элемент равен 100, второй —
200 , третий — 300 . Есть функция, принимающая параметрами адреса двух переменных, вычисляющая их среднее арифметическое и
записывающая результат в обе переменные:
void set_average(int
*х,
int
K
i n t z = ( * x 4 *y) /
*x = z ;
*У = z ;
2;
*у)
К части «параллельные программы и разделяемые данные»
83
M
Эту функцию вызвали в параллельных процессах, причём в одном —
для первого и второго элементов массива, а в другом — для второго
и третьего. Каковы могут быть значения элементов после этого, если
никаких средств синхронизации и взаимоисключения не предусмотрено, но при этом извлечение значения из отдельно взятого элемента
массива, а также занесение в него нового значения работают атомарно? Перечислите все возможные варианты.
7.03. В §7.1.3 приведён алгоритм
Петерсона,
позволяющий
выполнить корректное взаимоисключение для двух процессов с использованием переменной who_waits и массива флагов i n t e r e s t e d
из двух элементов:
void enter_section() {
i n t e r e s t e d [ 0 ] = TRUE;
who_waits = 0;
w h i l e ( w h o _ w a i t s = = 0 66
i n t e r e s t e d [ 1 ] ) {}
M
void leave_section()
K interested[0]
void enter_section() {
i n t e r e s t e d [ 1 ] = TRUE;
who_waits = 1;
w h i l e ( w h o _ w a i t s = = 1 66
i n t e r e s t e d [ 0 ] ) {}
M
void
= FALSE; M
leave_section()
K interested[1]
= FALSE; M
Останется ли алгоритм корректным, если в функциях e n t e r _ s e c t i o n
поменять местами первые две строки, вот так:
void enter_section()
K
void enter_section() K
who_waits = 0;
interested[0]
who_waits = 1;
= TRUE;
interested[1]
w h i l e ( w h o _ w a i t s = = 0 66
interested[1])
M
= TRUE;
while(who_waits==1
KM
66
i n t e r e s t e d [ 0 ] ) KM
M
— или он «сломается»? Ответ обоснуйте.
7.04. Напишите программу, соответствующую условиям задачи
6.13, без применения вызова s e l e c t — вместо этого в главном треде выполняйте вызов accept, а для обслуживания каждого нового
подключившегося клиента порождайте дополнительный тред. Не забывайте про взаимное исключение при обращении к любым данным,
доступным в разных тредах! Сравните объём и прочие характеристики этого решения с решением в событийно-ориентированном стиле
(на вызове s e l e c t ) .
К части 8 «ядро системы:
взгляд за кулисы»
8.01. Дана программа:
int
main()
K
double d;
scanf("%lf",
d = cos(d);
printf("%f",
r e t u r n 0;
&d);
d);
M
Предположим, мы используем такую версию компилятора и библиотеки, что полученный исполняемый файл использует абсолютный
минимум системных вызовов. Сколько системных вызовов выполнит
данная программа, и какие это будут системные вызовы?
8.02. Программа t r u e выглядит так:
i n t main()
{ r e t u r n 0; M
Предположим, мы используем такую версию компилятора и библиотеки, что полученный исполняемый файл использует абсолютный
минимум системных вызовов. Будет ли данная программа выполнять системные вызовы, и если да, то какие?
8.03. Среди библиотечных функций p r i n t f , scanf, f g e t c , fopen,
f c l o s e , read, malloc, f r e e , k i l l , s i g n a l , e x i t , g e t p i d есть ровно одна, которая не является системным вызовом и никогда не обращается
к системным вызовам. К а к а я это функция?
8.04. Среди библиотечных функций sin, a t o i , s p r i n t f , s s c a n f ,
strcpy, strcmp, malloc, f r e e , rand ни одна не является системным
К части «ядро системы: взгляд за кулисы»
85
вызовом, но есть ровно одна, которая может обратиться к системному вызову. Какая это функция?
8.05. На некотором компьютере реализована страничная модель
виртуальной памяти с двумя уровнями страничных таблиц. Ячейки
памяти восьмибитные, разрядность адреса составляет 32 бита, таблица первого уровня содержит 512 записей, таблицы второго уровня —
по 4096 записей каждая. Каков размер страницы?
8.06. На некотором компьютере реализована страничная модель
виртуальной памяти с двумя уровнями страничных таблиц. Ячейки
памяти восьмибитные, разрядность указателей составляет 64 бита,
но из них используется только 40, остальные зарезервированы; таблица первого уровня содержит 8192 записи, таблицы второго уровня — по 4096 записей каждая. Каков размер страницы?
8.07. На некотором компьютере реализована страничная модель
виртуальной памяти с тремя уровнями страничных таблиц. Ячейки
памяти восьмибитные, разрядность указателей составляет 32 бита;
таблицы каждого из трёх уровней содержат по 128 записей. Каков
размер страницы?
К части 9 «парадигмы в
мышлении программиста»
Рекурсия
9.01. Дан целочисленный массив (адрес его начала и длина); нужно определить, чему равен его максимальный элемент. Сформулируйте алгоритм решения этой задачи в терминах рекурсивного мышления (рекурсии как парадигмы), т. е. без явного указания последовательности действий. Напишите на Си функцию, реализующую этот
алгоритм и имеющую следующий профиль:
int
intvecmax(const
int
*arr,
int
len);
Обратите внимание, что при правильном решении функция не должна использовать циклы и модифицирующие («разрушающие») операции (присваивания и инкременты/декременты).
Обязательно сформулируйте ответы на следующие вопросы:
• какой случай используется в роли базиса рекурсии?
• чем (конкретно) случай, решаемый с помощью рекурсивного
вызова, проще, нежели исходный случай?
9.02. Является ли остаточной рекурсия в вашем решении предыдущей задачи? Почему? Перепишите решение так, чтобы рекурсия
стала остаточной. Можно ли теперь сформулировать принцип её работы в рамках рекурсии как парадигмы?
9.03. В целочисленном массиве длиной не менее двух элементов
нужно найти два наибольших значения его элементов; решение требуется в виде функции с профилем
void intvec2max(const
int
*arr,
int
len,
int
res[2]);
К части «парадигмы в мышлении программиста»
87
Предполагается, что функция запишет найденные значения в элементы массива res: наибольшее — в элемент r e s [ 0 ] , второе по величине — в элемент r e s [ 1 ] . Напишите такую функцию (возможно, с использованием вспомогательных функций) б е з п р и м е н е н и я
ц и к л о в ; присваивания используйте только для занесения значений
в res.
Является ли получившаяся у вас рекурсия остаточной? Если нет,
исправьте ваш код так, чтобы рекурсия стала остаточной, в этой
задаче это несложно.
9.04. Д а н массив беззнаковых целых; требуется определить максимальное значение его элементов и все элементы, имеющие это значение (в общем случае их больше одного) обнулить. Предложите решение этой задачи, не использующее циклы.
9.05. Можно ли в решении предыдущей задачи обойтись также и
без присваиваний, за исключением присваивания нулей элементам, в
которых находилось максимальное значение?
9.06. В стандартной библиотеке языка Си есть функция s t r s t r ,
позволяющая найти подстроку в строке (см. §4.10.2). Напишите на
Си функцию, делающую то же самое, не применяя циклов и разрушающих операций.
В качестве дополнительного (факультативного) упражнения попробуйте обойтись без вспомогательных функций.
9.07*. В §§2.11.3, 3.3.9, 4.3.22 и 9.2.4 разобраны решения задачи
о сопоставлении строки с образцом — на Паскале, на языке ассемблера и на Си. Эти решения друг от друга несколько отличаются по
структуре (в том числе слегка различаются между собой два решения на Си), но их объединяет главное: все они используют рекурсию.
Попробуйте решить эту задачу на языке Си без применения рекурсии.
9.08. Требуется программа, принимающая на вход (параметром
командной строки) целое число N и печатающее N первых чисел Фибоначчи. Напишите такую программу без применения разрушающих
операций.
Работа в явных состояниях
В задачах этого параграфа под «реализацией автомата» понимается создание трёх функций: первая из них выделяет
область памяти для хранения состояния автомата (скорее
всего, в виде какой-то структуры, но это не обязательно),
приводит условный автомат в исходное состояние (инициализирует выделенную область памяти) и возвращает адрес
88
Задачи
созданного объекта; вторая функция получает адрес объекта автомата через один из параметров и выполняет один
шаг автомата, выдав при этом нужную информацию (если информация скалярная5 её можно вернуть как значение
функции5 в противном случае придётся использовать выходной параметр — адрес, куда нужно записать полученную
из автомата информацию); третья функция получает адрес объекта автомата и уничтожает его5 освобождая память
(в простейшем случае — вызывает f r e e ) .
9.09. Реализуйте автомат, последовательно выдающий числа Фибоначчи.
9.10. Реализуйте автомат, который на каждом шаге выдаёт очередной элемент треугольника Паскаля, а также его «индексы» —
номер строки и номер элемента в этой строке, начиная с нулей. Иначе говоря, автомат на каждом шаге должен генерировать очередные
п, к и С£: (0,0,1), (1, 0,1), (1,1,1), (2,0,1), (2,1, 2), (2, 2,1), (3,0,1),
(3,1, 3), (3, 2, 3), (3, 3 , 1 ) . . . На всякий случай напомним, что при вычислении Сп не следует использовать никаких умножений, треугольник Паскаля как раз и предназначен для вычисления членов этой
последовательности с использованием только операции сложения.
9.11. Перестановкой
из N элементов называется некий упорядоченный набор, составленный из чисел 1, 2,..., N, в котором каждое
число встречается ровно один раз. Так, перестановок из двух элементов существует две ({1, 2} и {2,1}), перестановок из трёх элементов —
шесть ({1, 2, 3}, {1, 3, 2}, {2,1, 3}, {2, 3,1}, {3,1, 2}, {3, 2,1}), а в общем
случае перестановок из N элементов существует N! (эн-факториал).
Перестановки подробно обсуждаются в § 1.3.1, хотя там они формально не вводятся в качестве кортежей из чисел, вместо этого используются занумерованные бильярдные шарики.
Реализуйте автомат, который при его создании получает число
N (то есть функция создания автомата имеет целочисленный параметр), а на каждом шаге выдаёт очередную перестановку из N
элементов, для чего функции, которая реализует шаг автомата, передаётся адрес начала массива из N целых. После исчерпания перестановок, т. е. после того, как функция шага автомата была вызвана
N! раз, при последующих вызовах она д о л ж н а заполнять переданный массив нулями, чтобы показать, что больше перестановок нет.
К части 10 «язык СиН—Ь, ООП
и АТД»
Абстрактные типы данных
Следующие задачи построены в предположении, что вы у ж е
п р о ч и т а л и главу 10.3.
10.01. Дана функция main:
int
main()
K
A f i r s t = 1;
A second(10);
p r i n t f ( " f i r s t : %d%d\n", f i r s t [ 1 0 0 ] , f i r s t [ 2 0 0 ] ) ;
p r i n t f ( " s e c o n d : %d % d \ n " , s e c o n d [ 1 0 0 ] , s e c o n d [ 2 0 0 ] ) ;
r e t u r n 0;
M
Опишите класс A, объекты которого ведут себя как неизменяемые
массивы целых чисел, причём значение каждого элемента больше
значения его индекса на число N , которое передаётся как параметр
конструктора. Так, данная функция main должна напечатать:
f i r s t : 101 2 0 1
s e c o n d : 110 210
10.02. Дана функция main:
int
main()
K
В f i r s t ( 1 ) , second = 2;
f i r s t += 10; s e c o n d += 1000;
p r i n t f ( " % d %d\n", f i r s t . G e t ( ) ,
r e t u r n 0;
M
second.Get());
Задачи
90
Опишите класс В таким образом, чтобы программа с такой функцией
main компилировалась (без предупреждений) и работала, печатая
строку «11 1002».
10.03. Дана функция main:
i n t main() {
D x;
D y(x);
D z = y;
printf("/d /d /d\n",
r e t u r n 0;
x.Get(),
y.Get(),
z.Get());
M
Опишите класс D так, чтобы эта функция компилировалась без предупреждений и работала, печатая строку «0 1 2».
10.04. Опишите класс М, объекты которого представляют целочисленную матрицу 3 x 3 с индексацией от 1 до 3, причём для задания
позиции используются объекты другого класса, называемого I. Реализуйте операцию сложения матриц, а операцию индексирования перегрузите так, чтобы можно было выполнять как присваивания, так
и извлечения элементов матрицы. При создании матрицы делайте её
единичной (единицы на главной диагонали, остальные нули). Ваши
классы д о л ж н ы работать со следующим текстом функции mainO:
int
main()
K
M ml;
printf("/d
M m2;
ml[I(2,3)]
m2[I(2,3)]
M m3(ml 4
printf("/d
r e t u r n 0;
/d /d\n",
ml[I(l,l)],
ml[I(2,2)],
ml[I(2,3)]);
= 7;
= 350;
m2);
/d /d\n",
m3[I(l,l)],
m3[I(2,2)],
m3[I(2,3)]);
M
— причём должно печататься
l l 0
2 2 357
Использовать глобальные переменные и статические поля в этой задаче не следует.
10.05*. Усовершенствуйте класс М, описанный в предыдущей задаче, устранив потребность в объектах класса I; двойной индекс должен записываться обычным для Си и СиН—Н способом, через двойное применение операции индексирования. Текст функции main после этого должен стать таким:
К части «язык С и + + , ООП и АТД»
i n t main() {
М ml;
p r i n t f ( " / d / d */,d\n", m l [ l ] [ l ] ,
М m2;
m l [ 2 ] [ 3 ] = 7;
m2[2][3] = 350;
М m3(ml 4 m 2 ) ;
p r i n t f ( " / d / d /.d\n", m 3 [ l ] [ l ] ,
r e t u r n 0;
91
ml[2][2],
ml[2][3]);
m3[2][2],
m3[2][3]);
M
10.06. Опишите класс E, объект которого представляет собой
«бесконечную» целочисленнцю матрицу, элементы которой на главной диагонали равны нулю, а остальные элементы равны разности
индексов (т.е., например, элемент e [ 3 ] [ 2 0 0 ] равен -197, а элемент
e [ 1 2 9 0 5 ] [ 1 0 5 ] равен 12800). Так, следующая функция main():
i n t main() {
Е e;
p r i n t f ( " / d / d °/d\n",
p r i n t f ( " / d / d °/d\n",
r e t u r n 0;
e[0][0], e[l00][l00],
e[l500][7], e[7][55],
e[-l0][-l0]);
e[-8][-l6]);
M
должна компилироваться, работать и печатать
0 0 0
l493 -48 8
Естественно, в этой задаче не следует использовать глобальные переменные и статические поля; кроме того, здесь не нужно описывать
какие-либо настоящие массивы (операции [] д о л ж н ы применяться
только к объектам ваших классов).
10.07. Что напечатает следующая программа?
#include
class I K
int i;
public:
I() : i(6) K printf("sun\n"); M
I ( i n t a) : i ( a ) { p r i n t f ( " v e n u s °/d\n", i ) ; M
I ( c o n s t I& o t h e r ) : i ( o t h e r . i )
K p r i n t f ( " e a r t h °/d\n", i ) ; M
~I() K printf("moon\n"); M
int Get() K r e t u r n i ; M
v o i d o p e r a t o r + = ( c o n s t I& o p ) K i + = o p . i ; M
M;
92
Задачи
void f ( I 6 x,
I у)
K
у += 1 0 0 0 ;
x += у ;
M
int
main()
K
I i1;
I i2(50);
i 2 += 8 0 0 ;
f(i1, i2);
printf("/d /d\n",
r e t u r n 0;
i1.Get(),
i2.Get());
M
10.08. Напомним, что рациональное
число — это несократимая дробь вида ^ , где п — целое, т — натуральное. Опишите
класс Rational, реализующий понятие рационального числа, воспользовавшись числами типа long long для представления числителя и знаменателя дроби; требование о несократимости дроби пока
проигнорируйте. Снабдите класс четырьмя основными действиями
арифметики, соответствующими им операциями присваивания (+=,
-=, *=, /=), функциями преобразования к числу типа double и к целому (здесь желательны две функции: через отбрасывание дробной
части и через округление к ближайшему). Будет полезно предусмотреть метод (или два) д л я извлечения из объекта текущих значений
числителя и знаменателя.
Напишите набор тестов, демонстрирующий корректность работы
вашего класса (всех его методов).
10.09. Возможности класса, созданного при решении предыдущей задачи, несколько ограничены: все арифметические операции
имеют тенденцию наращивать значение знаменателя — как напрямую при выполнении умножения и деления, так и через приведение
к общему знаменателю, которое необходимо при сложениях и вычитаниях; рано или поздно (и скорее рано, чем поздно) значение знаменателя превышает возможности разрядности даже для long long.
Напишите тесты, демонстрирующие ограничения нехватки разрядности; желательно при этом найти точные границы возможностей
подобно тому, как это сделано в §2.2.5.
Воспользовавшись алгоритмом Евклида, напишите функцию,
отыскивающую наибольший общий делитель для двух чисел типа
long long; обратите внимание, что наибольший общий делитель всегда по определению положителен и не меняется при любой смене
знаков исходных чисел. Поскольку эта функция потребуется вам в
К части «язык С и + + , ООП и АТД»
93
классе Rational, она д о л ж н а быть его приватным методом; но так
как объект типа Rational ей для работы не нужен, следует сделать
её статической.
Воспользовавшись этой функцией, усовершенствуйте ваши арифметические операции так, чтобы, во-первых, результат их работы всегда представлял собой несократимую дробь; во-вторых, чтобы «лишние» множители по возможности изымались из чисел до выполнения
других операций: так, при перемножении двух дробей ^ • | следует
не только предварительно сократить обе дроби, если этого ещё не
сделано, но и проверить, нет ли нетривиального (т. е. отличного от
единицы) общего делителя в парах (п, q) и (т,р).
С помощью ранее написанных тестов убедитесь, что теперь возможности вашего класса стали шире; напишите тесты, демонстрирующие границы возможностей новой реализации, и сравните эти
границы со старыми.
Наследование
10.10. Что напечатает следующая программа?
#include
class А {
int i;
public:
A ( i n t x) { i = x ; p r i n t f ( " f i r s t \ n " ) ; }
v i r t u a l ~А() { p r i n t f ( " s e c o n d \ n " ) ; }
int f ( ) const { r e t u r n i 4 g() 4 h ( ) ; }
v i r t u a l int g() const { r e t u r n i ; }
i n t h() const { r e t u r n 6; }
M;
class В : public А {
public:
В() : А(0) { p r i n t f ( " t h i r d \ n " ) ; }
~В() { p r i n t f ( " f o u r t h \ n " ) ; }
i n t f ( ) c o n s t { r e t u r n g ( ) - 5; M
v i r t u a l i n t g() const { r e t u r n 8; M
i n t h ( ) c o n s t { r e t u r n 1; M
M;
i n t main() {
В b;
А* p = &b;
p r i n t f ( " r e s u l t = ('/.d ; 1 / . d ) \ n " , p - > f ( ) ,
r e t u r n 0;
M
b.f());
94
Задачи
10.11. Опишите абстрактный класс Body, представляющий некое
абстрактное физическое тело, для которого не задана форма, но
задана плотность составляющего его вещества. Плотность задаётся полем типа double. Предусмотрите в классе ч и с т о в и р т у а л ь н у ю функцию VolumeO, задающую объём тела, и простую функцию
MassO, вычисляющую массу как произведение объёма и плотности.
Унаследуйте от класса Body класс Cube, представляющий кубик, сделанный из однородного вещества и задаваемый длиной ребра
(первый параметр конструктора) и плотностью вещества (второй параметр конструктора), а также класс Tetrahedron, представляющий
правильный тетраэдр, сделанный из однородного вещества и задаваемый длиной ребра и плотностью. Напомним, что объём правильного тетраэдра составляет
а 3 . Д л я задания значения \ / 2 можно
воспользоваться константой M_SQRT2, которая определена в заголовочном файле math.h.
В результате следующая функция main():
i n t main() {
c o n s t Body * p , * q , * r ;
Cube a ( 2 , l 0 ) , b ( 5 , 0 . l ) ;
Tetrahedron t ( 6 , 2.5);
p = &a; q = &b; r = & t ;
printf("Volumes: /3.3lf /3.3lf / 3 . 3 l f \ n " ,
p->Volume(), q->Volume(), r->Volume());
printf("Weights: /3.3lf /3.3lf /3.3lf\n",
p->Mass(), q->Mass(), r->Mass());
r e t u r n 0;
M
должна откомпилироваться без ошибок и предупреждений, отработать и выдать
Volumes:
Weights:
8.000 l25.000
80.000 l2.500
25.456
63.640
Проверьте, что ваша реализация соответствует следующим условиям:
• все поля находятся в закрытой ( p r i v a t e ) части класса, открытыми и защищёнными могут быть только функции-члены;
• директива f r i e n d не используется;
• для инициализации объектов используются конструкторы;
• никакие методы не изменяют внутренние поля объектов, могут быть только функции, возвращающие значения полей (но
не меняющие ничего); как следствие, все методы, кроме конструкторов, помечены как константные;
К части «язык С и + + , ООП и АТД»
95
• данные базового класса нигде не дублируются полями порождённого класса.
10.12. Опишите абстрактный класс Prism, представляющий прямоугольную призму с известной высотой, но неизвестной формой
основания. Предполагается, что все величины имеют тип double.
Предусмотрите ч и с т о в и р т у а л ь н у ю функцию SquareO, возвращающую площадь основания призмы, и простую функцию VolumeO,
вычисляющую объём как произведение высоты на площадь основания.
Унаследуйте от класса Prism класс Box, представляющий прямоугольный параллелепипед с квадратом в основании, задаваемый длиной бокового ребра (первый параметр конструктора) и длиной стороны основания (второй параметр). Унаследуйте от класса Box класс
Cube, представляющий собой куб, задаваемый длиной ребра (единственный параметр конструктора). В результате следующая функция mainO:
int
main()
K
c o n s t P r i s m *p, *q, * r ;
Box a ( 0 . 5 , 2 ) , b ( 5 , 0 . 2 ) ;
Cube c ( 0 . 5 ) ;
p = 6a; q = 6b; r = 6c;
printf("Squares: /3.3lf /3.3lf /3.3lf\n",
p->Square(), q->Square(), r->Square());
printf("Volumes: /3.3lf /3.3lf / 3 . 3 l f \ n " ,
p->Volume(), q->Volume(), r->Volume());
r e t u r n 0;
M
должна откомпилироваться без ошибок и предупреждений, отработать и выдать
Squares: 4.000 0.040
Volumes: 2 . 0 0 0 0 . 2 0 0
0.250
0.125
Проверьте выполнение условий, перечисленных в конце предыдущей
задачи.
Обработка исключений
10.13. Что напечатает следующая программа?
Задачи
96
#include
c l a s s Ех K
i n t code;
public:
E x ( i n t i ) : c o d e ( i ) KM
E x ( c o n s t Ex& e x ) : c o d e ( e x . c o d e ) KM
i n t Get() const K r e t u r n code; M
M;
c l a s s Ех60 : p u b l i c Ех K
public:
E x 6 0 ( ) : E x ( 6 0 ) KM
M;
void f ( i n t i)
K
if(i>0)
throw E x ( i ) ;
printf("owl\n");
M
void
K
g()
try K
f(60);
M
c a t c h ( E x 6 0 6x) K
printf("dog\n");
M
printf("cat\n");
M
void
h()
K
try K
g();
printf("sheep\n");
M
c a t c h ( E x &x) K
printf("horse\n");
throw Ex60();
M
c a t c h ( E x 6 0 6x) K
printf("cow\n");
M
printf("elephant\n");
M
void
t()
K
try K h(); M
c a t c h ( E x 6x) K p r i n t f ( " w o l f
/d\n",
x.Get()); M
К части «язык С и + + , ООП и АТД»
97
printf("monkey\n");
M
i n t main() {
try K t(); M
catch(...) { printf("fox\n"); M
r e t u r n 0;
M
10.14. Вернитесь к решению задачи 10.09 и снабдите конструкторы класса Rational проверкой, что знаменатель отличен от нуля;
если проверка не прошла, выбрасывайте исключение, для которого
опишите специальный класс.
Шаблоны
10.15. Опишите идентификатор swap3 так, чтобы вычисление выражения вида s w a p 3 ( x , y , z ) (где х, у, z — переменные какого-то неизвестного типа) приводило к тому, что в переменной х оказывается
значение, которое находилось до этого в переменной y, в ней, в свою
очередь, значение, находившееся в переменной z, а в переменной z —
то, что раньше было в переменной х. Про тип переменных известно
только, что он допускает присваивание и описание переменных без
указания инициализирующих параметров.
10.16. Опишите идентификатор get_and_zero так, чтобы вычисление выражения вида a = get_and_zero(b), где a и b — переменные
некоторого (неизвестного) типа, приводило к тому, что в переменной
a оказывается старое значение переменной b, а в самой переменной
b — ноль. Про тип переменных известно только, что он допускает
копирование, присваивание переменных друг другу и присваивание
нуля (т.е. выражение a = 0, где a — переменная такого типа, является допустимым).
Этюды для закрепления навыков
10.17. Вернитесь к задачам 9.09-9.11 и оформите описанные в
них автоматы в виде объектов классов, имеющих конструктор д л я
инициализации и задания начальных параметров, если таковые нужны, деструктор для высвобождения захваченных ресурсов, если такие есть, и один обыкновенный публичный метод, выполняющий шаг
автомата. Приватные методы можно вводить без ограничений.
10.18. Вернитесь к условиям задач 6.12-6.17 и перепишите эти
программы на СиН—Н с использованием объектно-ориентированного
подхода.
Задачи
98
Библиотека FLTK
10.19. С использованием библиотеки FLTK напишите программу, которая получает через параметр командной строки некое сообщение, после запуска формирует на экране диалоговое окно, содержащее это сообщение и две кнопки с надписями Yes и No; если
пользователь нажимает кнопку Yes, программа должна завершиться успешно (с нулевым кодом завершения), если же пользователь
предпочтёт кнопку No — завершиться следует с кодом 1 (неуспех).
10.20. Если не предпринять специальных мер, нажатие клавиши
Escape в окошке программы, написанной на FLTK, приводит к нормальному завершению программы; по смыслу условия предыдущей
задачи это совершенно не то, что нужно. Усовершенствуйте программу, написанную для решения предыдущей задачи, так, чтобы при
нажатии Escape она завершалась с кодом 1.
10.21. Напишите программу, которая принимает произвольное
(но не менее одного) количество аргументов командной строки, каждый из аргументов использует как текст кнопки, формирует диалоговое окно, содержащее соответствующие кнопки, и в случае, если
пользователь нажимает на одну из кнопок — завершается успешно,
выдав в поток стандартного вывода десятичное представление номера кнопки, начиная с единицы (этот номер будет совпадать с индексом аргумента в массиве argv); если же пользователь н а ж а л Escape,
программа должна завершиться с кодом 1, ничего не напечатав.
10.22. Напишите с использованием FLTK программу — клавиатурный тренажёр. После старта программа должна прочитать текст
из некоторого текстового файла, в котором к а ж д а я строка — это
«упражнение», т.е. фраза, которую пользователь должен набрать.
Далее программа формирует диалоговое окно, в котором есть виджет для отбражения очередной ф р а з ы и поле текстового ввода; в
этом окне программа последовательно воспроизводит фразы, прочитанные из файла. Пользователю предлагается набрать такую же
фразу в поле ввода и нажать Enter. Если набранная фраза совпадает с ожидаемой, программа должна перейти к работе со следующей
фразой из файла, когда же они закончатся — выдать пользователю
информационный диалог, отображающий общее количество потраченного на упражнение времени, с кнопкой «Ок»; после нажатия на
кнопку программа завершается. Если очередную фразу пользователь
набрал с ошибками, при нажатии клавиши Enter набранный текст
должен исчезнуть, а фраза, которую нужно набрать — остаться той
же самой, чтобы её пришлось набрать повторно, и так до тех пор,
пока она не будет набрана правильно.
К части «язык С и + + , ООП и АТД»
99
10.23. С конца XIX века хорошо известна «игра в 15», она же «такен». В классическом варианте эта игра представляет собой квадратную коробку, в которой располагаются 15 квадратных фишек («плиток») размером вчетверо меньше коробки; при этом один квадратик
в коробке остаётся пустым. Плитки исходно расположены в случайной последовательности; задача игры — перемещая за один ход одну
плитку на пустое место, расставить все плитки в порядке возрастания номеров. Хорошо известен также тот факт, что ровно половина
исходных позиций неразрешима: их можно привести к позиции, в
которой все плитки стоят по порядку, но последние две (14 и 15)
поменены местами.
Рискнём предложить читателю модификацию «игры в 15», которую можно назвать «13». От классического варианта она отличается
только нумерацией плиток: они занумерованы от 0 до 13, причём
плиток с нулём в коробке две, и они не отличаются одна от другой. Целевая позиция в этом случае — сначала два «нуля», потом
остальные плитки от первой до тринадцатой. Поскольку две «нулевые» плитки неразличими, их можно поставить в любом порядке, что
делает все возможные начальные позиции заведомо разрешимыми.
Реализуйте программу, позволяющую пользователю играть в
«13». Программа должна формировать диалоговое окно с 15 квадратными кнопками, имеющими соответствующий текст (размером
70-80% от размеров кнопки) и расположенными на поле размером
4 х 4 кнопки; ход производится нажатием на одну из кнопок рядом
со свободным местом, после чего соответствующая кнопка перемещается в свободную позицию (меняются координаты её виджета). После
достижения целевой позиции следует выдать диалог с поздравлениями.
Желательно, чтобы ваша программа помнила начальную позицию и все сделанные пользователем ходы, позволяла возвращаться к
началу, откатывать любое количество ходов, записывать текущее состояние (позицию и ходы) в файл и считывать его из файла, а также
генерировать новую начальную позицию, используя псевдослучайные числа. Кроме того, желательно предусмотреть для пользователя
возможность самостоятельно задать начальную позицию; впрочем,
если файл для сохранения состояния будет простым текстовым, эту
возможность можно отдельно не реализовывать, предложив пользователю вручную сформировать соответствующий файл.
10.24*. Вернитесь к задаче 6.18 (см. стр. 81) и снабдите ваш сервер графической клиентской программой; изображения игральных
карт, составляющих различные колоды, можно легко отыскать в Интернете.
К части 11 «неразрушающие
парадигмы»
Л и с п и Scheme
Д л я решения задач из этого параграфа рекомендуется воспользоваться л ю б ы м из интерпретаторов Common Lisp, рассматриваемых во «Введении в профессию» — SBCL, GCL
или ECL, а т а к ж е интерпретатором Chicken Scheme (хотя
на самом деле можно использовать едва ли не любой интерпретатор). В задачах, предполагающих написание программы (в отличие от отдельной функции), т а к у ю программу следует обязательно оформить как исполняемый скрипт
(см. §§11.1.2, 11.2.1), либо для случая Chicken Scheme —
откомпилировать. Помните, что запуск программ из интерактивного сеанса работы с интерпретатором — это атавизм давно ушедшей эпохи5 когда не существовало конечных
пользователей; конечному же пользователю ваша программа вообще не должна показывать, на чём она написана.
Если вы хотите освоить и Лисп, и Scheme (что в целом полезно)5 правильно будет поначалу решение каждой задачи
писать на обоих языках; на более поздних этапах можно чередовать я з ы к и (одну задачу на одном, другую на другом),
можно для каждой задачи выбирать один из двух языков5
исходя из любых соображений вплоть до сегодняшнего настроения5 тут главное — не зацикливаться на одном из двух
языков5 иначе второй вы так толком и не попробуете.
11.01. Напишите функцию, которая принимает параметром натуальное число N и возвращает список натуральных чисел от 1 до
N, например, (1 2 3 4).
К части «неразрушающие парадигмы»
101
11.02. Напишите функцию, которая принимает два параметра —
произвольное выражение Е и целое число N — и возвращает построенный список, состоящий из N элементов Е.
11.03. Напишите функцию, которая принимает один параметр —
список произвольной длины, элементами которого тоже могут быть
списки на произвольную глубину вложенности — и подсчитывает
сумму входящих в этот список (на любой глубине вложенности) числовых атомов, а все остальные атомы (как и структуру самих списков) игнорирует.
11.04. Напишите функцию, которая получает параметром список
произвольной длины и вложенности, и возвращает список, построенный из атомов, входящих в исходный список на любом уровне вложенности. Например, из аргумента (1 2 (3 (4 5) 6 ( ( 7 8 ) ) 9 ) )
должен получиться список (1 2 3 4 5 6 7 8 9).
11.05. Напишите функцию p r o p e r l i s t , которая принимает один
аргумент и возвращает значение логической истины, если аргумент
является «правильным» списком, и ложь в любом другом случае. Напомним, что правильным (proper) считается либо пустой список, либо такой, в котором правый элемент (cdr) последней точечной пары
является пустым списком. Отметим, что встроенная функция l i s t p
( l i s t ? в Scheme) возвращает истину в том числе и для точечных
списков, таких как (1 . 2) или (a b c . d).
11.06. Не используя арифметические действия, напишите функцию, которая возвращает истину, если её (единственный) аргумент —
список из чётного числа элементов (верхнего уровня), а во всех
остальных случаях возвращает ложь.
11.07. Напишите функцию, которая получает два аргумента —
список L и целое число N, и возвращает список, состоящий из N
первых элементов списка L; если список L состоит всего из N элементов или окажется ещё короче, следует вернуть его весь (допускается
вернуть его копию).
11.08. Напишите функцию l i s t - i t e r , которая принимает один
параметр — произвольный список, а возвращает объект новой функции, (замыкание); порождённая функция должна, не принимая аргументов, при каждом вызове возвращать очередной элемент исходного
списка, пока этот список не кончится, после этого в случае дальнейших вызовов возвращать NIL (или #F для Scheme). Например, если
результат вызова ( l i s t - i t e r ' ( 1 2 3 ) ) присвоить переменной f , то
обращения к ( f u n c a l l f ) (для Scheme — просто ( f ) ) д о л ж н ы последовательно вернуть 1, 2, 3, а дальше соответственно NIL или #f.
102
Задачи
11.09. Используя свойства замыканий, напишите функцию, которая по заданному списку строит «перевёрнутый» список, используя
для просмотра списка функционал mapcar (map для языка Scheme).
11.10. В Common Lisp узнать длину строки можно с помощью
встроенной функции length, извлечь из строки символ с заданным
номером — с помощью функции char; в Scheme аналогичные функции называются s t r i n g - l e n g t h и s t r i n g - r e f . Напишите на этих
языках программы, соответствующие условиям задач 2.22, 2.23 и
4.12.
11.11. Напишите на Лиспе и / и л и Scheme программу, соответствующую какому-нибудь из пунктов задачи 2.19 (см. стр. 2.19), не применяя циклы. Внимательно проанализируйте получившуюся рекурсию;
если она не является остаточной (хвостовой), обязательно скорректируйте своё решение. Подав своей программе на стандартный ввод
бесконечный поток строк (например, с помощью команды yes), убедитесь, что количество занимаемой ею памяти не увеличивается со
временем.
11.12. Напишите программу, принимающую ровно один аргумент
командной строки, в котором должно быть записано арифметическое
выражение, вычисляет это выражение и выдаёт результат вычисления на стандартный вывод. Выражение может включать целые числа, круглые скобки и знаки пяти основных действий целочисленной
арифметики (+, -, *, / и %); кроме того, между любыми элементами
выражения (но, конечно, не внутри чисел) допускаются (но не являются обязательными) произвольные группы пробельных символов.
Д л я упрощения картины можете не обрабатывать унарные минусы
и плюсы, хотя их наличие если и усложняет разбор выражения, то
не так чтобы очень сильно.
11.13. Создайте программу, главная функция которой написана на Си, при этом некоторые из остальных функций написаны на
Chicken Scheme; например, можно сделать программу, печатающую
те из аргументов командной строки, которые являются палиндромами (без учёта пробелов), а проверку строки на палиндромичность
реализовать на Scheme.
Создайте программу, основная часть которой написана на Scheme,
но при этом из неё вызываются части, написанные на Си; например,
это может быть какой-то демонстрационный TCP-сервер, часть которого, отвечающая за сокеты, написана на Си, а прикладная функциональность — на Scheme.
Всю необходимую информацию о том, как интегрировать между
собой модули на Chicken Scheme и Си, найдите в Интернете.
К части «неразрушающие парадигмы»
103
Пролог
В задачах на обработку списков не следует применять встроенные и библиотечные предикаты, иначе вы не получите навыков, на формирование которых даны эти задачи.
11.14. Без использования арифметики напишите одноместный
предикат, истинный на списках, которые:
a) состоят из чётного числа элементов;
b) состоят из нечётного числа элементов;
c) содержат в произвольном месте два соседних одинаковых элемента;
d) в каждой чётной позиции (вторым, четвёртым, шестым элементом
и т.д.) содержат пустой список ( [ ] ) ,
и ложный на любых других аргументах.
11.15. Напишите без использования арифметики предикат
a t l e a s t 2 ( E , L ) , верный в случае, если элемент E встречается в списке
L не менее двух раз. Правильно написанный предикат должен работать в прототипах ( + , + ) и ( — , + ) то есть когда первый аргумент не
задан, предикат должен найти все такие элементы, которые входят
в список больше одного раза.
11.16. Напишите предикат s i m i l a r ( L 1 , L2), истинный тогда и
только тогда, когда L1 и L2 — списки одинаковой длины, причём L2
либо является копией L1, либо получен из L1 заменой одного или
нескольких (возможно, всех) элементов, являющихся списками, на
пустой список [] . Например, такому свойству удовлетворяют списки
L 1 = [ f ( c ) , [ 2 , 3 ] , [ a ] , [ c , b ] , 3 ] и L 2 = [ f ( c ) , [ ] , [ a ] , [ ] , 3 ] . Проверьте работу в прототипах ( + , + ) и ( + , - ) .
11.17. Напишите предикат i n s _ o n e ( L i s t , Elem, Res), устанавливающий отношение «Res есть список, полученный из списка L i s t
добавлением элемента Elem в любое его место — перед первым элементом, между любыми двумя или после последнего». При правильном решении ваш предикат должен работать в прототипах ( + , + , + ),
( + , + , - ) , ( + , - , + ), ( - , + , + ) и ( - , - , + ) ; например, в ответ на
запрос i n s _ o n e ( [ 1 , 2 ] , 0, R) вы получите три ответа: [ 0 , 1 , 2 ] ,
[ 1 , 0 , 2 ] и [ 1 , 2 , 0 ] , запрос ins_one(L, 2, [ 1 , 2 , 3 ] ) даёт ровно одно
решение ( [ 1 , 3 ] ) , запрос ins_one(L, X, [ 1 , 2 , 3 ] ) даст три решения
(догадайтесь, какие).
11.18. Напишите предикат shrink(L,R), истинный, когда список
R получен из списка L вычёркиванием:
а) ровно двух произвольных элементов;
104
Задачи
b) не более чем двух элементов;
c) ровно двух элементов, стоящих в списке подряд.
11.19. Напишите предикат strike(L,M), который истинен тогда
и только тогда, когда список M получен путём вычёркивания из списка L некоторого (возможно, нулевого) количества элементов, стоящих подряд, и вставления вместо них одного элемента []. Предикат должен работать как в прототипе ( + , + ), так и в прототипе ( + , - ) ; в частности, запрос s t r i k e ( [ 1 , 2 , 3 ] , M ) должен выдать
(в произвольном порядке) следующие решения: [ [ ] ] , [ 1 , [ ] ] , [ [ ] , 3 ] ,
[[],2,3] , [1,[],3], [1,2,[]] , [[],1,2,3] , [1,[],2,3] , [1,2,[],3] ,
[1,2,3,[]] .
11.20. Напишите предикат permute(L, M), задающий отношение
«список M является перестановкой списка L», т.е. списки состоят из
одинаковых элементов, возможно, стоящих в разном порядке. Проверьте работу в прототипах ( + , + ) и ( + , - ) .
Как ни странно, этот предикат обычно не желает работать S инвертированном прототипе, т.е. если вы заставили его работать в прототипе ( + , - ) ,
то, скорее всего, в прототипе ( — , + ) он не заработает (в лучшем случае уйдёт в бесконечную рекурсию после выдачи всех результатов). Пусть вас это
не беспокоит, не вы первые, не вы последние, кто обнаруживает такое свойство у этой задачи. В библиотеке SWI-Пролога есть предикат p e r m u t a t i o n ,
решающий ровно эту задачу и корректно работающий во всех прототипах, но
его реализация использует примитив v a r .
11.21. Напишите двухместный предикат, оба аргумента которого — списки, причём второй аргумент получен из первого вычёркиванием повторений элементов (т. е. если какие-то элементы списка
одинаковы, из них должен остаться только первый).
11.22. Напишите на Прологе программы, соответствующие условиям задач 2.22, 2.23 и 4.12.
1 1 . 2 3 (queens). В классической формулировке задача о восьми ферзях выглядит следующим образом: «как на шахматной доске расположить восемь ферзей так, чтобы никакие из них не могли
друг друга побить». Вполне очевидное обобщение даёт «задачу об N
ферзях»: как на доске размером N х N клеток расположить N ферзей так, чтобы они не могли друг друга побить; известно, что при
N € {2, 3} задача решений не имеет, минимальная доска, на которой
такое расположение возможно — 4 х 4.
Напишите программу на Прологе, принимающую ровно один аргумент командной строки — число N, и отыскивающую все возможные решения задачи об N ферзях. Поскольку, очевидно, к а ж д ы й
ферзь должен находиться на своей собственной вертикали, найденное
решение можно представить в виде последовательности из N чисел,
К части «неразрушающие парадигмы»
105
каждое от 1 до N, задающих номера горизонталей, где размещены
ферзи на каждой из вертикалей; ваша программа должна каждое из
решений выдать на отдельной строке в виде последовательности чисел в десятичном представлении, разделённых пробелами. Так, при
N = 4 программа должна напечатать:
2 4 l 3
3 l 4 2
(или наоборот). Д л я самопроверки можете использовать тот факт,
что при N = 8 должно получиться 92 решения — естественно, отличных друг от друга.
11.24* ( k n i g h t ' s tour). Задача «ход конём», впервые (во всяком случае, в сохранившейся до наших дней опубликованной работе) исследованная Леонардом Эйлером в XVIII веке, состоит в
том, как, используя ход шахматного коня, обойти все клетки доски, побывав в каждой клетке ровно один раз. Маршрут коня называется замкнутым,
если после посещения всех клеток конь может
вернуться за один ход в ту клетку, с которой начинал обход. Известно, что замкнутые маршруты существуют на квадратных досках
N х N, N = 6 , 8 , 1 0 , . . . (т. е. чётного размера, начиная с 6), что касается маршрутов незамкнутых, то их можно найти на досках 3 х 4,
3 х М, М ^ 7, 4 х 5 и на всех более крупных.
Напишите на Прологе программу, принимающую два аргумента
командной строки — числа N и М, задающие размер доски — и отыскивающую какой-нибудь один замкнутый маршрут, если для заданной доски такой возможен, если же невозможен — то какой-нибудь
один незамкнутый маршрут. Найденный маршрут следует выдать
на стандартный вывод в виде последовательности клеток, заданных,
например, их координатами через запятую, разделённых пробелами
(что-то вроде «1,1 2 , 3 3,1...») или как-то иначе.
Искать see маршруты на доске заданного размера мы не предлагаем, их
может оказаться неожиданно много. Так, для доски 5 х 5 сущестsует 1728
маршрутоs ^ с е незамкнутые, поскольку доска хоть и ^ а д р а т н а я , но нечётного размера), а на доске 8 х 8 будет больше 26 TpnwnoHos одних только
замкнутых маршрутоs, sсего же их (и замкнутых, и незамкнутых) оказывается 19.5 кsадриллионоs.
11.25*. Напишите на Прологе программу, которая принимает
ровно 16 аргументов командной строки, задающих начальное расположение фишек (плиток) игры «15» или «13» (правила игры «13»
см. в условиях задачи 10.23, см. стр. 99) — первые четыре аргумента
задают верхний ряд плиток, следующие четыре — второй и т. д. Пустая клетка задаётся символом «@». Если аргументов не 16, следует
выдать сообщение об ошибке и завершиться. К а к а я игра имеется в
Задачи
106
виду — «15» или «13» — программа должна заключить по набору
значений аргументов: если набор состоит из чисел от 1 до 15, то это
«15», если из чисел от 1 до 13 и двух «нулей» (обозначаемых «О»
и «ОО») — то «13», если же ни то, ни другое — это ошибка, о ней
следует сообщить и завершить работу.
Программа д о л ж н а найти решение головоломки; для игры «15»
задачу следует считать решённой, когда либо все плитки расположены по порядку, либо по порядку расположены все плитки, кроме двух
последних (15 и 14), а эти две поменены местами; д л я игры «13» задача решена, если плитки расположены по порядку, начиная с двух
«нулей», взаимное расположение которых неважно. В обоих случаях
пустой д о л ж н а быть н и ж н я я правая клетка. Решение представляет
собой последовательность ходов, при которых плитка, соседняя с пустой клеткой, передвигается на пустое место, а её исходная клетка
становится пустой; правильное решение не содержит повторяющихся
позиций (отметим, что если это не учесть с самого начала — скорее
всего, вы не сможете создать работающий решатель, поскольку ваша программа будет до бесконечности рассматриватьциклические
последовательности ходов и никогда не найдёт путь к искомой финальной позиции). Ход обозначается номером плитки, которую на
этом ходу передвигают.
Результат работы — последовательность ходов — следует выдать
на стандартный вывод.
Хоуп
11.26.
Какой
тип
("abc", ' a ' , t r u e , 1)?
имеет
в
языке
Хоуп
выражение
11.27. С интерпретатором h o p e l e s s можно провести следующий
диалог (напомним, «>:» — это приглашение интерпретатора, т.е.
строки, перед которыми стоит эта комбинация, набраны пользователем; свои ответы интерпретатор зачем-то предваряет символами «>>»):
>:
1,2,'a',true;
>> ( 1 , 2 , ' a ' , t r u e ) : num # num # c h a r # b o o l
>: 1 , 2 , ( ' a ' , t r u e ) ;
>> ( 1 , 2 , ' a ' , t r u e ) : num # num # c h a r # b o o l
>: 1 , ( 2 , ' a ' ) , t r u e ;
>> ( 1 , ( 2 , ' a ' ) , t r u e ) : num # (num # c h a r ) # b o o l
Какой полезный вывод можно сделать из этого диалога?
К части «неразрушающие парадигмы»
107
11.28. Пусть нам потребовалась функция, принимающая три числовых параметра и возвращающая список чисел. Каков будет тип
такой функции?
11.29. Напишите функцию MakeSeq, которая принимает три числовых параметра (назовём их х, у и d) и строит список из членов
арифметической прогрессии с разностью d, первым членом х, не
превосходящих у. Например, MakeSeq(1, 4 . 1 , 0 . 6 ) должна вернуть
список [1, 1 . 6 , 2 . 2 , 2 . 8 , 3 . 4 , 4].
11.30. Напишите функцию Twist, которая принимает два списка, состоящих из элементов какого-то одного (произвольного) типа
и возвращает список, состоящий из первых элементов обоих списков, вторых элементов обоих списков и т. д.; например, выражение
J o i n 1 ( [ 1 , 2 , 3 ] , [ 7 , 8 , 9 ] ) ) должно вернуть список [ 1 , 7 , 2 , 8 , 3 , 9 ] .
Если списки оказались разной длины, «лишние» элементы более
длинного списка проигнорируйте.
11.31. Чему равно выражение
letrec lst
== l
::
(map ( ( + 3 ) , l s t ) )
in F i r s t N ( l s t ,
l0);
— если F i r s t N строит список из первых N элементов своего первого аргумента, получив число N вторым аргументом? (эта функция
встречается в примерах, разобранных в книге). А что представляет
собой список 1 s t в правой части, если к нему не применять FirstN?
11.32. В §11.5.6 рассмотрена функция DropElems для списка чисел, в §11.5.8 она переписана для произвольных списков. Напишите
аналогичную функцию в каррированной форме.
11.33. В §11.5.12 разобраны примеры S i e v e (решето Эратосфена)
и P a s c a l s T r i a n g l e (построение треугольника Паскаля). Перепишите
эти примеры, не применяя кортежей, т. е. без использования символа #. Д л я этого все функции придётся записать в каррированной
форме.
11.34. Напишите на Хоупе две-три программы, соответствующие
каким-нибудь пунктам задачи 2.19 (см. стр. 2.19). Следите за тем,
чтобы ответ на введённую пользователем строку ваша программа
давала немедленно после ввода строки — для этого придётся всерьёз
задействовать возможности ленивой семантики. Подав своей программе на стандартный ввод бесконечный поток строк (например,
с помощью команды yes), убедитесь, что количество занимаемой ею
памяти не увеличивается со временем.
Задачи
108
З а д а ч и д л я р е ш е н и я на всех я з ы к а х
К а ж д у ю из задач этого раздела м о ж н о решить на л ю б о м
из рассмотренных четырёх « э к з о т и ч е с к и х » я з ы к о в , и любое
такое решение м о ж н о сделать д о с т а т о ч н о э ф ф е к т н ы м , раск р ы в с новой стороны в о з м о ж н о с т и той или иной парадигмы. Д о б и т ь с я от приведённых задач большей, если м о ж н о
т а к выразиться, учебной э ф ф е к т и в н о с т и м о ж н о , если к а ж д у ю из них решать на трёх я з ы к а х : на к а к о м - т о из лиспов
( C o m m o n Lisp или Scheme), на Прологе и на Хоупе.
Все п р о г р а м м ы д о л ж н ы б ы т ь о ф о р м л е н ы так5 чтобы ни при
их запуске5 ни при работе с ними5 в т о м числе некорректной5 пользователь не видел н и к а к и х особенностей5 обусловленных используемой реализацией я з ы к а ; программа д о л ж на запускаться как о б ы ч н ы й и с п о л н я е м ы й файл ( в о з м о ж но, п р е д с т а в л я ю щ и й собой с к р и п т на и с п о л ь з у е м о м я з ы ке, т.е. именно интерпретатор используемого я з ы к а д о л ж е н
б ы т ь указан в его первой строке), и не д о л ж н а
выдавать
приглашений к вводу, сообщений об о ш и б к а х и д р у г и х сообщений, ф о р м и р у е м ы х интерпретаторами (а не вашей программой).
11.35. Напишите программу, которая принимает через аргументы командной строки произвольное количество слов (не менее одного), затем читает из стандартного потока ввода произвольный текст
и выдаёт на печать те строки из него, в которых содержится хотя
бы одно из слов, заданных в командной строке. Строки следует выдавать (если строка должна быть выдана) немедленно после прочтения; в памяти нельзя хранить весь текст целиком, только текущую
строку.
11.36. Напишите программу, которая читает из стандартного потока ввода описание ориентированного графа в виде последовательности предложений, каждое из которых описывает дуги, исходящие
из одной вершины. Предложение начинается с имени исходной вершины, после которого ставится двоеточие и перечисляются через запятую вершины, в которые проведены дуги. Предложения разделяются символом точки с запятой, в конце последнего предложения
стоит точка. Символы пробела, табуляции и перевода строки могут
встречаться где угодно (кроме имени вершины) в любых количествах
и должны игнорироваться. Имена вершин состоят из цифр и латинских букв (заглавных и строчных). Например:
Living:
Animals, P l a n t s ,
Mushrooms, P r o t i s t s ,
Bacteria;
К части «неразрушающие парадигмы»
109
Animals: Chordata, Arthropoda, Mollusca;
C h o r d a t a : F i s h , B i r d s , Mammals, R e p t i l e s , A m p h i b i a n s ;
Arthropoda: I n s e c t s , Spiders, Crustaceans.
Программа д о л ж н а прочитать представление графа и установить,
является ли заданный г р а ф ориентированным
деревом, т.е. орграфом, имеющим ровно один корень, в котором все вершины, кроме
корня, имеют ровно одну входящую дугу, а корень не имеет ни одной
входящей дуги. В случае, если г р а ф является деревом, напечатать сообщение «THIS IS A TREE», если же не является — указать причины
(отсутствует корень; имеется более одного корня — перечислить их;
имеются вершины с более чем одной входящей дугой — перечислить
их).
В случае обнаружения ошибок во вводимых данных следует обязательно выдать осмысленное сообщение об ошибке с указанием номера строки вводимого текста.
11.37. Напишите программу, которая принимает в качестве первого аргумента командной строки текстовую запись арифметического выражения, представленного в польской инверсной записи.
Выражение может содержать целочисленные константы (одна или
несколько десятичных ц и ф р подряд), переменные (одна строчная латинская буква: a, b, c и т. д.) и символы целочисленных операций: +,
-, / , * и % (имеющих тот же смысл, что в языке Си). Напомним на
всякий случай, что скобки в П О Л И З е не нужны. Переменные и константы д о л ж н ы друг от друга отделяться пробелами, знаки операций
пользователь отделять пробелами не обязан (хотя и имеет право).
Остальные аргументы командной строки представляют собой значения переменных: второй — значение a, третий — значение b и т. д..
Ваша программа д о л ж н а вычислить выражение и напечатать результат (целое число).
11.38. В условиях предыдущей задачи замените польскую инверсную нотацию на прямую (сначала операция, затем операнды;
примерно как в Лиспе, только без скобок) и напишите соответствующую программу, по возможности используя уже написанные подпрограммы.
11.39. Используя код программ, решающих задачи 11.37 и 11.38,
напишите программу, которая может работать как с прямой, так и
с инверсной польской нотацией; если выражение (первый аргумент
командной строки) начинается со знака операции, считается, что это
прямая нотация, если с операнда (константы или переменной) — обратная нотация.
11.40. Модифицируйте решение предыдущей задачи так, чтобы
выражение (в прямой или инверсной польской записи) программа
110
Задачи
по-прежнему извлекала из первого аргумента командной строки, а
значения переменных читала из потока стандартного ввода: в каждой введённой строке первое число — значение переменной a, второе — значение переменной b и так далее. После прочтения и анализа
каждой строки вычисляйте и печатайте результат (либо сообщение
об ошибке, например, если количество значений не совпадает с количеством переменных, либо если введено не число), затем читайте
следующую строку и т. д., работайте до наступления ситуации «конец
файла».
11.41. Усовершенствуйте решение предыдущей задачи так, чтобы
в роли имён переменных в выражении могли использоваться произвольные последовательности латинских букв и цифр, начинающиеся с буквы. Значения переменных задаются в строках, вводимых из
стандартного потока: первое слово — имя переменной, второе — её
значение, третье — имя другой переменной, четвёртое — её значение
и т. д. Вводимая строка может задавать любой набор переменных,
не обязательно все, какие есть в выражении; значения переменных
сохраняются при вводе последующих строк, заменяются только те,
которые указаны в только что введённой строке; первое вычисление значения произведите, когда после анализа очередной введённой
строки все переменные, упоминаемые в выражении, окажутся заданы, затем вычисляйте новый результат после ввода каждой строки
(это может быть полезно, например, чтобы вычислить некую функцию в большом количестве разных точек).
11.42. Напишите программу, которая ч и т а е т и з п о т о к а с т а н д а р т н о г о в в о д а последовательность выражений, записанных в
п о л ь с к о й и н в е р с н о й з а п и с и (сначала операнды, потом операция),
и вычисляет (выполняет) операции по мере их чтения. Вводимый
текст может содержать целочисленные константы (одна или несколько десятичных цифр подряд), переменные ( о д н а и л и б о л ь ш е строчных латинских букв подряд: a, xyz, kadabra и т.д.), символы целочисленных операций: +, -, / , * и % (имеющих тот же смысл, что в
языке Си, все операции бинарные), символы служебных операций:
«=» — присваивание, причём переменная в записи присваивания ставится после выражения (например, «25 x =» означает «присвоить 25
переменной x»; «?» — напечатать значение, находящееся на вершине
стека, не удаляя из стека; «! » — извлечь из стека значение и напечатать его; «#» — напечатать на отдельной строке текущее содержимое
стека (в угловых скобках через пробел) и значения всех переменных
(парами имя-значение, через пробел). При выполнении команд «?» и
«! » выдавайте пробел после числа. Переменные и константы должны друг от друга при вводе отделяться пробелами, знаки операций
К части «неразрушающие парадигмы»
111
пользователь отделять пробелами не обязан (хотя и имеет право).
Вычисления д о л ж н ы производиться, когда получен символ перевода строки (либо раньше); если за время обработки введённой строки
хоть что-то было напечатано, выдать символ перевода строки. Программа должна продолжать работу до наступления ситуации «конец
файла». Например, в ответ на введённую строку
15 15*? х= х 5 / ? 20 f o o = 12 13! f o o #
должно быть напечатано
225 45 13
х 225 f o o 20
(допускается стек напечатать в виде «»). П р е д у с м о т р и т е о б р а б о т к у о ш и б о к ! (некорректное выражение, несуществующая переменная, деление на ноль и т. п.)
11.43. Усовершенствуйте программу, написанную для решения
предыдущей задачи, так, чтобы она допускала ровно один аргумент,
задающий (в виде числа от 2 до 36) основание системы счисления,
в которой потом будут проводиться вычисления. На вводе «цифры»,
превышающие 9, обозначаются латинскими буквами А (10), В (11)
и т.д., вплоть до Z, которая в системе по основанию 36 означает
цифру 35. Б у к в ы верхнего и нижнего регистра не различайте (ни
в именах, ни в литералах). Операнды, запись которых начинается
с десятичной цифры, ваш калькулятор должен рассматривать как
числа (константы), а начинающиеся с буквы — как идентификаторы
переменных; если первая цифра числа обозначена буквой, к нему следует добавить незначащий ноль, чтобы программа не воспринимала
его как идентификатор (например, А25 — это идентификатор переменной, а 0А25 — запись некоторого числа, при условии, что система
задана как минимум 11-ричная, в противном случае — ошибка).
11.44. Модифицируйте программу, написанную по условиям задачи 11.42, чтобы она производила вычисления не в целых числах, а
в числах с плавающей точкой. Добавьте одноместные операции д л я
округления к ближайшему целому и отбрасывания дробной части.
Постарайтесь сделать так, чтобы числа, имеющие нулевую дробную
часть, печатались как целые.
11.45*. Напишите программу, которая принимает два аргумента
командной строки; первый из них задаёт выражение в обычной инфиксной (не польской!) нотации, включающее константы, записанные в виде целых чисел и десятичных дробей, символы четырёх действий арифметики, символ ~ для обозначения возведения в степень,
имена переменных, состоящие из одной строчной латинской буквы,
отличной от «e»; буква e считается обозначением числа е (основания натуральных логарифмов), идентификатор p i используется д л я
112
Задачи
обозначения числа •к, также выражение может включать обозначения тригонометрических функций и обратных к ним (sin, cos, tg,
a r c s i n и т.п.), натурального логарифма ln, десятичного логарифма
lg; обычный логарифм в систему лучше не включать из-за сложностей с обозначением его основания. Второй аргумент командной
строки должен состоять ровно из одной латинской буквы, обозначающей одну из используемых в заданном выражении переменных.
Ваша программа должна, рассматривая выражение как функцию
от (возможно) нескольких переменных, взять её производную по заданной переменной. Обязательно выполните тривиальные оптимизации, такие как замена выражения 0 + х выражением х, замена 0 • х на
0, 1 • х на х; позаботьтесь, чтобы итоговое выражение не содержало
лишних круглых скобок.
К части 12 «компиляция,
интерпретация, скриптинг»
Я з ы к Tel
12.01. Выберите два-три примера из условий задач 2.19-2.21
(см. стр. 22) и напишите скрипты на языке Tcl, решающие те же задачи. Д л я посимвольного ввода используйте команду read s t d i n 1,
для обнаружения ситуации «конец файла» — команду eof stdin;
помните, что eof проверяет, не настал ли конец файла в ходе последней операции ввода, так что применять её следует после read.
12.02. Перепишите скрипты, созданные при решении предыдущей задачи, используя в этот раз команду g e t s и последующий анализ прочитанной строки. Д л я анализа строк достаточно знать, что
команда s t r i n g l e n g t h выдаёт длину указанной строки, а s t r i n g index возвращает символ заданной строки (нумерация идёт с нуля). Сравните получившиеся решения с теми, что использовали посимвольное чтение.
12.03. Выберите два-три примера из условий задач 2.22, 2.23
(см. стр. 24) и напишите соответствующие скрипты на Tcl. Д л я анализа строк используйте s t r i n g l e n g t h и s t r i n g index (см. условия
предыдущей задачи).
12.04. Напишите на Tcl скрипт, решающий задачу 2.52 (стр. 31).
Библиотека Tel/Tk
12.05. Д л я ознакомления с возможностями Tcl/Tk напишите
(в форме скриптов для интерпретатора wish) программы, соответствующие условиям задач 10.19 и 10.21 (см. стр. 98).
12.06. Используя геометрический менеджер grid, напишите на
Tck/Tk программу для игры в «15» и «13» (см. задачу 10.23).
114
Задачи
12.07*. Вернитесь к задаче 11.24 (стр. 105) и модифицируйте своё
решение так, чтобы в ходе поиска программа выдавала координаты
клеток, из которых состоят рассматриваемые недостроенные маршруты. Напишите на Тс1/Тк программу, которая принимает те же параметры, что и ваша программа на Прологе, рисует шахматную доску, запускает пролог-программу как внешнюю и в ходе её работы
визуализирует происходящий поиск с возвратами.
С задачей 12.07 у автора задачника связаны интересные воспоминания. Задача «ход конём» для решения на Прологе
предлагалась слушателям спецкурса «Парадигмы программирования» (да, когда-то очень давно это был именно спецкурс). Заставить программу, написанную на Прологе, работать в связке с T c l / T k для визуализации поиска придумали
сами студенты5 слушавшие курс5 автор их никак к такому
решению не подталкивал; по правде говоря5 в той версии
связка была устроена проще: прологовская программа выдавала команды для w i s h , а запускать её (и w i s h ) нужно
было конвейером.
Когда студент, получивший задание, подходит к нему настолько творчески — это, пожалуй, самое вдохновляющее,
что может произойти в практике преподавателя. Автору
остаётся лишь сожалеть5 что за двадцать с лишним лет работы все встретившиеся ему случаи такого рода можно пересчитать по пальцам (и, кажется, даже одной руки), а в
последние лет семь такого вообще не встречалось.
У К А З А Н И Я
116
Указания
1.06-1.09. Права доступа к файлам подробно рассмотрены в
т. 1, §1.2.13.
1.16. Здесь придётся комбинации из одного, двух и трёх шариков рассмотреть отдельно. С одним шариком всё понятно. С двумя
чуть сложнее: как первый, так и второй шарик можно выбрать четырьмя способами, только при этом мы все комбинации, кроме тех,
которые состоят из oduHaKosux uiapuKos, посчитаем дважды, ведь
условия задачи не предполагают упорядоченности выбранных шариков (красный плюс синий — это то же самое, что и синий плюс
красный). Ещё хуже обстоят дела с тремя шариками: каждый из
них по-прежнему можно выбрать четырьмя способами, но комбинации, состоящие из трёх разных шариков, мы посчитаем по много раз
каждую (кстати, по сколько раз? если вы не знаете, что ответить на
этот вопрос, перечитайте §1.3.1); с комбинациями, в которых два шарика одинковы, а третий имеет другой цвет, дела обстоят проще —
два одинаковых шарика выбираются четырьмя способами, а третий
к ним — тремя, так мы изначально игнорируем порядок, что и требуется. Наконец, комбинации, целиком состоящие из шариков одного
цвета, нам встретились ровно по одному разу каждая. Все эти случаи
придётся рассмотреть отдельно и просуммировать.
1.20. К а ж д а я игрушка может оказаться у Маши, у Пети, у Васи
или остаться на столе; исходите из этого.
1.21. Проще всего рассмотреть общее количество возможных
подмножеств из всех имеющихся кулонов, включая пустое множество (все кулоны остались в шкатулке) и множество из всех кулонов
(в шкатулке не осталось ничего); напомним, что каждый элемент исходного множества может в подмножество входить или не входить,
так что количество всевозможных подмножеств вычисляется очень
просто. Из этого количества следует выкинуть все «запрещённые»
варианты — когда не взято ни одного кулона, когда взят только один
или когда взяты вообще все. Задачу можно решить и другим способом: с собой нужно взять два, три или четыре кулона из пяти, что
соответствует С | , Cf и С§, остаётся их вычислить с помощью треугольника Паскаля и сложить.
1.22. Первую из двух ладей можно поставить на любую клетку
доски, а их, как известно, 64. Для второй ладьи, где бы ни стояла
первая, можно выбрать одну из семи оставшихся клеток горизонтального ряда, в котором стоит первая ладья, либо одну из семи
клеток соответствующего вертикального ряда, т. е. всего клеток для
её размещения оказывается 14. Кроме того, нужно учесть, что ладьи
по условию одинаковые, так что каждые две комбинации, получающиеся друг из друга, если ладьи поменять местами, неразличимы;
следовательно, нужно ещё разделить полученное число пополам.
К части 11
117
1.23. Начните с обруча, зафиксированного в пространстве, сектора которого закрашиваются в определённом порядке — например,
по часовой стрелке. Первый сектор можно закрасить одним из пяти
цветов, второй — одним из оставшихся четырёх, для третьего цветов останется три. Заметим теперь, что, «сдвинув» выбранные цвета
на один или два сектора, мы получим точно такую же комбинацию,
поскольку сектора одинаковые и никто не мешает повернуть обруч.
Следовательно, каждые три из рассмотренных нами отдельных сочетаний цветов в действительности неразличимы. Кроме того, обруч
можно перевернуть, и это сделает неразличимыми каждые два из
оставшихся сочетаний.
1.27. Обратите внимание, что сначала мастеру придётся выбрать
центральную бусину, потом два дополнительных вида бусин, и после
этого, повесив на нить центральную бусину, мастер каждую следующую пару симметричных бусин сможет выбрать всего двумя способами. Все бусы, состоящие из бусин ровно трёх разных видов, в этом
числе будут учтены по одному разу; есть ещё комбинации, где третий
тип бусины вообще не применялся — такие окажутся учтены по пять
раз каждая, поскольку их считали отдельно для каждого из пяти
возможных вариантов третьего типа бусины, но эти пять вариантов
в итоге неразличимы, так что по четыре из них нужно вычесть.
1.28. Попробуйте выписать три левых колонки треугольника Паскаля — начните с первых трёх строк, для последующих строк выписывайте только три первых числа. Очень легко заметить, что С^ = п,
что и понятно, если вспомнить смысл чисел С^; заметить закономерность для С^ (для произвольных натуральных п) лишь немногим
сложнее.
1.32. Не забывайте, что умножение на основание системы счисления (каково бы оно ни было) технически выглядит как «дописывание нолика»; также примите во внимание, что 3ю = II2, а
35ю = 32ю + 3ю = 1000002 + 112 = 1000112.
1.33. Искомое количество нулей равно максимальной степени
двойки, на которую делится число 30!; эта степень двойки, в свою
очередь, соответствует общему количеству двоек, которые получатся при разложении чисел от 1 до 30 на простые множители. Чтобы
не пришлось действительно раскладывать на простые множители все
тридцать чисел, задайте сами себе вопрос, сколько из этих чисел делятся на два, сколько — на четыре, сколько на восемь и на шестнадцать.
1.38. Как это делается, подробно рассказано в §1.3.2.
1.40. Принцип перевода тот же, что и для десятичных дробей:
умножаем на два, если получилось больше единицы — единицу уби-
118
Указания
раем; после каждого умножения выписываем очередную двоичную
цифру — единицу, если пришлось её убирать из получившегося числа, ноль в противном случае.
1.41, 1.42. Воспользуйтесь двоичным представлением длины верёвки в метрах.
1.46, 1.47. В обеих задачах начните с отрицания х; имея его в своём распоряжении, через стрелку Пирса можно очевидным образом
выразить дизъюнкцию, а через штрих Шеффера — конъюнкцию;
после этого попробуйте выразить константы 0 и 1. С остальными
функциями будет проще. Список всех 16 существующих функций
двух переменных см. в §1.3.3.
1.51. Проще всего сначала перечислить функции двух переменных, которые не обладают нужным свойством, то есть такие, которые от одного из своих аргументов не зависят. Таких функций всего
шесть: константы 0 и 1, а также функции, равные одному из своих аргументов или его отрицанию: х, х, у и у (см. §1.3.3, а в нём —
таблицу 1.8 и пояснения к ней). Из этого соображения немедленно вытекает ответ для функций двух переменных. С трёхместными
функциями несколько сложнее, но принцип тот же: не имеющих существенной зависимости ни от одного аргумента — две (константы 0
и 1), существенно зависящих от одной переменной — шесть (ж, х, у, у,
z, z), существенно зависящие от двух переменных проще посчитать
отдельно для каждой из трёх переменных, не входящих в число существенных зависимостей, и для этого воспользоваться уже известным
количеством функций двух переменных, существенно зависящих от
обеих.
2.07. Попробуйте подойти к вопросу с другой стороны: что конкретно считает переменная i в каждом из примеров, или, иначе говоря, чему, какой величине она равна в каждый момент?
2.15. Воспользуйтесь следующими соображениями. Обозначим
размер одной фигуры (первое число, введённое пользователем) буквой Н, а количество фигур (второе число) — буквой N. Весь ваш вывод состоит из N отдельных колонок, имеющих ширину Н+1 символ,
причём в каждой колонке (с номером к) первые
строк — «пустые»,
т. е. состоящие из Н + 1 пробелов, затем Н строк составляют искомую фигуру, и последующие строки (с номерами, превышающими
Sfc + Н) — опять «пустые». Пусть h = (Н — 1)/2 (та самая «половина высоты» фигуры); тогда (если колонки нумеруются с единицы)
si = 0 , S2 = h и т.д.; общая высота всего изображения при N = 1
составляет Н, а при увеличении N на единицу эта общая высота
увеличивается на h; общие формулы для s& и высоты изображения
получите сами. После этого останется сообразить, что внутри «буквы Z» (если её строки занумеровать с единицы) строки с номерами
К части 11
119
1, h + 1 и Н состоят из Н звёздочек и пробела (отделяющего следующую фигуру от предыдущей), все остальные — из одной звёздочки,
перед и после которой нужно напечатать определённое число пробелов (как оно вычисляется — попробуйте сообразить самостоятельно).
Процедура, печатающая n-ю строку к-й колонки изображения —
состоящую из одних пробелов, из одних звёздочек или из одной звёздочки с пробелами спереди и сзади, — д о л ж н а знать только число Н
и, конечно, числа п и к, то есть у неё будет три целочисленных параметра; всё остальное она просто вычислит. Обязательно напишите
эту процедуру! Это ключ к решению всей задачи. Главная программа будет состоять из простых вложенных циклов for: внешний —
для печати строк от первой до только что вычисленной общей высоты фигуры, внутренний — для печати нужной строки от каждой из
N колонок (путём вызова вышеупомянутой процедуры). Не забудьте
про перевод строки после печати всех колонок, относящихся к одной
строке!
Решение можно сделать ещё интереснее, если вместо процедуры написать функцию, возвращающую строку (т. е. имеющую тип
string).
2.16. Проще всего решить задачу следующим образом: просматривать введённую строку слева направо и, зафиксировав текущий
символ и убедившись, что это не пробел и не табуляция, вложенным
циклом просматршать
остаток строки (от символа, следующего
за текущим) в поисках символов, совпадающих с текущим; при обнаружении таких символов взводить какой-нибудь флаг, означающий,
что символ нужно будет напечатать, а сам символ в строке заменять пробелом, чтобы, дойдя до него, программа не напечатала его
снова. Символ печатать (или не печатать) после окончания работы
вложенного цикла.
Многим программистам может не понравиться предложение модифицировать исходную строку; в самом деле, такое решение нарушает один из базовых принципов программирования: если по смыслу
выполняемого с данными действия их не требуется менять, то менять
их не следует. Решить эту проблему очень просто: достаточно создать
копию строки и работать с ней, а не с основной строкой. Возможны
и другие решения.
2.19. Эти задачи можно (теоретически) решить разными способами, но наиболее правильный — использовать ровно один цикл
while, одну проверку на конец файла и один оператор чтения, как
это делается в примерах §2.5.3 (обратите внимание на программы
F i l t e r L e n g t h и Skiplndented). Другие подходы чреваты ошибками
с отслеживанием конца файла. «Поймать» ситуации начала слова
и конца слова очень легко, если в специально для этого созданной
120
Указания
переменной запоминать символ, прочитанный на предыдущем шаге:
тогда переход от пробельного символа к непробельному будет означать начало слова, обратный переход — конец слова; постарайтесь
только не запутаться с происходящим в начале и конце строки.
2.20. Проще всего на каждом шаге печатать прочитанный символ, но если на этом шаге наблюдается начало слова
(см. комментарий к задаче 2.19), то перед выводом текущего символа печатать ещё открывающую скобку, если ж е имеет место конец
слова, то (опять-таки перед выводом текущего символа) печатать закрывающую скобку.
2.24. Д л я этого придётся десятичное представление числа
(по крайней мере его дробной части) сгенерировать вручную, без
применения псевдофункции s t r или форматирующих возможностей
оператора write.
2.40, 2.41. В этих задачах нужен список, в каждом элементе которого хранится число и то, сколько раз число было введено (счётчик
вхождений). Не забудьте, что при чтении чисел отслеживать ситуацию «конец файла» следует с помощью функции SeekEof (см. §2.5.4).
2 . 4 2 - 2 . 4 4 . Здесь нужно использовать списки символов; чтение,
естественно, выполнять посимвольно.
3.01. Д л я решения примеров из этой задачи нужно помнить
структуру регистров общего назначения, о которой рассказывается в §3.2.1; кроме того, стоит освежить в памяти правила записи
целочисленных констант в разных системах счисления (см. §3.2.3).
Наиболее удобно будет перевести все числа в шестнадцатеричную
систему счисления, после чего вспомнить, что к а ж д ы й байт — это
ровно две шестнадцатеричные цифры.
3.12. Организуйте цикл, в котором вызывайте GETCHAR, если в EAX
оказалась -1, завершайте работу, если там же число 10 — печатайте
0К (не забудьте про перевод строки!), если же ни то, ни другое —
просто продолжайте выполнение цикла.
3.18. Макросы, представленные в файле s t u d _ i o . i n c , сохраняют
значения регистров, за исключением EAX, который используется д л я
возврата результата; вы можете использовать остальные регистры
процессора так, как вам удобно. Один из регистров следует выделить для хранения постепенно накапливаемого числа. Учтите, что
регистры EAX и EDX требуются для выполнения команды mul, так
что при каждом умножении они будут портиться; для накапливаемого числа правильнее будет использовать, например, EBX или ESI.
Исходно этот регистр следует обнулить.
После прочтения очередного символа (обращения к макросу
GETCHAR) следует прежде всего убедиться, что символ, во-первых,
К части 11
121
прочитан (то есть ситуация «конец файла» пока не возникла) и,
во-вторых, что он является цифрой; если наступил конец файла или
прочитана не цифра, выходим из цикла чтения и идём печатать звёздочки. Если же прочитана цифра, следует получить её численное
значение, вычтя из прочитанного кода код символа '0' (вы, возможно, помните, что это число 48, но пользоваться сим тайным знанием
не надо: наш ассемблер позволяет написать просто '0' , это намного
понятнее); далее следует число, накопленное к настоящему моменту в регистре, умножить на десять и к результату прибавить численное значение прочитанной цифры. Например, если пользователь
ввёл число 1437, то накопленное число будет меняться следующим
образом: сначала это будет ноль, после прочтения единицы — число
0 • 1 0 + 1 = 1, после прочтения четвёрки — 1 • 10 + 4 = 14, после
прочтения тройки — 14 • 10 + 3 = 143, после прочтения семёрки —
143 • 10 + 7 = 1437, что нам и требуется.
Запустив программу, введите какое-нибудь небольшое число и
убедитесь, что программа действительно печатает звёздочки и переводит строку; подсчёт звёздочек доверьте программе wc:
user 0);
NULL, WNOHANG, NULL);
К части 11
153
6.01. В «ip-адресах» 1 9 8 . 2 6 0 . 1 0 1 . 1 5 и 1 0 0 . 2 0 0 . 3 0 0 . 4 0 0 присутствуют «байты», превышающие 255, так что это на самом
деле никакие не ip-адреса. С остальными приведёнными адресами
всё в порядке; хотя некоторые из них относятся к специальным
областям и не могут использоваться обычным способом, они всё же
являются ip-адресами. 6.02. а) 2 5 5 . 2 5 5 . 2 5 5 . 0 ; b) 2 5 5 . 2 5 5 . 0 . 0 ;
с)
255.0.0.0;
d)
255.255.255.255;
е)
255.255.255.252;
f)
255.255.255.128;
g)
255.255.254.0;
h)
255.255.240.0.
6.03. /12. 6 . 0 4 . 1 9 5 . 4 2 . 1 7 0 . 1 2 9 / 3 2 ,
195.42.170.128/31.../25,
195.42.170.0/24,/23, 195.42.168.0/22,/21, 195.42.160.0/20,/19,
195.42.128.0/18./17,
195.42.0.0/16./15,
195.40.0.0/14./13,
195.32.0.0/12./11,
195.0.0.0/10../8,
194.0.0.0/7,
192.0.0.0/6../2, 128.0.0.0/1.
7.01. 0, 100, 200, 300, -100, -200, -300. 7.02. 150, 225, 225; 175,
175, 250; 150, 150, 250; 150, 250, 250. 7.03. Конечно, сломается. В самом деле, пусть первый процесс выполнил первую строку процедуры
e n t e r _ s e c t i o n в её «новом варианте» (who_waits = 0;), после чего
у него истёк квант времени. Пока первый процесс находится в очереди на выполнение, второй процесс добирается до своей процедуры e n t e r _ s e c t i o n , проходит её всю (при этом цикл ожидания, как
можно легко заметить, выполняться не будет, ведь первый процесс
не успел занести единицу в i n t e r e s t e d [ 0 ] ) и начинает выполнение
критической секции, где у него, в свою очередь, истекает квант времени. Между тем первый процесс получает очередной квант, проходит оставшуюся часть процедуры, и здесь цикл ожидания тоже
не выполняется, ведь в переменную who_waits второй процесс уже
занёс единицу. В результате оба процесса оказываются в своих критических секциях одновременно.
8.01. три: read, w r i t e и _ e x i t . 8.02. _ e x i t д л я выхода. 8.03.
f r e e . 8.04. malloc. 8.05. 2048 байт (ячеек). 8.06. 32768 (2 i 5 ) байт.
8.07. 2048 байт.
10.07.
sun
v e n u s 50
venus 800
moon
e a r t h 850
v e n u s 1000
moon
moon
1856 850
moon
moon
10.10. f i r s t
third
r e s u l t = ( 1 4 ; 3)
fourth
second
10.13. horse
w o l f 60
monkey
154
Ответы
10.15. t e m p l a t e E c l a s s T>
10.16. t e m p l a t e E c l a s s T>
v o i d s w a p 3 ( T &x, T &y, T &z)
T g e t _ a n d _ z e r o ( T & m)
K
K
T t;
tx = x ;
= y;
y = z;
z = t;
T t(m);
m = 0;
return t;
M
M
11.17.
i n s _ o n e ( L , E, [ E | L ] ) .
i n s _ o n e ( [ H | L ] , X, [ H | R ] )
: - ins_one(L,
X,
R).
1 1 . 2 6 . l i s t char # char # bool # num.
11.27. Конструктор кортежа (запятая) — правоассоциативен, т. е. работает справа налево; иначе говоря, (х, у, z, t) есть то же самое,
что (х, (у, (z, t))). Впрочем, вложенные кортежи, подобные тем,
что возникли в ответ на третье из введённых выражений, никакого
практического смысла не имеют и могут привести только к возникновению лишней путаницы; в приведённом примере мы загнали интерпретатор в угол, но лучше так не делать.
11.28.num # num # num -> l i s t ( n u m ) .
11.29. Например, так:
d e c MakeSeq : num # num # num - > l i s t ( n u m ) ;
M a k e S e q ( x , y , d) E=
i f x > y t h e n [] e l s e x : : M a k e S e q ( x + d ,
y,
d);
11.30.
dec Twist : l i s t ( a l p h a ) # l i s t ( a l p h a ) -> l i s t ( a l p h a ) ;
- - - T w i s t ( _ , [ ] ) E= [ ] ;
- - - T w i s t ( [ ] , _) E= [ ] ;
T w i s t ( x : : t l , y : : t 2 ) E= x : : y : : T w i s t ( t l , t 2 ) ;
11.31. [1, 4, 7, 10, 13, 16, 19, 22, 25, 28]; список l s t — это
бесконечная (!) арифметическая прогрессия с первым элементом 1 и
разностью 3.
11.32. Здесь возможны варианты, например:
d e c D r o p E l C : num - > l i s t ( a l p h a ) - > l i s t ( a l p h a ) ;
D r o p E l C 0 E= \ x => x ;
- - - D r o p E l C k E= \ [] => [] | (_ : : t a i l ) => D r o p E l C ( k - l )
tail;
(напомним, что \ в Хоупе означает то же, что и слово lambda).
ГЛАВНЫЕ СПОНСОРЫ
ПРОЕКТА
список наиболее крупных
пожертвовании
I: 214999, Nikolay Ksenev
II: 65536, u n D E F E R
III: 60000, анонимно
IV: 53500, анонимно
V: 45763, анонимно
VI: 41500, анонимно
VII: 32767, Д м и т р и й Нурисламов
V I I I : 29855, А н т о н
I X : 29592,
Хван
анонимно
X : 25600, К о в р и г и н Д м и т р и й
Анатольевич
X I : 25000, s a d s n a k e
X I I : 24344,
X I I I : 21600,
анонимно
анонимно
X I V : 21048, o s 8 0
X V : 20079,
анонимно
X V I : 19901, З a s о р и н А л е к с а н д р
X V I I : 19723, М а к с и м Ф и л и п п о s
X V I I I : 18712, Ш е р А р с е н и й B л a д и м и р о s и ч
X I X : 16384,
анонимно
X X : 16000, C п и р и д о н о s С е р г е й B я ч е с л a s о s и ч
X X I : 15001, А н я « c a n j a » Ф .
X X I I : 15000,
анонимно
Учебное издание
С Т О Л Я Р О В Андрей Викторович
ПРОГРАММИРОВАНИЕ: ВВЕДЕНИЕ В ПРОФЕССИЮ
ЗАДАЧИ И Э Т Ю Д Ы
Рисунок и дизайн обложки Елены
5oMenHosou
Напечатано с готового оригинал-макета
Подписано в печать 11.01.2022 г.
Ф о р м а т 60x90 1/16. Усл.печ.л. 9,75. Т и р а ж 500 (1-300) экз. Изд.№ 001.
И з д а т е л ь с т в о О О О " М А К С Пресс"
Лицензия И Д № 00510 от 01.12.99 г.
119992 ГСП-2, Москва, Ленинские горы,
М Г У им. М.В.Ломоносова, 2-й учебный корпус, 527 к.
Тел. 8(495)939-3890/91. Т е л . / ф а к с 8(495)939-3891
Отпечатано в полном соотетствии с качеством
предоставленных материалов в О О О «Фотоэксперт»
115201, г. Москва, ул. Котляковская, д. 3, стр. 13
