Классы
Предметы
Важное замечание:

С помощью наших видеоуроков вы сможете:
1. Подготовиться к завтрашнему уроку в школе.
2. Научиться грамотно пользоваться компьютером на домашнем уровне.
3. Понять основные тенденции и логическую основу этой отрасли.

Но если вы хотите стать специалистом, обратитесь к таким сайтам, как Codecademy.com, Teamtreehouse.com, www.piktomir.ru.

Поскольку информатика (и всё, что с ней связано, — электроника, робототехника и т.д.) — быстроразвивающаяся отрасль, школьная программа по ряду тем может отставать от действительности.

Если вы специалист и хотите добавить актуальную информацию, снять дополнение к уроку, пишите нам на info@univertv.ru.

Методы решения задач

На этом уроке мы познакомимся с различными методами решения задач с помощью компьютера.

Конспект

Чтобы решить задачу, необходима точная постановка задачи и правильный выбор метода ее решения. Постановка задачи сводится, как правило, к мате­матической форме описания условий задачи по схеме:

Задача (словесное описание).

Дано (перечисление исходных данных).

Требуется (перечисление требуемых результатов).

Связь (зависимость между исходными данными и требуемым результатом).

При (условия допустимости исходных данных).

Основные методы решения задач:

·   рекуррентный;

·   рекурсивный;

·   приближенные методы и т. д.

Выбор метода решения должен обеспечить получение требуемых результатов для любых допустимых исходных данных.

1. Рекуррентный метод

Формулы, в которых очередной член последовательности выражается через один или несколько предыдущих членов, называются рекуррентными соот­ношениями.

Метод, использующий рекуррентные соотношения, называется рекуррентным.

В программировании часто используют метод рекуррентного суммирования для определения суммы конечной последовательности чисел.

Применим описанную схему:

Задача (найти сумму конечной последовательности заданных чисел).

Дано ( – последовательность п чисел).

Требуется (найти  – сумму этих чисел).

Связь ().

При (любых значениях чисел последовательности).

Применив рекуррентный метод, получим соотношения:

Сумма здесь представлена в виде переменной величины, которая увеличивается, как только к ней прибавляется очередной элемент последовательности, на величину этого элемента. Итогом процесса будет получение значения суммы п элементов последовательности.

Одними из наиболее известных рекуррентных соотношений являются так называемые прогрессии – последовательности чисел, каждое из которых отличается от предыдущего по определённому правилу, одинаковому для всех членов прогрессии. Нам известны арифметические и геометрические прогрессии.

Другой не менее популярной последовательностью, которая задаётся рекуррентным способом, является так называемый ряд Фибоначчи.

Итальянский математик XIII века Фибоначчи построил математический ряд: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ..., описывающий биологический процесс (процесс размножения кроликов).

Легко заметить закономерность: член ряда Фибоначчи равен сумме двух предыдущих членов.

Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках, намного раньше, чем она стала известна в Европе.

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что:

1. В «нулевом» месяце имеется пара кроликов (1 новая пара).

2. В первом месяце первая пара производит на свет другую пару (1 новая пара).

3. Во втором месяце обе пары кроликов порождают другие пары и первая пара погибает (2 новые пары).

4. В третьем месяце вторая пара и две новые пары порождают в общем три новые пары, а старая вторая пара погибает (3 новые пары).

Закономерным является тот факт, что каждая пара кроликов порождает ещё две пары на протяжении жизни, а затем погибает.

Пусть популяция за месяц будет равна . В это время только те кролики, которые жили в месяце n-2, являются способными к размножению и производят потомков, тогда  пар прибавится к текущей популяции . Таким образом, общее количество пар будет равно: .

Приведём несколько наиболее популярных возможных появлений чисел Фибоначчи.

1. Филлотаксис (листорасположение) у растений описывается последовательностью Фибоначчи. Семена подсолнуха, сосновые шишки, лепестки цветков, ячейки ананаса также располагаются согласно последовательности Фибоначчи.

