Учебник. А. Ю. Босова Москва бином. Лаборатория знаний 2016 11 класс Базовый уровень Учебник
 Скачать 4.61 Mb.
|
|
Глава 2. алгоритмы и программирование 6. Какой вспомогательный алгоритм называется рекурсивным? Что такое граничное условие и каково его назначение в ре- курсивном алгоритме? 7. Алгоритм вычисления значения функции F(n), где n — на- туральное число, задан следующими соотношениями: F(n) = 2 при n ≤ 0; F(n) = F(n –→ 2) + F(n –→ 1) + F(n div 2) при n > 0. Требуется выяснить, чему равно значение функции F(10). 8. Исполнитель Калькулятор имеет следующую систему ко- манд: 1) прибавь 1; 2) умножь на 2. С помощью первой из них исполнитель увеличивает число на экране на 2, с помощью второй — в 2 раза. 1) Выясните, сколько разных программ, преобразующих чи- сло 1 в число 20, можно составить для этого исполни- теля. 2) Сколько среди них таких программ, у которых в качест- ве промежуточного результата обязательно получается чи- сло 15? 3) Сколько среди них таких программ, у которых в качест- ве промежуточного результата никогда не получается чи- сло 12? 9. Попробуйте найти рекурсивные синтаксические структуры: 1) в поэме А. Блока «Двенадцать»; 2) в стихотворении М. Лермонтова «Сон»; 3) в романе М. Булгакова «Мастер и Маргарита»; 4) в фольклоре. 10. Найдите информацию о таких геометрических фракталах, как Снежинка Коха, Т-квадрат, Н-фрактал, кривая Леви, Драконова ломаная. 11. Напишите программу вычисления значения функции F(n), рассмотренной в примере 4 этого параграфа. Вычислите с её помощью значение функции F(7). 12. Напишите программу вычисления C n n k k n k ! ( )! ! . Используй- те подпрограмму. 13. Дана программа: program rek; procedure F(n: integer); 131 Структурное программирование §9 begin if n>0 then begin F(n-4); writeln(n); F(n div 3) end; end; begin F(9) end. Не выполняя программу на компьютере, выясните, что по- лучится в результате работы этой программы. Проверьте свой результат, выполнив программу на компью- тере. Дополнительные материалы к главе смотрите в авторской мастер ской. 132 Глава 3 инфОрмациОннОе мОДелирОВание § 10 модели и моделирование 10.1. Общие сведения о моделировании Человек стремится познать объекты (предметы, процессы или явления) окружающего мира, т. е. понять, как устроен конкрет- ный объект, каковы его структура, основные свойства, законы развития и взаимодействия с другими объектами. При этом за- частую исследуются не сами объекты, а их модели. Из курса информатики основной школы вам известно, что: • модель — это новый объект, который имеет свойства данного объекта, существенные для определённого исследования; • моделирование — метод познания, заключающийся в создании и исследовании моделей; • натурная (материальная) модель — реальный предмет, в уменьшенном или увеличенном виде воспроизводящий внеш- ний вид, структуру или поведение моделируемого объекта; • информационная модель — описание объекта-оригинала на одном из языков кодирования информации; • по форме представления можно выделить знаковые, образные и смешанные информационные модели; • для создания информационной модели объекта необходимо: 1) выяснить цель моделирования; 2) выделить свойства объекта-оригинала, существенные с точ- ки зрения цели моделирования; 133 модели и моделирование §10 3) установить взаимосвязи между значениями выбранных свойств и выразить их в некоторой форме (словесно, таб- лицей, графиком, функцией, уравнением, неравенством, системой и т. п.). Модель — общенаучное понятие; моделирование имеет место в любых областях знания и сферах человеческой деятельности. Приведите примеры моделей, с которыми вы встречались на уро ках физики, химии, биологии, истории, математики, обществозна ния, литературы. В информатике рассматриваются общие подходы к созданию и ис пользованию информационных моделей, связанные с использовани ем компьютерной техники. 10.2. компьютерное моделирование Информационные модели, реализованные с помощью систем про граммирования, электронных таблиц, специализированных матема тических пакетов или программных средств для моделирования, называются компьютерными моделями. компьютерное моделирование включает в себя процесс реали зации информационной модели на компьютере и исследование с помощью этой модели объекта моделирования — проведение вы числительного эксперимента. С помощью компьютерного моделирования решаются многие научные и производственные задачи: прогнозирование погоды и климатических изменений; конструирование транспортных средств и дизайн лекарственных препаратов; стратегическое управление организациями и прогнозирование цен на финансовых рынках; прогнозирование прочности конструкций и исследование поведе- ния зданий, конструкций и деталей под механической нагрузкой; многие другие задачи. Рассмотрим основные этапы компьютерного моделирования более подробно (рис. 3.1). На первом этапе в результате анализа условия задачи опре- деляется объект моделирования и цель создания модели. После этого в объекте моделирования выделяются параметры (свойства, 134 Глава 3. информационное моделирование рис. 3.1. Основные этапы компьютерного моделирования основные части), существенные с точки зрения поставленной цели. Далее уточняется, какие результаты и в каком виде долж- ны быть получены, а также какие исходные данные для этого нужны. На втором этапе определяются параметры модели и связи между ними; приводится математическое описание зависимостей между параметрами модели. На третьем этапе выбирается или разрабатывается алгоритм получения из исходных данных результатов, подбираются про- граммные средства реализации алгоритма на компьютере и со- здаётся компьютерная модель. На четвёртом этапе осуществляется работа непосредственно с полученной компьютерной моделью. Сначала на заранее разрабо- танных тестах (наборах исходных данных, для которых заранее известны результаты) осуществляется проверка правильности (те- стирование) модели, и при необходимости модель дорабатывается. После тестирования, когда есть уверенность в правильности функ- ционирования модели, переходят непосредственно к компьютер- ному эксперименту — целенаправленным действиям пользователя над компьютерной моделью. В ходе такого экспериментирования сознательно изменяются условия функционирования модели и накапливаются данные о её «поведении». В процессе проведения эксперимента может выясниться, что нужно усовершенствовать или изменить используемый алгоритм, уточнить информацион- ную модель или внести изменения в постановку задачи. В таких 135 модели и моделирование §10 случаях происходит возвращение к соответствующему этапу, и процесс начинается снова. На пятом этапе результаты эксперимента анализируются, на их основе делаются выводы о моделируемом объекте. На основе всестороннего анализа полученных результатов принимается не- которое решение, что и является конечной целью моделирования. Компьютерное моделирование даёт возможность: • существенно расширить круг исследуемых объектов (модели- рование прошлого и будущего, несуществующего или невос- производимого в реальных условиях); • исследовать процессы в развитии, при необходимости ускоряя или замедляя их и проводя эксперименты многократно; • находить оптимальные решения без затрат на изготовление пробных экземпляров; • проводить эксперименты без риска негативных последствий для здоровья человека или окружающей среды; • визуализировать получаемые результаты. 10.3. Списки, графы, деревья и таблицы Между данными, используемыми в той или иной информаци- онной модели, всегда существуют некоторые связи, определяющие ту или иную структуру данных. Вспомните, как мы определяли структуру данных при рассмотре нии алгоритмов и программ. О каких информационных моделях тогда шла речь? С какими структурами данных вы сталкивались в программировании? Различают линейные и нелинейные структуры данных. В курсе информатики основной школы вы познакомились с линейным односвязным списком — последовательностью ли- нейно связанных элементов, для которых разрешены операции добавления элемента в произвольное место списка и удаление любого элемента. Связь элементов списка осуществляется за счёт того, что каждый элемент списка содержит кроме данных адрес элемента, следующего за ним в списке. В линейном спи- ске для каждого элемента, кроме первого, есть предыдущий элемент; для каждого элемента, кроме последнего, есть следую- щий элемент. Частным случаем линейного односвязного списка является стек — последовательность, в которой включение и исключение 136 Глава 3. информационное моделирование элементов осуществляются с одной и той же стороны этой по- следовательности. Ещё одним частным случаем линейного односвязного списка является очередь — последовательность, у которой включение элементов производится с одной стороны последовательности, а исключение — с другой. Сторона, где происходит включение эле- ментов, называется хвостом; сторона, где происходит исключе- ние — головой. Понятие очереди как структуры данных очень близко к бытовому понятию «очередь» (рис. 3.2). рис. 3.2. Иллюстрация понятия «очередь» Подумайте, какая связь между стеком и следующими объектами: Почему стек является структурой типа LIFO (от англ. Last In, Firts Out — последним пришёл, первым ушёл)? Почему очередь является структурой типа FIFO (от англ. First In, First Out — первым пришёл, первым ушёл)? Примеры нелинейных структур данных вам также хорошо известны — это графы и деревья (рис. 3.3). Граф — это множество элементов (вершин графа) вместе с набором отношений между ними. 137 модели и моделирование §10 рис. 3.3. Примеры графовых структур Граф является многосвязной структурой, обладающей следую- щими свойствами: 1) на каждый элемент может быть произвольное количество ссы- лок; 2) каждый элемент может иметь связь с любым количеством других элементов; 3) каждая связка может иметь направление и вес. Ненаправленная (без стрелки) линия, соединяющая вершины графа, называется ребром. Линия направленная (со стрелкой) называется дугой. При этом вершина, из которой дуга исходит, называется начальной, а вершина, куда дуга входит, — конечной. Граф называется неориентированным, если его вершины соедине- ны рёбрами. Вершины ориентированного графа соединены дуга- ми. Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией — ве- сами вершин или рёбер. Графы являются основным средством для описания структур сложных объектов. С их помощью можно описать вычислитель- ную сеть, транспортную систему, схему авиалиний и другие объ- екты. Одной из разновидностей графа является дерево. Дерево — это совокупность элементов (вершин), в которой вы- делен один элемент (корень), а остальные элементы разбиты на непересекающиеся множества (поддеревья). Каждое поддерево явля- ется деревом, а его корень является потомком корня дерева, т. е. все элементы связаны между собой отношением «предок — пото- мок». В результате образуется иерархическая структура вершин. Частным случаем дерева является бинарное дерево, в котором каждая вершина может иметь не более двух потомков. Деревья используются для представления родственных связей (генеалогическое дерево), для определения выигрышной стратегии в играх и т. д. 138 Глава 3. информационное моделирование Ещё одной знакомой вам структурой данных являются табли- цы, состоящие из строк и граф (столбцов, колонок), пересечение которых образуют ячейки. Таблицы применяют для наглядности и удобства сравнения показателей. Оформляют таблицы в соответствии с рисунком 3.4. рис. 3.4. Оформление таблицы Название таблицы, при его наличии, должно отражать её содер жание, быть точным, кратким. Название следует помещать над таб лицей. Заголовки граф и строк таблицы следует писать с прописной буквы, а подзаголовки граф — со строчной буквы, если они со ставляют одно предложение с заголовком, или с прописной буквы, если они имеют самостоятельное значение. В конце заголовков и подзаголовков таблицы точки не ставят. Заголовки и подзаголовки граф указывают в единственном числе. Если все показатели, приведенные в графах таблицы, выражены в одной и той же единице физической величины, то её обозначение необходимо помещать над таблицей справа. Если в графе табли цы помещены значения одной и той же физической величины, то обозначение единицы физической величины указывают в заголовке (подзаголовке) этой графы. Эти и другие требования к оформлению таблиц содержатся в ГОСТ 2.105–95 «ЕСКД. Общие требования к оформлению текстовых документов». В курсе информатики основной школы вы познакомились с таблицами типа: • «объект — свойство», содержащими информацию о свойствах отдельных объектов, принадлежащих одному классу; 139 модели и моделирование §10 • «объект — объект», содержащими информацию о некотором одном свойстве пар объектов, принадлежащих одному или разным классам. Таблицы, в которых отражено наличие или отсутствие связей между отдельными элементами некоторой системы, называются двоичными матрицами. Вспомните и приведите примеры таблиц типа «объект — свойст во», «объект — объект», отражающих не только количественные, но и качественные характеристики свойств (двоичные матрицы). Табличный способ представления данных является универсаль- ным — любую структуру данных, в том числе и представленную в форме графа, можно свести к табличной форме. Это тем более важно в связи с тем, что для компьютерной обработки табличное представление данных является предпочтительным. Пример 1. Построим таблицу, соответ- рис. 3.5. Граф схе- мы дорог ствующую неориентированному графу (рис. 3.5), отражающему схему дорог между не- которыми населёнными пунктами. Строки и столбцы таблицы будут со- ответствовать вершинам графа. Если две вершины являются смежными (соединены ребром), то в ячейку на пересечении со- ответствующих столбца и строки будем записывать вес этого ребра. В противном случае (вершины не являются смежными) в ячейку будем записывать 0. Получится таблица типа «объ- ект — объект». Такую таблицу называют матрицей смежности. Часто в ма- трицах смежности вместо нуля ставят знак минус, что обеспечи- вает б→ольшую наглядность. A B C D A B C D A 0 7 6 0 A – 7 6 – B 7 0 9 0 B 7 – 9 – C 6 9 0 13 C 6 9 – 13 D 0 0 13 0 D – – 13 – 140 Глава 3. информационное моделирование Матрица смежности неоринтированного графа симметрична от- носительно главной диагонали, идущей от левого верхнего угла к правому нижнему углу. У матрицы смежности неориентирован- ного графа такая симметрия отсутствует. Пример 2. Обед в школьной столовой состоит из двух блюд и напитка. На первое можно выбрать щи или окрошку, на вто- рое — плов или пельмени, на третье — сок или компот. Все возможные варианты представлены с помощью дерева на ри- сунке 3.6. рис. 3.6. Дерево вариантов обеда Для того чтобы представить эту же информацию в таблице, будем двигаться по дереву от листьев к корню, описывая все возможные варианты обеда. Обед Напиток 2-е блюдо 1-е блюдо Вариант 1 Сок Плов Щи Вариант 2 Компот Плов Щи Вариант 3 Сок Пельмени Щи Вариант 4 Компот Пельмени Щи Вариант 5 Компот Плов Окрошка Вариант 6 Сок Плов Окрошка Вариант 7 Компот Пельмени Окрошка Вариант 8 Сок Пельмени Окрошка 141 модели и моделирование §10 Получилась таблица типа «объект–свойства»: объектами в ней являются варианты обеда, а свойствами — составляющие его блюда. При этом число граф в полученной таблице соответствует числу уровней в дереве. При решении класса задач, связанного с нахождением крат- чайшего пути в ориентированном графе, можно: 1) от исходного графа перейти к матрице смежности; 2) по матрице смежности построить дерево решений; 3) по дереву решений выбрать подходящий вариант. Пример 3. Найдём кратчайший путь от вершины А до вер- шины F в графе, приведённом на рисунке 3.7. рис. 3.7. Ориентированный граф Составим матрицу смежности, соответствующую данному ори- ентированному графу: A B C D E F A – 6 3 13 – – B – – – 9 7 – C – – – – – 16 D – – – – 1 7 E – – – – – 4 F – – – – – – По матрице смежности построим полное дерево перебора ре- шений — рисунок 3.8. 142 Глава 3. информационное моделирование рис. 3.8. Полное дерево перебора решений На рисунке 3.8 видно, что кратчайший путь из вершины A в вершину F равен 17 и имеет вид A–B–E–F. рис. 3.9. Схема дорог Пример 4. На рисунке 3.9 представ- лена схема дорог, связывающих города A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном на- правлении, указанном стрелкой. Сколь- ко разных путей существует из города А в город G? Существует несколько способов реше- ния этой задачи. Рассмотрим их. Вариант 1. По графу можно построить матрицу смежности, а на её основе построить дерево, корнем которого будет служить вершина А. Число листьев построенного дерева будет равно числу дорог из города А в город G. Постройте дерево и подсчитайте число дорог из города А в город G самостоятельно. Вариант 2. Пусть К Х — число путей из города А в город Х. Начнем считать число путей с конца маршрута. Так как в город G есть дороги из городов C, E, F, то К G = К C + К E + К F В свою очередь К С = 1 + К D = 1 + 1 = 2, К E = К B + К C = 1 + 2 = 3, К F = К C = 2. Таким образом, К G = 2 + 3 + 2 = 7. 143 модели и моделирование §10 Вариант 3. Можносчитать число путей с начала маршрута. При этом процесс подсчёта удобно изображать на самом графе — рисунок 3.10. рис. 3.10. Схема дорог с подсчётом числа путей Пример 5. На рисунке 3.11 представлена схема дорог, свя- зывающих населённые пункты A, B, C, D, E, F, G. В таблице содержатся сведения о длинах этих дорог (в километрах). Схему и таблицу создавали независимо друг от друга, поэтому в них используются разные обозначения. Необходимо выяснить длину пути в километрах из пункта D в пункт F. Г1 Г2 Г3 Г4 Г5 Г6 Г7 Г1 15 10 20 25 Г2 15 25 10 Г3 10 30 20 Г4 20 25 15 Г5 15 10 Г6 30 15 Г7 25 10 20 10 15 рис. 3.11. Схема дорог и таблица их длин Рассмотрим имеющийся граф и выясним степень каждой вер- шины — число рёбер соединяющих некоторую вершину с други- ми вершинами. Получим: A B C D E F G 3 2 3 5 2 4 3 |