Учебник. А. Ю. Босова Москва бином. Лаборатория знаний 2016 11 класс Базовый уровень Учебник
 Скачать 4.61 Mb.
|
|
Глава 3. информационное моделирование На основании имеющейся таблицы мы также можем сделать выводы о том, сколькими дорогами соединён тот или иной на- селённый пункт с другими населёнными пунктами: Г1 Г2 Г3 Г4 Г5 Г6 Г7 4 3 3 3 2 2 5 Сопоставив полученную информацию, можем сказать, что че- рез Г1 в таблице обозначен населённый пункт F, а через Г7 — D. Согласно таблице, расстояние между этими пунктами равно 25 км. СамОе ГлаВнОе Модель — это новый объект, который имеет свойства дан- ного объекта, существенные для определённого исследования. Моделирование — метод познания, заключающийся в создании и исследовании моделей. Информационная модель — описание объекта-оригинала на одном из языков кодирования информации. В информатике рассматриваются общие подходы к созданию и использованию информационных моделей, связанные с исполь- зованием компьютерной техники. Информационные модели, реализованные с помощью систем программирования, электронных таблиц, специализированных математических пакетов или программных средств для модели- рования, называются компьютерными моделями. Компьютерное моделирование включает в себя процесс реализации информаци- онной модели на компьютере и исследование с помощью этой модели объекта моделирования — проведение вычислительного эксперимента. Между данными, используемыми в той или иной информаци- онной модели, всегда существуют некоторые связи, определяющие ту или иную структуру данных. Различают линейные и нелиней- ные структуры данных. Линейный односвязный список — последовательность линейно связанных элементов, для которых разрешены операции добав- ления элемента в произвольное место списка и удаление любого элемента. Частным случаем линейного односвязного списка явля- ется стек — последовательность, в которой включение и исклю- чение элементов осуществляются с одной стороны этой последо- вательности. Ещё один частный случай линейного односвязного списка — очередь, представляющая собой последовательность, 145 модели и моделирование §10 у которой включение элементов производится с одной стороны последовательности, а исключение — с другой. Примерами нелинейных структур данных являются графы и деревья. Граф — это множество элементов (вершин графа) вместе с набором отношений между ними, называемых рёбрами (дугами) графа. Дерево — это совокупность элементов (вершин), в которой выделен один элемент (корень), а остальные элементы разбиты на непересекающиеся множества (поддеревья). Каждое поддерево является деревом, а его корень является потомком корня дерева, т. е. все элементы связаны между собой отношением «предок — потомок». Частным случаем дерева является бинарное дерево, в котором каждая вершина может иметь не более двух потомков. Таблица — это структура данных, состоящая из строк и граф (столбцов, колонок), пересечение которых образуют ячей- ки. Таблицы применяют для наглядности и удобства сравнения показателей. Табличный способ представления данных является универсальным — любую структуру данных, в том числе и пред- ставленную в форме графа, можно свести к табличной форме. Это тем более важно в связи с тем, что для компьютерной обработки табличное представление данных является предпочтительным. Вопросы и задания 1. Что такое модель? Что такое моделирование? В каких об- ластях науки и техники оно применяется? 2. Какие модели называются натурными? Приведите примеры натурных моделей. 3. Какие модели называются информационными? Приведите примеры информационных моделей. Какова роль информа- тики в информационном моделировании? 4. Создайте информационную модель одной из комнат вашей квартиры с целью оклейки её обоями. Представьте информа- ционную модель в знаковой и графической формах. 5. Какие модели называются компьютерными информационны- ми моделями? 6. Опишите основные этапы компьютерного моделирования. 7. Приведите примеры линейных структур данных. Чем оче- редь отличается от стека? 8. Муравьи идут друг за другом по неровной лесной тропе. На их пути встречаются ямки, в которые могут провалить- ся несколько муравьёв. Когда ямка заполняется муравьями, 146 Глава 3. информационное моделирование остальные муравьи проходят через неё, а затем по одному вытаскивают провалившихся. Например, вот как четыре му- равья проходят через ямку, вмещающую двух муравьёв: Пусть по тропе идут 8 муравьёв. В каком порядке они бу- дут идти после преодоления участка с четырьмя ямками, вмещающими 2, 4, 5 и 1 муравья соответственно? Какую структуру данных иллюстрирует данный пример? 1) 9. Выясните, что представляет собой обратная польская запись, и вычислите значение записанного с её помощью выраже- ния: 1 2 + 3 →× 4 5 ×→ +. 10. Что такое граф? Какой граф называется ориентированным? Какой граф называется неориентированным? Какой граф на- зывается взвешенным? Приведите примеры. 11. Что такое дерево? Какое дерево называется бинарным? При- ведите примеры. 12. Почему графы и деревья считаются многоуровневыми струк- турами данных? 13. Информация о родственных связях в некоторой семье пред- ставлена следующим образом: parent(Юрий, Пётр); parent(Анна, Ева); parent(Ирина, Георгий); parent(Маргарита, Анна); parent(Анна, Николай); parent(Пётр, Георгий); parent(Михаил, Николай); parent(Маргарита, Пётр); parent(Юрий, Анна); parent(Маргарита, Александр); parent(Дарья, Руслан); parent(Александр, Руслан); parent(Михаил, Ева); parent(Юрий, Александр). Запись parent(A, B) означает, что А является родителем В. Нарисуйте генеалогическое древо этой семьи. Сколько у Ирины племянников и племянниц? 1) По материалам международного конкурса по информатике «Бобёр» (bebras.ru). 147 модели и моделирование §10 14. В кладовке хранятся ёлочные игрушки — большие и ма- ленькие красные и золотые шары и звёзды. При этом иг- рушки разного размера, цвета и формы хранятся в от- дельных коробках. Например, в одной коробке — большие красные звёзды, в другой — маленькие красные звёзды и т. д. Известно, что среди игрушек нет ни маленьких ша- ров, ни маленьких золотых звёзд. Всего звёзд 25, а ша- ров — 17. Всего больших игрушек — 32; красных игру- шек — 28. Золотых звёзд на 2 больше, чем золотых шаров. В скольких коробках хранятся игрушки? Сколько игрушек в каждой коробке? Постройте граф, представляющий состав игрушек. Исполь- зуйте его для решения задачи. Представьте эту же информа- цию в табличной форме. 15. Что с вашей точки зрения более наглядно представляет структуру системы: граф или таблица? Какая форма пред- ставления информации предпочтительна для компьютерной обработки данных? 16. Решите следующую задачу, составив двоичную матрицу. Ваня, Кирилл, Петя и Саша учатся в 5, 6, 7 и 8 классах. Как-то они отправились в лес за белыми грибами. Шести- класснику не повезло — он не нашёл ни одного гриба, а Петя с пятиклассником нашли много грибов. Ваня и семи- классник нашли куст малины и позвали Кирилла полако- миться ягодами. Восьмиклассник, шестиклассник и Кирилл объясняли Саше, как ориентироваться на местности. В ка- ком классе учится каждый из мальчиков? 17. Как осуществляется переход от ориентированного графа к дереву решений? 18. Найдите кратчайший путь от вершины А до вершины F в ориентированном графе: 148 Глава 3. информационное моделирование 19. На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J. По каждой дороге можно двигать- ся только в одном направлении, указанном стрелкой. Сколько разных путей существует из города А в город J? 20. На рисунке представлена схема дорог, связывающих населён- ные пункты A, B, C, D, E, F, G. В таблице содержатся све- дения о длинах этих дорог (в километрах). Схему и таблицу создавали независимо друг от друга, поэтому в них использу- ются разные обозначения. Необходимо выяснить длину пути в километрах из пункта E в пункт F. Г1 Г2 Г3 Г4 Г5 Г6 Г7 Г1 9 2 Г2 9 8 11 Г3 3 12 Г4 2 8 4 7 Г5 3 11 Г6 11 12 4 11 9 Г7 7 9 § 11 моделирование на графах 11.1. алгоритмы нахождения кратчайших путей между вершинами графа Графы как информационные модели находят широкое приме- нение во многих сферах нашей жизни. Например, с их помощью 149 моделирование на графах §11 можно планировать оптимальные транспортные маршруты, крат- чайшие объездные пути, расположение торговых точек и других объектов. Необходимость решения задач, связанных с поиском кратчайшего пути на графе, возникает при проектировании ин- женерных сетей и линий электропередач, в микроэлектронике и во многих других случаях. Путь между вершинами А и В графа считается кратчайшим, если: • эти вершины соединены минимальным числом ребер (в слу- чае, если граф не является взвешенным); • сумма весов рёбер, соединяющих эти вершины, минимальна (для взвешенного графа). Есть множество алгоритмов определения кратчайшего пути между вершинами графа, в том числе: 1) алгоритм построения дерева решений; 2) алгоритм Дейкстры; 3) метод динамического программирования. Алгоритм построения дерева решений, как правило, исполь- зуется для нахождения кратчайшего пути в ориентированном гра- фе. Его мы рассмотрели в предыдущем параграфе. Алгоритм Дейкстры служит для нахождения кратчайшего пути между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Суть алгоритма состоит в следующем. Каждой вершине графа ставится в соответствие метка — минимальное известное рассто- яние от источника до этой вершины. Метка самого источника полагается равной 0. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. На первом шаге расстояние от источника до всех остальных вершин неизвестно. Метки вершин (кроме источника) считаются равными бесконечности, все вершины считаются непосещёнными. Далее, из всех непосещённых вершин выбирается вершина, имеющая минимальную метку. Для каждого из соседей этой вер- шины (кроме отмеченных как посещённые) рассчитывается новая длина пути, как сумма значений текущей метки этой вершины и длины ребра, соединяющего её с соседом. Если полученное зна- чение длины меньше значения метки соседа, то значение метки заменяется полученным значением длины. После рассмотрения всех соседей вершина помечается как посещённая. Этот шаг ал- горитма повторяется, пока есть непосещённые вершины. Работа алгоритма завершается, когда все вершины посещены. 150 Глава 3. информационное моделирование Рассмотрим работу алгоритма на примере. На рисунке 3.12 кружками обозначены вершины графа, в кружки вписаны имена вершин. Вершины соединены линиями — рёбрами графа. Око- ло каждого ребра обозначен его «вес» — длина пути. Рядом с каждой вершиной дана метка — длина кратчайшего пути в эту вершину из вершины А: для вершины А — это 0, для всех дру- гих вершин она неизвестна и обозначена знаком «бесконечность». рис. 3.12. Алгоритм Дейкстры. Начальное состояние Минимальную метку (0) имеет вершина А. Её соседи — вер- шины В, C, D. Очерёдность рассмотрения соседей: B, D, C. По- сле изменения их меток получим результат, представленный на рисунке 3.13. рис. 3.13. Алгоритм Дейкстры. Шаг 1 После изменения меток всех соседей вершины А она поме- чается как просмотренная. Теперь минимальная метка из непро- смотренных вершин у вершины В. Её соседи — вершины D и Е. Так как 5 + 9 > 10, метка вершины D не изменяется. Вершина Е получает метку 19 (рис. 3.14). Теперь минимальная метка из непросмотренных вершин у вер- шины D. Её соседи — вершины С, Е и F. Так как 10 + 3 < 15, метка вершины C изменяется. Вершина F получает метку 18. Метка вершины Е не изменяется (рис. 3.15). 151 моделирование на графах §11 рис. 3.14. Алгоритм Дейкстры. Шаг 2 рис. 3.15. Алгоритм Дейкстры. Шаг 3 Далее в качестве вершин с минимальными метками будут по- очерёдно рассматриваться вершины С, F и E. К изменению меток соседних с ними вершин это не приведёт (рис. 3.16). Полученные в результате работы алгоритма метки вершин графа — это и есть кратчайшие расстояния от вершины А до каждой из этих вершин. рис. 3.16. Алгоритм Дейкстры. Результат работы 152 Глава 3. информационное моделирование Метод динамического программирования основан на том, что процесс решения задачи разбивается на стадии (шаги), на каждой из которых принимаются решения, приводящие к достижению поставленной цели. рис. 3.17. Лабиринт Предположим, персонажу некоторой игры необходимо пройти по лабиринту из пункта А в пункт В, набрав при этом как можно меньше штрафных бал- лов, количество которых указано в клетках лабиринта, причём перемещать- ся можно только вверх или вправо. С помощью графа начальные условия могут быть заданы так, как показано на рисунке 3.17. Составим таблицу, в которой ка- ждая ячейка будет соответствовать определённой клетке лабиринта. Числа в ячейках будут равны минимальному числу штрафных баллов, которое можно получить, пройдя путь от начала до соответствую- щей клетки. Заполнять таблицу будем снизу вверх и слева направо. При этом для заполнения каждой новой ячейки будем рассматривать числа двух соседних с ней заполненных ячеек, находящихся сле- ва от неё и под ней. Будем выбирать наименьшее из этих двух чисел, прибавлять к ним число текущей ячейки и результат за- писывать в неё. 11 8 8 8 8 16 3 3 5 3 5 13 3 5 13 А 9 А 9 А 9 10 А 9 10 17 11 11 11 11 17 11 11 17 17 8 8 16 8 8 16 20 8 8 16 20 3 5 13 22 3 5 13 22 3 5 13 22 А 9 10 17 А 9 10 17 А 9 10 17 Ответ равен числу в правом верхнем углу таблицы. 153 моделирование на графах §11 Давайте считать, что числа, обозначающие веса вершин рассмо тренного графа, — это призовые баллы, которые можно получить, пройдя по соответствующим клеткам лабиринта. Самостоятельно подсчитайте, какое максимальное число призовых баллов можно набрать, пройдя этот лабиринт. 11.2. Знакомство с теорией игр Рассмотрим несколько примеров. Пример 1. Это задачка из учебника информатики для 4 класса 1) Алёша Попович и Добрыня Никитич воюют с девятиглавым змеем. По очереди богатыри хо- дят к его пещере и срубают 1, 2 или 3 головы. Как начавшему бой Алёше обрести славу победи- теля змея (срубить последнюю го- лову), если и Добрыня готов при- ложить все усилия, чтобы стать победителем в этой битве? Изобразим на числовой линейке текущее число голов змея: 9 8 7 6 5 4 3 2 1 0 Здесь: 9 — начальное значение; 0 — конечное значение (по- беда). Алёша обретёт славу победителя, если после его последнего удара у змея останется 0 голов. Для этого нужно, чтобы после очередного удара Добрыни у змея осталось 3, 2 или 1 голова. Иначе говоря, позиции 3, 2 и 1 являются для Алёши выигрыш- ными (как, впрочем, для любого из богатырей, кому они доста- ются в качестве исходных при последнем ударе). Выигрышные и проигрышные позиции на числовой линейке будем помечать буквами «В» и «П» соответственно: В В В 9 8 7 6 5 4 3 2 1 0 Если Добрыня выйдет на бой с черырёхголовым змеем (будет находиться в позиции 4), то любым своим ударом он создаст 1) Семёнов А. Л. Информатика: Учеб. пособие для 4 кл. нач. шк. В 2 ч. Ч. 2 / А. Л. Семёнов, Т. А. Рудченко. — М.: Просвещение, 2008. — 48 с. : ил. 154 Глава 3. информационное моделирование Алёше условия для выигрыша (переведёт Алёшу в выигрышную позицию). Следовательно, задача Алёши на предыдущем шаге состоит в том, чтобы перевести Добрыню в эту заведомо проиг- рышную для него позицию: П В В В 9 8 7 6 5 4 3 2 1 0 Четырёхголового соперника Алёша сможет обеспечить Добры- не, если сам будет находиться в одной из позиций 7, 6 или 5: Любой удар Добрыни приведёт к благоприятному для Алёши результату только в том случае, если Добрыня выйдет на бой с восьмиголовым змеем: П В В В П В В В 9 8 7 6 5 4 3 2 1 0 Следовательно, первым своим ударом Алёша должен срубить змею одну голову. Выигрышная стратегия — это правило, следуя которому игрок вы игрывает независимо от того, как играет противник. Игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Выигрышная стратегия может быть толь ко у одного игрока. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации при различной игре противника. На рисунке 3.18 в форме дерева представлена выигрышная стратегия для Алёши. Поэтому для Алёши всегда указывается один ход («Ход А»), обеспечивающий требуемый результат. А вот для Добрыни, фактически выступающего в качестве соперника, рассматриваются все возможные варианты («Ход Д»). 155 моделирование на графах §11 рис. 3.18. Дерево выигрышной стратегии для Алёши Пример 2. А эта задача из открытого банка заданий ЕГЭ по информатике (fipi.ru). Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может выполнить одно из следующих дей- ствий: • добавить в кучу один камень (+ 1); • добавить в кучу два камня (+ 2); • увеличить количество камней в куче в 3 раза (→× 3). Например, имея кучу из 5 камней, за один ход можно полу- чить кучу из 6, 7 или 15 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда ко- личество камней в куче превышает 45. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 46 или больше камней. Будем считать, что в начальный момент в куче S камней, 1 ≤ S ≤ 45. Выясним, при каких значениях числа S Петя может выиг- рать первым ходом. Если S = 45, то, добавив в кучу один камень (+ 1), два камня (+ 2) или утроив количество камней в ней (→× 3), Петя становится победителем. Если S = 44, то стать победителем можно, если добавить в кучу два камня (+ 2) или утроить количество камней в ней (→× 3). Если S = 43, то Петя становится победителем, утроив количе- ство камней в куче (→× 3). Также можно действовать для любого S ≥ 16 (16 →× 3 = 48, 15 →× 3 = 45). |