2. Длины фаланг пальцев человека относятся примерно как числа Фибоначчи.

3. Американский писатель-фантаст Дэн Браун в книге «Код да Винчи» описал анаграмму на основе последовательности Фибоначчи.

4. Светящиеся числа Фибоначчи от 1 до 55 прикреплены на дымовой трубе Turku Energia в Турку и главном вокзале Цюриха.

5. Числам Фибоначчи посвящён один их шуточных лимериков Джеймса Линдона:

Плотная пища жён Фибоначчи

Только на пользу им шла, не иначе.

Весили жёны, согласно молве,

Каждая – как предыдущие две.

Если в ряду Фибоначчи взять отношение последующего члена к предыдущему и наоборот, получим числа 1,618 и 0,618. Эти числа были открыты «пифагорейцами» и получили название «золотых».

Золотое сечение (золотая пропорция, деление в крайнем и среднем отношении) – деление величины (например, длины отрезка) на две части таким образом, при котором отношение большей части к меньшей равно отношению всей величины к её большей части.

В дошедшей до нас античной литературе деление отрезка в крайнем и среднем отношении  впервые встречается в «Началах» Евклида (ок. 300 лет до н. э.), где оно применяется для построения правильного пятиугольника.

Термин «золотое сечение» был введён в обиход Мартином Омом в 1835 году. Лука Пачоли, современник и друг Леонардо да Винчи, называл это отношение «божественной пропорцией».

Приблизительная величина золотого сечения равна , а точнее 1,6180339887.

Число  называется также золотым числом.

 – иррациональное алгебраическое число, положительное решение квадратного уравнения .

Это число можно выразить через тригонометрические функции:

Или через такие соотношения:

Отношение двух соседних чисел последовательности Фибоначчи (предыдущего к последующему) с увеличением номера этих членов стремится к золотому сечению.

В правильной пятиконечной звезде каждый отрезок делится пересекающим его отрезком в золотом сечении. Отношение диагонали правильного пятиугольника к стороне равно золотому сечению (рис. 1).

 

Рис. 1. Золотое сечение в различных фигурах

Пропорции пирамиды Хеопса, храмов, барельефов, предметов быта и украшений из гробницы Тутанхамона свидетельствуют, что египетские мастера пользовались соотношениями золотого сечения при их создании.

При обсуждении оптимальных соотношений сторон прямоугольников (размеры листов бумаги A0 и кратные, размеры фотопластинок (6:9, 9:12) или кадров фотоплёнки (часто 2:3), размеры кино- и телевизионных экранов – например, 4:3 или 16:9) были испытаны самые разные варианты. Оказалось, что большинство людей не воспринимает золотое сечение как оптимальное и считает его пропорции «слишком вытянутыми».

Начиная с Леонардо да Винчи, многие художники сознательно использовали пропорции «золотого сечения».

Известно, что Сергей Эйзенштейн искусственно построил фильм «Броненосец Потёмкин» по правилам золотого сечения, разбив ленту на пять частей (в первых трёх действие развивается на корабле, в двух последних – в Одессе), где переход в город происходит точно в точке золотого сечения.

Рекуррентные формулы арифметической, геометрической прогрессий и ряда Фибоначчи выглядят следующим образом:

.

2. Рекурсивный метод

При решении задач иногда используют рекурсивный метод. Рекурсивным называется метод вычисления функций через самих себя, когда значение функции для некоторых аргументов можно выразить через значение этой же функции от других аргументов.

Пример 1:

.

Пример 2:

Рекурсивный метод часто используют при доказательстве различных фактов с помощью метода математической индукции.

