VII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Рекурсия – эффективный инструмент моделирования объектов и явлений реального мира
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение:
С понятием рекурсии я встретился в сентябре этой осени, когда я готовился к олимпиаде по программированию. По началу задачи, связанные с рекурсией, вызвали у меня недоумение, так как это была совершенно новая область знаний, с которой мне не приходилось работать ранее. Но я решил разобраться в этом вопросе. Немного позже, когда я узнал, что будет проходить ежегодная конференция, я решил выступить на ней с работой “Рекурсия – эффективный инструмент моделирования объектов и явлений реального мира”. Пока я прорешивал задачи, изучал теорию, я понял, что рекурсия была мне с детства знакома, в том числе благодаря таким шуточным стихотворениям, как
|
У попа была собака Он ее любил Она съела кусок мяса Он ее убил, а на камне написал: Что у попа была собака… |
У царя был двор, На дворе был кол, На колу мочало, Начинай сначала… |
Потом я понял, что рекурсию можно увидеть практически каждый день.
Цель работы: изучить рекурсию, область ее применения, способы представления.
Методы и приемы:
поиск и сбор информации по рекурсии.
Изучение возможностей рекурсии и практическое их применение на примере создания данного проекта.
Полученные данные:
Программа для создания и решения графов.
Программа для наглядного изображения возможностей рекурсии.
Выводы:
Рекурсия применима во всех областях народного хозяйства, науки, техники и образования.
Знание рекурсии облегчает решение многих вопросов.
План исследования:
Рекурсия в реальном мире.
Рекурсия в естественных науках.
Решение повседневных задач с помощью рекурсии.
Постановка и решение задач исследования
I этап: Теоретический
Поиск, изучение и анализ информации по вопросам:
Что такое рекурсия?
Где встречается рекурсия в реальном мире?
Где встречается рекурсия в естественных науках?
Как решаются повседневные задачи с помощью рекурсии?
II этап: Практический
Общение с представителями старших классов по поводу рекурсии
Решение задач на рекурсию из экзаменационных материалов ЕГЭ
Постановка собственных целей и задач по созданию программ, с использованием рекурсии.
Создание программы для решения логистических задач методом графов.
Рекурсия в реальном мире
Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний, но наиболее широкое применение находит в математике и информатике. (по материалам интернет ресурса – Wikipedia.org)
Рекурсия вполне распространенное явление даже в повседневной жизни. Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал. Среди географических объектов, в которых можно увидеть черты рекурсивного объекта, самым известным является пресноводное озеро Тааль, расположенное на острове Лоусон в провинции Батангас, Филиппины. На озере находится вулканический остров Тааль, в его кратере имеется еще одно озеро. А на нем в свою очередь есть свой собственный небольшой остров, Вулкан-Пойнт. Поэтому человек не мог упустить из виду такое явление и стал активно использовать его. Но как человек использует рекурсию?
Так же рекурсия очень часто используется в графике. Если внимательно посмотреть на упаковки товара, символику, то можно увидеть примеры рекурсии.
Например на упаковке товара изображена женщина, несущая поднос, на котором стоит упаковка товара. (см рис. I)
Рис. I
Так же рекурсивная графика может использоваться для создания узоров, на предприятиях. На одном предмете могут быть изображения с разной глубиной рекурсии. Примером графической рекурсивной функции может служить кривая Коха:
Кривая Коха — фрактальная кривая, описанная в 1904 году шведским математиком Хельге фон Кохом. Три копии кривой Коха, построенные (остриями наружу) на сторонах правильного треугольника, образуют замкнутую кривую бесконечной длины, называемую снежинкой Коха. (см. рис II)
Рис. II.
uses graphABC;
var
i:integer;
procedure drawline(ax,ay,fx,fy,i: integer);
var
bx,by,cx,cy,dx,dy,ex,ey:integer;
begin
if (i=0) then
line(ax,ay,fx,fy)
else
begin
bx:=(2*ax+fx) div 3;
by:=(2*ay+fy) div 3;
cx:=bx+by-ay;
cy:=by+ax-bx;
ex:=2*bx-ax;
ey:=2*by-ay;
if ax = fx then
begin
dx:=cx;
dy:=ey;
end
else
begin
dx:=ex;
dy:=cy;
end;
drawline(ax,ay,bx,by,i-1);
drawline(bx,by,cx,cy,i-1);
drawline(cx,cy,dx,dy,i-1);
drawline(dx,dy,ex,ey,i-1);
drawline(ex,ey,fx,fy,i-1);
end;
end;
begin
i:=6;
drawline(100,100, 100, 200, i);
end.
Рекурсия в естественных науках
Одними из самых первых рекурсивных функций, описанных человеком, стали факториал и ряд Фибоначи. Факториал числа n — произведение всех натуральных чисел от 1 до n включительно. Например факториал числа 5=1*2*3*4*5. Так же стоит упомянуть и ряд Фибоначи, в котором каждое следующее число – сумма 2х предыдущих.
Пример функции, находящей факториал числа:
function factorial(n:integer):integer;
begin
if n>1 then
factorial:=(factorial(n-1))*n
else if n=1 then factorial:=1;
end;
Пример функции, находящей n число фибоначи:
function fibonachi(a:integer):integer;
begin
if a>2 then fibonachi:=fibonachi(a-2)+fibonachi(a-1) else if a<3 then fibonachi:=1;
end;
Другим примером бесконечной рекурсии является эффект самовозбуждения у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы. Автогенераторы применяются, например, в радиопередающих устройствах. Основными техническими характеристиками автогенератора являются диапазон рабочих частот, стабильность частоты, мощность на выходе. Из них наиболее важной является допустимая нестабильность частоты автоколебаний. Для целей радиопередачи относительная нестабильность частоты может лежать в интервале 10 − 6 . . .10 − 15 {\displaystyle 10^{-6}...10^{-15}} от до герц.
Решение повседневных задач с помощью рекурсии.
Большая часть информации была найдена в интернете. Но как поисковая система, получая короткий запрс, выдавала мне именно то, что я искал? Я решил найти ответ на данный вопрос и понял, что поисковые системы основаны на применении рекурсии.
Одним из основных источников информации в современном мире является интернет. Но из-за огромного количества сайтов, поиск информации был проблемой, пока не был создан рекурсивный поиск. Свой базовый алгоритм расчета PageRank создатели Google опубликовали давно. И как бы он с тех пор ни менялся, сколько бы его ни дополняли усовершенствованиями, основа остается прежней. Нельзя узнать, какую величину PageRank страница B передает по ссылке странице A, пока мы не сосчитали, какой PageRank получила страница B от всех прочих страниц, которые на нее сослались, а этого нельзя узнать, пока мы не посчитаем PageRank этих страниц. Именно поэтому для создания удобного поиска необходимо использовать рекурсию. Но как же работает рекурсивный поиск?(по материалам интернет ресурса - http://wiki.webimho.ru)
1й этап. Сканирование, заносящее в базу данных новые сайты. Сканирование может быть описано, как автоматизированный процесс систематического изучения общедоступных страниц в Интернете. «Googlebots» посещают список URL-адресов, полученных в процессе прошлого сканирования и дополненных данными карты сайта, которую предоставляют веб-мастера и анализируют их содержание. При обнаружении ссылок на другие страницы во время посещения сайта, боты также добавляют их в свой список и устанавливают систематические связи.
2й этап. Индексация — процесс сохранения полученной информации в базе данных в соответствии с различными факторами для последующего извлечения информации. Ключевые слова на странице, их расположение, мета-теги и ссылки представляют особый интерес для индексации Google. Для того чтобы эффективно хранить информацию о миллиардах страниц в базе данных поисковой системы, Google использует крупные центры обработки данных в Европе, Азии, Северной и Южной Америке. В этих центрах, как было подсчитано, на основе энергопотребления Google в 2010 году, работает около 900,000 серверов.
Основная цель процесса индексации: быстро реагировать на поисковой запрос пользователя. Его как раз мы и будем обсуждать на следующей стадии.
3й этап – Обработка . Когда пользователь вводит запрос, Google производит в базе данных поиск, подходящий под условия и алгоритмически определяет актуальность содержания, что выводит к определенному рейтингу среди найденных сайтов. Логично, что результаты, которые считаются более релевантными для пользователя поисковой системы, намеренно получают более высокий ранг, чем результаты, которые имеют меньше шансов обеспечить адекватный ответ. Компания использует более 200 факторов для определения релевантности и значимости конкретной страницы.
Другой важной задачей, которую облегчила рекурсия, стала логистика. Логистические задачи решаются с помощью графов. Графом называют графическое изображение, состоящее из вершин и соединяющих некоторые пары вершин ребер. Графы используются, в том числе, для решения логистических проблем. Например: по какому пути быстрее доставить груз из Москвы в Санкт-Петербург. Граф представляет из себя матрицу логического типа, каждый элемент которой – наличие\отсутствие узла. Алгоритм поиска должен будет построить дерево возможных путей из начальной вершины, концевыми узлами которого будут вершины, из которых нельзя попасть ни в какую вершину, не принадлежащую ранее построенной ветви (не помеченную как уже посещенную). Задача будет решена, когда один из концевых узлов совпадет с конечной вершиной, путь в которую требуется найти.
Так же одной из важнейших задач ученика 11го класса является успешная сдача ЕГЭ. Я беседовал с учениками 11го класса по поводу рекурсии, и выяснил, что данный вопрос кажется для них очень сложным. Всего существует 3 типа задач на рекурсию:
1) Алгоритмы, опирающиеся на несколько предыдущих значений
2) Вызов рекурсивных процедур
3) Алгоритмы, опирающиеся на одно предыдущее значение
Особое беспокойство вызвал 2й раздел, включающий в себя задачи по типу данной:
procedureF(n:integer);
begin
if n >0then
G(n -1);
end;
procedureG(n:integer);
begin
writeln('*');
if n >1then
F(n -2);
end;
Но на самом деле, если разобраться в данном вопросе, эти задачи окажутся довольно простыми.
Выводы:
1) Рекурсия является актуальной и на данный момент, так как помогает решать очень важные вопросы (ч.3), в областях ИКТ, математики и физики, логистики и производства.
2) В ходе данной работы было написано мною несколько программ, которые могут выполнять поставленные перед ними задачи в областях логистики, математики и физики (я сам ставил перед собой условие, составлял программу и решал поставленную передо мной задачу).
3) В ходе данной работы была выяснена важность рекурсии.
4) Я был удивлён, как просто можно решать сложные задачи, используя рекурсию.
5) Выяснил, что рекурсия не зря входит в материал 11го класса, так как умение размышлять, используя рекурсию, очень важно и актуально на данный момент, так как это позволяет решать многие вопросы более простым путём.
Список литературы:
1)https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F
2) https://habr.com/ru/post/275813/
3)https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F
4) Анисимов А. В.Рекурсивные преобразователи.
5) Баррон Д. Рекурсивные методы в программировании. М.: Мир, 1974. - 80 с.
6) Журнал (Информатика) 1996 №44
5) Журнал (Информатика) 1997 №35
6) Методические материалы ВМК