Учебник Информатика и информационные технологии Задачник-практикум 8-9 класс Гейн Юнерман

А.Г.ГЕИН Н.А. ЮНЕРМАН ИНФОРМАТИКА и ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Задачник- практикум Учебное пособие для учащихся 8-9 классов общеобразовательных учреждений Москва «Просвещение» 2008 Предисловие Информатика принадлежит к числу быстро меняющихся дисциплин, и хотя общие ее контуры остаются сравнительно стабильными, в каждом школьном учебнике по-своему расставлены акценты. Создавая задачник-практикум, мы ориентировались именно на общие контуры предмета, очерченные в Обязательном минимуме образования по информатике. Поэтому данная книга будет полезна учащимся, изучающим информатику по любому учебнику. Весь материал разделен на разделы, соответствующие основным образовательным линиям курса; разделы делятся на параграфы, некоторые из которых подразделяются на подпараграфы. Помимо собственно заданий, в книгу включены вопросы по основным теоретическим положениям школьного курса информатики; как нам представляется, это поможет читателю проверить себя в знании теории, которая необходима для успешного выполнения практических заданий. Для удобства читателя каждый раздел и параграф открывается краткой сводкой основных определений и сведений; определяемые термины выделены там жирным шрифтом, а формулировки основных свойств и правил даны курсивом. За более подробными разъяснениями в случае необходимости читатель может обратиться к одному из тех учебников информатики, которые приведены в списке рекомендуемой литературы. В задачнике представлены задания разного уровня сложности. Более трудные задания помечены символом *. Оценка сложности задания — вещь достаточно субъективная, так что некоторые из указанных заданий могут и не показаться трудными для читателя этой книги. Кроме того, задачник содержит задания, относящиеся, на наш взгляд, к дополнительному материалу и направленные в основном на расширение кругозора. Такие задания отмечены знаком Ряд заданий ориентирован на их выполнение с помощью компьютера. Около таких заданий стоит знак §5. Мы надеемся, что данная книга будет полезна широкому кругу тех, кто изучает и преподает школьную информатику. Желаем успехов! Информация, виды ииформаци! и способы ее представления Понятие информации является первичным в информатике и не может быть строго определено в других терминах. Оно лишь разъясняется и иллюстрируется конкретными примерами применения данного термина. Более того, в разных разделах информатики термин «информация» понимается более широко или более узко, в зависимости от тех проблем, которые в данном разделе рассматриваются. В § 1 приведено несколько таких толкований. Информация и информационные процессы Информация — это то, что позволяет живым организмам, их сообществам или техническим системам реагировать на окружающую среду посредством тех или иных механизмов, обеспечивая целенаправленную деятельность. Такая точка зрения на понятие информации обычно принимается в тех разделах информатики, которые близки к кибернетике. Нередко говорят, что информация — это сведения, знания об окружающем человека мире и о самом себе. Так обычно разъясняется понятие информации в гуманитарных науках, где центральным объектом является человек как существо социальное. В теории передачи и хранения информации под информацией понимается последовательность сигналов или символов какого-либо алфавита, кодирующая некоторое сообщение без учета смыслового содержания. Аналогично понимается термин «информация» и в науках, изучающих компьютерную обработку информации. Более общее понимание термина «информация» состоит в том, что информация — это отражение разнообразия в существующем мире. Отсутствие разнообразия, когда неотличимы никакие два объекта, явления или процесса, это и есть отсутствие какой бы то ни было информации. Такое I Информация, виды информации I 5 и способы ее представления понимание обычно принято в философских науках, рассматривающих общие проблемы познания. Информацию, зафиксированную каким-либо способом, называют информационным объектом. Информационный процесс — это процесс, в ходе которого изменяется содержание информации или форма ее представления. Среди информационных процессов выделяют следующие основные виды: получение, хранение, передача, обработка, использование информации. Получение информации — это реализация чьей-либо способности к отражению различных свойств объектов, явлений и процессов в окружающем мире. Передача информации — это процесс, в результате которого обладателем информации становится новый субъект или объект. Передача информации всегда осуществляется по некоторому каналу связи от источника информации к ее приемнику. Под обработкой информации понимают любое преобразование ее содержания или формы представления. Обработка информации может происходить двумя способами: формально или эвристически. Использование информации — обязательный элемент формирования целенаправленной деятельности. При использовании информации выявляются такие свойства, как ее новизна, актуальность, достоверность, объективность, ценность, полнота и т. п. Информация обладает новизной, если ее смысловое содержание отличается от смыслового содержания ранее имевшейся информации. Информация актуальна (иными словами, своевременна), если она оказывает влияние на формирование целенаправленной деятельности именно в данный момент времени. Информация достоверна, если принимается, что она отражает реальное положение дел, в частности, не вступает в противоречие с уже имеющейся информацией, также признаваемой в качестве достоверной. Вовсе не исключается, что с поступлением новой информации данная информация уже перестанет быть достоверной. Информация объективна, если она не зависит от свойств источника информации. Надо понимать, что абсолютно не зависеть от свойств источника информация не может, однако при тех или иных условиях можно считать, что такое влияние пренебрежимо мало. Информация обладает ценностью (или, по-другому, полезностью), если она повышает вероятность достижения цели в целенаправленной деятельности той системы, которая использует эту информацию. Информация полна, если ее достаточно для достижения цели. Полная информация может быть избыточной, если для достижения цели достаточно только части данной информации. Этими свойствами информация обладает в рамках конкретно протекающего информационного процесса. |В%пДа н'щ Ниже приведено несколько примеров употребления слова «информация». Для каждого примера укажите, какое понимание этого термина — кибернетическое, гуманитарное, техническое или философское — в нем присутствует. а) На основе имеющейся информации командование приняло решение о наступлении войск по всему фронту. б) Без генетической информации невозможно воспроизведение живых организмов. в) Обнаружив медоносы, пчелы передают своим сородичам информацию об этом, исполняя определенную последовательность движений, называемую «танцем». г) Полученная экспериментально информация о свойствах веществ при низких температурах позволила создать принципиально новые материалы. д) Информация, записанная на дискету, занимает больше половины этой дискеты. е) Проведенные минувшим летом археологические раскопки дали ценную информацию о живших в этой местности людях эпохи неолита. ж) Информация на компакт-диске оказалась весьма полезной. Приведите еще 2—3 примера употребления термина «информация». Для каждого примера укажите, какое понимание этого термина используется в нем. Из перечисленных ниже процессов выделите информационные и укажите, к какому виду информационных процессов они относятся: а) выплавка чугуна; б) измерение температуры воздуха; в) перевод единиц измерения в системе СГСЕ в единицы СИ; г) движение Луны вокруг Земли; д) фотографирование планеты Марс космическим кораблем-разведчиком; е) производство бензина из нефти; ж) перевод текста с немецкого языка на французский; з) построение с помощью циркуля и линейки треугольника по заданным трем сторонам; и) разработка алгоритма решения задачи; к) исполнение алгоритма; л) решение задачи по химии; м) вычисление значения алгебраического выражения по заданным значениям входящих в него переменных; н) увеличение размеров тела при нагревании; о) написание сочинения по литературе. I Информация, виды информации И 1 и способы ее представления @ а) Приведите примеры физических (химических, биологических) процессов, посредством которых осуществляется какой-либо информационный процесс. б) Приведите примеры информационных процессов, которые инициируют какой-либо физический (химический, биологический и т. п.) процесс. в) Для неинформационных процессов, перечисленных в задании 2, укажите те, которые используются человеком для осуществления какого-либо информационного процесса. ^ а) Приведите примеры приборов, изобретенных человеком для расширения своих возможностей получения информации об окружающем мире. б) Приведите примеры извлечения живыми существами информации об окружающей среде, которые невозможны для человеческих органов чувств. в) Человек для расширения своих возможностей получения информации использует не только приборы, но и способности животных. Приведите примеры такого использования. ® Опираясь на известные вам сведения из биологии, укажите, какие формы представления информации используют животные для ее сохранения и передачи другим животным. Приведите примеры тех форм, которые не встречаются в человеческой практике. ® а) Всякая реклама несет информацию для покупателя. Найдите в газете какую-нибудь рекламу и укажите, какими из свойств обладает информация в выбранной вами рекламе, б) Какими свойствами, на ваш взгляд, должна обладать информация в любой рекламе? ® Получаемая информация может использоваться бессознательно (для живых организмов — рефлекторно) либо осознанно. Во втором случае информация используется для выработки решения, как следует действовать в имеющейся ситуации. а) Приведите примеры рефлекторного и осознанного использования информации. б) Может ли быть недостоверной информация, используемая рефлекторно? в) Приведите примеры, когда осознаваемая информация, получаемая из наблюдения, оказывается недостоверной. В приведенных примерах определите, полна ли информация для принятия требуемого решения. Если, на ваш взгляд, она не полна, то какую еще информацию вы бы хотели иметь? а) Вы с родителями планируете отправиться в туристическую поездку. Вы выяснили, какие туристические фирмы организуют такие поездки, продолжительность поездки, стоимость путевки. б) Вы хотите завести щенка. В центре собаководства вы узнали, какой породы щенки сейчас есть в продаже, сколько такой щенок стоит, какими должны быть условия содержания. @ Первый фрагмент описания забастовки английских шахтеров взят из газеты консервативной партии, второй — из газеты лейбористской партии. 8 «Сегодня началась забастовка шахтеров. Прекратилась подача угля на электро- и теплостанции. Снабжение теплом и электричеством жилых домов, больниц, школ переведено на пониженный режим в целях поддерживать в них тепло хотя бы на минимальном уровне. Если шахтеры не прекратят забастовку, жители окажутся в смертоносных объятиях холода». «Сегодня шахтеры прекратили работу. Они требуют повышения зарплаты, которая оставалась неизменной более 10 лет. Решение о забастовке нелегко далось шахтерам, понимающим, что без их угля в домах будет не так тепло, как к тому привыкли жители. Но они вынуждены были пойти на забастовку ради своих семей, своих детей. Шахтеры верят, что все с пониманием отнесутся к их борьбе за свое право достойной жизни в обществе». Какими свойствами обладает информация, помещенная в каждой из газет? За счет чего создается у читателей разное отношение к описываемым событиям? 21 Кодирование символьной информации Для передачи информации или ее хранения в виде того или иного сообщения требуется определенный способ кодирования. Кодирование своей главной целью имеет сохранение информации и придание ей формы, обеспечивающей полноценную (т. е. без потерь и искажений) передачу информации от источника к получателю. Об информации, представленной последовательностью знаков, говорят, что она символьная; информация, представленная посредством какого-либо изображения, называется видеоинформацией. Знаковую систему представления информации называют языком. Языки бывают коммуникативные (языки межчеловеческого общения), формализованные (состоящие из терминов и обозначений, за которыми закреплен однозначный смысл) и формальные (определенные формальными синтаксическими правилами). По своему происхождению языки делятся на естественные и искусственные. К формальным искусственным языкам относятся все языки программирования. Примером коммуникативного искусственного языка является язык эсперанто. Вся информация, циркулирующая в компьютере, закодирована в двухсимвольном алфавите. Для представления символьной информации используются кодовые таблицы. Стандартной является кодовая таблица ASCII (American Standard Code for Information Interchange). В таблице 1.1 приведена основная часть этого кода, содержащая латинский алфавит, цифры и ряд вспомогательцых символов. Расширения этой таблицы с символами национальных языков получили название кодовых страниц. Для русско- 9 Информация, виды информации 9 и способы ее представления го языка это прежде всего кодовые страницы СР-866 и СР-1251 (последнюю называют еще Windows-1251). В таблицах 1.2 и 1.3 приведены эти страницы. В сети Интернет используется страница КОИ-8 (Код Информационного Обмена 8-битовый), ее можно видеть в таблице 1.4. Для экономии места мы не приводим двоичные коды символов, а только указываем их десятичный порядковый номер. Таблица 1.1 Основная часть ASCII Двоичный код Десятичный код Символ Двоичный код Десятичный код Символ 00100000 32 Пробел 00111111 63 ? 00100001 33 ! 01000000 64 @ 00100010 34 п 01000001 65 А 00100011 35 # 01000010 66 В 00100100 36 $ 01000011 67 С 00100101 37 % 01000100 68 D 00100110 38 & 01000101 69 Е 00100111 39 01000110 70 F 00101000 40 ( 01000111 71 G 00101001 41 ) 01001000 72 Н 00101010 42 ★ 01001001 73 1 00101011 43 + 01001010 74 J 00101100 44 01001011 75 К 00101101 45 - 01001100 76 L 00101110 46 01001101 77 М 00101111 47 / 01001110 78 N 00110000 48 6 01001111 79 0 00110001 49 1 01010000 80 Р 00110010 50 2 01010001 81 Q 00110011 51 3 01010010 82 R 00110100 52 4 01010011 83 S 00110101 53 5 01010100 84 Т 00110110 54 6 01010101 85 и 00110111 55 7 01010110 86 V 00111000 56 8 01010111 87 W 00111001 57 9 01011000 88 X 00111010 58 01011001 89 Y 00111011 59 01011010 90 Z 00111100 60 < 01011011 91 [ 00111101 61 = 01011100 92 \ 00111110 62 > 01011101 93 ] 10 Продолжение Двоичный код Десятичный код Символ 01011110 94 Л 01011111 95 _ 01100000 96 ' 01100001 97 а 01100010 98 Ь 01100011 99 с 01100100 100 d 01100101 101 е 01100110 102 f 01100111 103 g 01101000 104 h 01101001 105 i 01101010 106 j 01101011 107 к 01101100 108 1 01101101 109 m 01101110 110 n Двоичный код Десятичный код Символ 01101111 111 О 01110000 112 Р 01110001 113 q 01110010 114 г 01110011 115 S 01110100 116 t 01110101 117 U 01110110 118 V 01110111 119 W 01111000 120 X 01111001 121 у 01111010 122 Z 01111011 123 { 01111100 124 1 01111101 125 } 01111110 126 ~ 01111111 127 Таблица 1.2 Расширение СР-866 А Б В Г д Е ПТУ» ЛХ 3 И 1Г К Л М Н 0 П 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 Р С т у Ф X ц Ч ш щ Ъ Гы Ь Э Ю Я 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 а б в г д е *Я1« /IV 3 и й к л м н 0 п 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 *:•: н* 1 1 ^1 ■п =1 Ф II т1 ё JJ d 1 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 L J. т h — + 1= 1^ \Ь Ft JL Т II- = JL ТГ 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 Л т И IL 1= F ГГ tt Ф J Г 1 ■ 1 1 ■ 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 Р с т У Ф X Ц ч ш Щ ъ ы ь э ю я 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 — ± > < Г J • • ТЗГ" • • V 2 ■ 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 11 Таблица 1.3 Информация, виды информации и способы ее представления Расширение СР-1251 ъ t t » ... t t € %0 Л> < Н> К Ъ Ц 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 5 < > м п • - — □ тм л> > н> к h Ц 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 У У J та I 1 1 § Ё © е « “1 - ® 1 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 0 ± I i Г Р 11 • ё № е » j S S 1 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 А Б В Г Д Е ПТ1* лх 3 И Й К Л М Н 0 П 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 Р С Т У Ф X Ц Ч ш щ Ъ ы Ь Э Ю Я 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 а б в г Д е ж 3 и и к л м н 0 п 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 Р с т У ф X ц ч ш Щ ъ ы ь э ю я 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 Таблица 1.4 Расширение КОИ-8 (koi-8r) :i28 1 129 Г 130 1 131 L 132 J 133 h 134 135 Т 136 1 137 + 138 ■ 139 ■ 140 1 141 1 142 1 143 ! й Ш I Г ■ « V < > j б 2 О • • ’ш 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 :i60 11 161 162 ё 163 F 164 Гг 165 У 166 Т1 167 li 168 F 169 'ОТ 170 ТЬ 171 172 1Г 173 174 У 175 ; Ih i176 r 177 178 Ё 179 т 180 il 181 т 182 ТГ 183 ТГ 184 185 JL 186 Ж 187 Ф 188 189 JL ТГ 190 © 191 I ю a 6 Ц Д е Ф г X и й к л м н 0 :192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 nr ^208 я" 209 "F 210 с 211 т 212 У 213 ж 214 в 215 ь 216 ы 217 218 ш 219 “F 220 Ж 221 ч 222 ъ 223 ;ю '224 A 225 Б 226 ц 227 Д 228 Б 229 Ф 230 Г 231 X 232 И 233 |“1"’ 234 К 235 Л 236 М 237 Н 238 0 239 : li Я P ГС’ Т У лх В Ь ы 1 3 Ш Э щ Ч Ъ j240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 12 i^Bonpocbi и^задания Q Для каждой из приведенных ниже записей укажите, на каком языке она сделана — коммуникативном, формализованном или формальном. Попытайтесь определить область применения каждого из использованных языков. а) Выхожу один я на дорогу. (М. Ю. Лермонтов) б) То be or not to be. (У. Шекспир) в) 2КОН + H2SO4 = K2SO4 + 2Н2О (неизвестный автор) г) Сяпала калуша по напушке и увазила бутявку, и волит: «Калу-шата, калушаточки! Бутявка!» (Л. Петрушевская) д) (а - b)^ = - 2аЬ + (неизвестный автор) е) F=ma (И. Ньютон) ж) h (И. Дунаевский) з) PRINT X и) * На тело, погруженное в жидкость, действует выталкивающая сила, равная весу вытесненной жидкости и направленная против силы тяжести. (Архимед) к) * Через точку, не лежащую на данной прямой, можно провести ровно одну прямую, параллельную данной. (Евклид) л) * Если X, и Х2 — корни уравнения х^ + рх + q = О, то X, + Х2 = -р, а х,Х2 = Q. (Ф. Виет) Q а) Какому языку принадлежат знаки, изображенные на рисунке 1.1? Каково значение этих знаков? Назовите (или нарисуйте) другие знаки этого языка, б) Какому языку принадлежат знаки, изображенные на рисунке 1.2? Каково значение этих знаков? Назовите (или нарисуйте) другие знаки этого языка. ф ф Рис. 1.1. Рис. 1.2. Таблица 1.5 Предметная область Используемые знаки языка математика химия литература география музыка ... (предложите свой вариант) Rx R, 1-^ R, ФС Рис. 1.3. 13 Информация, виды информации и способы ее представления Таблица 1.6 А*- Е« К-.- {]• — • ф • • _ • Щ — ю» •- Б — • • • Ж» • Л • р._. X • • • • • • _ • я В.— 3—•• м — с • • • ц-.-. ы -. — Г — • И.. Н-* т- ч . Ь-« •- Д-.. й. 0 у.._ ш э • • — • • На рисунке 1.3 изображена запись информации об электронной схеме. Каковы знаки этого языка? Каков смысл каждого из этих знаков? ^ В правом столбце таблицы 1.5 укажите символы языка, которые используются для кодирования сообщений в той области, которая указана в левом столбце. Q В таблице 1.6 приведен код азбуки Морзе. а) Определите, какое сообщение передано азбукой Морзе: б) Закодируйте азбукой Морзе сообщение «Я ЛЮБЛЮ ИНФОРМАТИКУ». @ Пусть стрелка t означает перемещение на одну клетку вверх, стрелка i означает перемещение на одну клетку вниз, стрелка <------перемещение на одну клетку влево, стрелка -» — пере- мещение на одну клетку вправо. а) Закодируйте последовательностью стрелок кратчайший маршрут из клетки А в клетку В на клетчатом поле с перегородками, изображенном на рисунке 1.4. (За один ход можно переместиться ровно на одну клетку, при этом запрещается проходить «сквозь» перегородки.) б) На рисунке 1.5 изображен план лабиринта; его центр отмечен точкой. Закодируйте последовательностью стрелок путь из центра до выхода. 0 Для пяти букв русского алфавита заданы их двоичные коды: Е —001; О — 100; П — 10; Р — 101; Т — 01. Какое слово русского языка, состоящее из этих букв, закодировано двоичной строкой 101001010110100101? Рис. 1.4. 14 0 Из 5 букв русского алфавита А, М, Н, О и Р известны двоичные коды двух букв: О — 001 и Н — 101. Кроме того, известно, что двоичной строкой 010010110100101 закодировано слово РОМАН. Запишите двоичную строку, кодирующую слово НОРМА. 0 Каждая из букв А, К, О, Р, Т закодирована некоторой трехсимвольной последовательностью нулей и единиц. Известно, что слово ТРАКТОР закодировано строкой 101010100110101011010. Запишите двоичную строку, кодирующую слово: а) КРОТ, б) АРКА, в) КАРТА, г) РОТОР. (JSf Каждая из букв А, К, О, Р, Т закодирована не более чем трехсимвольной последовательностью нулей и единиц. Известно, что слово ТРАКТОР закодировано строкой 111011000111001101. Запишите двоичную строку, кодирующую слово: а) КРОТ, б) АРКА, в) КАРТА, г) РОТОР. СЦГкаждая из букв А, В, К, Н, О, Р закодирована некоторой последовательностью нулей и единиц. Известно, что слово ВОРОНА закодировано строкой 011011110100110, а слово КОРОВА — строкой 011101111010110. а) Какой строкой кодируется слово КОРОНА? б) Можно ли по этим данным определить, какой строкой кодируется слово КРОНА? в) Можно ли по этим данным определить, какой строкой кодируется слово КРАН? а) Какие десятичные коды имеют символы, содержащиеся в основной части кодовой таблицы ASCII? б) Зависит ли десятичный код цифры от того, какое выбрано расширение таблицы ASCII? Ответ «Да» надо подтвердить примером такой цифры, ответ «Нет» обосновать. Представьте двоичным кодом в трех различных кодировках текст «Победа!». Представьте десятичным кодом в трех различных кодировках текст «Любишь кататься — люби и саночки возить!» Получено несколько русскоязычных сообщений, которые не удается прочитать. Для каждого сообщения попытайтесь определить, в какой кодировке пришло сообщение и в какой было отправлено. Раскодируйте каждое сообщение (стоящий в конце пунктов символ «;» в сообщение не входит). а) =р1Хяшыр ю±хэ2; б) 9 ЪОБА ЙОЖПТНБФЙЛХ ОБ ПФМЙЮОП; в) КГ" §J п 9а®П , -Г" бг©бп у у®Пг; г) оПХУНДХ, бЙМЪ, 1-ЦН ЮОПЕКЪ ЙН ЛМЕ Б ЦНЯРХ! s) На листке бумаги было записано (по-русски) несколько терминов, относящихся к информатике. В каждом слове каждую букву заменили ее порядковым номером в алфавите (например, вместо «а» написали 1, вместо «л» — 13 и т. д.). Одно из слов выглядит теперь так: 186122118191033. Запишите это слово. 15 Информация, виды информации и способы ее представления Кодирование видеоинформации Цветное изображение на экране компьютера образуется смешением трех основных цветов: красного, синего и зеленого. Каждый основной цвет образуется свечением специального люминофора, нанесенного на экран монитора в виде небольших полосок или кружочков. Группа, скомпонованная из трех полосок разноцветных люминофоров, называется триадой. Изменение интенсивности свечения того или иного люминофора в триаде и создает нужный цвет триады, воспринимаемой человеческим глазом как единое целое. В таблице 1.7 приведено кодирование в случае, когда для каждого цвета в триаде есть только две возможности — светиться с определенной интенсивностью (кодируется символом 1), либо не светиться вообще (кодируется символом 0). Указанное кодирование цвета называется Л^В-кодировкой (от английского названия цветов — Red, Green, Blue). Любой цвет задается тройкой чисел (а, Ь, с), показывающих, в каком соотношении нужно взять три указанных цвета. Можно при этом считать, что каждое из чисел меняется в дигшазоне от 0 до 1, где числу 1 соответствует максимально возможная яркость источника света, передающего данный цвет, а числу 0 соответствует отсутствие света, несущего данный цвет. Поскольку компьютер может обрабатывать числа только ограниченной разрядности, каждый из отрезков [0; 1], в пределах которого меняются параметры а, 6 и с, делится на равные части; количество этих частей, как правило, является степенью числа 2. Каждая из точек деления определяет степень яркости, по-другому градацию, данного основного цвета, с помо- щью которого передается требуемый цвет. Для кодирования графической информации экран делят на много рядов одинаковых квадратиков. Каждый такой квадратик называется пиксель (от английского Picture’s ELe-ment — элемент картинки). Число строк на экране и количество пикселей в строке называют разрешением заданного графического режима. Таблица 1.7 Крас- ный Синий Зеле- ный Цвет 0 0 0 Черный 0 0 1 Зеленый 0 1 0 Синий 1 0 0 Красный 0 1 1 Бирюзовый 1 0 1 Желтый 1 1 0 Малиновый 1 1 1 Белый 16 ы и задания а Q Что является пикселем в случае цветного монитора и почему он так называется? Q Как получается ярко-белый цвет на экране цветного монитора? О Для хранения растрового изображения размером 128 х 128 пикселей отвели 4 Кбайта памяти. Каково максимально возможное число цветов в палитре изображения? Q Растровый графический файл содержит цветное изображение с палитрой из 256 цветов размером 10х 10 пикселей. Каков информационный объем этого файла? ^ а) Один из самых первых графических режимов, называвшийся сокращенно СОА (от Crayon Graphics Adaptor — графический адаптер «как цветной карандаш»), предусматривал 320 х 200 пикселей на экране. Каждый из пикселей мог гореть одним из восьми цветов — именно тех, которые указаны в таблице 1.7. Сколько бит требуется, чтобы закодировать изображение в этом режиме? б) Выполните то же задание для режима VGA (Video Graphics Adaptor): 640 x 480 пикселей. При этом каждый элемент триады допускает не 2, а 64 градации яркости. ф а) Вы хотите работать с разрешением 800 х 600, используя одновременно 65 536 цветов (16-битное кодирование). В магазине продаются видеокарты с памятью 256Кб, 512Кб, 1Мб, 2Мб, 4Мб. Какие карты можно покупать для вашей работы? б) Если вам необходимо разрешение 1200x 1600 пикселей и 16 777 216 цветов (24-битное кодирование — режим True-Coior; этого количества цветов достаточно для качественного воспроизведения обычной цветной фотографии), какие тогда видеокарты годятся для вашей работы? О а) При RGB-кодировании тройке чисел (1/2; 1/2; 0) соответствует коричневый цвет. Какой цвет, по вашему мнению, соответствует набору (1/4; 1/4; 0)? А набору (3/4; 3/4; 0)? б) Как при RGB-кодировании задается оранжевый цвет? @ Пусть используется режим True-Coior. Укажите цвет, который задается кодом: а) 000000000000000000000000; б) 000000001111111111111111; в) 011111110111111101111111; г) 011111110111111100000000; д) *0111111100000000011 mi 1. @ Пусть используется режим Hi-Coior. Укажите цвет, который задается кодом: а) 1111100000011111; б) 0111101111101111; в)* 1111101111100000. 17 Информация, виды информации и способы ее представления Кодирование числовой информации Знаки, посредством которых кодируется числовая информация, называются цифрами. Способ представления числовой информации с помощью цифр называется системой счисления. Различают позиционные и непозиционные системы счисления. В позиционной системе значение цифры зависит от ее расположения в записи числа. Это место называют разрядом; разряды нумеруются слева направо. В непозиционных системах значение цифры не зависит от занимаемого ею места. 4.1. Позиционные системы счисления С произвольным основанием Среди позиционных систем особую роль играют системы, в которых каждый следующий разряд в Ъ раз больше предыдущего (& — фиксированное для данной системы число, большее 1). В этом случае Ъ называют основанием системы, а саму систему счисления называют Ь-ичной. Для записи любого натурального числа в 6-ичной системе требуется Ъ цифр. Обычно используются цифры от О до & - 1^. Запись aia2...a„_ia„ является представлением числа с в позиционной системе счисления с основанием Ь, если с = ai • -н Па • -I- ... + а„_1 • + а„ • причем каждый коэффициент неотрицателен и меньше Ь. Позиционный принцип распространяется и на дробные числа: запись aia2...a„_ia„, a„ + i...a„ является представлением дробного числа с в системе счисления с основанием Ь, если с = Ui • + Па • Ъ’^-^ + ... + а„_1 • Ы -I- + а„ • + • Ь-1 ч- ... ч-• Ь”-'", где по-прежнему каждый коэффициент Ui неотрицателен и меньше Ъ. Главное удобство позиционной нумерации состоит в том, что действия над числами в такой системе счисления выполняются поразрядно. Все, что требуется знать для выполнения действий над многозначными числами, — это таблицы сложения и умножения для однозначных чисел. Если число записано не в десятичной системе счисления, то основание системы будем записывать в виде нижнего индекса справа от числа; например, ISg, 357ц. В случае, когда основание системы ясно из контекста, мы будем, как и для десятичной системы, не писать этот индекс. ^ Другие возможные варианты цифр рассматриваются в разделе 4.3. la просы и задания i " 'г. ,2 il Что такое система счисления? Что называют основанием позиционной системы счисления? 0 Что называют представлением числа в позиционной системе счисления с данным основанием? ^ Сколько цифр используется в позиционной системе счисления с основанием; а) 2; б) 8; в) 9; г) 16; д) 256; е) Ь? Существует ли позиционная система счисления, в которой для записи чисел используется ровно одна цифра? (i* Запишите наименьшее и наибольшее л-разрядные числа в системе счисления с основанием Ь, если; а) Ь = 2; л = 3; б) 6 = 3; п = 2; в) Ь = 5; л = 5. Каждую пару полученных чисел переведите в десятичную систему счисления. ^ Сравните числа; а) 1268д и 4569: б) 34537,1 и 43656, в) 88888888888888888823 и 888888888888888888823: г) 3434343434343434343434з4 и 434343434343434343434з4. id'i К чему приводит увеличение в 6 раз числа, записанного в шестеричной системе счисления? А увеличение в 36 раз? а) Составьте таблицы сложения и умножения в семеричной системе счисления. б) Используя результат пункта а, вычислите 65у + 56у и 65у • 56у. О Переведите числа 579 и 2468 в системы счисления с основанием: а) 5; б) 7; в) 9. (ц:) Переведите в восьмеричную систему счисления числа 866, 1287, 45297, 5423, 74268. Переведите в десятичную систему счисления числа 8669, 1287,,, 45297,2, 5423у, 74268д. О Определите, может ли в какой-либо системе счисления быть верным равенство: а) 7 + 8 = 14; б) 7 + 8 = 16; в) 7 + 8 = 17. В системе счисления с некоторым основанием десятичное число 12 записывается как 110. Укажите это основание. а) Определите, в какой системе счисления справедливо равенство: 112 + 211 + 12= 1001. б) Определите, в какой системе счисления справедливо равенство: 212+ 112 + 222 = 1101. (Г) Число 23, записанное в десятичной системе счисления, в некоторой другой позиционной системе счисления записывается как 32. Какое основание имеет эта система? 19 Информация, виды информации и способы ее представления ф а) Укажите все основания системы счисления, после перевода в которую десятичного числа 37 получается число, оканчивающееся на цифру 2. б) Укажите все основания системы счисления, после перевода в которую десятичного числа 33 получается число, оканчивающееся на цифру 6. ф*Число 551 записано в десятичной системе счисления. После перевода этого числа в позиционную систему счисления с иным основанием получилось число, записанное теми же цифрами, но в другом порядке. Каким может быть основание этой иной системы счисления? dif Существует ли такая позиционная система счисления, в которой число 43 является квадратом целого числа, записанного в той же системе счисления? фДля двух позиционных систем счисления с основаниями х и у выполняется равенство 488;, = 904^. Какое наименьшее значение может иметь х? ф* Для позиционных систем счисления с основаниями х, у и ху выполняется равенство 35* + 23у= 19;^,. Найдите х и у. ф Переведите в десятичную систему счисления дробные числа 86,6д, 12,87ц, 452,96,2. 54,237, 74,263д. Ответ запишите обыкновенными дробями. ф Переведите в пятеричную систему счисления дробные числа 86,6; 12,87; 40,96; 54,23; 74,268. Результат округлите до шестого разряда после запятой. ф (®/ Наиболее известная из непозиционных систем счисления — римская нумерация. В ней семь цифр: I, V, X, L, С, D, М. Они означают соответственно 1,5, 10, 50, 100, 500, 1000. Если меньшая цифра стоит справа, то она прибавляется к предыдущей, а если слева, то вычитается. а) Прочитайте числа XXII, XXIX, XXX, XXVIII, XL, XCV, XCIV. б) Запишите римскими цифрами следующие числа: 24, 25, 27, 49, 51, 55, 505, 497, 929. 4.2. Системы счисления, используемые в програ^ировании В компьютере вся информация представляется в двоичном коде. Поэтому для кодирования числовой информации применяется двоичная система счисления. Чтобы уменьшить длину записи, в программировании используются восьмеричная и шестнадцатеричная системы счисления. Десятичные, двоичные, восьмеричные и шестнадцатеричные коды первых шестнадцати натуральных чисел представлены в таблице 1.8. Для систем с основанием 6 = 2" существует простой алгоритм перевода целых чисел из двоичной системы в систему с основанием Ь. Для этого запись числа в двоичной сис- 20 Таблица 1.8 Десятичная система Двоичная система Восьмеричная система Шестнадцатеричная система 1 1 1 1 2 10 2 2 3 11 3 3 4 100 4 4 5 101 5 5 6 110 6 6 7 111 7 7 8 1000 10 8 9 1001 11 9 10 1010 12 А 11 1011 13 В 12 1100 14 С 13 1101 15 D 14 1110 16 Е 15 1111 17 F 16 10000 20 10 теме разбивают на блоки по л цифр, начиная с разряда единиц и двигаясь влево, и каждую такую группу заменяют цифрой соответствующей системы счисления (при Ь = 8 такой блок называют триадой, при 6 = 16 его называют тетрадой). Обратный перевод осуществляется расписыванием каждой цифры ее представлением в двоичной системе счисления. Аналогичный алгоритм справедлив и для 6-ичных дробей: на блоки по п цифр разбивается дробная часть, начиная от запятой и двигаясь вправо. О 0 Вопрос Ь1 и задан и я а) Переведите из десятичной в двоичную, восьмеричную и шестнадцатеричную системы счисления числа: 19, 44, 129, 561, 1322. б) §! Пользуясь инженерным калькулятором, переведите из десятичной в двоичную, восьмеричную и шестнадцатеричную системы счисления числа: 1573, 13 245, 666 666. Переведите из двоичной в десятичную систему счисления числа: 1001, 10101, 111001, 10111101. а) Переведите из шестнадцатеричной в десятичную систему счисления числа: 25, 4F, 1А7, АВС. 21 Информация, виды информации и способы ее представления б) Пользуясь инженерным калькулятором, переведите из шестнадцатеричной в десятичную систему счисления числа-D1AE, FFFF. Q Сколько существует натуральных чисел, меньших 1000, содержащих в своей записи ровно две единицы после перевода их в двоичную систему счисления? Q Переведите из двоичной в восьмеричную и щестнадцатеричную системы счисления числа: 1001, 10101, 111001, 10111101. ф Переведите числа 37, 5F, 1В7, СВА, DA1E, FFFF а) из шестнадцатеричной в двоичную систему счисления; б) из шестнадцатеричной в восьмеричную систему счисления, ф Переведите числа 35, 27, 147, 741, 3456, 7777 а) из восьмеричной в двоичную систему счисления; б) из восьмеричной в шестнадцатеричную систему счисления, ф Сравните числа, записанные в двоичной системе счисления: а) 10101 и 101010; б) 1101 и 1001; в) 111001 и 110111. Для пары чисел из пункта в определите, на сколько одно число больше другого. Ф Даны числа 35,о, Збз, ЗА,6, 1001012, 1ЗО4. Запишите эти числа в порядке возрастания. €) Составьте таблицы сложения и умножения однозначных чисел в системе счисления с основанием: а) 2; б)(^ 8; в) 16. Ф Используя результат задания 10а, найдите в двоичной системе счисления: а) суммы 11 111 + 11 111 и 101 101 + 100 011; б) разности 111 101-101 111 и 100 000- 111; в) произведения 1101 1011 и 10 101 10 101; г) частное и остаток при делении 111 111 на 100 и 100 000 на 111. 0 Используя результат задания 106, найдите в восьмеричной системе счисления: а) суммы 3333 + 5555 и 67 176 + 30 703; б) разности 111 101-101 111 и 100 000- 111; в) произведения 765 123 и 57 425 • 54 364; г) частное и остаток при делении 777 777 на 100 и 100 000 на 777. 0 (®, Используя результат задания 10в, найдите в шестнадцатеричной системе счисления: а) суммы 7777 + 5678 и АВ CDF + 20 802; б) разности 111 101 — 101 111 и 100 000- 111; в) произведения 7А5 • 1ВЗ и 5С 4D5 • F4 А6В; г) частное и остаток при делении ВВВ ВВВ на 100 и 100 000 на ВВВ. ф а) Переведите из двоичной в восьмеричную и шестнадцатеричную системы счисления числа: 1,001; 101,01; 11,1001; 10111,101. б) Переведите из восьмеричной в двоичную систему счисления числа: 2,5; 4,7; 1,57; 75,1; 77,77; 45,67. в) Переведите из шестнадцатеричной в двоичную систему счисления числа: 3,7; 6,F; 1А,7; С,ВА; FF,FF; DA,1E. f; a) Переведите из шестнадцатеричной в восьмеричную систему счисления число 2А5.СЕ. б) Переведите из восьмеричной в шестнадцатеричную систему счисления число 375,42. а) Переведите из двоичной в десятичную систему счисления числа: 100,1; 10,101; 1110,01; 1011,1101. Ответы запишите обыкновенными и десятичными дробями. б) Переведите из шестнадцатеричной в десятичную систему счисления числа: 2,5; 4,F; 1А,7; АВ,С; D1,AE; FFF.F. Ответы запишите обыкновенными и десятичными дробями. а) Используя кодовую таблицу СР-1251 (см. табл. 1.3), закодируйте фразу «Знание — сила!» в двухсимвольном алфавите 0 и 1 и полученный двоичный код запишите шестнадцатеричными цифрами. б) Выполните то же задание, используя кодовую таблицу КОИ-8 (см. табл. 1.4). Т|) Замените звездочки цифрами 0 и 1 так, чтобы получилась верная запись в двоичной системе счисления: **1** - **0* = ***. ■7) Замените звездочки цифрами так, чтобы получились верные записи примеров в двоичной системе счисления, а) ^*0*10*1 б) _**0*1* в) ^***"1* г) _*0**** |***1 ♦**1000* ♦010* *1 *01 **4с0****1 ♦ ♦♦♦ 4.3. Уравновешенные и другие системы счисления В позиционной системе счисления с нечетным основанием Ь в качестве цифр могут использоваться целые числа в диапазоне от - (6 - 1)/2 до (Ь - 1)/2. Такая система счисления называется уравновешенной. В уравновешенных системах счисления в записи «отрицательных цифр» вместо знака «—» обычно пишут черту над цифрой. В нашей стране в 70-х годах XX века был создан компьютер «Сетунь», выполнявший вычисления в троичной уравновешенной системе счисления. ОСЫ U зада! ■ г' Ь > ■ ■■•f'V'M .-it: ■Ш %-j Напишите цифры, которые используются в уравновешенной системе счисления с основанием: а) 3; б) 5; в) 11. Q Запишите числа: 3; 5; 101; 729; -4; -12; -101 а) в уравновешенной системе счисления с основанием 3; б) в уравновешенной системе счисления с основанием 5; в) в уравновешенной системе счисления с основанием 11. sjl а) Переведите в обычную десятичную систему счисления числа, записанные _в ур^1вновещенной_ системе счисления с основанием 3: 1011; 111011; 111; 10111; 111. 23 Информация, виды информации и способы ее представления б) Переведите в обычную десятичную систему счисления числа, записанные в_у|мвновешенной системе счисления с основанием 5: 12011; 1112; 11021; 2112. в) Переведите в обычную десятичную систему счисления числа, записанные в уравновешенной системе счисления с основанием 11: 15211; 5112; 11442; 2Т54. Q а) Сформулируйте правило сравнения двух целых чисел, записанных в одной и той же уравновешенной системе счисления, б) Сформулируйте правило, по которому осуществляется переход от числа, записанного в данной уравновешенной системе счисления, к противоположному числу. 0 а) Составьте таблицы сложения и умножения однозначных чисел в уравновешенной системе счисления с основанием 3. б) Составьте таблицы сложения и умножения однозначных чисел в уравновешенной системе счисления с основанием 5. Q а) Сформулируйте правило сложения двух целых чисел, записанных в одной и той же уравновешенной системе счисления, б) Сформулируйте правило умножения двух целых чисел, записанных в одной и той же уравновешенной системе счисления. Q Выполните действия в уравновешенной системе счисления с основанием 3: а) 101 + 111; _б)_11011 + 10J01; в) 1111111 + _ г) 101011+ 101011; д) 101101 - 101011; е) 10111 • 1111. Q Выполните действия в уравновешенной системе счисления с основанием 5: а) 210J2+222212; б) T2J21 + 22222; в) 22222 + 10101; г) 21012 + 22121; д) 201101 - 102011; е) 212-121. ‘•^Рассмотрим еще один пример системы счисления. Пусть т,, n?2, ..., rriif — некоторый набор попарно взаимно простых чисел. Для каждого натурального числа в его записи на /-е место поставим остаток от деления этого числа на т,. Получившуюся запись будем называть представлением числа в остаточной системе счисления по модулям т,, гпг, ..., /п*. а) В каком диапазоне может изменяться каждая из цифр числа, написанного в этой системе счисления? б) Какое наибольшее (в десятичной системе счисления) натуральное число можно записать в данной системе? в) Как производятся действия над числами в данной системе? за Измерение количества информации Понимание, что является мерой для количества информации, зависит от трактовки самого понятия информации. Каждый из получающихся в этом случае подходов к измерению количества информации представлен в этом параг- I 24 рафе. Тем не менее, независимо от подхода, единицей измерения информации является 1 бит (от английского Шпагу digiH — двоичная цифра). Обычно используются более крупные единицы измерения информации — 1 байт, 1 килобайт, 1 мегабайт, 1 гигабайт, 1 терабайт и т. д. Соотношение между этими единицами таково: 1 байт = 8 бит; 1 Кбайт = 1024 байт; 1 Мбайт = 1024 Кбайт; 1 Гбайт = 1024 Мбайт; 1 Тбайт = 1024 Гбайт. fMMiimiii % ^ Каков коэффициент пересчета байтов в килобайты; килобайтов в мегабайты? А коэффициент пересчета битов в байты? © Сколько байтов в одном мегабайте? Сколько битов в одном мегабайте? 5.1. Информационный объем сообщения Любая информация, представленная в виде сообщения, может быть закодирована в двухсимвольном алфавите. Количество символов в такой кодировке называют информационным объемом сообщения. Количество информации, закодированной одним символом двоичного алфавита, принимают за 1 бит. Для кодирования символьной информации применяется обычно 8-битный код ASCII (см. § 2) или 16-битный код UNICODE. Если сообщение закодировано в А-символьном алфавите, то информационный объем одного символа принимают равным log2 N. Этот коэффициент используется при подсчете количества информации, записанной не в двухсимвольном алфавите. Вапрось! И задания 9 а) Посчитайте (в байтах), каков информационный объем этой страницы задачника, считая, что каждый символ кодируется в ASCII. Выразите полученное число в килобайтах. б) Объем дискеты 1,44 Мбайт. Сколько страниц текста поместится на дискете, если каждая страница имеет такой же инфор-■мационный объем, как тот, что вы подсчитали, выполнив задание а? Какое кодирование вы бы предложили для языка племени Мум-бо-Юмбо, в алфавите которого 16 букв, и все большие, а цифр и 25 Информация, виды информации и способы ее представления © © © © знаков препинания и вовсе нет? Если ваш ответ — 4-битное, то найдите ошибку. Без какого символа нельзя обойтись? © ДНК человека (его генетический код) можно представить как слово в четырехбуквенном алфавите — каждая буква обозначает некоторое звено цепи ДНК. Каков информационный объем ДНК, содержащей примерно 1,5- 10^® звеньев? © Каков информационный объем музыкального фрагмента, содержащего п нот? Рассмотрите свои ответы к заданиям 6а и 66 из § 2. Сколько бит содержит сообщение о маршрутах? Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях («включено» или «выключено»). Какое наименьшее количество лампочек должно быть на табло, чтобы с его помощью можно было передать 50 различных сигналов? Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от о до 100, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений. Для передачи секретного сообщения используется код, состоящий из десяти цифр, каждая цифра кодируется одним и тем же минимально возможным количеством бит. Определите информационный объем сообщения длиной 150 символов. Представьте себе, что из туманности Андромеды (одна из ближайших к нам галактик) пришло сообщение в виде последовательности радиосигналов двух видов (один из них мы обозначили нулем, а другой — единицей): 000000000111110000000000000000000000000000000000000111 111100000000000000000000000000000000000001111100000000 000000000000000000000000000000001000000000000000000000 000000000000000000001110000000000000000000000000000000 000000001111100000000000011000000000000000000000001111 111000000000011110000000001100000000001011111010000000 011111100000000010000000000000111000000000011111111111 111111000000000000010100000000000001000000000010000000 000000001010000000000000100000000001000001111111111111 111111111111111111111111111111111111111111111111111111 1111111111111111111 а) Сколько бит информации содержит это сообщение? б) Многие ученые считают, что жители высокоразвитых цивилизаций обладают органами чувств, аналогичными нашему зрению. Используя это предположение в качестве предварительной информации о цивилизации, попытайтесь расшифровать сообщение. (Совет. Разложите число, равное количеству бит информации в этом собщении, на простые множители.) 26 Ф Сколько информации содержит следующая картинка? •к'к'к'к'к •k'k'k^ie'k'k 'к'к'к'к'к * 'kii'k 'k’k'kii'k 'k’k'k'k'kit'k i(ii -kic ie ’k'k'k'k'k * kkickk к 'k'kii kkkkkkkkkkkkkkk * * к к * * к к ***************************************** ***************************************** Ф Сколько секунд потребуется модему, передающему сообщение со скоростью 28 800 бит/с, чтобы передать цветное растровое изображение размером 640 х 480 пикселей, если цвет каждого пикселя кодируется тремя байтами? 0 В течение 5 минут было передано сообщение, объем которого составил 375 байт. Каков размер алфавита, посредством которого записано сообщение, если скорость передачи сообщения — 200 символов в минуту? 0 Юстасу (он же штандартенфюрер Штирлиц, он же полковник Исаев — главный герой произведений Ю. Семенова) необходимо передать в центр следующую радиограмму: «Дорогой Алекс! От всей души поздравляю Вас с Новым годом. Желаю здоровья, счастья и успехов в работе. Все еще Ваш, Юстас». Пеленгатор определяет место передачи, если она длится не менее 30 с. С какой скоростью (бит в секунду) должна работать радистка Кэт, чтобы не быть запеленгованной? 5.2._ Количество неопределенности. Вероятностный подход к измерению количества информации Если на некоторый вопрос можно дать однозначный ответ «Да» или «Нет», то говорят, что в ответе содержится 1 бит информации. В этом случае говорят также, что неопределенность исходной ситуации уменьшилась вдвое. Типичная ситуация состоит в том, что надо выбрать (по каким-либо свойствам) 1 элемент из множества, содержащего « элементов. Если п = 2™, то потребуется в точности т вопросов, каждый из которых вдвое уменьшает неопределенность — таким вопросом исходное множество разбивается на две части с равным числом элементов, и ответ на вопрос указывает, в которой из этих частей содержится искомый элемент. Следовательно, на выявление одного элемента требуется т бит информации. Если же п не является степенью числа 2, то количество вопросов зависит от того. 'll Мнформ(1<41^я, ьиды информт^! м пюсобы ее предстаьл<г:««| в меньшую или большую часть попадет элемент при очередном разбиении. В таком случае за количество информации принимается среднее количество вопросов при заданной оптимальной стратегии разбиения. Это количество равно log2 п (формула Хартли). В изложенной модели предполагается, что вероятность выбора любого элемента одна и та же. В случае неравновероятных исходов количество информации подсчитывается по формуле Шеннона: Я= Pi 10g2 -^+Р2 10g2 -7- + ..- +Р„ 10g2 Pi Р2 Рп где Pi, Рг, •••» Рл — соответствующие вероятности выбора элементов. Если наступление одного события приносит информацию, количество которой а наступление другого события приносит информацию, количество которой Н^, и события независимы, то событие, состоящее в том, что происходят оба события, приносит информацию, количество которой равно jFjTi -I- Цопросы и.задания J Как связано уменьшение неопределенности с количеством полученной информации? ,> В квадратной таблице размером 8x8 клеток ровно одна клетка закрашена черным цветом, остальные клетки белые. Требуется установить, где она располагается (т. е. узнать номер ряда и номер столбца, на пересечении которых находится клетка). Получена информация, что клетка стоит на диагонали, начинающейся в верхней левой клетке. Укажите в битах количество полученной информации. . J Олимпийская сборная завоевала золотые, серебряные и бронзовые медали. Каждый вечер руководитель сборной достает одну из медалей, любуется ею и кладет обратно. Информационный объем сообщения «Извлечена золотая медаль» равен 2 битам, а информационный объем сообщения «Извлечена серебряная медаль» равен 3 битам. Известно, что в копилке сборной 5 бронзовых медалей. Сколько всего медалей завоевала сборная? _ Игра Угадай-ка. Один игрок задумывает целое число из заранее определенного диапазона, например, от 1 до 16. Второй игрок, задавая такие вопросы, на которые первый может отвечать только «Да» или «Нет», должен выяснить, какое число было задумано. К примеру, можно спросить «Верно ли, что задуманное число равно 7?» или «Задуманное число больше 3?» а) Какие вопросы нужно задавать, чтобы за наименьшее число вопросов гарантированно угадать задуманное число из диапазона от 1 до 16? Какое наименьшее количество вопросов нужно задать? Сколько информации содержит исходная ситуация? 128 б) Какое количество информации мы должны получить, чтобы угадать одно из 64 первых натуральных чисел; одно из 128 первых натуральных чисел; одно из 100 первых натуральных чисел? Сколько вопросов придется задать, чтобы гарантированно получить ответ в каждом из этих трех случаев? © а) Задумывается нечетное число от 1 до 63. Сколько вопросов в игре Угадай-ка придется задать, чтобы гарантированно угадать задуманное число? б) Известно, что задуманное число меньше 1000 и является квадратом некоторого целого числа. Сколько вопросов в игре Угадай-ка придется задать, чтобы гарантированно угадать задуманное число? Сколько бит информации вы получили дополнительно, располагая сведениями, что задуманное число является не просто целым неотрицательным числом, а квадратом некоторого целого числа? © Объясните, почему в игре Угадай-ка с первыми 16 натуральными числами нельзя гарантировать угадывание числа за 3 вопроса. ©*Два игрока играют в Угадай-ку для химиков: один загадывает название химического элемента, а другой, задавая вопросы о его свойствах, должен определить загаданный элемент. Какое наименьшее число вопросов требуется, чтобы гарантированно угадать элемент? © (^ В таблице 1.9 приведены вероятности появления букв русского алфавита в произвольном тексте. Таблица 1.9 Буква Вероят кость Количество информации Буква Вероят кость Количество информации 0 0,090 й 0,012 е, ё 0,072 X 0,009 а, и 0,062 ж 0,007 т, н 0,053 ю, ш 0,006 с 0,045 Ц, Щ, э 0,003 р 0,040 Ф 0,002 в 0,035 У 0,021 к 0,028 я 0,018 м 0,026 Ы, 3 0,016 Д 0,025 ь, ъ, б 0,014 п 0,023 ч 0,013 29 Информация, виды информации и способы ее представления а) Используя эти данные, подсчитайте для каждой буквы количество информации, которое приносит ее появление в тексте. Ответы округлите до тысячных. б) Считая, что каждая буква в тексте появляется независимо от предшествующих, подсчитайте количество информации в словах ИНФОРМАЦИЯ, ИНФОРМАТИКА, ВЕРОЯТНОСТЬ. О ^ а) Загрузите какой-либо файл с достаточно длинным текстом и, используя, например, текстовый редактор, определите, с какой частотой встречаются в нем буквы русского алфавита, цифры и знаки препинания. Составьте на основании полученных данных таблицу, аналогичную таблице 1.9. Насколько ваши результаты отличаются от тех, которые приведены в таблице 1.9? б) Определите количество информации в какой-либо фразе рассматриваемого вами текста. в) Выполните задания, аналогичные пунктам а и б, для текста на иностранном языке. 5.3. Изм^ение количества информации ПО Колмогорову Академиком А. Н. Колмогоровым был предложен подход, позволяющий измерять количество информации независимо от способа кодирования. За количество информации принимается объем самого короткого сообщения, из которого можно извлечь передаваемую информацию. Вопросы И задания i ® а) Пусть требуется передать в сообщении все натуральные числа от 262 144 до 823543, включая это число. Каков информационный объем сообщения в коде ASCII? (Не забудьте о пробелах, отделяющих числа друг от друга.) б) Вместо сообщения, подготовленного вами в пункте а, можно передать следующий алгоритм; Алгоритм цел: п; { Делать от л := 262144 до 823543 { Сообщить л; } > Какой объем имеет это сообщение? @ а) Заметим, что 262 144 = 2’®, а 823 543 = 7^. Используя эту информацию, составьте еще более короткий, нежели в задании 1, алгоритм, позволяющий передать сообщение о перечислении всех чисел в диапазоне от 262 144 до 823 543. б)* Информационный объем передаваемого сообщения можно сократить за счет использования дополнительной информации о содержании сообщения. Обдумайте это и приведите примеры подобного сокращения информационного объема сообщения. Алгоритмизация, CTpyiciypbi данных программирояаиия Понятие алгоритма и исполнителя. Линейные алгоритмы Алгоритм — приводящая к определенному результату последовательность действий, допустимых для некоторого исполнителя. Исполнитель — субъект или объект, выполняющий действия согласно предписанной ему инструкции. Исполнитель может быть формальным или эвристическим. Формальный исполнитель выполняет инструкцию, не вникая в ее смысл и не принимая во внимание цель, с которой она составлена. Эвристический исполнитель согласовывает свои действия с целевыми установками и принимает решение о том, как выполнить то или иное действие, сообразуясь со смыслом инструкции. Каждый исполнитель полностью характеризуется своим набором допустимых действий и средой, в которой он существует. Запись алгоритма состоит из команд, каждая из которых указывает исполнителю, какое допустимое действие тот должен совершить, получив эту команду. Набор всех команд исполнителя называется системой команд исполнителя (сокращенно СКИ). Кроме этого, в записи алгоритма присутствуют операторы алгоритмических конструкций, определяющие порядок выполнения команд алгоритма. При отсутствии таких операторов команды, из которых составлен алгоритм, будут исполняться одна за другой в порядке их записи в алгоритме. Такой алгоритм называется линейным. 31 структур!»! Д(Й(а6в1,1(>4 №i энемвнаьа ирогрс9Мйммро№|{иь«1»1 в записи алгоритма могут присутствовать комментарии, поясняющие человеку, читающему данный алгоритм, для чего предназначено данное действие в алгоритме. Комментарии в записи алгоритма условимся выделять круглыми скобками со звездочками, например: {*комментарий*). Среда исполнителя — это совокупность объектов и связей между ними, над которыми данный исполнитель может совершать допустимые для него действия. Совокупность тех результатов, которые можно получить с помощью данного исполнителя, называется его достижимыми целями. ; 1 Какими допустимыми действиями вы снабдили бы робота, если поручить ему исполнять функции: а) почтальона: б) продавца мороженого; в) водителя автобуса: г) регулировщика. В чем проявляются эвристические особенности, когда исполнителем в каждом из указанных случаев является человек? Пусть дан отрезок АВ. Определите, для решения какой задачи предназначен следующий алгоритм: Поставить ножку циркуля в точку А. Установить раствор циркуля равным длине отрезка АВ. Провести окружность. Поставить ножку циркуля в точку В. Провести окружность. Провести прямую через точки пересечения окружностей. © а) Имеется два кувшина емкостью 7 и 11 литров. Исполнитель ДЖИНН может: набирать воду из реки в каждый кувшин; выливать из него воду: определять, налита ли вода в кувшине доверху. Составьте алгоритм, выполнив который, ДЖИНН наберет из реки 9 литров воды. б) Может ли ДЖИНН набрать 7 литров, если в его распоряжении два кувшина емкостью 6 и 8 литров? в) * Имеется два кувшина емкостью а и Ь литров. Какому необходимому и достаточному условию должны удовлетворять натуральные числа а и Ь, чтобы можно было составить алгоритм, выполнив который ДЖИНН наберет из реки ровно 1 литр воды? Имеется три кувшина емкостью 9, 15 и 25 литров. С ними управляется исполнитель ДЖИНН, который описан в задании 3. Составьте алгоритм, выполнив который ДЖИНН наберет из реки 17 литров воды. ^ Исполнитель умеет заменять в слове ровно одну букву, причем из осмысленного слова должно получаться снова осмысленное 32 С J 3 С В С Е D G F D А F А Н Е D а) Рис. 2.1 б) в) слово (иначе исполнитель ломается). Составьте алгоритмы преобразования а) слова ШАР в слово КУБ; б) слова ВОЛК в слово КОЗА. О Для каждой из фигур, изображенных на рисунке 2.1, а—в, составьте алгоритмы нахождения с помощью карандаша и линейки ее центра тяжести. О а) На одном берегу находятся три джентльмена и три дикаря. Для переправы имеется лодка, вмещающая двух человек. Если в какой-то момент дикарей на берегу окажется больше, чем джентльменов, то последние будут съедены (джентльмен будет съеден даже в том случае, если он просто выйдет на берег, где дикарей будет больше). Грести умеют все. Составьте алгоритм, позволяющий им переправиться на другой берег без человеческих жертв, б) Имеется ли алгоритм, позволяющий совершить аналогичную переправу, если на одном берегу окажутся четыре джентльмена и четыре дикаря? © а) Три рыцаря, каждый в сопровождении оруженосца, съехались на берегу реки, намереваясь переправиться на другую сторону. Им удалось найти маленькую лодку, и переправа прошла бы легко. Но одно затруднение чуть было не помешало этому. Все оруженосцы, словно сговорившись, наотрез отказались оставаться в обществе незнакомых рыцарей без своих хозяев. И все же переправа состоялась, все 6 человек благополучно перебрались на другой берег с помощью одной двухместной лодки. При этом соблюдалось условие, на котором настаивали оруженосцы. Составьте алгоритм, позволяющий совершить переправу. б) К реке подъехали четыре рыцаря с оруженосцами и обнаружили одну трехместную лодку. Могут ли они переправиться на другой берег, соблюдая условие предыдущей задачи? в) Четыре рыцаря, каждый в сопровождении оруженосца, должны переправиться через реку на лодке без гребца, которая вмещает не более двух человек. Посреди реки есть остров, на котором можно высаживаться. Составьте алгоритм, позволяющий совершить эту переправу так, чтобы ни на берегах, ни на остро- 33 Алгоритмизация, структуры данных и элементы программирования Рис. 2»2 К С к с к а) К с к к с к с к с к б) к к к с с в) ве, ни в лодке ни один оруженосец не находился в обществе чужих рыцарей без своего хозяина. © На столе лежит шесть одинаковых монет. Требуется расположить их так, чтобы центры этих монет были вершинами правильного шестиугольника. Исполнитель может только перемещать имеющиеся монеты, но не может производить никаких измерений и вычислений. а) Составьте необходимый алгоритм. б) * Составьте алгоритм при дополнительном ограничении, что ис-полнитель не может поднимать монеты над поверхностью стола. (и) Дана бесконечная полоска клетчатой бумаги. На некоторых клетках стоят фишки двух цветов — красные и синие. Исполнитель может взять две фишки, стоящие в соседних клетках, и переставить их на любые две соседние свободные клетки, не меняя расположение этих двух фишек относительно друг друга. Например, если фишки стояли так, как показано на рисунке 2.2, а, то исполнитель одним действием может преобразовать эту конфигурацию в конфигурацию, показанную на рисунке 2.2, б, но не может преобразовать в конфигурацию, показанную на рисунке 2.2, в. (На этих рисунках буквами К и С обозначены красные и синие фишки соответственно.) а) Составьте алгоритм, с помощью которого исполнитель преобразует конфигурацию, показанную на рисунке 2.2, а, в конфигурацию, показанную на рисунке 2.2, г. Фишки при этом могут оказаться совсем в других клетках полоски. б) Составьте алгоритм, с помощью которого исполнитель преобразует конфигурацию, показанную на рисунке 2.3, а, в конфи-гурацию, показанную на рисунке 2.3, б. Ф Исполнитель умеет: — умножать число на 2; — увеличивать число на 1. а) Составьте алгоритм получения числа 1000 из единицы. б) * Сколько действий в самом коротком из таких алгоритмов? к с к с к с к к к к к с с с Рис. 2.3 а) б) 134 0 Исполнитель умеет из любой дроби а/б получать любую из дробей (а - Ь)/Ь, (а + Ь)/Ь и Ь/а. Например, из дроби 5/8 можно получить дроби -3/8, 13/8 и 8/5. а) Как получить из дроби 1/2 дробь 1/4? А как получить 67/91? б) * Пусть дробь а/Ь несократима. Верно ли, что исполнитель может из нее получить любую другую обыкновенную дробь? 0С числом, записанным на доске, разрешается производить два действия: умножать на 2 и стирать у неоднозначного числа последнюю цифру. Например, из числа 56 можно получить числа 112 и 5. а) Как получить из числа 458 число 14? б) * Всегда ли с помощью указанных действий можно получить из произвольного натурального числа любое другое натуральное число? ■ВШ[ 7 1 Ветвления в алгоритме Среда, в которой действует исполнитель, может накладывать ограничения на возможность выполнения того или иного действия или последовательности действий. Чтобы исполнитель мог учитывать обстановку, сложившуюся в окружающей его среде, в том числе и в результате его собственных действий, в число допустимых действий исполнителя должны входить действия по проверке условий, относящихся к обстановке, имеющейся к данному моменту в среде, где действует этот исполнитель. Такие условия обычно записываются в форме высказываний. Если высказывание истинно (т. е. условие выполнено), то исполнитель осуществляет некоторую последовательность действий, если же высказывание ложно, то исполнитель либо выполняет другую последовательность действий, либо вообще переходит к исполнению действий, предусмотренных алгоритмом после проверки условий. Конструкция, реализующая в алгоритме указанную возможность выбора исполняемой последовательности действий в зависимости от условия, называется ветвлением. Кроме того, к ветвлениям относится и конструкция выбор. Суть этой конструкции состоит в том, что в зависимости от значения условия-селектора исполняется та последовательность действий, которая помечена данным значением. О Почему в алгоритмах приходится применять конструкцию ветв-ления? © Какие действия должны быть допустимыми для исполнителя, чтобы в алгоритмах для этого исполнителя стало возможным использовать конструкцию ветвления? 35 Алгоритмизация, структуры данных и элементы программирования 7.1. Ветвления в полной и неполной формах В алгоритмах ветвление записывается в одной из двух форм: Если (условие) то { действие; действие; — неполная форма ветвления, или Если (условие) то { действие; действие; иначе { действие; действие; ... } — полная форма ветвления. Фигурные скобки показывают, какая последовательность действий исполняется, если условие выполнено — она записана после слова то — и какая исполняется, если условие не выполнено — эта последовательность записана после слова иначе. Фигурные скобки, используемые для обрамления группы действий в алгоритме, называют операторными скобками. Если после то (или иначе) указывается только одно действие, то операторные скобки можно не писать. Напомним еще раз, что условие, которое используется в алгоритме, должно быть таким, чтобы его проверка была допустимым действием исполнителя. Само условие представляет собой некоторое высказывание, т. е. повествовательное предложение, которое либо истинно, либо ложно. Чтобы наглядно представлять формы организации действий, используют схемы алгоритмов. На рисунке 2.4 приведены схемы алгоритмов ветвлений в неполной форме и в полной форме. Рис. 2.4 а) б) -Вопросы и задания Какое ветвление называют ветвлением в полной форме, а какое — в неполной? а) Рассмотрите следующую команду, включенную в алгоритм подготовки к экзамену: Если (завтра попадется билет № 13) то { учить билет № 13; }. 36 Будет ли исполним такой алгоритм? б) Приведите примеры каких-либо не проверяемых человеком условий. е в киоск «Мороженое» завезли неограниченное количество мороженого по 3 р. 50 к. Составьте алгоритм работы продавца мороженого по обслуживанию одного покупателя. О а) Однажды Петя подошел к перекрестку, регулируемому светофором. В уме он быстро составил алгоритм перехода улицы: Остановиться; Посмотреть на светофор; Если (горит зеленый) то { дойти до середины; остановиться; } иначе { стоять; } Посмотреть на светофор; Если (горит зеленый) то { идти до конца; } иначе { стоять; } К каким неприятным последствиям может привести исполнение этого алгоритма? Напишите правильный алгоритм перехода улицы. б) Проснувшись утром, Петя почувствовал недомогание. Недолго думая, он составил для себя следующий алгоритм: Измерить температуру; Если (температура выше 37°) то { Вызвать врача; } Пойти в школу; Исправьте этот алгоритм, чтобы не допустить ухудшения состояния здоровья Пети. © Для решения каких задач предназначены следующие алгоритмы? Укажите, какие условия в них проверяются. Какие действия совершаются, если условия выполнены, и какие — если условия не выполнены? а) Найти сумму углов А и С четырехугольника ABCD; Найти сумму углов В и D четырехугольника ABCD; Если (сумма углов А и С) = (сумма углов В и D) то { Построить серединный перпендикуляр к отрезку АВ; Построить серединный перпендикуляр к отрезку ВС; Найти точку пересечения построенных перпендикуляров; } иначе { Сообщить "Построение невозможно"; } б) Найти сумму сторон АВ и CD четырехугольника ABCD; Найти сумму сторон ВС и AD четырехугольника ABCD; Если (сумма сторон АВ и CD) = (сумма сторон ВС и AD) то { Построить биссектрису угла А; Построить биссектрису угла В; Найти точку пересечения построенных биссектрис; } иначе { Сообщить "Построение невозможно"; } 37 Алгоритмизация, структуры данных и элементы программирования © На экране компьютера в каком-либо текстовом редакторе напечатано некоторое слово. Курсор находится на первой букве этого слова. Школьник выполнил следующий алгоритм: Нажать клавишу «Стрелка вправо»; Нажать клавишу «Стрелка вправо»; Если (курсор находится на букве «а») то { Нажать на клавишу с буквой «о»; } Какое слово будет напечатано на экране после выполнения этого алгоритма, если первоначально было записано слово а) слава; б) олово. О Составьте алгоритм, в результате выполнения которого запрашивается число. Если это число находится в пределах от -1 до +1, то сообщается число О, если число не находится в пределах от -1 до +1, то сообщается число 1. О Составьте алгоритм для размена к рублей двух- и пятирублевыми монетами. © Исполните алгоритм, изображенный схемой на рисунке 2.5, при различных значениях а, Ь, с. Определите, для чего предназначен этот алгоритм. 0 Среди 4 монет имеется ровно одна фальшивая, отличающаяся от остальных по массе. а) Составьте алгоритм, позволяющий за 2 взвешивания на чашечных весах без гирь выделить эту монету. Обозначьте массы монет буквами и изобразите схему алгоритма. б) * Можно ли за 2 взвешивания гарантированно определить, фальшивая монета легче или тяжелее, чем настоящая? Рис. 2.5 38 Ф а) Среди 6 монет имеется ровно 2 фальшивые монеты, отличающиеся от настоящих только по массе. Составьте алгоритм, позволяющий за 3 взвешивания на чашечных весах без гирь выделить обе фальшивые монеты. Обозначьте массы монет буквами и изобразите схему алгоритма. б) Среди 6 монет имеется ровно 2 фальшивые, обе легче настоящих, но их масса различна. Составьте алгоритм, позволяющий за 3 взвешивания на чашечных весах без гирь выделить обе фальшивые монеты. Обозначьте массы монет буквами и изоб-разите схему алгоритма. Фа) Среди 18 монет имеется ровно одна фальшивая, отличающаяся от остальных по массе. Составьте алгоритм, позволяющий за 2 взвешивания на чашечных весах без гирь определить, легче эта монета или тяжелее, б) Решите задачу из пункта а для 19 и 20 монет. W а) Есть 4 камня разной массы. За какое наименьшее число взвешиваний на чашечных весах без гирь можно выделить самый легкий и самый тяжелый камень? Составьте соответствующий алгоритм. Обозначьте массы камней буквами и изобразите схему алгоритма. б) Решите задачу из пункта а для 6 камней разной массы. Обозначьте массы камней буквами и изобразите схему алгоритма. *а) Имеется 3 камня разной массы. За какое наименьшее число взвешиваний на чашечных весах без гирь можно расположить их в порядке возрастания масс? Составьте соответствующий алгоритм. Обозначьте массы камней буквами и изобразите схему алгоритма. б) Решите задачу из пункта а для 4 камней разной массы. Обозначьте массы камней буквами и изобразите схему алгоритма. ф: в записи алгоритма конструкцию выбор будем оформлять так: Выбор ПРИ (условие_1): { действие; действие; ... } ПРИ (условие_2): { действие; действие; ... } ПРИ (условие_п): { действие; действие; ... } иначе { действие; действие; ... } Ветвь, начинающаяся словом иначе, может отсутствовать. ;Вопросыи?за Дания' а) Составьте алгоритм, который по номеру месяца сообщал бы его название. б) Составьте алгоритм, который по номеру года и названию месяца сообщал бы количество дней в данном месяце. 39 Алгоритмизация, структуры данных и элементы программирования В старояпонском календаре был принят двенадцатилетний цикл. Годы внутри цикла носили названия животных: крысы, коровы, тигра, зайца, дракона, змеи, лошади, овцы, обезьяны, петуха, собаки и свиньи. Составьте алгоритм определения по номеру года его название в старояпонском календаре, если известно, что 2008 год является годом крысы. Результаты централизованного тестирования оцениваются по 100-балльной шкале. Ученый совет одного из вузов принял следующую шкалу перевода баллов, набранных в результате тестирования, в оценку вступительного экзамена: 85 баллов и выше — оценка «5»; от 65 до 84 баллов — оценка «4»; от 40 до 65 баллов — оценка «3»; менее 40 баллов — оценка «2». Составьте алгоритм определения экзаменационной оценки в данном вузе по результатам централизованного тестирования. Составьте алгоритм, который по значению возраста пользователя сообщал бы, к какой возрастной группе тот относится: • до 13 — детство; • от 14 до 24 — молодость; • от 25 до 59 — зрелость; • после 60 — старость. Требуется по координатам точки определить номер четверти, в которой эта точка находится, или ось координат, на которой она лежит. Составьте соответствующий алгоритм. Циклы Нередко исполнителю необходимо повторить несколько раз какую-либо последовательность действий. То, сколько раз придется повторять, может быть известно заранее, до исполнения указанной последовательности, а может определяться выполнением условия, которое проверяется каждый раз перед выполнением последовательности действий или сразу после этого. Алгоритмическая конструкция, позволяющая указать исполнителю на повторяемость последовательности действий, называется циклом. Последовательность действий, которая будет выполняться в цикле, называется телом цикла. Основные виды циклов: цикл простого повторения (цикл Повторить п раз), цикл с предусловием (цикл Делать пока), цикл с постусловием (цикл Повторить ... до), цикл со счетчиком (цикл Делать от... до... с шагом...). Вид цикла указывается в его заголовке. Чтобы завершить исполнение тела цикла досрочно, используется стандартный оператор Покинь. i40 Ф. Вопросы Ф , 1 ' Г'- 'S « о Когда целесообразно применять алгоритмическую конструкцию цикл? О Для чего служит заголовок цикла? Что такое тело цикла? ® Зачем нужен оператор Покинь? 8.1. Цикл с предусловием (цикл Делать пока) и цикл с постусловием (цикл Повторить ... до> Цикл с предусловием — это цикл, в котором действия, составляющие тело цикла, исполняются до тех пор, пока остается истинным условие, записанное в заголовке цикла. В алгоритмах цикл с предусловием будем записывать в следующей форме: Делать пока (условие) { действие; действие; действие; } Цикл с постусловием — это цикл, в котором действия, составляющие тело цикла, исполняются до тех пор, пока не станет истинным условие, записанное в окончании цикла. В алгоритмах цикл с постусловием будем записывать в следующей форме: Повторять { действие; } действие; до (условие) В качестве условия обычно используется какое-либо высказывание, проверка истинности которого является допустимым действием исполнителя. В цикле с предусловием эта проверка осуществляется всегда перед началом очередного исполнения тела цикла, а в цикле с постусловием — всегда после очередного исполнения тела цикла, и никогда не совершается во время исполнения тела цикла (даже если в результате исполнения какого-либо действия высказывание становится ложным). Указанные две формы цикла с условием взаимозаменяемы, т. е. использование одного из них может быть заменено другим. Однако при решении задач на алгоритмизацию нужно стараться выбрать ту форму, которая более естест- 41 Алгоритмизация, структуры данных и элементы программирования а) б) Рис. 2.6. Схемы алгоритмов циклов: а) с предусловием; б) с постусловием венна (например, приводит к выполнению исполнителем меньшего числа действий). На рисунке 2.6 приведены схемы алгоритмов циклов с предусловием и постусловием. ОШ просы и задания 9 У’’*. V, i ^ в каких случаях применяют цикл с условием? О ф ф ф в чем разница между циклом с предусловием и циклом с постусловием? а) Имеется цикл с предусловием. Может ли так случиться, что тело этого цикла не будет исполнено ни разу? б) Имеется цикл с постусловием. Может ли так случиться, что тело этого цикла не будет исполнено ни разу? Имеется несколько одинаковых по виду монет, среди которых ровно одна фальшивая, отличающаяся от настоящей по весу. Составьте алгоритм нахождения фальшивой монеты с помощью чашечных весов без гирь, если а) известно, что фальшивая монета легче настоящей; б) неизвестно, какая монета легче — настоящая или фальшивая. Имеется несколько одинаковых по виду монет, среди которых, возможно, встречаются фальшивые. Известно, что все фальшивые монеты имеют один и тот же вес, и он меньше, чем у настоящей монеты. Составьте алгоритм нахождения всех фальшивых монет с помощью чашечных весов без гирь (по условию предполагается, что в наборе обязательно есть хотя бы одна настоящая монета). Дана полоска клетчатой бумаги, на клетках которой стоят фишки двух цветов — красные и синие — по одной фишке в каждой клетке. Число клеток в полоске конечно, но не задано. Исполнитель умеет: — определять цвет фишки, стоящей в данной клетке; — определять, последняя ли это фишка в ряду; 42 — менять местами фишки в двух соседних клетках; — перемещаться в соседнюю клетку (вправо или влево). Среди фишек, стоящих на полоске, обязательно есть хотя бы одна красная и хотя бы одна синяя. Составить алгоритм, позволяющий из произвольного расположения фишек на полоске получить расположение, при котором сначала идут подряд все синие фишки, а затем все красные. Q Рассмотрите алгоритм, представленный схемой на рисунке 2.7. При любом ли значении X при выполнении этого алгоритма будет сообщаться некоторое число? да нет Г<^Х>1> Увеличить Сообщить Хна! X- 1 Рис. 2.7 А Исполнитель умеет запрашивать число и имеющееся у него число увеличивать на 1 или уменьшать на 1. Составьте алгоритм, выполнив который исполнитель для запрошенного числа сообщит его дробную часть. Обозначьте запрашиваемое число буквой X и изобразите искомый алгоритм в ------- виде схемы. А Имеются две кучки камней, в одной 13 штук, в другой 15. Исполнитель имеет три допустимых действия: а) взять из первой кучки 3 камня и переложить их во вторую; б) взять из второй кучки 4 камня и переложить их в первую; в) проверять, остались ли в кучке камни. Исполнитель выполняет алгоритм: Делать пока ((в первой кучке есть камни) и (во второй кучке есть камни)) { Взять из первой кучки 3 камня и переложить их во вторую; Взять из второй кучки 4 камня и переложить их в первую; } Через несколько шагов исполнитель прекратил работу. Антон сказал: «Это произошло потому, что кончились камни в первой кучке». Борис сказал: «Это произошло потому, что кончились камни во второй кучке». Виктор сказал: «Это произошло потому, что исполнитель не может выполнить первое допустимое действие». Гриша сказал: «Это произошло потому, что исполнитель не может исполнить второе допустимое действие». Кто из ребят прав? ^*Автомат за один шаг преобразует данное ему натуральное число следующим образом: если число делится на 3, то он делит его на 3, в противном случае вычитает из него 1. Сколько существует натуральных чисел Л/, каждое из которых данный автомат за 10 последовательных шагов превратит в 1? 43 Алгоритмизация, структуры данных и элементы программирования 8.2. Цикл простого повторения (цикл Повторить п Конструкцию цикла Повторить п раз будем оформлять так: Повторить п раз { действие; действие; действие; } Здесь п — числовая переменная целого типа либо арифметическое выражение, значение которого также имеет целый тип (см. § 9.1). Некоторые языки программирования допускают в качестве ограничителя п числовую переменную и вещественного типа; в этом случае тело цикла исполняется [п] раз. Цикл со счетчиком — это цикл, в котором известно, сколько раз нужно исполнить тело цикла, причем значение счетчика может влиять на исполнение действий в теле цикла. В алгоритмах цикл со счетчиком будем записывать в следующей форме: Делать от К := { действие; действие; ... до ... с шагом действие; } Здесь К — целочисленная переменная (см. § 9.1); после знака «:=», слов до и с шагом могут стоять числовые константы, переменные или арифметические выражения. Слова с шагом могут отсутствовать; в этом случае после очередного исполнения тела цикла значение переменной К автоматически увеличивается на 1. Тело цикла исполняется до тех пор, пока значение переменной К не станет больше значения, стоящего после слова до. На рисунке 2.8 приведена схема алгоритма цикла со счетчиком. Рис. 2.8. Схема алгоритма со счетчиком !44 Вопросы и задания ^ А В каких случаях, на ваш взгляд, целесообразно пользоваться циклом Повторить п раз, в каких — циклом со счетчиком, а в каких — циклом с пост- или предусловием? А Определите, сколько раз исполняется тело цикла в каждом из указанных ниже случаев. а) Делать от К :=-^ flo 7 с шагом 3 { действие: действие; } б) Делать от К := -5 до -7 с шагом -2 { действие; действие; } в) Делать от /С := 9*8 { действие; 11 *3 до 3*8 + 4*4 с шагом 2 действие; } ^ Рассмотрите фрагмент алгоритма: Алгоритм Счет цел: X, К\ { Делать от К := ЗХ^ - 2Х-1до2Х-ь1с шагом (X'* - 7Х^)/2 + 5 { действие; действие; } } При каких значениях X тело цикла выполняется: а) 3 раза; б) 1 раз; в) хотя бы 1 раз; г) ни разу? На некоторых клетках бесконечного клетчатого листа бумаги лежит п плиток. Исполнитель имеет следующее допустимое действие: он снимает плитку с одной из клеток и кладет ее на клетку, симметричную исходной относительно какой-либо клетки, покрытой зеленой плиткой. Будем считать, что все плитки пронумерованы числами от 1 до п, и договоримся записывать допустимое действие исполнителя следующей командой: Отразить плитку к относительно плитки пт, Рассмотрите следующий алгоритм: Запросить л; (* запрашивается количество плиток на поле, поскольку у исполнителя нет допустимого действия, позволяющего считать плитки *) Делать от /<= 1 до л - 1 { Отразить плитку К относительно плитки К + 1; } Отразить плитку л относительно плитки 1; 45 Рис. 2.9 а) Алгоритмизация, структуры данных и элементы программирования 4 5 3 6 2 7 1 8 5 7 4 8 1 6 2 4 10 9 8 2 7 4 1 3 6 5 б) в) Как будут располагаться плитки на листе бумаги после исполнения данного алгоритма, если первоначально они располагались так, как показано на рисунках 2.9, а—в? Ф Имеется набор к палочек длиной 1 см и п палочек 3 см. Исполнитель своим действием может положить на стол палочку заданной длины в заданном положении и в заданную точку (например, горизонтально и правый конец в заданной точке). Составьте алгоритм, исполнив который указанный исполнитель или выложит из всех палочек какой-либо прямоугольник, или сообщит, что при данных /сип это сделать невозможно. Имеется 2п камней попарно различной массы. Составьте алгоритм, позволяющий за Зп -2 взвешивания на чашечных весах без гирь выделить самый легкий и самый тяжелый камень. ^ J Переменные в алгоритмах Чтобы хранить информацию, с которой работает компьютер, надо для нее выделить место в оперативной памяти и обозначить это место подходящим именем. Такое поименованное место в оперативной памяти, предназначенное для хранения информации, не подлежащей дроблению на более мелкие составные части, называют переменной. Информация, которая хранится в переменной, называется ее значением. Чтобы переменная получила некоторое значение или изменила его, используют операцию присваивания. Эту операцию будем обозначать символом «:=». Слева от знака присваивания всегда указывается имя переменной, а справа пишется выражение, состоящее из констант и имен переменных, связанных знаками операций, допустимых для данного исполнителя. В выражении могут присутствовать скобки, указывающие на изменение естественного порядка действий. 146 Кроме имени и значения, переменная имеет характеристику, которая называется тип. Он указывает, как обрабатывать ту информацию, которая хранится в переменной. Основные типы переменных: вещественный, целый, символьный, строковый, логический. i Вопросы и задания в! '•:s: ^ Что такое переменная? Q Чем характеризуется переменная? е Что такое значение переменной? Для чего переменной имя? Q Для чего нужна операция присваивания? 0 Какие типы переменных вы знаете? Какие операции можно производить над переменными каждого из известных вам типов? 9.1. Переменные числового тиню Для числовой информации обычно используются два типа переменных: целый и вещественный. Выражение, в котором фигурируют константы и переменные только числовых типов, называется арифметическим. При вычислении значения арифметического выражения действуют стандартные правила, устанавливающие старшинство операций: первой выполняется возведение в степень, затем умножение и деление и, наконец, сложение и вычитание. В языке программирования Pascal целый тип обозначается как integer, вещественный — как real. В записи констант типа real для отделения дробных знаков вместо запятой используется точка. В таблице 2.1 приведены обозначения операций, принятые в большинстве языков программирования, а также их взаимодействие с типами переменных. В таблице 2.2 приведены обозначения стандартных функций, принятых в большинстве языков программирова-нияЧ ^ в таблице 2.2 приведены обозначения стандартных функций, принятые в языке Turbo Pascal. Если учащиеся изучают другой язык программирования, то при выполнении заданий данного и последующих параграфов следует использовать обозначения того языка, который реально изучается. Ввиду возможных здесь разночтений мы, в частности, в записях алгоритмов с переменными не придерживаемся правил какого-либо языка программирования, а используем общеупотребительную математическую запись. 47 Алгоритмизация, структуры данных и элементы программирования Таблица 2.1 Операция Выражение Типы операндов Тип результата Сложение А+В Оба целые Целый Хотя бы один вещественный Вещественный Умножение А * В Оба целые Целый Хотя бы один вещественный Вещественный Вычитание А В Оба целые Целый Хотя бы один вещественный Вещественный Деление А/В Целый или вещественный Вещественный Целочисленное деление А div В Оба целые Целый Остаток при целом делении А mod В Оба целые Целый Таблица 2.2 Функция Обращение Тип аргумента Тип результата Арктангенс arctan (х) Целый или вещественный Вещественный (радианы) Дробная часть frac (х) Целый или вещественный Вещественный Квадрат sqr (X) Целый или вещественный Вещественный Корень квадратный sqrt (х) Целый или вещественный Вещественный Синус sin (х) Целый или вещественный (радианы) Вещественный Косинус cos (X) Целый или вещественный (радианы) Вещественный Экспонента (показательная функция у=е*) exp (х) Целый или вещественный Вещественный Логарифм натуральный ln(x) Целый или вещественный Вещественный Модуль аргумента abs (x) Целый Целый Вещественный Вещественный Округление round (x) Вещественный Целый Случайное число в интервале [0; 1] random — Вещественный Случайное число в интервале [0; х] random (x) Целый Целый 148 просы и задания 1^- Какие типы переменных используются для работы с числовой информацией? Какие операции над числами обычно допустимы в языках программирования? Q Запишите операцию присваивания для вычисления значения переменной, заданной формулой. Образец. Значение переменной задано формулой 4,7: у + .^4,6у X = л/0,6 + 7у = тогда оператор присваивания в языке Pascal будет иметь вид: X := (4.7 / у + sqrt(4.6*y)) / sqrt (0.6 + 7*sqr(y)). а) X в) У Д) У 7,5 + 8,7-13,34 = 14-2,8-5,6 х^ -2,4х + X + 1 х^ + 2 б) г = г) v = 2,5 а+ьх+У х+у X Ь л/а + ху -1 + у~2 +Ь2 ’ е)* X = max (у, z); ж)* у = min з)* Z = min 2х +1. х^ +1 +1 2х + 1 х + 0,5у^, max 3,3 + у‘ О Запишите в общеупотребительной математической форме следующие выражения: а) sqrt (sqr (х) + 1 )/abs(x + 1); б) а + Ь/{с + d)/{e + f/g * ft); в) (X + y)/z * х/у - z; г) sqr(sqrt(x + у) - 1) * sqrt (sqr (x + у) - 1). Q Составьте алгоритм, позволяющий по величине радиуса круга вычислить длину окружности и площадь круга. ^ Составьте алгоритм, позволяющий по значениям катетов прямоугольного треугольника вычислять длину высоты, опущенной на гипотенузу. ^ а) По стороне правильного треугольника требуется определить площадь кольца, образованного описанной и вписанной окружностями этого треугольника. Составьте соответствующий алгоритм, 49 Алгоритмизация, структуры данных и элементы программирования © б) Заданы стороны треугольника. Требуется определить площадь фигуры, заключенной между вписанной и описанной окружностями этого треугольника. Составьте соответствующий алгоритм. Q В десятиэтажном доме 5 подъездов по 60 квартир в каждом. Составьте алгоритм, позволяющий по номеру квартиры определить подъезд и этаж, где располагается данная квартира. Составьте алгоритм решения уравнения ах + Ь = 0. Значения а и Ь запрашиваются у пользователя. © Чему будут равны а и Ь после выполнения каждого из следующих алгоритмов? Сколько раз будет выполняться тело цикла в каждом из алгоритмов? а) цел: а, Ь; а := -2; Ь:=-1; Делать пока {а + Ь< а*Ь) { а := Ь + 1; Ь ;= 2*а; } б) вещ: а, Ь\ а := 13; Ь:=1; Делать пока {а-Ь>а / Ь) { а :=а-ь 10; Ь := -3*Ь; } в) цел: а, б; а := -3; 6:^-1; Делать пока (а < Ь) { Если (Ь <а -I- 3) то { а\=а-Ь\ Ь:=Ь + 2\} иначе { а := а + 2; Ь :=Ь-а; } } (U) в алгоритме нахождения суммы квадратов первых ста чисел Петя поменял местами несколько строк. Вот как выглядит его алгоритм: цел: S; К] S := 0; Делать от К= 1 до 100 { S.= S + K^\ Сообщить "Я нащел сумму. Вот она:"; Сообщить S; } Устраните путаницу в строках. 50 Ф Заданы 3 числа. Составьте алгоритм для определения того, можно ли из отрезков, имеющих длины, равные этим числам, составить треугольник. Если можно, то сообщить вид этого треугольника: остроугольный, прямоугольный или тупоугольный. 0 Электрическая цепь состоит из двух сопротивлений и Яг-Составить алгоритм, с помощью которого по сопротивлению Я всей цепи можно определить, параллельно или последовательно соединены в ней сопротивления. (Сопротивлением проводов можно пренебречь.) ^ Составить алгоритм, который по запрашиваемому номеру года сообщает, является ли этот год високосным. Ф Последовательность значений переменной X строится так: Xi = 1; Хг = 3; ... = Х„_2 - 2Х„_, для каждого п>2. а) Чему равны Xgi Х4; Х7? б) Составьте следующие алгоритмы: — нахождения первого значения, большего 1000; — нахождения суммы первых 20 значений переменной X; — нахождения первых десяти положительных значений переменной X; — нахождения наибольшего из первых 30 значений переменной X. в) Напишите и отладьте программы, реализующие составленные алгоритмы. 0 Для вычисления кубического корня из положительного числа А пользуются следующим рекуррентным соотношением: / л Xn=- 3 Хд|_ а) Составьте алгоритм приближенного вычисления кубического корня из числа А. Подумайте, какое выражение надо выбрать в качестве условия продолжения цикла. б) (р Напишите программу, реализующую составленный алгоритм. Проведите с программой вычислительный эксперимент: сколько членов последовательности нужно вычислить, чтобы получить заданную точность при различных значениях А. 0 а) Составьте алгоритм для вычисления значений функции, указанной в задании 2в, для п значений аргумента х на отрезке [-2; 2], делящих этот отрезок на п - 1 равных частей. б) р Напишите программу, реализующую составленный алгоритм. Проведите вычислительный эксперимент для л = 11, 21, 41. По результатам эксперимента постройте графики данных функций. в) р Напишите и отладьте программы построения графиков функций. г) р Реализуйте вычисление значений функции из задания 2в в Microsoft Excel. Постройте с помощью электронной таблицы график данной функции. 51 Алгоритмизация, структуры данных и элементы программирования *а) Составьте алгоритмы для вычисления значений функции, указанной в задании 2ж, для п значений аргумента х на отрезке [-3; 3], делящих этот отрезок на л - 1 равных частей. б) §1 Напишите программу, реализующую составленный алгоритм. Проведите с ней вычислительный эксперимент для п = 11, 31,61. По результатам эксперимента постройте график функции. в) Напишите и отладьте программы построения графиков функций. г) Реализуйте вычисление значений функции из задания 2ж в Microsoft Excel. Постройте с помощью электронной таблицы график этой функции. 0 а) Составьте алгоритм для определения количества цифр в записи заданного натурального числа. б) Составьте алгоритм для определения суммы цифр заданного натурального числа. в) Составьте алгоритм для определения суммы квадратов цифр заданного натурального числа. г) Р Напишите и отладьте программы, реализующие составленные алгоритмы. а) Составьте алгоритм, позволяющий для заданного натурального числа определить, сколько раз каждая из цифр от О до 9 встречается в записи числа. б) §1 Напишите и отладьте программу, реализующую составленный алгоритм. ^а) Простым называется натуральное число, имеющее ровно два делителя. Составьте алгоритм для определения наименьшего простого делителя заданного натурального числа. (Совет. Подумайте, каким будет результат, если исходное натуральное число равно 1.) б) Напишите и отладьте программу, реализующую составленный алгоритм. а) Пусть N — нечетное натуральное число, не кратное 5. Составьте алгоритм, позволяющий найти наименьшее число, составленное только из цифр 1 и делящееся на N. б) * Напишите и отладьте программу, реализующую составленный алгоритм. Проведите с ней вычислительный эксперимент для N-3] 11; 17; 31. а) Пусть переменная х принимает последовательно целые значения от 1 до N. Требуется определить, сколько раз функция — 1 у =-----, где а — натуральное число, будет иметь целочислен- X -1-1 ное значение для указанных значений переменной х. Составьте алгоритм, позволяющий ответить на этот вопрос; значения а и А/ запрашиваются у пользователя. б) * ip Напишите программу, реализующую составленный алгоритм. Проведите с ней вычислительный эксперимент для а = 2; 3; 7; 10 и Л/= 11; 17; 31. 52 (^*а) На координатной плоскости заданы три вершины треугольника А У1), В (Хг, Уг) и С (Х3, Уз), координаты которых целые числа. Составьте алгоритм, с помощью которого можно определить, лежит ли точка Р (Х4, У4) с целочисленными координатами внутри треугольника. б) На координатной плоскости заданы три вершины треугольника А (xi, У1), В (Хг, Уг) и С (Х3, Уз), координаты которых целые числа. Точка Р {Х4, У4} также с целочисленными координатами является центром окружности с целочисленным радиусом г. Составьте алгоритм, позволяющий определить, лежит ли данная окружность целиком внутри треугольника. в) § Напишите и отладьте программы, реализующие составленные алгоритмы. 'На координатной плоскости даны две точки А (х,, у,) и В (Хз, Уг), координаты которых целые числа. Они служат центрами окружностей целочисленных радиусов и Яг. Составьте алгоритм, позволяющий определить, сколько имеется точек с целыми координатами, лежащими одновременно в обеих окружностях, б) 1в Напишите и отладьте программу, реализующую составленный алгоритм. ф*а) На координатной плоскости даны два треугольника, заданные координатами своих вершин — Д (х,, у,), В (xg, Уг), С (Хз, Уз) и F(X4, У4), G (xg. Уз), Н(хе, Уб), все координаты которых целые числа. Составьте алгоритм, с помощью которого можно определить, подобны ли треугольники АВС и FGH. б) § Напишите и отладьте программу, реализующую составленный алгоритм. Составьте алгоритм нахождения максимального значения выражения 5х^ - 6у^, если натуральные числа х, у удовлетворяют неравенствам: X - 2у < 4, 2ху > 7, X -I- у < 100. Ф (§/ а) Используя графические операторы, нарисуйте домик с трубой. Сделайте так, чтобы из трубы колечками шел дым (см. рисунок 2.10 как пример некоторых кадров этого «мультфильма»), б) Выведите в правом углу картинки циферблат цифровых часов, пусть фон вне дома меняется в зависимости от времени су- О Рис. 2.10 53 Алгоритмизация, структуры данных и элементы программирования 11.25 Рис. 2.11 ток, показываемых этими часами, а в окне дома зажигается и гаснет свет (рис. 2.11). Напишите программу, которая рисует часы, причем так, чтобы они шли (см. рисунок 2.12 как пример некоторых кадров этого «мультфильма»). 9.2. Переменные символьного типа Для хранения информации, предстгшляющей собой один символ или последовательность символов, применяют переменные, которые имеют символьный тип. Сокращенно этот тип мы будем записывать как сим. Последовательность символов нередко называют строкой. Для переменных этого типа обычно рассматриваются операции соединения (по-другому, конкатенации) и вырезания, т. е. выделения части строки. Операция соединения состоит в том, что к первой строке приписывается вторая. Команду соединения будем записывать знаком «-1-», например: А + В. Здесь черюз А и В обозначены переменные символьного типа. 54 Операцию вырезания будем записывать так: ЧастьГИНФОРМАТИКА", 3, 5), где на первом месте указывается слово, из которого вырезается часть, на втором — номер места, с которого начинается вырезаемая часть, наконец, на третьем месте указывается число символов в вырезаемой части. В результате выполнения написанной команды получится слово ФОРМА. Вместо самого слова в качестве первого аргумента может указываться символьная переменная; операция тогда будет выполняться над значением этой переменной. Операцию нахождения длины слова, т. е. числа символов, из которых составлено слово, будем записывать так: ДлинаС'ИНФОРМАТИКА"). Здесь также вместо слова может быть указана символьная переменная, к значению которой применяется данная операция. В приведенном примере результатом выполнения операции является число 11. Для обеих команд кавычки являются служебным знаком, показывающим, что мы имеем дело с самим словом, а не с именем какой-либо переменной. Поэтому кавычки не учитываются при подсчете числа символов. В частности, слово может вообще не содержать символов. Такое слово называется пустым, оно обозначается как а его длина равна 0. Пустое слово надо отличать от слова " ", которое состоит из одного символа — пробела. Всевозможные слова над заданным алфавитом считаются упорядочиваемыми в алфавитном порядке. Это означает, что значения строковых переменных можно сравнивать не только на совпадение и несовпадение (равенство и, соответственно, неравенство слов), но и относительно заданного упорядочения, индуцированного порядком символов в алфавите. 1|. Вопросы и задания^ А Какие операции применяются для действий над данными символьного и строкового типов? А Найдите слово русского языка, которое больше, чем слово ПАРА, и меньше, чем слово ПАРК. А а) Каким будет результат исполнения следующего алгоритма при различных допустимых значениях входной переменной? Алгоритм Предложение сим: А, В; { Сообщить "Введите какое-нибудь личное местоимение"; Запросить А; В := "ид в кино"; I Алгоритмизация, структуры данных I 55 и элементы программирования Если (А = "Они") то { S := Д + " " + Часть(В,1, 2) + "ут” + Часть(В, 3, Длина{В)-2): } иначе { Выбор ПРИ (А = "Я"): {В := А+" "+Часть(В,1, 2) + "у"+ Часть (В, 3, Длина(В) - 2); } ПРИ (А = "Ты"): { В := Д+" "+Часть(В,1, 2) + "ешь"+ Часть(В, 3, Длина(В) - 2); } ПРИ (Часть(Д, 1, 2) = "0н"): { В \= А +" "+ Часть{В,1, 2) + "ет" + Часть(В, 3, Длина(В) - 2); } ПРИ (Д = "Мы"): { В := Д +" " + Часть(В,1, 2) + "ем"+ Часть (В, 3, Длина(В) - 2); } ПРИ (Д = "Вы"); { В := Д + " " + Часть(В,1, 2) + "ете" + Часть {В, 3, Длина(В) - 2); } } (*конец ветвления*) Сообщить В; } Объясните, почему в данном алгоритме понадобилось ветвление Если ... то... иначе... б) Составьте аналогичный алгоритм для какого-нибудь другого глагола и обстоятельства места или времени. Рассмотрите следующий алгоритм: Алгоритм сим: X, Y, Z; цел: К, Ц { Запросить X; Запросить У; Запросить Z; L := Длина(У); К:=1; Делать пока {К < Длина(Х)+1) { Если (Часть(Х, К, L) = Y) то {X := Часть(Х, 1, X - 1) + Z + Часть(Х, К+L, Длина(Х) - L); } К:=К+ 1; }(*конец цикла*) Сообщить "Вот новое слово", X; } Каков будет результат работы этого алгоритма для: а) Х= "колокол", У= "кол", Z = "к"; б) X = "поп", Y = "п", Z = "пот"; в) X = "кол", Y = "к", Z = "кок". ^ а) Дана строка. Составьте алгоритм, в результате исполнения которого будут сообщены по одному разу все содержащиеся в строке символы. б) (р Напишите и отладьте программу, реализующую составленный алгоритм. 56 А а) Даны два слова из одинакового количества символов. Расстоянием Хэмминга называется количество позиций, в которых символы одного слова не совпадают с символами второго слова. Например, в словах «пароход» и «паровоз» есть ровно две позиции — пятая и седьмая, — в которых символы первого слова не совпадают с символами второго слова. Так что расстояние Хэмминга между этими словами равно 2. Составьте алгоритм для нахождения расстояния Хэмминга между заданными словами. б) ig Напишите и отладьте программу, реализующую составленный алгоритм. А Составьте алгоритм, позволяющий узнать, имеется ли в двух данных строках хотя бы один общий символ, б) |р Напишите и отладьте программу, реализующую составленный алгоритм. А а) Заданы два слова. Составьте алгоритм, позволяющий определить, может ли второе слово быть получено из первого вычеркиванием некоторого количества символов, б) g Напишите и отладьте программу, реализующую составленный алгоритм. А а) Дана строка, состоящая из нескольких слов русского языка, разделенных пробелами. Требуется записать строку, в которой те же слова шли бы в обратном порядке. Например, из строки МАША ЕЛА КАШУ должна быть получена строка КАШУ ЕЛА МАША. Составьте соответствующий алгоритм, б) |р Напишите и отладьте программу, реализующую составленный алгоритм. ^ а) Дана строка, состоящая из нескольких слов русского языка, разделенных пробелами. Требуется сообщить слово, содержащее наименьшее количество букв (если таких несколько, сообщить любое). Составьте соответствующий алгоритм, б) Напишите и отладьте программу, реализующую составленный алгоритм. А а) Дата задана строкой в формате дд.мм.гггг (дд — число, мм — номер месяца, гггг — год). Составьте алгоритм для подсчета количества дней, прошедших от начала года до данной даты. б) Дата задана в том же формате, что и в пункте а. Составьте алгоритм для определения даты предыдущего дня и даты последующего дня. в) 1^ Напишите и отладьте программы, реализующие составленные алгоритмы. а) В строке написано несколько натуральных чисел, отделенных друг от друга символом пробел. Требуется сформировать строку, в которой через пробел записаны натуральные числа, на единицу большие тех, которые были в строке. Например, из строки 12 839 50 должна быть получена строка 13 840 51. Составьте соответствующий алгоритм. б) |р Напишите и отладьте программу, реализующую составленный алгоритм. 57 Алгоритмизация, структуры данных и элементы программирования Переменные логического типа, или, по-другому, булевы, — это переменные, принимающие только два значения. Одно из этих значений обычно обозначают Истина, другое — Ложь. Применяются также обозначения True и False, 1 и 0. Над логическими переменными выполняются логические операции и, или, не, результат применения которых задается следующими равенствами: Истина и Истина = Истина Истина и Ложь = Ложь Ложь и Истина = Ложь Ложь и Ложь = Ложь Истина или Истина = Истина Истина или Ложь = Истина Ложь или Истина = Истина Ложь или Ложь = Ложь не Истина = Ложь не Ложь = Истина В языках программирования эти операции часто обозначаются соответственно как AND, OR и NOT. Логические значения также вырабатываются при сравнении значений переменных. Например, для числовых переменных а и Ь при сравнении а > Ъ, для числовых переменных с и d при сравнении с Ф d, для логической переменной f при сравнении f = Истина. Логическое значение вырабатывается и в комбинациях операций сравнения, скажем, в такой: {х^ 4- 7л: - 15 < 0) (х > 1). Указанная комбинация имеет значение Истина, например, при х = 1,5 и при X = -9, а при X = о имеет значение Ложь. Вопросы и задания О Какие операции применяются для действий над данными логи-ческого типа? ® Пусть X — переменная целого типа. Перечислите те ее значения, при которых истинно следующее логическое выражение: а) (х^ + 4х > 15) и (x^ + 6х < 45); б) (х^ - 4х < 23) или (х^ + 6х < 17): в) ((х^ + 7х - 15 < 0) (х> 0)) и (х< 4); г) Часть ("молоток", х, 1) = Часть ("молоток". Длина ("молоток")-х, 1). а) Дан алгоритм: Алгоритм 1 вещ: уА[1:10, 1:2]; лог: q\ цел: К\ О 58 { Делать от К := 1 до 10 { Запросить А\К. 1]; Запросить А[К, 2]; } q := Ложь; Делать от К := 1 до 10 { Если {А[К, 1]2 + Д[К, 2] 2 > 25) то { Q := Истина; } } Если (Q = Истина) то { Сообщить "Есть точка, удаленная от начала координат больше чем на 5"; } иначе { Сообщить "Все точки удалены от начала координат не больше чем на 5"; } } Определите, каким будет результат исполнения этого алгоритма для массива А, заданного следующей таблицей: 1 3 -5 8 -4 0 7 1 2 4 -4 0 1 2 -4 7 6 2 -2 А: б) Дан алгоритм: Алгоритм 2 вещ: В[1:10, 1:3]; лог: q; цел: К] { Делать от /С := 1 до 10 { Запросить В[К, 1]; Запросить В[К, 2]; Запросить В[К, 3]; } q := Истина Делать от К := 1 до 10 { Если (В[К, 2f-4*B[K, 1]*В[К, 3] <0) то { q := Ложь; }} Если (q = Истина) то { Сообщить "Все квадратные уравнения имеют корни"; } иначе { Сообщить "Есть квадратное уравнение, не имеющее корней"; } } Определите, каким будет результат исполнения этого алгоритма для массива В, заданного следующей таблицей: 1 0,5 2 1 3 -1 0,5 -2 3 7 2 4 5 0 -4 -2 3 13 3 10 1 3. 1 -2 1 1 4 4 1 1 Б: Бг а) Составьте алгоритм, позволяющий проверить, состоят ли две заданные строки из одного и того же набора символов (при 59 Алгоритмизация, структуры данных и элементы программирования этом порядок символов и количество употреблений одного и того же символа может в этих строках быть различным). б) Составьте алгоритм, позволяющий проверить, состоят ли заданные несколько строк из одного и того же набора символов. Когщиество строк и строки запрашиваются у пользователя. в) W Напишите и отладьте программы, реализующие составленные алгоритмы. W а) Дан массив А [1:50] логического типа. Составьте алгоритм, при исполнении которого будет сообщено значение Истина, если такое значение имеет четное число элементов массива, и значение Ложь в противном случае. б) Решите задачу пункта а для двумерного массива Б [1; 15, 1:10]. ® Дан массив А [1:50] логического типа. Составьте алгоритм, при исполнении которого будет сообщено значение Истина, если такое значение имеет больше половины элементов массива, и значение Ложь в противном случае. 10| Вспомогательные алгоритмы ««K# и подпрограммы Принцип процедурной алгоритмизации состоит в том, что в ходе исполнения одного алгоритма возможно обращение к другим алгоритмам, которые называют вспомогательными. Соответствующие вспомогательным алгоритмам программы называют подпрограммами. Обращение к вспомогательному алгоритму производится по имени этого алгоритма. Механизм передачи необходимой информации во вспомогательный алгоритм состоит в присваивании переменным, которые называются аргументами вспомогательного алгоритма, значений, подлежащих обработке данным алгоритмом. Механизм получения результатов после исполнения вспомогательного алгоритма определяется видом данного алгоритма. Виды вспомогательных алгоритмов рассматриваются в § 10.1 и § 10.2. Вспомогательный алгоритм может не иметь аргументов или результатов. Использование вспомогательных алгоритмов позволяет: — сократить запись алгоритма за счет выделения однотипных блоков в подходящий вспомогательный алгоритм; — использовать готовые алгоритмы как блоки для сборки более сложного алгоритма (стандартные вспомогательные алгоритмы, программирование снизу вверх); — осуществлять декомпозицию сложной задачи на более простые (нисходящее программирование); — применять механизм рекурсии. 60 Алгоритм-процедура предусматривает указание прямо в этом алгоритме переменных, которым будут присваиваться результаты исполнения вспомогательного алгоритма. Вот как выглядит описание вспомогательного алгоритма данного типа: Алгоритм Имя (арг тип: переменная, тип: переменная, рез тип: переменная) тип: переменная ... ; { действие; действие; действие; } Вместо простых переменных здесь могут употребляться иные структуры данных (массивы, стеки; об этих структурах см. § 11 и § 13). Слово Алгоритм, его имя и указанные в скобках имена аргументов и результатов (вместе с их описанием) образуют заголовок вспомогательного алгоритма. Фигурирующие в заголовке алгоритма переменные называются формальными параметрами. Обращение к вспомогательному алгоритму мы будем указывать оператором Вызвать. Записывать обращение к вспомогательному алгоритму будем так: Вызвать Имя (выражение, выражение, переменная, ...) переменная. Выражения, стоящие на местах формальных аргументов, и переменные, указанные на местах результатов, называются фактическими параметрами. Типы выражений и переменных, являющихся фактическими параметрами, должны совпадать с типами формальных переменных, на местах которых они находятся. Вспомогательный алгоритм для своей работы может использовать собственные (внутренние) переменные. Такие переменные называются локальными. Их значения не идентичны значениям одноименных структур, данных в основном алгоритме. В схемах обращение к вспомогательному алгоритму изображается так, как показано на рисунке 2.13 Рис. 2.13 Изображение обращения к вспомогательному алгоритму в схемах алгоритмов 61 Алгоритмизация, структуры данных и элементы программирования Ё Вопросы И задания о Для чего нужны аргументы и результаты вспомогательного алгоритма? SB чем разница между формальными и фактическими параметрами? Пусть для решения какой-то задачи вы решили воспользоваться готовым вспомогательным алгоритмом. Нужно ли вам знать, какие локальные переменные использовал составитель этого вспомогательного алгоритма? Какая информация необходима вам, чтобы воспользоваться данным вспомогательным алгоритмом? О Рассмотрите следующий алгоритм дежурного по столовой в военно-спортивном лагере. Алгоритм Дежурство { Если (наступило время завтрака) то { Войти в столовую; Расставить на столах тарелки; Разложить на столах ложки; Расставить на столах стаканы; Поставить на стол хлебницы с хлебом; Поставить на столы по два чайника с чаем; Поставить на столы по кастрюле с кашей; Впустить пришедших в столовую; } Если (завтрак закончился) то { Вытереть столы; Уйти из столовой; } Если (наступило время обеда) то { Войти в столовую; Расставить на столах тарелки; Разложить на столах ложки; Расставить на столах стаканы; Поставить на стол хлебницы с хлебом; Поставить на столы по два чайника с компотом; Поставить на столы по кастрюле с супом; Впустить пришедших в столовую; Разнести второе; } Если (обед закончился) то { вытереть столы; уйти из столовой;} Если (наступило время ужина) то { Войти в столовую; Расставить на столах тарелки; Разложить на столах ложки; Расставить на столах стаканы; Поставить на стол хлебницы с хлебом; Поставить на столы по два чайника с чаем; Впустить пришедших в столовую; } Если (ужин закончился) то { Вытереть столы; Уйти из столовой;} } 62 Выделите в указанном алгоритме блоки однотипных действий и оформите их в виде вспомогательного алгоритма. Какие формальные параметры удобно иметь в таком вспомогательном алгоритме? Сократите запись исходного алгоритма за счет обращения к составленному вами вспомогательному алгоритму. ® Имеется следующий вспомогательный алгоритм: Алгоритм Воздействие, (арг предмет: х, у, z; время: f; рез предмет: х) { Поместить у на х; Подождать t минут; Удалить у с помощью z; } Запишите команды вызова этого вспомогательного алгоритма, выполнив которые исполнитель (человек): а) выведет пятно с куска ткани при помощи пятновыводителя и воды; б) вымоет окно; в) съест ложку варенья; г) почистит зубы. Придумайте еще какую-нибудь задачу, которую можно решить с помощью алгоритма Воздействие. О Выполнив задание 3 из §7.1, вы составили алгоритм работы продавца мороженого по обслуживанию одного покупателя. Оформив этот алгоритм как вспомогательный, составьте алгоритм обслуживания тем же продавцом очереди за мороженым. О Изонить. Известен следующий прием изготовления узоров сплошной нитью. Окружность делится точками на п частей; сама окружность не рисуется. Затем выбирается натуральное число к и, начиная с некоторой точки, отсчитывается к-я точка против часовой стрелки. Первая точка соединяется со второй точкой нитью (рис. 2.14, а). Затем делается шаг в соседнюю точку по часовой стрелке (нить проходит по изнанке и поэтому не видна). После этого операция повторяется (на рисунках 2.14, б и 2.14, в изображены результаты исполнения второго и четвертого шагов). й= 19 к^7 й = 19 к = 7 й = 19 к = 7 а) Первый шаг Рис. 2.14 б) Второй шаг в) Четвертый шаг 63 Алгоритмизация, структуры данных и элементы программирования л = 19 к = 1 Процесс заканчивается, когда очередная точка начала линии повторится (на рисунке 2.15 показан окончательный узор). Составьте алгоритм, согласно которому компьютер по заданным п \л к рисовал бы узор, образованный нитью указанным способом. (Совет. Подумайте, какие вспомогательные алгоритмы здесь цел^ообразно создать.) б) * Напишите программу и комплекс подпрограмм, соответствующие составленным алгоритмам. Протестируйте работу вашего программного комплекса. Проведите вычислительный эксперимент для выяснения, при каких п \л к в создаваемом узоре используются все точки, а сам узор представляет собой замкнутую линию. в) * Попытайтесь на основе данных вашего вычислительного эксперимента из пункта б сформулировать условие для пик, при котором получается узор, образованный замкнутой ломаной линией, имеющей вершинами все п точек. г) * Вместо окружности можно за исходный контур взять какую-нибудь другую замкнутую линию, например овал или границу полукруга (рис. 2.16 и 2.17). Составьте алгоритмы рисования соответствующих узоров. Рис. 2.15 « = 19 к = 7 и = 19 к^7 Первый шаг ВИС.2.1Д. Окончательный узор « = 16 к = 6 Первый шаг Рис. 2.17 Л = 16 к = в Окончательный узор 64 10.2. Вспомогательный алгоритм-функция Алгоритм-функция — это вспомогательный алгоритм, результат которого присваивается переменной не внутри этого алгоритма, а в основном алгоритме. Заголовок алгоритма-функции будем записывать так: Алгоритм тип: Имя (арг тип: переменная, переменная, ...) Переменные в заголовке выступают формальными параметрами алгоритма-функции. Вызов алгоритма-функции осуществляется в команде присваивания: а Имя(переменная, переменная, ...) Здесь переменные — это фактические параметры. Вопросы и задания 1 © в чем состоит различие между процедурой и алгоритмом-функцией? Что у них общего? О Составьте алгоритм-функцию, вычисляющую кубический корень из числа согласно рекуррентному соотношению, приведенному в задании 15 из § 8.1. Воспользуйтесь этим вспомогательным алгоритмом для составления алгоритма решения кубического уравнения )^ + px + q = 0 по формуле Кардано 2 4 27 V 2 V 4 27 а) Составьте алгоритм-функцию, аргументом которого служит натуральное число N, а результатом — натуральное число, записанное теми же цифрами в обратном порядке. б) Палиндромом называется число (или слово), которое читается справа налево так же, как и слева направо. Используя алгоритм-функцию, составленный при выполнении пункта а, составьте алгоритм, позволяющий для заданного числа выяснить, является ли оно палиндромом. в) Составьте алгоритм, позволяющий найти количество натуральных чисел-палиндромов в заданном интервале (а; Ь). г) “ Напишите и отладьте программы, реализующие составленные алгоритмы. О Число 153 обладает удивительным свойством — оно равно сумме кубов своих цифр. Составьте алгоритм, позволяющий найти все натуральные числа, обладающие таким свойством. (Совет. Воспользуйтесь решением задачи 18г из §9.1 и запишите нахождение суммы кубов цифр числа в виде алгоритма-функции.) Выполнив задание 20 из § 9.1, вы составили алгоритм нахождения наименьшего простого делителя. © 65 Алгоритмизация, структуры данных и элементы программирования а) Используя этот алгоритм как основу, составьте алгоритм-функцию, аргументом которой служит натуральное число, большее 1, а результатом — наименьший простой делитель этого числа. б) Используя алгоритм-функцию, составленную в пункте а, составьте алгоритм нахождения суммы всех различных простых делителей данного натурального числа. Если исходное число 1, то сообщить: «Искомая сумма не существует». в) Используя алгоритм-функцию, составленную в пункте а, составьте алгоритм для разложения на простые множители заданного натурального числа (т. е. найти все простые делители числа и для каждого простого делителя найти показатель наибольшей степени, на которую делится исходное число). Если исходное число 1, то сообщить: «Искомое разложение не существует». г) §! Напишите и отладьте программы, реализующие составленные алгоритмы. ф а) Алгоритм Евклида. Для нахождения наибольшего общего делителя двух натуральных чисел тип Евклид предложил следующий метод. Разделить число m на п с остатком. Если остаток г равен О, то процесс закончен и НОД (т, п) = п. В противном случае разделить п на г с остатком г,. Если остаток г, равен О, то процесс закончен и НОД (т, п) = г^. В противном случае разделить г на с остатком Гг. И т. д. Запишите этот метод нахождения наибольшего общего делителя в виде алгоритма-функции со следующим заголовком: Алгоритм цел: НОД (арг цел: т, п) б) Натуральные числа тип называются взаимно простыми, если НОД (т, п) = 1. Функция, сопоставляющая каждому числу п количество натуральных чисел, не превосходящих л и взаимно простых с ним, называется функцией Эйлера и обозначается (р (п). Используя алгоритм-функцию, составленную при выполнении пункта а, составьте алгорим-функцию, подсчитывающую значение ф (л) для каждого натурального п. в) Через ф (п) обозначим функцию, которая каждому натуральному числу л сопоставляет сумму натуральных чисел, не превосходящих л и взаимно простых с ним. Используя алгоритм-функцию, составленную вами при выполнении пункта а, составьте алгоритм-функцию, подсчитывающую значение ф (л) для каждого натурального л. г) Напишите и отладьте программы, реализующие составленные алгоритмы. Проведите вычислительный эксперимент, подсчитывая для раз-Ф(л) личных п значение Ф(п) Как связано это отношение с вели- чиной л? Особое внимание обратите на случай, когда л = 1. д) Объясните результаты вашего эксперимента. 166 10.3. Рекурсия В общем случае рекурсией называется ситуация, когда алгоритм непосредственно или через другие алгоритмы вызывает себя в качестве вспомогательного. Сам алгоритм при этом называется рекурсивным. Вопросы и за да н и я i - I О Рассмотрите следующий алгоритм, использующий вспомогательный алгоритм-функцию Оборот. Алгоритм сим: А\ С; { Запросить А\ С := Оборот(А); Сообщить С; } Алгоритм сим: Оборот (сим: В) { Если (Длина(Б) = 1) то { Оборот := В; } иначе { Оборот := Часть [В, Длина(В), 1) + Оборот(Часть {В, 1, Длина(В)- 1)); } } Что будет сообщено при применении этого алгоритма к словам: а) марс; б) топор; в) огород; г) шалаш. 0 Рассмотрите следующий алгоритм, использующий алгоритм-функцию НОД (х, у), описанную в задании 4а из § 10.2, и алгоритм-функцию ФОК (х). Алгоритм цел: х; { Запросить х; X := ФОК(х); Сообщить х; } Алгоритм цел: ФОК(цел: х) { Если (х= 1) то { ФОК := 1; } иначе { ФОК:= ФОК(х- 1)* х / НОД(ФОК(х- 1), х); } } а) Что будет сообщено при выполнении этого алгоритма для чисел 1; 4; 8? б) Напишите нерекурсивный алгоритм, вычисляющий для натурального числа X тот же результат. О Древняя легенда гласит, что при сотворении мира в одном из буддийских храмов была положена бронзовая плита с тремя стержнями и на один из них были нанизаны 64 золотых диска так, как показано на рисунке 2.18. Монахи этого храма должны 67 Алгоритмизация, структуры данных и элементы программирования перенести все диски с одного стержня на другой, соблюдая следующие правила: 1) за один раз можно переносить только один диск; 2) нельзя класть больший диск на меньший; 3) переносить диск можно с любого стержня на любой. ____________ Согласно легенде, как только все диски соберутся на другом стержне, наступит конец света. Составьте алгоритм перемещения дисков с одного стержня на другой. I а) Составьте рекурсивный алгоритм для подсчета суммы квадратов цифр для запрашиваемого натурального числа п. Сравните его с нерекурсивным алгоритмом, который вы составили, выполнив задание 18в из § 9.1. б) Составьте рекурсивный алгоритм для подсчета произведения цифр для запрашиваемого натурального числа п. I Составьте алгоритм для определения наибольшего простого делителя для запрашиваемого натурального числа. (Совет. Воспользуйтесь алгоритмом, который вы составили, выполнив задание За из § 10.2.) I* Составьте алгоритм для определения всех перестановок, которые можно составить из чисел 1, 2...п (п — натуральное число). На вечеринку пришло п гостей-мужчин, каждый из которых был в шляпе. После вечеринки каждый из них ушел, надев не свою шляпу. Составьте алгоритм для определения всех вариантов распределения шляп по гостям после вечеринки (для удобства можно считать, что гости и их шляпы перенумерованы натуральными числами от 1 до п). 10.4. Нисходящее и восходящее программирование Основной метод решения сложной задачи состоит в ее разбиении на более простые задачи и/или выделение в ней таких задач, решение которых уже известно. В алгоритмизации подход, связанный с разбиением на более простые задачи, называют методом нисходящего программирования (программированием сверху вниз); второй подход, при котором требующийся алгоритм собирается из готовых вспомогательных алгоритмов, называют методом восходящего программирования (программированием снизу вверх). Готовые вспомогательные алгоритмы, оформленные так, чтобы ими можно было легко пользоваться при конструировании других алгоритмов (нередко они оформлены как алгоритмы-функции), обычно называются стандартными и размещаются в библиотеке стандартных алгоритмов. Соответствующие подпрог- 168 раммы тоже называются стандартными и размещаются в библиотеке стандартных подпрограмм. Вопросы и задания Q а) Разработайте проект решения следующей задачи: Известно, что 1 января 2000 года — суббота. Требуется определить день недели любого дня любого месяца любого года в XXI веке. Дата запрашивается в формате дд.мм.гггг; если вводится несуществующая дата, например, 31.06.2008 или 29.02.2007, то необходимо сообщить об этом. Реализуйте этот проект, написав соответствующие основной и вспомогательные алгоритмы. б) §! Напишите программу и комплекс подпрограмм, соответствующие алгоритмам вашего проекта. Протестируйте работу вашего программного комплекса. @ а) Разработайте проект решения следующей задачи при условии, что будут обрабатываться не более чем 10-разрядные целые числа. Напечатать число 2" в десятичной записи для заданного п > 40. Реализуйте этот проект, написав соответствующие основной и вспомогательные алгоритмы. (Совет. Обдумайте, какую структуру данных здесь целесообразно использовать для хранения ци(^ этого числа.) б) Э Напишите программу и комплекс подпрограмм, соответствующие алгоритмам вашего проекта. Протестируйте работу вашего программного комплекса. Получите результаты для л в диапазоне от 41 до 50. О Натуральное число а-^а2...Эп--{а„ называется самоделящимся, если для любого к^п его первые к цифр образуют число, делящееся на а^ (т. е. число a^a2--.ai< делится на а/^). Например, числа 217 и 459 являются самоделящимися, а число 235 нет. Разработайте проект решения следующей задачи. Для заданных натуральных чисел т\лп (т<п) найти количество самоделящихся чисел, заключенных между тип. Реализуйте этот проект, написав соответствующие основной и вспомогательные алгоритмы. О Простые числа вида 2” + 1 называются числами Ферма. а) Разработайте проект решения следующей задачи. Указать те натуральные значения п, при которых число 2" + 1 простое. Реализуйте этот проект, написав соответствующие основной и вспомогательные алгоритмы. (Совет. Обдумайте, для каких п можно, ничего не вычисляя, сразу сказать, что данное число не является простым.) б) §1 Напишите программу и комплекс подпрограмм, соответствующие алгоритмам вашего проекта. Протестируйте работу вашего программного комплекса (для проведения теста укажем. 69 Алгоритмизация, структуры данных и элементы программирования что при п = 8 получается простое число, а при п = 32 мое). Получите результаты для всех п< 100. состав- о* Натуральное число называется сверхпростым, если оно само простое и остается простым при любой перестановке его цифр. а) Разработайте проект решения следующей задачи. Для данного натурального числа п найти все п-значные сверхпростые числа, в записи которых имеется хотя бы две различные цифры. Реализуйте этот проект, написав соответствующие основной и вспомогательные алгоритмы. б) Напишите программу и комплекс подпрограмм, соответствующие алгоритмам вашего проекта. Проведите вычислительный эксперимент для разных п. Для какого наибольшего п вам удалось найти все сверхпростые числа? (Результат можно признать хорошим, если п > 50.) ® il(^ В 1742 г. математик Гольдбах высказал гипотезу, что каждое нечетное число, начиная с 7, представимо в виде суммы трех простых чисел. Почти 200 лет решение проблемы не удавалось сдвинуть с мертвой точки. В 1934 году академик И. М. Виноградов доказал, что существует некоторое число N, такое, что все нечетные числа, большие чем Л/, представимы в виде суммы трех простых чисел. Причем это число N было вычислено (К. Бо-роздкин): Л/ = е® ’ , где число е~ 2,71828. Число N имеет 4 008 659 цифр. К сожалению, мощности современных компьютеров все еще не хватает, чтобы проверить все нечетные числа, меньшие этого N. Попытайтесь как можно для большего количества нечетных чисел проверить гипотезу Гольдбаха. Игра «Жизнь». Эту игру придумал Д. Конуей. На бесконечном клетчатом листе живут колонии закрашенных клеток. У каждой клетки 8 соседей. Клетки рождаются и умирают, а их колонии эволюционируют во времени по определенным правилам. Вот эти правила. 1) Если закрашенная клетка имеет четыре или более закрашенных соседей, то она умирает (т. е. перестает быть закрашенной) от перенаселенности. 2) Если закрашенная клетка не имеет закрашенных соседей или имеет ровно одного такого соседа, то она умирает от недостатка общения. 3) Если незакрашенная клетка имеет ровно трех закрашенных соседей, то она закрашивается (в этом случае говорят, что родилась новая закрашенная клетка). Время в этой игре течет дискретно, т. е. по шагам. За один шаг с каждой клеткой происходит (или не происходит) изменение, описанное выше указанными правилами. Пусть на поле имеется некоторая колония. Разработайте проект, позволяющий наблюдать на экране компьютера жизнь данной колонии клеток. Проследите, как эволюционируют разные колонии из четырех, пяти, шести, семи, восьми клеток. 70 Массивы Массив — это набор однотипных данных, снабженных системой из одного или нескольких индексов, к£1ждый из которых принимает последовательные целые значения^. Количество индексов называют размерностью массива, тип входящих в него элементов — типом данного массива. Чтобы задать массив, надо указать его имя, тип, диапазон изменения каждого индекса, например, вещ: М[1:14, 1:25, 1:70]. Для обращения к элементу массива используют имя массива и значения индексов, определяющих данный элемент. Обычно значения индексов указываются после имени массива в скобках через запятую. Каждый элемент массива удобно представлять себе как отдельную переменную. Поэтому к нему можно обратиться и присвоить то или иное значение точно так же, как и для самостоятельной переменной. Одномерный массив часто называют линейным и обычно представляют в виде строки. Двумерный массив можно представлять себе как прямоугольную таблицу; первый индекс соответствует номеру строки, второй — номеру столбца. На рисунке 2.19 показано, как в таблице располагаются элементы двумерного массива А[1:3, 1:4]. Я А[1,1] А[1,2] А[1,3] А[1,4] А[2,1] А[2,2] А[2,3] А[2,4] А[3,1] А[3,2] А[3,3] А[3,4] Рис. 2.19 I Вопросы и задан и я В .’я\'гг О Могут ли элементы массива иметь разный тип? @ Может ли массив не содержать ни одного элемента? ® Сколько элементов содержит массив: а) А[0:3]; б) В[-2:5]; в) С[0:5, -3:0]. О Какие значения линейного массива М будут сообщены при выполнении следующего алгоритма: ^ Более точно, в качестве индексов может выступать любой перечислимый тип. Поэтому, кроме целого типа, для индексирования элементов могут использоваться типы символьный (char) и логический (boolean). Однако для простоты мы в дальнейшем в описаниях массивов будем использовать только целочисленный тип. 71 Алгоритмизация, структуры данных и элементы программирования Алгоритм цел: /, М[1:6]: { Запросить М[1:6]; Делать от / := 2 до 6 { М[1] :=М[1] + М[1-Ц-, } (*конец цикла*) Делать oj / := 1 до 6 { Сообщить М[1\\ } } Если массив задан: а) таблицей 2.3; б) таблицей 2.4? Таблица 2.3 Таблица 2.4 2 1 -3 2 1 -1 -1 0 -1 2 0 1 ф Какое значение переменной К будет сообщено при выполнении следующего алгоритма: Алгоритм цел: /, К’М[1:6]; { Запросить М[1:6]: К:= 0; Делать от / := 1 до 6 { Если {М[1] < 1) то { K■.= K+^ ■, } } (*конец цикла*) { Сообщить К\ } } Если массив задан: а) таблицей 2.3; б) таблицей 2.4? © Какие значения линейного массива М будут сообщены при выполнении следующего алгоритма: Алгоритм цел: I, { Запросить МП:61: Делать от / := 1 до 6 { Если {/ mod 2 = 0) то { M[f\ := М[1] * (-1); } Сообщить М[1]; } (*конец цикла*) } Если массив задан: а) таблицей 2.3; б) таблицей 2.4? © а) Дан двумерный числовой массив А [1:15, 1:10] целого типа. Составьте алгоритм, который по данному массиву А строит массив В той же размерности. В массиве В элемент В [/, /] имеет значение «Четное», если число А [/, J] четное, и значение «Нечетное» в противном случае. б) Р Напишите и отладьте программу, реализующую составленный алгоритм. 72 @ а) Составьте алгоритм, с помощью которого массив А [1:100] целого типа будет заполнен первыми ста простыми числами’, б) Напишите и отладьте программу, реализующую составленный алгоритм. © а) Составьте алгоритм, с помощью которого в заданном массиве А [1:100] целого типа будут найдены те элементы, которые являются степенями числа 2. Найдите сами числа и их индексы в массиве. б) Напишите и отладьте программу, реализующую составленный алгоритм. dJ) а) Составьте алгоритм, с помощью которого в заданном массиве А [1:100] целого типа будут найдены те элементы, которые являются простыми числами. Найдите сами числа и их индексы в массиве. б) ® Напишите и отладьте программу, реализующую составленный алгоритм. Ф Прямоугольная таблица задана с помощью числового массива А [1:20, 1:34]. Составьте алгоритмы, позволяющие определить, симметрична ли эта таблица относительно: а) вертикальной оси, проходящей через центр таблицы; б) горизонтальной оси, проходящей через центр таблицы; в) точки, находящейся в самом центре таблицы. Напишите и отладьте программы, реализующие составленные алгоритмы. 0 Квадратная таблица задана с помощью числового массива А [1:20, 1:20]. Составьте алгоритмы, позволяющие определить, симметрична ли эта таблица относительно: а) диагонали, идущей из левого нижнего угла таблицы в правый верхний угол; б) диагонали, идущей из левого верхнего угла таблицы в правый нижний угол; в) обеих диагоналей. Напишите и отладьте программы, реализующие составленные алгоритмы. 0 Гусеница, сидящая на дереве, в солнечный день поднимается на 3 см вверх, а в пасмурный день спускается на 2 см вниз. Если в какой-то момент гусеница доползает до вершины или до корня дерева, то она останавливается и больше ни в этот день, ни в последующие дни никуда не ползет. Дан линейный массив, содержащий 30 элементов (результаты наблюдений погоды в течение 30 последовательных дней); каждый элемент — буква П или С в зависимости от того, пасмурным или солнечным был день. Составьте алгоритм, позволяющий по начальному местоположению гусеницы на дереве определить ее местонахождение по истечении 30 дней. 0 а) Таблица, состоящая из 25 столбцов и 20 строк, задана при помощи двумерного числового массива А [1:20, 1:25] целого типа. Составьте алгоритм, который формирует два одномер- ’ Определение простого числа дано в задании 20 из § 9.1. 73 Алгоритмизация, структуры данных и элементы программирования который для каждой строки находит ее а затем из всех найденных элементов ных массива Б [1:25] и С [1:20]; в массиве В располагаются максимальные элементы каждого столбца (первый элемент массива — максимальный элемент первого столбца массива А, второй элемент — максимальный элемент второго столбца массива Лит. д.); в массиве С аналогично располагаются максимальные элементы строк массива А. б) Напишите и отладьте программу, реализующую составленный алгоритм. 0 Таблица, состоящая из 25 столбцов и 20 строк, задана при помощи двумерного числового массива А [1:20, 1:25]. а) Составьте алгоритм, который для каждой строки находит ее максимальный элемент, а затем из всех найденных элементов выбирает наименьший. б) Составьте алгоритм, минимальный элемент, выбирает наибольший. в) §1 Напишите и отладьте программу, реализующую этот алгоритм. Проведите вычислительный эксперимент, позволяющий накопить информацию о том, для какого алгоритма в результате получается большее число: максимальное число из минимальных или минимальное из максимальных. г) Попытайтесь теоретически обосновать результат, наблюдавшийся вами в вычислительном эксперименте, описанном в пункте в. 0 Элемент двумерного числового массива, рассматриваемого как таблица, называется точкой локального минимума, если он не превосходит ни одного из своих восьми соседей. а) Дан двумерный числовой массив >4 [1:25, 1:20] вещественного типа. Составьте алгоритм, который отыскивает все точки локального минимума. б) Напишите и отладьте программу, реализующую составленный алгоритм. 0 Дана таблица результатов шахматного турнира. Составьте алгоритм определения победителя этого турнира. 0 Прямоугольная таблица представлена массивом А [1:20, 1:30]. а) Составьте алгоритм, с помощью которого можно поменять местами две заданные строки. б) Составьте алгоритм, с помощью которого можно поменять местами два заданных столбца. в) §! Напишите и отладьте программы, реализующие составленные алгоритмы. 0 Дан двумерный массив А [1:25, 1:2], в котором записаны координаты 25 точек плоскости. Составьте алгоритм поиска двух самых удаленных друг от друга точек. фДан линейный массив Д [1:100] целого типа. Составьте алгоритм, позволяющий в этом массиве найти самую длинную последовательность, состоящую из подряд идущих положительных чисел. 74 0 Электрическая цепь собрана из п сопротивлений. Все сопротивления соединены параллельно (рис. 2.20). Значения сопротивлений хранятся в одномерном массиве вещественного типа. Составьте алгоритм, позволяющий найти сопротивление данной цепи. (Совет. Составьте подходящее рекуррентное соотношение.) ^ В вещественном массиве 4 [1:п] заданы элементы Д[1]=а и А[п] = Ь. Составьте алгоритм, который по запрашиваемым числам а, Ь и п заполнил бы массив А так, чтобы все элементы, кроме первого и последнего, были бы средним арифметическим двух своих соседей. Магическим квадратом порядка п называется таблица, имеющая п строк и п столбцов, заполненная натуральными числами от 1 до так, что сумма чисел в каждой строке, в каждом столбце и на каждой диагонали одна и та же. а) Составьте алгоритм, позволяющий для заданной таблицы проверить, является ли она магическим квадратом. б) Составьте алгоритм, позволяющий построить все магические квадраты порядка 3. в) * Составьте алгоритм, исполняя который для заданного натурального числа п можно построить хотя бы один магический квадрат порядка п или сообщить, что такого квадрата не существует. ф*Дан многочлен f (х) = Зо + а,х + + ... + а„х", где п < 100. Его коэффициенты располагаются в одномерном массиве Л [1:100] следующим образом: при / < п, при / > п. A[i] {o' а) Составьте алгоритм, определяющий по заполненному массиву А степень многочлена (если многочлен нулевой, то нужно сообщить, что степень не определена). б) Схема Горнера. Для вычисления частного и остатка при делении многочлена f (х) на двучлен х - а применяют так называемую схему Горнера. Вот ее описание. Задан многочлен f (х) = Bq + а,х + ЗгХ^ + ... + a„x’'. Записываем в строку все коэффициенты многочлена, начиная со старшего: Зп ... 32 а, 3q Под этой строкой записывается строка ^п-1 t>n-2 ■■■ бо Г, где Ь„_ 1 = а„, = а^ + ,а + а„ при к<п, г = а^а + ао. П - 1 — ЭТО частное, а Тогда многочлен Ьо + Ь^х + Ь2Х^ + ... + Ь„. г — остаток при указанном делении. Составьте алгоритм, реализующий схему Горнера, для многочлена, коэффициенты которого хранятся в массиве А, как это 75 Алгоритмизация, структуры данных и элементы программирования указано выше. Коэффициенты частного и остаток сохраните в подходящем массиве В. в) Объясните, что схема Горнера действительно дает частное и остаток при делении многочлена на двучлен. г) Известно, что значение многочлена в точке а равно остатку г, получающемуся при делении данного многочлена на двучлен х-а. Составьте алгоритм-функцию для вычисления по схеме Горнера значения многочлена в заданной точке (массив В для этого, естественно, не нужен). Д) Напишите и отладьте программы, реализующие составленные алгоритмы. Графы Граф — это совокупность точек, называемых вершинами, некоторые из которых соединены линиями. Две вершины называются смежными, если имеется соединяющая их линия, на которой нет других вершин. Если на каждой линии, соединяющей две смежные вершины, выбрано направление, то такой граф называется ориентированным, или сокращенно орграфом. Линия, соединяющая две смежные вершины, для орграфа называется дзтой; а для неориентированного графа — ребром. Допускается, чтобы дуга или ребро (в данном случае безразлично) соединяла вершину саму с собой. Вершина называется изолированной, если она не соединена линией ни с какой другой вершиной. Граф (орграф), у которого каждому ребру или, соответственно, каждой дуге сопоставлено некоторое число, называется нагруженным. В зависимости от рассматриваемой задачи это число может интерпретироваться как расстояние между вершинами, или как время перехода от одной вершины к другой, или как пропускная способность канала, соединяющего две данные вершины, или еще каким-либо образом. Иногда бывает удобно рассматривать не-нагруженный граф (орграф) как нагруженный, в котором каждому ребру (дуге) поставлено в соответствие число 1. Путь в графе (орграфе) из вершины А в вершину В — это последовательность ребер (дуг) ACi, С1С2, ..., Количество ребер (дуг), составляющих путь, называется длиной этого пути. Путь, начало и конец которого совпадают, называется циклом. Цикл длины 1 называют петлей. Орграф, изображенный на рисунке 2.21, имеет петлю около вершины А и цикл АВС А длины 3. 76 А В С D А 2 3 6 0 В 0 0 2 0 С 2 0 0 0 D 4 3 5 0 Таблица 2.5 Обычно граф (орграф) задают одним из двух способов: перечислением всех его ребер (дуг) или таблицей, где в клетке на пересечении строки и столбца, соответствующих данным вершинам, указано, соединены эти вершины ребром (дугой) или нет. Для нагруженного графа (орграфа) для каждого ребра (дуги) указывается нагрузка. Нагруженный орграф, изображенный на рисунке 2.21, можно задать списком дуг: (АА; 2), (АВ; 3), (АС; 6), (ВС; 2), (СА; 2), (DA; 4), (DB; 3), (DC; 5). В таблице 2.5 приведена таблица смежности для этого графа. В таблице смежности ненагруженного графа везде вместо чисел, указывающих нагрузку (т. е. отличных от 0), стояло бы число 1. В заданиях к этому параграфу мы для простоты будем считать вершины графа перенумерованными натуральными числами от 1 до п (без пропусков и повторений). Список дуг для нагруженного орграфа будем задавать как двумерный массив А [1:3, 1:п], где в первой строке, соответствующей этому массиву таблицы, указывается первый конец дуги, во второй — второй конец, а в третьей — величина нагрузки. Для неориентированного графа соответствующий массив содержит только две первые строки. Если орграф (граф) задается таблицей смежности, то договоримся считать значение первого индекса номером первой вершины, а второго индекса — номером второй вершины; сами номера вершин в массиве не присутствуют. В Вопросы и задания ш ^ Что такое граф? Какой граф называют ориентированным? ^ Что такое ребро графа? Что такое дуга орграфа? О Какой граф или орграф называется нагруженным? Q Как задают графы и орграфы? Каковы особенности таблицы смежности для неориентированного графа по сравнению с таблицей смежности для орграфа? 0 Дана таблица смежности графа, но неизвестно, ориентированного или нет. Составьте алгоритм, позволяющий ответить на вопрос, ориентирован данный граф или нет. @ а) Дан граф и выбрана некоторая его вершина А. Вершина В называется п-достижимой из вершины А, если существует путь из 4 в 6 длины п и нет более короткого пути, соединяющего Аи В.В частности, 1-достижимые вершины из вершины А — это смежные с ней вершины. 77 Алгоритмизация, структуры данных и элементы программирования Составьте алгоритм, при помощи которого для заданного числа п будут найдены все вершины, л-достижимые из заданной вершины. Рассмотрите два варианта задания графа — списком ребер и таблицей смежности. б) ® Напишите и отладьте программы, реализующие составленные алгоритмы. Q а) Граф называется связным, если любая вершина его л-до-стижима хотя бы при одном л из любой другой вершины. Составьте алгоритм, позволяющий определить, является ли данный граф связным. Рассмотрите два варианта задания графа — списком ребер и таблицей смежности. б) Напишите и отладьте программы, реализующие составленные алгоритмы. @ а) Дан орграф. Составьте алгоритм, позволяющий для заданной вершины найти все циклы, проходящие через эту вершину. Рассмотрите два способа задания орграфа — списком ребер и таблицей смежности. б) Дан граф. Составьте алгоритм, позволяющий для заданной вершины найти все циклы, проходящие через эту вершину. Рассмотрите два способа задания графа — списком ребер и таблицей смежности. в) Напишите и отладьте программы, реализующие составленные алгоритмы. © а) Дан орграф. Составьте алгоритм, позволяющий найти все циклы этого орграфа. Рассмотрите два способа задания орграфа — списком ребер и таблицей смежности. б) Дан граф. Составьте алгоритм, позволяющий найти все циклы этого графа. Рассмотрите два способа задания графа — списком ребер и таблицей смежности. в) Напишите и отладьте программы, реализующие составленные алгоритмы. ф а) Дан граф и две его вершины. Составьте алгоритм, позволяющий отыскать кратчайшие пути между этими вершинами {или сообщить, что эти вершины не достижимы друг для друга). Рассмотрите два способа задания графа — списком ребер и таблицей смежности. б) Дан орграф и две его вершины. Составьте алгоритм, позволяющий отыскать кратчайшие пути между этими вершинами (или сообщить, что эти вершины не достижимы друг для друга). Рассмотрите два способа задания орграфа — списком ребер и таблицей смежности. в) ® Напишите и отладьте программы, реализующие составленные алгоритмы. Ф а) Дан граф и две его вершины. Составьте алгоритм, позволяющий отыскать наиболее длинные пути, не содержащие циклов, между этими вершинами (или сообщить, что эти вершины не достижимы друг для друга). Рассмотрите два способа задания графа — списком ребер и таблицей смежности. 78 б) Дан орграф и две его вершины. Составьте алгоритм, позволяющий отыскать наиболее длинные пути, не содержащие циклов, между этими вершинами (или сообщить, что эти вершины не достижимы друг для друга). Рассмотрите два способа задания орграфа — списком ребер и таблицей смежности. в) ® Напишите и отладьте программы, реализующие составленные алгоритмы. Основные вычислительные методы Этот раздел можно считать не относящимся напрямую к информатике. Однако потребность в применении рассматриваемых здесь вычислительных методов нередко возникает при построении математических моделей и проведении вычислительного эксперимента с ними. 13.1. Методы приближенного решения уравнений Пусть дана некоторая функция f (л:) и отрезок [а; Ь], причем на концах этого отрезка функция принимает значения противоположных знаков. Если функция непрерывна, т. е. ее график — непрерывная линия, то график функции пересекает ось абсцисс в некоторой точке с отрезка [а; &]. Иными словами, / (с) = 0, т. е. с — корень уравнения f (л:) = о (рис. 2.22). Метод деления пополам Для отыскания корня уравнения f (л:) = 0 берем середину отрезка [а; &], точку JCj = (а + Ь)/2. В этой точке вычисляем значение функции f(x). Оно имеет тот же знак, что и значение на одном из концов отрезка [а; &]. Будем рассматривать ту половину отрезка [а; 6], на концах которой функция f (х) имеет разные знаки. Новый отрезок тоже содержит корень уравнения f (х)-0, поскольку на его концах Рис. 2.22. Поиск корня методом деления пополам 79 Алгоритмизация, структуры данных и элементы программирования Рис. 2.23. Поиск корня методом хорд б) функция f (л:) снова имеет разные знаки. Этот отрезок в 2 раза короче предыдущего. И самое главное: с ним можно поступить точно так же — еще раз поделить пополам (рис. 2.22, б) и т. д. Поскольку длина отрезка каждый раз уменьшается вдвое, можно получить отрезок как угодно малой длины, внутри которого содержится корень уравнения f (лс) = 0. Концы отрезка дают приближенное значение корня с точностью, равной длине отрезка: левый конец отрезка — приближенное значение корня с недостатком; правый конец — приближенное значение корня с избытком. Метод хорд Этот метод решения уравнения / (л:) = 0 состоит в следующем. Рассмотрим график функции f (л:) на отрезке [а; &] и соединим концы графика отрезком (рис. 2.23, а). Этот отрезок пересекает ось абсцисс в некоторой точке х^. Возьмем ее за первое приближение к корню. Затем вычисляем значение функции в полученной точке. Из двух отрезков [а, ajj] и [Xj, Ь] рассматриваем тот, на концах которого значения функции / (л:) имеют различные знаки. Снова проводим хорду; точка пересечения с осью абсцисс дает нам следующее приближение к корню — точку Х2 (рис. 2.23, б) и т. д. Вопросы И задания г-? о о о Пусть функция на концах отрезка [3; 4] принимает разные знаки. За сколько шагов методом деления пополам можно получить точность 0,001? Можно ли при составлении алгоритма решения уравнения методом деления пополам для получения ответа с заданной точностью Е воспользоваться циклом в форме Повторить п раз? При положительном ответе укажите, как число исполнений тела цикла зависит от Е; при отрицательном объясните почему. ©Составьте алгоритмы вычисления всех корней уравнения X® + Зх - 1 = о методом деления пополам и методом хорд с точностью 0,0001. Напишите и отладьте программы, реализующие составленные алгоритмы. 80 О Пусть для вычисления значения функции при заданном значении аргумента имеется вспомогательный алгоритм, оформленный как алгоритм-функция. Вот заголовок этого алгоритма: Алгоритм вещ: f (вещ: х) Используя указанный алгоритм-функцию, составьте алгоритм нахождения корня уравнения f (х) = 0 на заданном промежутке с заданной точностью: а) методом деления пополам; б) методом хорд. 13.2. Методы сортировки Пусть дан линейный массив числового или строкового типа. Нередко возникает задача расположения элементов этого массива в порядке возрастания (или убывания). Для этого разработаны разные методы. Сортировка выбором. В массиве разыскивается наименьший элемент и ставится на первое место, а первый элемент — на место наименьшего. Затем процедура повторяется, начиная со второго элемента, и т. д. Сортировка обменами {«пузырьком^). При просмотре массива А в каждой паре соседних элементов А [г] и А [г -I-1] эти элементы меняются местами, если А [г] > А [г -t- 1]. Так делается до тех пор, пока в массиве не останется пар, в которых меньший элемент стоит правее большего. Сортировка вставками. Пусть первые h элементов массива уже расположены в порядке возрастания. Берется элемент с номером k + 1 W. вставляется в предшествуюш;ий отрезок массива на свое место. Так делается до тех пор, пока не будут просмотрены все элементы массива. Быстрая сортировка. В исходном массиве А случайным образом выбирается элемент. Все остальные элементы массива записываются левее него, если они меньше или равны выбранному элементу, и правее, если они больше его. Взаимное расположение остальных элементов в преобразованном массиве роли не играет. Если, к примеру, исходный массив выглядит так: 8, 12, 3, 7, 20, 11, 5, 15, и выбран элемент 7, то массив преобразуется в такой: 3, 5, 7, 8, 12, 20, 11, 15 или такой: 3, 5, 7, 12, 8, 20, 11, 15, в зависимости от того, как будет реализовано перемещение элементов. Выбранный элемент в новом массиве всегда стоит уже на своем месте и в процессе дальнейшей сортировки больше никуда сдвигаться не будет. Выбранным элементом 81 Алгоритмизация, структуры данных и элементы программирования массив разбивается на две части, и с каждой частью проделывается та же процедура. Процесс продолжается, пока каждая из частей не станет одноэлементной. >Вопросы И задания ® Имеется 5 камней разной массы. Требуется расположить их в порядке возрастания масс, пользуясь чашечными весами без гирь. а) Составьте алгоритмы упорядочения камней, используя методы сортировки выбором, пузырьком, вставками, быстрой сортировки. Каждый алгоритм оформите в виде схемы алгоритма. б) Определите, сколько взвешиваний требуется выполнить в каждом из этих алгоритмов, чтобы гарантированно решить задачу. @ Дан одномерный массив из 25 чисел. а) Составьте алгоритм перестановки элементов этого массива в порядке убывания. б) Инверсией называется такая пара элементов в одномерном массиве, для которой элемент с большим индексом меньше элемента с меньшим индексом. Составьте алгоритм для подсчета числа инверсий в данном массиве. в) Составьте алгоритм, выполнив который компьютер удалит из массива наименьшее число элементов так, чтобы оставшиеся шли в убывающем порядке. г) Составьте алгоритм для удаления из массива наименьшего числа элементов так, чтобы в оставшейся последовательности элементов не было инверсий. д) Напишите и отладьте программы, реализующие составленные алгоритмы. е а) Дан одномерный массив из 25 чисел. Составьте алгоритм, после исполнения которого элементы, стоящие на нечетных местах, будут упорядочены по возрастанию, а элементы, стоящие на четных местах, — по убыванию. б) Напишите и отладьте программу, реализующую составленный алгоритм. О Дан двумерный целочисленный массив А [1:15, 1:10]. Для каждой строки подсчитывается сумма всех ее элементов. Составьте алгоритм, который расположит строки этого массива в порядке возрастания этих сумм. О Дан двумерный массив А [1:25, 1:2], в котором записаны координаты 25 точек плоскости. Составьте алгоритм, после исполнения которого координаты точек будут расположены в порядке возрастания удаленности этих точек от одной из них (от какой именно — запрашивается у пользователя) © а) Дан линейный массив А [1:100] целого типа. Составьте алгоритм, который разместит в начале массива все отрицательные элементы, сохранив их взаимное расположение, а за ними все остальные элементы, также не нарушая их порядка. I82 б) S Напишите и отладьте программу, реализующую составленный алгоритм. Qt На прямой заданы 25 отрезков координатами своих концов. Эти координаты записаны в двумерный числовой массив Д[1:25, 1:2]. Требуется определить, какое максимальное число отрезков имеет общую для этих отрезков точку. Составьте алгоритм нахождения этого числа. О а) Даны два слова. Составьте программу, позволяющую определить, можно ли из букв, входящих в первое слово, составить второе слово. Буквы можно переставлять, но нельзя использовать букву большее число раз, чем она встречается в первом слове. Например, из слова ИНФОРМАТИКА можно составить слово РАКИТА и нельзя составить слово МОТОР, б) §1 Напишите и отладьте программу, реализующую составленный алгоритм. О а) Дан массив А [1:20], состоящий из целых чисел. Составьте алгоритм, позволяющий определить, можно ли переставить числа в этом массиве так, чтобы каждое число, начиная со второго, делилось на предыдущее. б) Напишите и отладьте программу, реализующую составленный алгоритм. Свойства алгоритмов Для алгоритмов рассматриваются различные их свойства. Некоторыми свойствами должны обладать все алгоритмы, необходимость других для того или иного алгоритма вытекает из постановки задачи, для решения которой предназначается данный алгоритм. Перечислим наиболее часто рассматриваемые свойства алгоритмов. Дискретность. Под дискретностью понимается то, что алгоритм состоит из описания последовательности тактов обработки, организованной таким образом, что в начальный момент задается исходная ситуация, а в каждый следующий момент ситуация преобразуется на основе данных, полученных в предшествующие такты обработки. Дискретность алгоритма означает, что он исполняется по шагам: каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего. Детерминированность. Это свойство означает, что на каждом шаге исполнения алгоритма (см. свойство дискретности) однозначно определено преобразование объектов среды исполнителя, полученных на предшествующих шагах алгоритма. В некоторых учебниках это свойство алгоритма называют точностью. 83 Алгоритмизация, структуры данных и элементы программирования Результативность. Это свойство подразумевает, что каждое действие в алгоритме после своего завершения создает ситуацию, в которой все имеющиеся объекты однозначно определены. Если это по каким-либо причинам невозможно, то алгоритм должен сообщить, что решение задачи не существует. Это свойство является обязательным для любого алгоритма. Нередко говорят о результативности алгоритма в целом, подразумевая, что алгоритм предназначен для решения той или иной задачи. Обычно одновременно с результативностью в целом подразумевается и конечность алгоритма, т. е. завершение его работы за конечное число шагов (при этом количество шагов может быть заранее неизвестным и различным для разных начальных ситуаций). Свойство алгоритма, что в нем могут использоваться только допустимые действия исполнителя, нередко называют понятностью алгоритма (в некоторых учебниках — эффективностью, в других — элементарностью действий). Понятность является обязательным свойством любого алгоритма. С точки зрения практической ценности алгоритма важно, чтобы множество допустимых начальных ситуаций было для него достаточно большим (иногда говорят, потенциально бесконечным). Это свойство алгоритма называют массовостью. Конечность алгоритма нужно обосновывать лишь в том случае, если в нем используется цикл, для которого заранее неизвестно количество исполнений тела цикла (т. е. цикл с предусловием или цикл с постусловием), или рекурсия. Основным инструментом обоснования конечности алгоритма в этом случае служит лимитирующая функция. Так называют переменную величину, которая каждый раз меняет свое значение при очередном исполнении тела цикла или рекурсивном обращении к вспомогательному алгоритму и обладает следующими двумя свойствами: • она принимает лишь конечное число значений (быть может зависящее от исходных данных); • в ходе исполнения алгоритма она принимает каждое свое допустимое значение не более одного раза. Обоснование результативности алгоритма нередко подразумевает выявление (и доказательство) того, что именно является результатом исполнения алгоритма. Одним из приемов исследования алгоритма на результативность является обнаружение подходящего инварианта, т. е. такой характеристики объекта, обрабатываемого с помощью данного алгоритма или его фрагмента (например, тела цикла), которая не изменяется. 84 Вопросы й задания О Перечислите свойства, которые обычно рассматриваются для алгоритма. Какие из этих свойств обязательно должны присутствовать? Объясните, почему наличие лимитирующей функции обеспечивает конечность алгоритма. @ Объясните, почему следующие инструкции не являются алгоритмами; а) Фрагмент инструкции по приготовлению теста для торта: Добавьте щепотку соли. Слегка потрясите, чтобы смесь стала комковатой. Подогрейте коньяк в маленькой кастрюльке и влейте его в смесь. б) Фрагмент инструкции по употреблению лекарства от кашля: ...Если врач не прописал иначе, то 3—4 раза в день по 15—20 капель, лучше всего в горячей сладкой воде. а) Может ли обладать свойством конечности алгоритм, согласно которому работает операционная система вашего компьютера? (Совет. Подумайте, к каким эффектам приводила бы конечность этого алгоритма.) б) Приведите примеры алгоритмов, которые не могут обладать свойством конечности. Рассмотрите приведенный ниже алгоритм. Среда: чудо-дерево, на котором растут апельсины и бананы, обладающее следующим свойством — если с него срывают два одинаковых плода, то тут же вырастает один апельсин, а если два разных, то один банан. Исполнитель: Садовник. Допустимые действия: сорвать два плода с чудо-дерева; проверить, что количество плодов на чудо-дереве больше заданного натурального числа. Алгоритм Сбор урожая { Делать пока (на чудо-дереве более одного плода) { Сорвать два плода; } } а) Объясните, почему этот алгоритм не является детерминированным. б) Зависит ли результат от того, какой плод будет срывать Садовник при каждом исполнении тела цикла, или он определяется начальной ситуацией на чудо-дереве? Недетерминированный алгоритм, результат исполнения которого полностью определяется начальной ситуацией, называется однозначным. 85 Алгоритмизация, структуры данных и элементы программирования @ Исполнитель имеет следующие допустимые действия: — стереть с доски два числа и вместо них написать одно, равное их сумме, уменьшенной на 1; — сосчитать количество чисел на доске; — сравнить два натуральных числа. Рассмотрите следующий алгоритм. Алгоритм Сумма { Делать пока (на доске более одного числа) { Стереть какие-нибудь два числа и вместо них записать их сумму, уменьшенную на 1; } } а) Объясните, почему этот алгоритм не является детерминированным. б) Будет ли этот алгоритм однозначным? ^ Исполнитель имеет следующие допустимые действия: — стереть с доски два числа а и б, а вместо них написать одно, равное аЬ + а + Ь] — сосчитать количество чисел на доске; — сравнить два натуральных числа. Рассмотрите следующий алгоритм. Алгоритм Замена { Делать пока (на доске более одного числа) { Стереть какие-нибудь два числа а и Ь и вместо них написать одно, равное аЬ+а + Ь; } } а) Объясните, почему этот алгоритм не является детерминированным. б) Будет ли этот алгоритм однозначным? Предположим, что исполнитель обладает способностью за одно действие написать весь натуральный ряд, а также вычеркнуть из него все числа, удовлетворяющие какому-либо условию, даже если этих чисел бесконечно много. Рассмотрите следующий алгоритм для этого исполнителя: Алгоритм { Написать весь натуральный ряд; Вычеркнуть из него число 1; Делать пока (есть необведенные числа среди невычеркнутых) { Среди невычеркнутых чисел обвести самое маленькое из необведенных; Из необведенных чисел вычеркнуть те, которые кратны последнему обведенному числу; } (* конец цикла *) Сообщить Обведенные числа; } Конечен ли этот алгоритм? Ответ обоснуйте. 86 ^ Имеется кубик, на каждой из шести граней которого наРисано некоторое число (не обязательно одно и то же). Исполнитель изменяет данный ему кубик следующим образом: на каждой грани он пишет число, равное среднему арифметическому числа на этой грани и его четырех соседей (все шесть чисел на гранях кубика меняются одновременно). Рассмотрите алгоритм для этого исполнителя. Алгоритм { Взять кубик; Делать пока (среди чисел на гранях есть хотя бы два неравных) { На каждой грани заменить число на среднее арифметическое этого числа и четырех чисел, написанных на соседних гранях; } (* конец цикла *) Положить кубик; } Каким должен быть начальный кубик, чтобы этот алгоритм был конечным? 0 Рассмотрите следующий алгоритм. Алгоритм Преобразование_троек цел: S, X, у, z, А[1:3]; { Запросить ДГ1:31: S :=А[1]*А[1] +А[2]*А[2] +А[3]*А[3]; Если (А[1] А[2]) или (А[2] А[3]) то { Делать пока (s mod 4 = 0) или (s mod 4 = 3) { х:=(А[2]+А[3])/2; у:=(А[1]+4[3])/2 z:=(A[1]+4[2])/2 А[Ц А[2] ^[3] = х; = у; = z; } } S :=А[1]*А[1] + А[2]*А[2] + А[3]*А[3]; (*конец цикла*) (*конец ветвления *) Сообщить А[1:3]; } Заканчивается ли исполнение данного алгоритма за конечное число шагов при любом начальном заполнении массива 4? (ЛГРассмотрите следующий алгоритм: Алгоритм Суммирование вещ: S; цел: А/; { S:=1; Л/:=1; Делать пока (S<20) { Л/ := Л/ + 1; S :=S+ 1/Л/2; } (*конец цикла*) 87 Алгоритмизация, структуры данных и элементы программирования } Сообщить N; Закончится ли исполнение данного алгоритма за конечное число шагов? 0 Рассмотрите следующий алгоритм, предназначенный для обработки натуральных чисел тип. Алгоритм Загадка цел; т, п, х, у, и, v, { Запросить п, т\ х \=т\ у := п; и :=т\ v := п; Делать пока (х < у) или (х > у) { Если (х< у) то { у :=у-х; 1/:=у/+и; } иначе { X :=х-у; и := и+ } } у := (и + v)/2; Сообщить X, у; } а) Конечен ли этот алгоритм? Ответ обоснуйте. б) Для чего предназначен данный алгоритм? в) * Найдите подходящие инварианты и докажите гипотезу, выдвинутую вами при выполнении пункта б. 0 Рассмотрите следующий алгоритм. Алгоритм Особое суммирование цел: X, у, z; { Запросить х; у := X + S (х); Делать пока (х mod 9 у) { z:=y + S(y); х:=у; у :=z; } (*конец цикла*) Сообщить х; } Через S в этом алгоритме обозначен следующий алгоритм-функция: Алгоритм цел: S (арг цел: х) { Если (х< 10) то { S ;=х; } иначе { S := S (х div 10) + (х mod 10); } } а) Укажите все значения х, не превосходящие 100, для которых алгоритм «Особое суммирование» заканчивает работу за конечное число шагов. б) Сколько раз исполняется тело цикла для тех значений х, при которых алгоритм «Особое суммирование» заканчивает работу за конечное число шагов? 188 Ф Рассмотрите следующий алгоритм. Алгоритм Загадка 2 X, у, z\ { Запросить х; у :=х + Р(х); Делать пока (х ф у) { z-.= y + P(y); X := у; у :=z; } (*конец цикла*) Сообщить х; } Алгоритм цел: Р (цел: х) { Если (х< 10) то { Р :=х; } иначе { Р := Р (х div 10)*(х mod 10); } } а) * Будет ли алгоритм «Загадка 2» конечным? б) (.§ Напишите и отладьте программу, реализующую алгоритм «Загадка 2». Проведите вычислительный эксперимент, придавая X различные значения (например, 9, 99, 999, 9999 и т. д.). Попытайтесь по результатам эксперимента определить, ограничено ли число исполнений тела цикла в основном алгоритме какой-нибудь константой, не зависящей от х. в) * (®/ Попытайтесь результаты вашего эксперимента объяснить теоретически. 0 Рассмотрите следующий алгоритм: Алгоритм Сумма вещ: S; цел: N, М\ { S:=1; Л/:=1; Сообщить "Введите натуральное число М"\ Запросить М\ Делать пока (S < М) { А/:=Л/+ 1; S :=S+ 1/Л/; } (*конец цикла*) Сообщить А/; } а) Для решения какой задачи предназначен этот алгоритм? б) * При M=^ тело цикла не выполняется ни разу и, следовательно, алгоритм конечен. При любом ли значении М данный алгоритм конечен? Ответ обоснуйте. в) Напишите и отладьте программу, реализующую данный алгоритм. Проведите вычислительный эксперимент, задавая значения М от 1 до 20. При каждом ли из указанных значений М удалось получить результат? Организуйте тестирование программы, чтобы выявить причину обнаруженного вами феномена. 89 Алгоритмизация, структуры данных и элементы программирования Универсальный исполнитель Универсальным исполнителем называется такой формальный исполнитель алгоритмов, посредством которого может быть имитирована работа любого формального исполнителя, обрабатывающего закодированную подходящим образом информацию. Иными словами, любая цель, достижимая для некоторого формального исполнителя, является достижимой и для универсального исполнителя. В частности, это означает эквивалентность любых двух универсальных исполнителей в том смысле, что они имеют одно и то же множество достижимых целей. Поскольку для всякого исполнителя существуют цели, не являющиеся достижимыми (см. задание 28 из § 11), то имеются задачи, для решения которых не существует алгоритмов решения. Такие задачи называются алгоритмически неразрешимыми. Алгоритмически неразрешимые задачи всегда являются массовыми, т. е. множество исходных данных в таких задачах всегда бесконечно. Имеется много различных универсальных исполнителей. Ниже речь будет идти только о двух из них: машине Тьюринга и машине Поста. ашина Тьюринга Среда, в которой работает машина Тьюринга, представляет собой бесконечную (в обе стороны) ленту, разбитую на одинаковые секции. Во время работы машина движется вдоль ленты, смещаясь каждый раз точно на одну секцию вправо или влево. При этом машина может находиться в различных состояниях. Этих состояний конечное число, и для их обозначения мы будем использовать символы Qq, ..., g„. Набор символов, кодирующих состояния машины, называют внутренним алфавитом машины Тьюринга. Кроме того, имеется внешний алфавит, символы которого могут вписываться в секции ленты и распознаваться. Пусть это будут а^, ..., а^. В любой момент работы машины в каждой секции хранится ровно один знак внешнего алфавита, причем только символ По разрешается использовать бесконечное число раз. Этот символ будем называть «пробелом» и изображать на ленте пустой клеткой. Остальные символы внешнего алфавита используются для записи на ленту сообщения. К началу работы машины на ленту записывается исходная информация (т. е. последовательность символов внешнего алфавита). В ходе работы машины эта последовательность изменяется. Если после выполнения конечного числа 90 действий машина прекращает работу — будем говорить, что машина останавливается, — то на ленте оказывается записанной новая последовательность символов, которую и считают результатом обработки исходной информации. Допустимые действия машины Тьюринга таковы: — записать какой-либо символ внешнего алфавита в секцию ленты (символ, бывший там до того, затирается); — сместиться в соседнюю секцию; — сменить состояние на одно из обозначенных символом внутреннего алфавита. Конечно, в этом перечислении в каждой строке указано не одно действие, а группа действий одного вида — действий «записать символ внешнего алфавита» столько, сколько этих символов, сместиться в соседнюю секцию можно вправо, а можно влево, действий по изменению состояния столько, сколько этих состояний (т. е. сколько символов внутреннего алфавита). Как видно из этого описания, машина Тьюринга «бегает» вдоль ленты и заменяет одни символы на другие. Каждая команда машины содержит одно действие из каждой группы действий и имеет вид указание указание указание о записи символа о перемещении машины о смене состояния Например команды могут выглядеть так: щ -* Qj — в обозреваемую секцию записать а^, сместиться вправо (к следующей секции) и перейти в состояние ai<— Qj — в обозреваемую секцию записать а^, сместиться влево (к следующей секции) и перейти в состояние д^; CjSgy — в обозреваемую секцию записать П;, остановиться и перейти в состояние д^. Для осуществления действий машина Тьюринга имеет операционно-логический блок. У этого блока имеется два входа: через один из них поступает информация о том, какой символ стоит в обозреваемой ячейке, через другой — символ, обозначающий состояние, в котором находится машина на данном шаге своей работы. Эта информация однозначно определяет, какую именно команду следует выполнить машине. Поскольку команда может содержать указание на выполнение трех действий — записи символа на ленту, смещения и смены состояния — операционно-логический блок имеет три выхода: запись символа А, смещение М и смена состояния Q (рис. 2.24). Поскольку у машины Тьюринга два входа, ее реакцию на подаваемые симво- Рис. 2.24. Опера- ционно-логический блок машины Тью ринга 91 Алгоритмизация, структуры данных и элементы программирования Таблица 2.6 Внешний алфавит А Состояния машины Q Qo Яо *^Яа *^Яа + 4-^(7, *^<7о Зо*~Яз +*~Яа Таблица 2.10 хр Яо Яа Зо Зо^Яо * *—*' 2. => 6. # 3. 4. 7. 8. Выполните следующую программу для машины Поста для тех заполнений информационной ленты, которые изображены на рисунках 2.30, а—в. 1. " 4. # 7. 2. «= 5. => 8. 3. ?? 9 6. => 9. Рис. 2.30 ? 2 ! @ Составьте программу для машины Поста, преобразующую ис ходную информацию, представленную на рисунке 2.31, а, в ин формацию, представленную на рисунке 2.31, б. @ Рассмотрите следующую программу. I ? 5 ? 2 5. 6. 7. 8. ?? 6 ? 5 задачи взгляд. Рис. 2.31 О 1. 2. 3. 4. => а) Для решения какой предназначена, на ваш эта программа? б) Для любой ли начальной разметки ленты машина Поста закончит работу по этой программе за конечное число шагов? Составьте программу для машины Поста, которая к заданной в некотором месте последовательности меток, между которыми нет пустых секций, добавит справа еще одну метку. Первая метка последовательности стоит в начальной клетке. Если считать, что количеством меток кодируется соответствующее натуральное число, то этой программой вы «научите» машину Поста к данному числу прибавлять число 1. Пусть на информационной ленте в двух местах записаны две последовательности меток, отделенные друг от друга одной пустой секцией. Первая метка первой последовательности стоит в начальной секции. Составьте программу, выполнив которую машина Поста на той же ленте в третьем месте запишет последовательность, состоящую из суммарного числа меток в заданных последовательностях. ' ' ' , * ? , ’ Раздел 3 Информационное и компьютерное моделирование Системы и структуры Система — это совокупность абстрактных или материальных объектов вместе с известными либо заданными связями и отношениями, образуюш;ими в определенном смысле единое целое. Совокупность отношений, которыми наделена система, называется структурой этой системы. Связи элементов создают систему только тогда, когда в результате этих связей образуется новый целостный объект, обладающий такими свойствами, которые без этих связей не были присущи совокупности данных элементов. Появление таких свойств называют системным эффектом. Если число элементов в системе конечно, то ее удобно изображать в виде ориентированного графа (о понятии графа и ориентированного графа см. § 12), вершинами которого являются элементы системы, а дуги соответствуют связям между элементами. О Представьте следующие объекты как системы: а) шкаф; б) гитара; в) автомобиль; г) телефонный аппарат. Укажите для каждой системы, что в ней является элементами и каковы связи между элементами. В чем проявляется системный эффект для каждой из систем? Ф Представьте следующие объекты как системы: а) семья; б) школа; в) завод; г) ферма. 97 Информационное и компьютерное моделирование а) б) в) Рис. 3.1 Укажите для каждой системы, что в ней является элементами и каковы связи между элементами. В чем проявляется системный эффект для каждой из систем? 0 Представьте следующие объекты как системы: а) биология как наука; б) информатика как учебная дисциплина; в) литературное произведение; г) школьное сочинение по литературе. Укажите для каждой системы, что в ней является элементами и каковы связи между элементами. В чем проявляется системный эффект для каждой из систем? Q Представьте следующие объекты как системы и изобразите их с помощью подходящего графа или орграфа: а) родословная вашей семьи; б) авторучка; в) субъект Российской Федерации, в котором вы проживаете. @ Для каждого графа, изображенного на рисунке 3.1, приведите пример объекта, который имеет данную структуру. Информационное моделирование Модель — это соответствующее целям моделирования и сохраняющее существенные свойства представление некоторого объекта (процесса или явления) другим объектом (процессом или явлением), который может быть изучен уже имеющимся инструментарием той или иной науки. Построение любой модели начинается с выявления факторов, существенных для исследуемого объекта, процесса или явления. Поскольку в любой модели учитывается только часть информации об объекте, процессе или явлении, никакая модель не эквивалентна исходному объекту, процессу или явлению. Если построенная модель дает удовлетворительные результаты при решении задач, для которых модель строилась, то говорят, что она адекватна рассматриваемому объекту (процессу или явлению). Всякая модель имеет 198 ограниченную область адекватности, и за пределами этой области она перестает удовлетворительно отражать свойства моделируемого объекта. Модели классифицируются по способу представления моделируемого объекта на описательные, т. е. представленные текстом на естественном языке, имитационные (их иногда называют копирующими) и знаковые, т. е. представленные с помощью условных обозначений. Довольно часто модель содержит элементы всех трех способов представления. Нередко модель представлена в виде системы. Такие модели называют системными. Системные модели всегда знаковые. 17.1. Понятие информационной модели Информационной моделью называется модель, представляющая объект, процесс или явление набором параметров и связей между ними. Параметры модели выражают влияние факторов на строение и функционирование модели. Процесс описания факторов с помощью параметров называется формализацией. Информационная модель, в которой параметры и зависимости между ними выражены в математической форме, называется математической моделью. Вопросы и задания О Приведите примеры информационных и неинформационных моделей. Q Почему информационная модель всегда системна? ^ Можно ли утверждать, что всякая системная модель является информационной? Положительный ответ обоснуйте, отрицательный ответ подтвердите примером системной, но не информационной модели. О Одним из тех, благодаря кому в российской школе появилась информатика, был академик А. П. Ершов. Ему принадлежат слова: «Понимание необходимости и способность к построению информационной модели должно стать глубинной составляющей инженерно-технического мышления специалиста». Обдумайте эти слова. Попытайтесь привести примеры, которые подтверждают эту мысль. В какой мере этот тезис можно было бы распространить на специалистов гуманитарного профиля? 0 Чертеж электрической схемы является моделью реальной схемы. Является ли эта модель системной? Является ли она информационной? О Ниже приведены некоторые виды моделей, с которыми человеку нередко приходится иметь дело. Укажите, какие из них явля- 99 Информационное и компьютерное моделирование & Ф ются имитационными, какие информационными, но не математическими, а какие математическими. а) План местности. б) Формула химического вещества. в) Литературная повесть. г) Формула равноускоренного движения. д) Компьютерная игра «Пасьянс». е) Классный журнал. ж) Железнодорожное расписание движения поездов. з) Карта климатических поясов. и) Картина И. Репина «Бурлаки на Волге». к) Электрическая схема. л) Второй закон Ньютона. м) Компьютерная игра «Гонки». н) Прямоугольный параллелепипед. Во время ремонта корабля потребовалось заделать пробоину в обшивке. Имеется лист стали. Удастся ли с его помощью закрыть пробоину? Постройте математическую модель, которая, на ваш взгляд, поможет избежать бесплодных попыток залатать пробоину. ‘Требуется изготовить футляр цилиндрической формы, закрывающийся с двух сторон крышками. Исходная заготовка — лист прямоугольной формы. Постройте математическую модель, которая, на ваш взгляд, позволит оптимально использовать материал для изготовления одного футляра. Из двух населенных пунктов навстречу друг другу вышли два путника. Скорость каждого из них не постоянна, а заключена в некоторых пределах. Составьте математическую модель, с помощью которой для заданного момента времени можно было бы получить ответы на следующие вопросы; а) Обязательно ли к этому моменту времени они встретились? б) Могла ли к этому моменту времени произойти встреча? в) Можно ли быть уверенным, что встреча еще не произошла? 17.2. Статические модели Нередко при построении модели одним из предположений выступает неизменность или пренебрежимо малая изменяемость рассматриваемого объекта во времени, иными словами, его статичность. Получающиеся при этом модели называются статическими. При построении системных статических моделей нередко используются графы и орграфы. i, f Вопросы и зодония Среди перечисленных моделей укажите статические: а) глобус; б) компьютерная игра «Гонки»; 100 в) уравнение химической реакции; г) зависимость между температурой остывающего тела и временем; д) классный журнал; е) соотношение между количеством хищников на данной территории и количеством травоядных животных; ж) расписание уроков. Для каждого случая дайте обоснование. О На старинной карте (рис. 3.2) изображены ходы и гроты в пещере, где разбойники прячут сокровища. Попасть в тот грот, где спрятаны сокровища, можно, только пройдя по каждому ходу и только один раз. И если в этом гроте произнести заклинание, то сразу окажешься на поверхности. а) Может ли Али-Баба сразу, не проходя по лабиринту, найти на карте заветный грот? б) Найдите хотя бы один путь, ведущий от входа к сокровищам. Злая фея заперла принцессу в одной из комнат замка. Все двери замка открыты, кроме одной — потайной, которая ведет наружу. Но как только принцесса проходит через дверь, та захлопывается и больше уже не открывается. Потайная же дверь откроется как только окажутся закрытыми все остальные двери замка. План замка изображен на рисунке 3.3. а) Определите, в какой комнате злая фея оставила принцессу и в какой комнате находится потайная дверь. (Разумеется, потайная дверь находится в одной из внешних стен замка.) б) Найдите какой-нибудь путь, ведущий к свободе. О 101 Информационное и компьютерное моделирование Фея заперла принцессу в одной из комнат двухэтажного замка. План этажей этого замка изображен на рисунках 3.4 и 3.5; закрашенными клетками обозначены лестницы с одного этажа на другой. Условия освобождения те же, что и в задаче 3. Определите, в какой комнате оставила принцессу злая фея и в какой находится потайная дверь. (Разумеется, потайная дверь располагается на первом этаже в одной из внешних стен замка.) Найдите какой-нибудь путь, ведущий к свободе. Злой колдун запер вас в одной из комнат трехэтажного замка. На рисунках 3.6—3.8 представлен план этажей этого замка. Рис. 3.5 102 1-й этаж Рис. Э.6 2-й этаж Рис. 3.7 3-й этаж Рис. 3.8 103 Таблица 3.1 Информационное и компьютерное моделирование Алексеево Борисово Васильево Гаврилово Денисово Алексеево 3 4 2 Борисово 4 2 Васильево 2 3 Гаврилово 5 3 2 Денисово 2 закрашенными клетками обозначены лестницы с'одного этажа на другой. Условия освобождения те же, что и в задаче 3. Определите, в какой комнате колдун вас запер и в какой комнате находится потайная дверь, а также укажите какой-нибудь путь, ведущий к свободе. О Таблица стоимости перевозок строится следующим образом; в клетке, стоящей на пересечении строки с названием населенного пункта А и столбца с названием населенного пункта Б, указана стоимость перевозки груза из пункта А в пункт Б; пустая клетка означает, что между этими пунктами нет прямого сообщения. Стоимость проезда по маршруту складывается из стоимостей проезда между соседними станциями. Используя таблицу 3.1, определите минимальную стоимость маршрута: а) из Алексеево в Васильево; б) из Борисово в Денисово; в) из Гаврилово в Борисово; г) из Денисово в Гаврилово. (Совет. Преобразуйте табличную модель в модель в форме орграфа.) О На рисунке 3.9 изображены два размеченных графа, моделирующие систему дорог между несколькими населенными пункта- 13 13 И а) Рис. 3.9. Графы дорог между населенными пунктами б) 104 Рис. 3.10. Схема метода нисходящего программирования ми. Требуется со станции (она на графе обозначена буквой С) развезти почту во все остальные пункты. Для каждого графа ответьте на вопросы: а) Существует ли маршрут, проехав по которому можно побывать в каждом населенном пункте ровно один раз и снова вернуться на станцию? б) Какой самый короткий маршрут, обеспечивающий доставку почты во все населенные пункты и возвращение на станцию? Ответ запишите перечислением вершин графа в том порядке, в каком они будут посещаться при прохождении намеченного маршрута. О На рисунке 3.10 в виде орграфа представлено применение метода нисходящего программирования (см. § 10.4) к решению некоторой задачи. а) Обратите внимание, что данный граф не имеет маршрутов, которые бы начинались и заканчивались в одной и той же вершине. Будет ли выполняться это свойство для любого орграфа, изображающего применение метода нисходящего программирования? б) Как вы думаете, может ли для орграфа, изображающего применение метода нисходящего программирования, существовать вершина, в которую входят несколько дуг? Положительный ответ аргументируйте примером подходящей задачи и разработкой ее решения методом нисходящего программирования, отрицательный — доказательством. ^ Для орграфа, как и в случае неориентированного графа, нередко оказывается полезным на его дугах проставить числовые метки. Орграф с размеченными дугами называют сетью. В зависимости от ситуации, для моделирования которой применяется сеть, числовые метки называют либо длинами дуг, либо их пропускной способностью. а) Для сетей, представленных на рисунке 3.11, найдите кратчайший путь из вершины Vq в каждую другую вершину сети. б) §1 В § 12 описано два способа представления сети — списком дуг и таблицей смежности. Для каждого из этих способов разработайте алгоритм нахождения кратчайшего пути из заданной вершины во все остальные вершины. (Совет. Возможно, вам окажутся полезными решенные вами задачи 6 и 10 из § 12.) Напишите и отладьте программы, реализующие составленные алгоритмы. 0 Приведите примеры моделей в форме графа, с которыми вам доводилось иметь дело. 17.3. Динамические модели. Черный ящик Модели, в которых учитывается изменение моделируемого объекта во времени, называют динамическими. Изменение объекта во времени обычно называют его функционированием или эволюцией. Рассматривая функционирование объекта, нередко бывает достаточно сосредоточить свое внимание на внешних воздействиях, вызывающих изменения объекта, и результатах этих воздействий. Внешние воздействия воспринимаются объектом через его входы, а результаты передаются объектом во внешнюю среду через его выходы. При этом нередко предполагается несущественным внутреннее устройство объекта. Объект, внутреннее устройство которого принципиально скрыто от исследователя, был введен в кибернетике под названием черный ящик. Схематично черный ящик можно представлять себе так, как он изображен на рисунке 3.12. Рис. 3.12. Черный ящик 106 Вопросы и задания о Пусть речь идет о моделировании поведения водителя автомобиля при переезде перекрестка, который регулируется светофором а) Будет ли эта модель динамической? б) Можно ли в этой модели считать водителя черным ящиком? (Совет. Оцените, насколько важна информация о внутренни> процессах человека, переезжающего перекресток.) а) Инструкция по эксплуатации стиральной машины представляет собой некую описательную модель. Верно ли, что в этоР модели стиральная машина представлена как черный ящик? При положительном ответе укажите, что является его входами и выходами; при отрицательном ответе укажите, как в инструкции отражена внутренняя структура стиральной машины. б) Приведите примеры приборов (устройств), описание которых трактует эти приборы (устройства) как черные ящики. Приведите пример использования черного ящика в исследованиях: а) по физике; б) по химии; в) по биологии. В заданиях 4—7 приведены примеры некоторых черных ящиков. Каждый ящик описывается его реакциями на информацию, подаваемую на его входы. На входы могут подаваться последовательности символов, которые могут восприниматься либо как последовательности любых символов, либо как последовательности букв русского алфавита, либо как натуральные числа — информацию, представленную другим способом, данные ящики не воспринимают. Требуется определить, что делает данный ящик. Q Черные ящики, описанные таблицами 3.2—3.4, имеют один вход и один выход. ^ Черные ящики, описанные таблицами 3.5—3.7, имеют два входа и один выход. ^ Черные ящики, описанные таблицами 3.8—3.10, имеют один вход и два выхода. Q Черные ящики, описанные таблицами 3.11—3.13, имеют два входа и два выхода. Таблица 3.2 Таблица 3.3 № опыта Информация на входе Резуль- тат 1 шалаш 5 2 159 3 3 (№%? 4 4 alfa 4 5 гипопотам 10 № опыта Информация на входе Резуль- тат 1 оно поп 2 125 не понимаю 3 яйцо акчп 4 (№%? не понимаю 5 зима ийнб 107 Таблица 3.4 Информационное и компьютерное моделирование № ойыта Информация на входе '1, ' книга книга 2 1234321 1234 :ш..л колокол кол крокодил кродил (%№%%№? (%№? Таблица 3.5 № опыта Информация на входах Результат 1<йвход , 2-й вход \ раз два раз .2 148 112 148 364 5423 364 ;'-,4 2781 658 658 5 один один один Таблица 3.6 № опыта ■ Информация на входах f’ , Результат \.',Чгй:|хрД-'':'': 2 и вход -1 ■ крокодил бегемот не понимаю ■ 2^-' 15 6 не понимаю " 3; ■ 6 крокодил не понимаю крокодил 3 дил 5 крокодил 15 не могу Таблица 3.7 № опыта Информация на входах Результат 1-й вход , 2-й вход ■ "1 шалаш шапка 3 .2. физика 4 0 3 42 12 1 ^ .'4 (№%? %!)№ 2 5 28 попугаев 44 чижа 2 108 Таблица 3.8 № опыта Информация на входе Результат , , 1-й выход 2-й выход ' 1 шалаш Не понимаю 2 1268 1 3 3 3157 4 0 4 4444 0 4 5 123456 3 3 Таблица 3.9 № опыта Информация на входе Результат 1-й выход 2-й выход 1 1267 16 27 2 крокодил коои ркдл 3 проблема полм рбеа 4 компромисс кмрмс опоис 5 а Не могу Таблица 3.10 № опыта Информация на входе Результат 1-й вьшзд 2-й вьр|Д 1 крокодил Не понимаю 2 123 6 6 3 252 9 20 4 22 4 4 5 11 1 1 6 1 1 1 Таблица 3.11 № опыта Информация на вхбдах Результат 1-й вход 2-й вход 1-й выход 2-й выход 1 вариант коридор не понимаю 2 12 7 19 5 3 12 12 24 0 4 5 43 48 38 5 89 0 89 89 109 Таблица 3.12 Информационное и компьютерное моделирование |о qribiTcft if .<'Ь, Информация на входах Результат 1-й вход 2-й вход 1^й-выход 2-й выход '1 шалаш коробка Не понимаю 2 шалаш 4 Не понимаю ' 3 9 8 72 1 4 12 16 48 4 5 25 25 25 25 Таблица 3.13 № опыта Информация на входах Результат 1-й вход 2-й вход 1-й выход 2-й выход 1 beoin end Не понимаю 3 for Не понимаю . ' 3 integer 3 t о .'4 ’■ abc 4 Не могу '■ 5"'"' abb 3 а Ь 17.4. Фактографические модели Фактографическими называют такие статические информационные модели, объекты в которых описываются значениями некоторого набора признаков, фиксированного для данной модели. Признаки, которыми характеризуется объект, по-другому называют атрибутами. Выбор атрибутов определяется целями моделирования. Нередко фактографическую модель представляют в виде базы данных (сокраш;енно БД). Базу данных определяют, в свою очередь, как совокупность сведений о конкретных объектах реального мира в какой-либо предметной области или разделе предметной области. В практике используются три вида баз данных: иерархические, реляционные и сетевые. В иерархических базах данных атрибуты соподчинены между собой так, что данные образуют древовидную структуру. Сетевая база данных представляет собой более общую структуру, нежели иерархическая база — в ней элементы связаны не только от одного уровня к следующему, а, вообще говоря, произвольным образом. Реляционная база данных — это совокупность связанных между собой таблиц, столбцы которых задаются атрибутами данных, а каждая строка состоит из значений атрибутов для койкре^ного объекта. ■ no ! Для работы с фактографической моделью, представл^-ной той или иной базой данных, требуется специаль^я программная оболочка, называемая системой управления базой данных (сокращенно СУБД). Система управления базой данных играет роль, аналогичную языку программирования. Можно считать, что это некоторая система ко]манд, обеспечивающая организацию данных и манипулирование ими. Главная функция СУБД — давать ответы на запросы пользователя, иными словами, удовлетворять его информационную потребность. Кроме того, СУБД позволяет изменять (как говорят, редактировать) записи, хранящиеся в базе данных, вносить новые сведения и выполнять другие операции над данными, например упорядочивать их по значениям заданного атрибута (сортировка данных). iSonpocbi и зодания О Ниже перечислены названия баз данных, которые предполагается создать. Для каждой из проектируемых БД назовите атрибуты, которые вы предложили бы иметь в этой БД. Укажите также для каждой из БД, какую структуру — иерархическую, реляционную или сетевую — уместнее всего, по вашему мнению, для нее использовать. а) БД «Почтовые марки». б) БД «Страны Европы». в) БД «Металлы». г) БД «Кислоты». д) БД «Архитектурные памятники моего города» е) БД «Водоемы ...» (вместо многоточия поставьте название вашей области, края или республики). Предложите какую-либо полезную, на ваш взгляд, базу данных и укажите входящие в ее состав атрибуты. Пусть требуется создать базу данных «Овощи». Какие наборы атрибутов вы предложите, если эта база данных нужна: а) овощеводу; б) директору овощехранилища; в) заведующему производством комбината питания. О Пусть проектируется БД «Кулинарные рецепты». Какую структуру — иерархическую, реляционную или сетевую — уместнее всего, по вашему мнению, использовать для такой БД? Приведите аргументы в поддержку своей точки зрения. 0 В БД «Озера» хранятся следующие сведения об озерах мира: • название озера — атрибут Название; • площадь, км^ — атрибут Площадь; • максимальная глубина, м — атрибут Глубина; • континент, на котором расположено данное озеро. Континент; • высота над уровнем моря, м — атрибут Высота; атрибут Ill Информационное и компьютерное моделиромние • происхождение (тектоническое, лагуна, вулканическое, за-прудное, ледниковое, карстовое) — атрибут Происхождение; • наличие или отсутствие стока — атрибут Сток. В запросе к этой БД указывается название атрибута и значения, по которым требуется провести поиск. Например, чтобы найти все озера с глубиной больше 100 м, составляется запрос Глубина >100, а для нахождения африканских озер, не имеющих стока, потребуется запрос Континент = Африка И Сток = Нет. Составьте запросы, позволяющие найти: а) все озера-карлики (площадь меньше 100 км^ ); б) все озера с площадью более 10 000 км^ и глубиной более 500 м; в) все озера, расположенные выше 500 м, кроме африканских; г) все американские озера. 0 Какой запрос БД «Озера» (см. задание 5) надо сформулировать, чтобы выяснить: а) все ли озера ледникового происхождения мельче 100 м; б) все ли озера мельче 100 м имеют ледниковое происхождение? 0 Однажды школьник решил воспользоваться БД «Озера» (см. задание 5), чтобы найти все африканские и австралийские озера. Тут подошел злоумышленник и быстро составил следующий запрос: Континент = Африка И Континент = Австралия. В БД не оказалось озер, удовлетворяющих этому запросу. Объясните почему. Какой запрос надо составить? 17.5. Информационные модели в задачах управления. Понятие обратной связи Под управлением обычно понимают целенаправленное взаимодействие объектов, одни из которых являются управляющими, другие — управляемыми. На рисунке 3.13 схематично изображена ситуация управления для двух объектов. При построении информационных моделей, описывающих системы управления, естественно отвлекаться от особенностей физической реализации как самих объектов, так и каналов передачи управляющих воздействий. С этой точки зрения управляющий объект характеризуется целевыми установками и своими возможностями воздействовать на управляемый объект. В свою очередь, объект управления характеризуется своими функциональными возможностя- Управляющий Управляющее Управляемый объект воздействие объект Рис. 3.13. Схема управления для системы из двух объектов 112 Рис. 3.14. MU (т. е. тем, что он может сделать или в к£1кое состояние перейти) и допустимыми на него воздействиями. Нередко управляющее воздействие осуществляется так, что оно не затрагивает внутреннюю структуру управляемого объекта. Иными словами, управляемый объект выступает как черный ящик (см. § 17.3). В этом случае схема управления выглядит так, как показано на рисунке 3.14. Управление может быть разомкнутым, т. е. не учитывать информацию о состоянии объекта управления, и управлением по принципу обратной связи. Последнее понятие возникло в кибернетике как средство описания саморегулирующихся систем. В схеме управления наличие обратной связи означает, что информация с тех или иных выходов поступает на входы (рис. 3.15). Обратной связью называют воздействие выходных параметров динамической системы на ее же входные параметры. Главным атрибутом обратной связи является то, что изменение состояния объекта непосредственно связано с этим состоянием. Различают системы управления с положительной и отрицательной обратной связью. Эпитет «отрицательная» означает, что она обеспечивает выработку управляющего воздействия, направленного на уменьшение рассогласования между заданным и действительным параметрами системы. Возникающий при этом эффект устойчивости системы к внешним воздействиям называют гомеостазом системы. Положительная обратная связь, наоборот, усиливает возникшее рассогласование. >*ис. 3.15. Схема управлений) с обратной бвйзыо [113 Информационное и компьютерное моделироеоние Что называется управлением динамической системой? Привейте примеры управления какими-либо динамическими системами. Могут ли при моделировании систем управления использоваться статические модели для представления объекта управления? Среди приведенных ниже примеров взаимодействия укажите те, которые относятся к понятию обратной связи. Для каждого указанного вами случая укажите тип обратной связи, т. е. положительна она или отрицательна. а) изменение времени года и количество листьев на деревьях; б) изменение цены на товар и количество покупателей этого товара; в) изменение сигналов светофора и движение транспорта через перекресток; г) звонок будильника и переход человека от сна к бодрствованию; д) изменение яркости горения лампочки и подаваемого напряжения; е) изменение числа хищников и числа травоядных животных на данной тер-ритории. О Как вы считаете, верно ли утверждение, что в живой природе любая динамическая система обязательно облада-ет механизмом обратной связи? О Первым применением в технических системах управления по принципу обратной связи было создание регулятора Уатта, управлявшего подачей пара в цилиндры паровой машины (рис. 3.16). а) Какой тип обратной связи использовался в этом регуляторе? б) Приведите примеры других технических систем, в которых используется управление по принципу обратной связи. Постарайтесь, чтобы в этих примерах фигурировала как отрицательная, так и положительная обратная связь. Рис. 3.16. Регулятор Уатта 3 Элементы математической логики Основным понятием математической логики является высказывание. Над высказываниями можно выполнять операции, о которых кратко рассказывается в § 18.1. 18.1. Алгебра логики Высказывание — повествовательное предложение, о котором Можно сЫазатБ, истинно оно или ложно. Договоримся высказывания обозначать большими Латинскими буквами. 114 Таблица 3.14 А в А&В AvB — А-*В \а*^в И и И И Л И и И л Л И л Л л Л и л И и И л л л л Л и И и Если А и В — некоторые высказывания, то высказывание и. В* называется конъюнкцией указанных высказываний и обозначается А & В, высказывание «А или В* называется дизъюнкцией указанных высказываний и обозначается А у В, высказывание «не А» называется отрицанием высказывания А и обозначается -lA, высказывбшие «если А, то В* называется импликацией высказываний А и В и обозначается А ^ В, высказывание «А тогда и только тогда, когда В* называется равносильностью и обозначается А В. Символы &, V, -1, -+, называются логическими связками. Зависимость значений истинности полученных с помощью связок высказываний от значений истинности высказываний А и В определяется таблицей истинности связок (табл. 3.14). Символ «И» означает истинное высказывание, символ «Л» — ложное высказывание. Если Aj, Ag,..., А„ — обозначения некоторых высказываний, то выражение, полученное из них с помощью связок, называется формулой. В формуле могут использоваться скобки для указания порядка применения связок. Чтобы писать меньше скобок, договариваются, что связка -i старше связок & и V, которые, в свою очередь, старше связок —>■ и «-». Если символам придавать значение И или Л, то с помощью таблиц истинности для связок можно вычислить соответствующее значение формулы. Формула называется тождественно истинной, если при любых значениях входящих в нее символов она принимает значение И. Две формулы от одного и того же набора символов называются равносильными, если у них одинаковые таблицы истинности. Формула F называется логическим следствием формул Gj, G2, ..., G„, если она истинна всякий раз, когда истинны все формулы Gj, G2, ..., G„. Вопросы и задания Г О Составьте таблицы истинности для следующих формул: а) X&Y-*-,Y&Z] б) (X & YZ) ^ {{Z-* ^Y) ^ X). О а) Проверьте, что формулы Xv-,XnX^(Y^X) являются тождественно истинными, а формулы X&-iXnX-^(X->y) таковыми не являются. Информационное 15 и компьютерное моделировоние б) Приведите еще несколько примеров тождественно истинных формул. Определите, какие из следующих формул тождественно истинны, а какие нет: а)Х&У^Х; 6)XvV'->X; b)X&V'^XvV'; r)Xvy^X&V'; д) (Х^У)^(/^Х); е) (Х^^Х)->Х; ж) ЬХ-^Х)^Х; 4 (X-^VO-^bV'-^-^X); и) (Х<-^У)^(-,У^-,Х). О ^ Определите, существует ли формула F такая, что формула G тождественно истинна: а) G = X& y->-.F&Z; б) G= {F&Y-* ^Z)(Z^-^Y); в) G = {F&Y^^Z)^((Z^-.Y)-*F). © Постройте формулу F, имеющую таблицу истинности, заданную: а) таблицей 3.15; б) таблицей 3.16; в) таблицей 3.17. О Известно, что высказывание {А v (-В л -А) л (-.С)) ложно. Что можно сказать о значении высказываний Л, S и С? а) Логические переменные К, L \л М таковы, что высказывание {К &.L) ->■ (-.L & М) истинно. Сколько имеется различных наборов значений переменных К, L \л М, удовлетворяющих этому условию? б) Логические переменные К, L \л М таковы, что высказывание {Kv L)-*{L& М) ложно. Сколько имеется различных наборов значений переменных К, L \л М, удовлетворяющих этому условию? Таблица 3.15 Таблица 3.17 X Y Z F и И и и и и л и и л и л и л л л л и и л л и л и л л и и л л л л Таблица 3.16 X Y Z F и и и л и и л и и л и и и л л л л и и и л и л и л л и л л л л и А в с D F и и и и и и и и л л и и л и и и и л л и и л и и л и л и л и и л л и л и л л л и л и и и и л и и л л л и л и и л и л л л л л и и л л л и л и л л л и л л л л л и 116 0 о а) Докажите, что формулы F и G равносильны тогда и тольк тогда, когда формула F •е-» G тождественно истинна, б) Докажите, что формула F является логическим следствием формул G,, Ог.... G„ тогда и только тогда, когда формула G, & (З2 &... & G„ F тождественно истинна. © Обозначим буквой U высказывание «я поеду автобусом», буквой V высказывание «автобус опоздает», буквой W высказывание «я пропущу свидание», буквой X высказывание «я начну огорчаться», буквой Y высказывание «мне следует ехать домой», буквой Z «я получу работу». а) Запишите формулами следующие высказывания: «Если я поеду автобусом и автобус опоздает, то я пропущу свидание» (формула Fi); «Если я пропущу свидание и начну огорчаться, то мне не следует ехать домой» (формула Fj); «Если я не получу эту работу, то я начну огорчаться и мне следует ехать домой» (формула F3); «Если я поеду автобусом и автобус опоздает, то я получу работу» (формула F4). б) Верно ли, что формула F4 является логическим следствием формул F,, F2 и F3 ? в) Верно ли, что формула F, является логическим следствием формул F2, F3 и F4 ? Обозначьте буквами элементарные высказывания (т. е. такие высказывания, которые уже бессмысленно представить с помощью связок других высказываний) и, используя их, запишите формулами следующие высказывания. а) Если Джонс не встретил этой ночью Смита, то Смит был убийцей или Джонс врет. Если Смит не был убийцей, то Джонс не встретил Смита этой ночью и убийство произошло после полуночи. Если убийство произошло после полуночи, то Смит был убийцей или Джонс лжет. Убийство произошло до полуночи. Смит был убийцей. б) Намеченная атака удастся, если захватить противника врасплох или его позиции плохо защищены. Захватить противника врасплох можно, только если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Атака не удастся. в) Верно ли, что в каждом из пунктов а и б последнее высказывание является логическим следствием всех предыдущих? 18.2. Решение логических задач средствами математической логики При решении логических задач требуется установить истинность или ложность некоторых высказываний, если известна истинность некоторых формул, куда искомые высказывания входят как переменные. Иными словами, нужно проверить, является ли интересующее нас высказывание или его отрицание логическим Следствием формул, данных в условии задачи. 117 I О Информационное и компьютерное моделирование Идут соревнования школы по прыжкам в длину. Осталось четыре участницы. В этот момент болельщиками были сделаны такие прогнозы: а) Первой будет Наташа, а Майя будет второй. б) Лида займет второе место, а Рита будет четвертой. в) Второй будет Наташа, а Рита третьей. После окончания соревнований оказалось, что в каждом из этих прогнозов только одно утверждение верно. Кто какое место занял в соревновании? В финал соревнований вышли 4 спортсмена: Алексеев, Борисов, Васильев и Дмитриев. Перед началом финала болельщики высказали такие предположения: а) Васильев победит, а Алексеев будет вторым; б) Алексеев будет третьим, а Дмитриев — первым; в) Васильев будет последним, а первым будет Борисов. После окончания соревнований оказалось, что каждый болельщик был прав только в одном своем прогнозе. Определите, как распределились места среди спортсменов. В спортивных соревнованиях принимали участие пять спортсменов: Антонов, Бодров, Васин, Горин и Дроздов. До начала соревнований болельщиками были сделаны такие прогнозы: а) Первое место завоюет Горин, а Бодров будет четвертым. б) Васин выйдет победителем, а Дроздов займет второе место. в) Дроздов займет третье место, а Васин окажется последним. г) Горин будет четвертым, а Антонов — вторым. После соревнований оказалось, что в каждом из этих прогнозов только одно утверждение верно. Кто какое место занял в соревновании? Футбольный мяч среди осколков вазы — бесспорная улика происшествия. Однако на вопрос «Кто это сделал?» три его участника дали следующие ответы. — Коля не бил по мячу — это сделал Витя. — Разбил Коля. Саша вообще не играет в футбол дома. — Витя не виноват, и вообще, я еще уроки не сделал. Выяснилось, однако, что только двое в каждом из своих заявлений говорили правду, а один оба раза солгал. Кто же разбил вазу? Один из трех братьев разбил чашку. На вопрос «Кто это сделал?» от них были получены следующие ответы. а) Витя не разбивал чашку, это сделал Боря. б) Чашку разбил Витя, а Алеша не виноват. в) Этого не делал ни Боря, ни Витя. Оказалось, что двое мальчиков сказали правду только в одном своем утверждении, а третий мальчик оба раза солгал. Кто же разбил чашку? 118 ^ Один из четырех мальчиков разбил окно. На вопрос «Кто это сделал?» от них были получены следующие ответы. а) Это сделал Миша или Коля. б) Это сделал Витя или Коля. в) Это не могли сделать ни Толя, ни Миша. г) Это сделал Витя или Миша. Оказалось, что три из этих четырех утверждений истинны. Можно ли по этим данным определить, кто разбил окно? Q В туристическом походе в одной палатке жили Алеша, Боря, Витя и Гоша. Все они учатся в разных классах (с 5-го по 8-й) и занимаются в разных кружках: математическом, авиамодельном, шахматном и фотокружке. Выяснилось, что Алеша и шестиклассник учатся в одной школе. Фотограф старше Гоши, Алеша старше Вити, а шахматист старше Алеши. В воскресенье Алеша с фотографом играли в теннис, а Гоша проиграл авиамоделисту в городки. Определить, кто в каком классе учится и в каком кружке занимается. ф На свой день рождения Миша пригласил Дашу, Машу и Наташу. Но, зная, что отношения у девочек между собой не простые, он предположил: а) если придет Маша, то Наташа придет только в том случае, если придет Даша; б) не может быть, чтобы не пришла ни Даша, ни Маша; в) достаточное условие, чтобы не пришла Наташа, — это отсутствие Даши. После дня рождения оказалось, что из трех предположений только одно было ложным. Кто был у Миши на дне рождения? ^ В некотором королевстве узника, приговоренного к смерти, отдавали на растерзание тигру. Но милосердный король давал ему шанс спастись. Узнику предлагалось самому выбрать, в какую из двух комнат войти. В каждой комнате мог находиться кто-то один: принцесса или тигр, впрочем, могло быть, что в каждой комнате находится по принцессе или, наоборот, по тигру. На двери каждой комнаты висит табличка с высказыванием. Друзья предупредили узника, что высказывания либо оба одновременно истинны, либо оба ложны. Подойдя к дверям, узник на одной из них прочитал: «По крайней мере в одной из этих комнат находится принцесса». На двери второй комнаты висела табличка: «В другой комнате — тигр». Может ли узник избежать встречи с тигром и если да, то в какую дверь ему следует войти? Основы вычисписолмой в памяти компьютера вся информация представляется в двоичном коде. Это положение называют принципом двоичного кодирования — одним из трех так называемых принципов фон Неймана, лежащих в основе вычислительной техники. Соответственно, обработка информации в компьютере — это преобразование исходной последовательности символов двухсимвольного алфавита в результирующую последовательность. Символы двз^символь-ного алфавита договоримся обозначать О и 1. Технически такой алфавит может быть реализован по-разному: низкий и высокий потенциал напряжения, отсутствие или наличие намагниченности, низкая или высокая интенсивность светового потока. Для осуществления такого двоичного кодирования напряжение на все логические элементы компьютера подается дискретно — импульсами — с оп1>еделенной тактовой частотой. Появление импульса на входе логического элемента кодирует подачу символа 1 на этот вход. Отсутствие импульса на входе логического элемента кодирует подачу символа О. Логические элементы. Вентили Логическим элементом или вентилем называют устройство с несколькими входами (возможно, одним) и одним выходом, которое преобразует входные двоично закодированные сигналы в двоичный сигнал на выходе. Условно логический элемент можно изобразить так, как показано на рисунке 4.1. Различных логических элементов с п вхо- ^ дами существует 2^". В таблице 4.1 указано, у} как логические элементы с одним входом обрабатывают входной сигнал. Элемент X называется тождественной еди- " ницей, элемент е (л:) — просто тождественным. Рис. 4.1 / 120 Таблица 4.1 Входной сигнал X Сигнал на выходе X е(х) vM 0 0 1 0 1 0 1 1 1 0 0 Рис. 4.2. Комбинация ^2 ^г)' элементов f, и fg & а) Г элемент v (л:) — отрицанием (или вентилем НЕ), элемент о — тождественным нулем. В таблице 4.2 указано, как обрабатывает пару входнйх сигналов каждый из 16 логических элементов с двумя входами. Приведем общепринятые названия некоторых из этих логических элементов (не повторяя названных ранее). & — конъюнкция (или вентиль И); V — дизъюнкция (или вентиль ИЛИ); —»• — импликация; — эквиваленция; Ф — антиэквиваленция (или сравнение по модулю 2); I — элемент Шеффера; Т — элемент Пирса. Логические элементы можно комбинировать друг с другом, подавая на входы одного элемента то, что получилось на выходах дру-—^ ^ гих элементов. Пример такой комбинации ' ^ изображен на рисунке 4.2. Получившееся устройство можно рассматривать как логический элемент с тремя входами Xi, JCg, Xg. Комбинируя вентили НЕ, И, ИЛИ можно собрать схему, равносильную любому логическому элементу от любого числа переменных. Для удобства эти вентили в схемах обозначают так, как показано на рисунке 4.3. б) в) Рис. 4.3. Обозначения вентилей: а) И; б) ИЛИ; в) НЕ Таблица 4.2 Входной сигнал XiXg Сигнал на выходе X X, vxg Xg —X, Х,-»Х2 Xi|X2 e(Xi) е(Х2> X, ФХ2 00 1 0 1 1 1 0 0 0 01 1 1 0 1 1 0 1 1 10 1 1 1 0 1 1 0 1 11 1 1 1 1 0 1 1 0 I 121 Основы вычислительной техники MM.in.nni'KTT о Для каждого из заданных логических выражений постройте схему из вентилей И, ИЛИ, НЕ. а) Х->Уу(ХуУ)&Х: б) Y&(Xv Y)&Z; в) Z& YvX&{YvZ). 0 Упростите логические выражения, приведенные в задании 1, и для каждого из них постройте соответствующую схему. О а) Составьте формулу для схемы, изображенной на рисунке 4.4. б) Составьте таблицу значений логической функции, реализованной схемой, изображенной на рисунке 4.4. в) Какая функция из перечисленных в таблице 4.2 эквивалентна логической функции, реализованной данной схемой? О Выполните задание 3 для схемы, изображенной на рисунке 4.5. ^ У 0 Выполните задание 3 для схемы, изображенной на рисунке 4.6. 0 Выполните задание 3 для схемы, изображенной на рисунке 4.7. 0 а) Для импликации, эквиваленции, антиэквиваленции, элемента Шеффера и элемента Пирса постройте эквивалентные им схемы, использующие только вентили И, ИЛИ, НЕ. б)* Объясните, почему из вентилей И, ИЛИ, НЕ можно собрать схему, эквивалентную любому логическому элементу. 0 а) Можно ли из вентилей И и НЕ построить схему, эквивалентную вентилю ИЛИ? Для положительного ответа укажите такую схему, отрицательный ответ обоснуйте. 4 5 Рис. 4.4 X у Рис. 4.6 Рис. 4.7 I 122 б)* Можно ли из вентилей И и ИЛИ построить схему, эквивалентную вентилю НЕ? Для положительного ответа укажите такую схему, отрицательный ответ обоснуйте. О Составьте для логической функции f таблицу значений. Какая из функций, перечисленных в таблице 4.2, эквивалентна функции f? ж л л а) f = (у — X): б) f = (XI у) I (у IX): в) f = (xty) t (ytx). 2$ Организация памяти компьютера Для запоминания одного бита информации в оперативной памяти применяется устройство, называемое триггером. На рисунке 4.8 приведена схема так называемого SR-тригге-ра (от английских Set — установка и Reset — сброс). Триггер имеет ^ва входа — S и Д, а также два выхода, обозначенные Q и Q. Такое обозначение выходов не случайно: эти выходы всегда имеют противоположные значения. Но у этой схемы есть еще одна важная особенность — наличие контура обратной связи. Как уже было сказано, напряжение на входы подается не непрерывно, а импульсами. Поэтому процесс управления триггером дискретен^. Каждый импульс кодирует число 1. Таблица значений выходов триггера в зависимости от сигналов, подаваемых на его входы, приведена в таблице 4.3. В двух п^ледних строках: значения Q и Q оказались равными вместо того, чтобы быть противоположными. Поэтому на входы SR-тригтера запрещается одновременно подавать значения S = 1 и Д = 1. Подача 1 на вход S устанавливает триггер в положение 1, а подача 1 на вход Д сбрасывает его значение до 0. Если же никаких импульсов не поступает или продолжает поступать Рис. 4.8 Таблица 4.3 Входы Выходы S Я Q Q а 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 0 * В реальной схеме для того, чтобы на каждом такте на входы подавалось уже выработанное значение Q, после НЕ-элементов ставится синхронизирующий элемент задержки. 123 Основы вычислительной техники импульс на тот же вход, то состояние триггера не меняется. Это и означает, что триггер помнит ин^юрмацию. Восемь расположенных подряд бит птяти (иными словами, блок из восьми триггеров) образуют в памяти компьютера 1 байт. Все байты пронумерованы, начиная с 0. Номер байта называется его адресом. Адреса в пгиияти компьютера представлены в двоичной системе счисления. Занесение информации в память, а также извлечение из памяти производится процессором по указанному ему адресу. Наибольшая последовательность бит, которую процессор может обрабатывать как единое целое, называется машинным словом. Длина машинного слова всегда является степенью числа 2 (но не меньше 8). Адрес машинного слова — это наименьший адрес содержащегося в нем байта. О Укажите контур обратной связи в SR-триггере. Какую, по вашему мнению, роль играет этот контур в обеспечении возможности триггера запоминать информацию? © Проверьте правильность заполнения таблицы 4.3. © На рисунке 4.9 приведена схема JK-триггера. а) Составьте таблицу значений выходов в зависимости от сигналов, подаваемых на вход для JK-триггера. б) Объясните, почему и в этом триггере следует запретить одновременную подачу сигнала 1 на оба входа. в) Выясните, как на JK-триггере устанавливается значение 1 и как оно сбрасывается. Почему можно считать, что JK-триггер выполняет роль элемента памяти? О Укажите контур обратной связи в JK-триггере. Какую, по вашему мнению, роль играет этот контур в обеспечении возможности триггера запоминать информацию? © Компьютер имеет память 2 Кб. Каков наибольший возможный адрес байта памяти компьютера? Ответ запишите в двоичном коде. Переведите адрес этого байта в шестнадцатеричный код. © Компьютер работает с 4-байтовым машинным словом. а) Какие адреса имеют машинные слова в этом компьютере? б) Сколько машинных слов может содержать память компьютера, если объем памяти составляет 1 Кб? в) Каков наибольший адрес машинного слова? Png.i..4i,8. 124 Основная литература Гейн А. Г. Информатика и информационные технологии: учеб, для 8 кл. общеобразоват. учреждений / А. Г. Гейн, А. И. Сенокосов, Н. А. Юнерман. — М. : Просвещение, 2005. Гейн А. Г. Информатика и информационные технологии: учеб, для 9 кл. общеобразоват. учреждений / А. Г. Гейн, А. И. Сенокосов. — М. : Просвещение, 2006. Сенокосов А. И. Информатика: учеб, для 8—9 кл. шк. с углуб. изучением информатики / А. И. Сенокосов, А. Г. Гейн. — М. : Просвещение, 1995. Семакин И. Г. Информатика. Базовый курс для 7—9 кл. / И. Г. Семакин, Л. А. Залогова, С. В. Русаков, Л, В. Шестакова. — М. : Лаборатория Базовых Знаний, 2000. Информатика. Задачник-практикум. В 2 т./ под ред. И. Г. Семакина, Е. К. Хеннера. — М. : ЛБЗ, 1999. — 304 с.; т. 2 — М. : ЛБЗ, 1999. Мачульскнй В. В. Культура информационной деятельности: Базовый курс информатики и информационных технологий. 7 кл. / В. В. Мачульский, В. И. Жильцова, В. Г. Мещериков и др. — Смоленск: Ассоциация XXI век, 2003. Мачульский В. В. Культура информационной деятельности: учеб, пособ. для 8 кл. общеобразоват. учреждений / В. В. Мачульский, А. Г. Гейн, В. И. Кадочникова и др. — Смоленск: Ассоциация XXI век, 2004. Мачульский В. В. Культура информационной деятельности: учеб, пособ. для 9 кл. общеобразоват. учреждений / В. В. Мачульский, А. Г. Гейн, В. И. Жильцова и др. — Смоленск: Ассоциация XXI век, 2006. Дополнительная литература Алексеев А. В. Олимпиады школьников по информатике / А. В. Алексеев. — Красноярск: Кн. изд-во, 1995. Андреева Е. Системы счисления и компьютерная арифметика / Е. Андреева, И. Фалина. — М. : ЛБЗ, 2000. Гейн А. Г Информатика и информационные технологии: кн. для учителя: метод, рекомендации к учеб. 8 кл. / А. Г. Гейн, Н. А. Юнерман. — М. : Просвещение, 2005. Касаткин В. Н. Информация, алгоритмы, ЭВМ: пособие для учителя / В. Н. Касаткин. — М. : Просвещение, 1991. Кольман Э. Занимательная логика / Э. Кольман, О. Зих. — М. : Наука, 1966. Ефимова О. А. Практикум по компьютерной технологии: метод. пособие / О. А. Ефимова, М. В. Моисеева, Ю. А. Шаф-рин. — М. : АБФ, 1997. Шафрин Ю. А. Информационные технологии / Ю. А. Шаф-рин. — М. : Лаборатория Базовых Знаний, 1998. I 125 Ответы 6 2.7. ПОРТРЕТ. 8. 101001010110100. 10. а) 0110100111; б) Г0010101100; в) 0110010111100; г) 10100111001101. 11. а) 0111011110100110. 16. рекурсия. § 3.3. 4 цвета. 4. 800 байт. 8. б) Бирюзовый; в) серый; д) светло-желтый. §4.1. 14. а) 4; б) 5. 15. 7. 16. а) 5, 7 и 35; б) 9 и 27. 19. х= 14. 20. х = 7, у = 4. § 4.2.4. 45. _ § 4!з!_2._ а)_10, JTT. JITjT, 1000000ЛТ, ТТО, TTiTI; б) 12, 10, 110_1, 11_1_1_1, 11, 22, 1101. 7. а) 1011, б) 1110, д) 1111011, е) 11001111. § 5.1.6. 6. 7. 70 байт. 8. 600 бит. 11. 256. 12. 8. § 5.2. 2. 3. 3. 17. 5. а) 5; б) 5. §7.1.13. а) За 4 взвешивания; б) за 7 взвешиваний. 14. а) За 3 взвешивания; б) за 5 взвешиваний. § 8.2. 2. а) 3 раза; б) 2 раза; в) 1 раз. §9.1.2. е) X := (y + z +abs (y-z))/2. 9. а) а = 0, Ь = 0; цикл исполняется 1 раз; б) а = 13, Ь=1; цикл исполняется 0 раз; в) а = 3, Ь=1; цикл исполняется 12 раз. 14. а) Хз = -5; Х4=13; Ху = -181. § 9.2. 4. а) Сообщит слово «кок» и прекратит работу; б) сообщит слово «потопот» и прекратит работу; в) алгоритм зациклится. § 9.3. 2. а) -10, -9, -8, -7, 3, 4; в) -8, -7, -6, -5, -4, -2, -3, -2, -1, 2, 3; г) 2, 4, 6. § 10.3.1. б) ропот; в) дорого. § 11. 3. а) 4; б) 8; в) 24. 4. а) 2, 3, 0, 2, 3. 2. 5. б) 4. 6. а) 2, -1, -3, -2, -1,-1. § 13. 1. б) 10 взвешиваний, 10 взвешиваний, 8 взвешиваний, 7 взвешиваний. §14. 9. Числа на всех гранях кубика должны быть одинаковыми. 13. а) 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99. § 17.2.6. а) 5; б) 5; в) 4; г) 5. 7. б) Маршрут для первого графа: СБГЕЖДВАИЗС; маршрут для второго графа СБГЕЗКИЖДВАЛС. § 18.2. 2. 1-е место — Дмитриев, 2-е место — Алексеев, 3-е место — Борисов, 4-е место — Васильев. 4. Коля. 8. Никто из этих трех девушек. 9. Избежит встречи с тигром, если войдет во вторую дверь § 19. 8. Можно; схема приведена на рисунке О.1. О—^ 1126 Содержание Предисловие............................ 3 Раздел 1. Информация, виды информации и способы ее представления....................................... 4 § 1. Информация и информационные процессы............ — § 2. Кодирование символьной информации............... 8 § 3. Кодирование видеоинформации.....................15 § 4. Кодирование числовой информации.................17 4.1. Позиционные системы счисления с произвольным основанием........................................— 4.2. Системы счисления, используемые в программировании .........................................19 4.3. Уравновешенные и другие системы счисления 22 § 5. Измерение количества информации............... 23 5.1. Информационный объем сообщения..............24 5.2. Количество информации как мера неопределен- ности. Вероятностный подход к измерению количества информации..................................26 5.3. Измерение количества информации по Колмогорову 29 Раздел 2. Алгоритмизация, структуры данных и элементы программирования......................................30 § 6. Понятие алгоритма и исполнителя. Линейные алгоритмы..........................................— § 7. Ветвления в алгоритме............................34 7.1. Ветвления в полной и неполной формах.........35 7.2. Конструкция Выбор............................38 § 8. Циклы............................................39 8.1. Цикл с предусловием (цикл Делать пока) и цикл с постусловием (цикл Повторить ... до)............40 8.2. Цикл простого повторения (цикл Повторить п раз) и цикл со счетчиком (цикл Делать от ... до). . . 43 § 9. Переменные в алгоритмах..........................45 9.1. Переменные числового типа....................46 9.2. Переменные символьного типа..................53 9.3. Переменные логического типа..................57 § 10. Вспомогательные алгоритмы и подпрограммы.........59 10.1. Вспомогательный алгоритм-процедура..........60 10.2. Вспомогательный алгоритм-функция............64 10.3. Рекурсия....................................66 10.4. Нисходящее и восходящее программирование. . . 67 127 § 11. Массивы.........................................70 § 12. Графы...........................................75 § 13. Основные вычислительные методы..................78 13.1. Методы приближенного решения уравнений. ... — 13.2. Методы сортировки.........................80 § 14. Свойства алгоритмов.............................82 § 15. Универсальный исполнитель......................89 15.1. Машина Тьюринга............................— 15.2. Машина Поста..............................97 Раздел 3. Информационное и компьютерное моделирование ............................................. ... 96 § 16. Системы и структуры..............................— § 17. Информационное моделирование....................97 17.1. Понятие информационной модели.............98 17.2. Статические модели........................99 17.3. Динамические модели. Черный ящик.........105 17.4. Фактографические модели..................109 17.5. Информационные модели в задачах управления. Понятие обратной связи....................111 § 18. Элементы математической логики.................113 18.1. Алгебра логики...........................— 18.2. Решения логических задач средствами математической логики................................116 Раздел 4. Основы вычислительной техники..............119 § 19. Логические элементы. Вентили.....................— § 20. Организация памяти компьютера..................122 Основная литература................................. 124 Дополнительная литература..............................— Ответы...............................................125 Учебное издание Гейн Александр Георгиевич Юнерман Нина Ароновна ИНФОРМАТИКА И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Задачник-практикум Учебное пособие для учащихся 8—9 классов общеобразовательных учреждений Зав. редакцией Т. А. Бурмистрова, Редактор О. В. Платонова Художник 0.77. Богомолова Художественный редактор 0.77. Богомолова Технический редактор и верстальщик 77. В. Лукина Корректоры А. К. Райхчин, Л. С. Александрова Налоговая льгота — Общероссийский классификатор продукции ОК 005-93— 953000. Изд. лиц. Серия ИД № 05824 от 12.09.01. Подписано в печать с оригинал-макета 23.06.08. Формат 60x90 '/,в- Бумага писчая. Гарнитура Прагматика. Печать офсетная. Уч.-изд. л. 7,27. Тираж 3000 экз. Заказ № 3866. Открытое акционерное общество «Издательство «Просвещение». 127521, г. Москва, 3-й проезд Марьиной рощи, д. 41. Отпечатано в ОАО «Тверской ордена Трудового Красного Знамени полиграфкомбинат детской литературы им. 50-летия СССР*. 170040, г. Тверь, проспект 50 лет Октября, 46. )& УДК 373.167.1:004 ББК 32.81я72 Г29 Гейн А. Г. Г29 Информатика и информгщионные технологии : задачник-практикум : з^еб. пособие для учащихся 8—9 кл. общеобразоват. учреждений / А. Г. Гейн, Н. А. Юнерман. — М. : Просвещение, 2008. — 127 с. : ил. — ISBN 978-5-09-016677-5 УДК 373.167.1:004 ББК 32.81я72 ISKN 978-5-09-016677-5 Издательство «Просвещение», 2008 Художественное оформление. Издательство «Просвещение», 2008 Все права защищены А. Г. Гейн, Н. А. Юнерман Тетрадь для лабораторных работ к учебнику 8 класса А. Г. Гейн, Н. А. Юнерман Тетрадь для лабораторных работ к учебнику 9 класса А. Г. Гейн, Н. А. Юнерман Тематические тесты для 8 класса А. Г. Гейн, Н. А. Юнерман Тематические тесты для 9 класса ISBN 978- 5- 09- 016677- 5 III 785090 166775