Пояснить суть этого метода можно на следующем примере: вы стоите на первой ступеньке бесконечной лестницы. И вы умеете подниматься на 1 ступеньку с любой ступеньки. Это значит, что вы сможете добраться до любой ступеньки этой лестницы (с 1 на 2, со 2 на 3 и т. д.). Ещё один наглядный пример: предположим, вы стоите в вагоне метро. Вы спросили у стоящего перед вами соседа, выходит ли он на следующей станции, и получили утвердительный ответ. И вы знаете, что каждый из впереди стоящих совершает аналогичную процедуру с аналогичным результатом. Это означает, что, сколько бы человек не стояло перед вами, вы сможете выйти на следующей остановке.

Математическая индукция – метод математического доказательства, используется чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 – база (базис) индукции, а затем доказывается, что если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 – шаг индукции, или индукционный переход.

Доказательство по индукции наглядно может быть представлено в виде так называемого принципа домино. Пусть какое угодно число косточек домино выставлено в ряд таким образом, что каждая косточка, падая, обязательно опрокидывает следующую за ней косточку (в этом заключается индукционный переход). Тогда если мы толкнём первую косточку (это база индукции), то все косточки в ряду упадут.

Рассмотрим пример рекурсивного метода доказательства верности индуктивного перехода.

Предположим, необходимо доказать, что для любого натурального числа n верно следующее утверждение:

.

База: при :  – верно.

Переход: пусть эта формула верна при некотором . Докажем, что она верна и при .

То есть, нам известно, что: , а доказать необходимо, что: .

Воспользуемся рекурсивным методом: . Но мы знаем, что, по предположению индукции: . Получаем: . Доказано.

3. Приближённые методы вычисления

Один из приближенных методов решения задач – метод половинного деления, который применяется, например, для решения алгебраического уравнения. Сущность метода заключается в том, что интервал неопределенности делят пополам и проверяют, в какой половине находится корень. Эта половина становится новым интервалом неопределенности, а вся процедура повто­ряется до тех пор, пока не будет достигнута заданная точность расчетов.

Еще одним приближенным методом является метод Монте-Карло. Он используется для вычисления площади фигуры, ограниченной произвольным контуром.

Пусть есть фигура на плоскости, и пусть она расположена внутри квадрата, сторона которого известна и равна А. Площадь фигуры можно вычислить, засыпав квадрат ровным слоем песка. Число песчинок внутри квадрата будет пропорционально площади данной фигуры. Из этой пропорции можно определить искомую величину.

Для решения задач с применением этих и других методов используются среды программирования, в которых решение записывается на языке программирования, служащем основой данной среды.

Например, задача нахождения площади произвольной плоской фигуры легко моделируется и программируется в любой среде программирования, в объ­ектно-ориентированной среде Borland Delphi в том числе.

Роль песчинок могут играть точки, выводимые произвольно на заданный уча­сток. Их координаты можно задавать с помощью генератора случайных чи­сел.

Итак, мы поговорили о некоторых методах решения задач с помощью компьютера. На следующем уроке мы начнём знакомство с работой в объектно-ориентированной среде программирования.

 

Список литературы

  1. Угринович Н.Д. Информатика-9. – М.: БИНОМ. Лаборатория знаний, 2012.
  2. Гейн А.Г., Юнерман Н.А. Информатика-9. – М.: Просвещение, 2012.
  3. Соловьёва Л.Ф. Информатика и ИКТ. Учебник для 9 класса. – СПб.: БХВ-Петербург, 2007.

 

Дополнительные рекомендованные ссылки на ресурсы сети Интернет

  1. Интернет-портал «Создание.рф» (Источник).
  2. Интернет-портал «Edu.dvgups.ru» (Источник).
  3. Интернет-портал «Coolreferat.com» (Источник).

 

Домашнее задание

  1. Приведите задачу, для решения которой нужно воспользоваться:
    • Арифметической прогрессией;
    • Геометрической прогрессией;
    • Рядом Фибоначчи.
  2. Приведите задачу, которую вы решите методом половинного деления.
  3. Приведите и решите задачу методом математической индукции.