Составление алгоритмов и блок — схем

Составление алгоритмов и блок-схем.

Цели урока:

Образовательные:

— формирование и закрепление навыков по составлению и выполнению алгоритмов;

— проверка знаний;
— повышение интереса к изучению предмета;
— воспитание навыка быстрого мышления.

Развивающие:

— способствовать развитию умения планировать последовательность действий для достижения поставленной цели;

— способствовать развитию алгоритмического и логического мышления;

— развитие творческой активности учащихся;
— развитие познавательных интересов.

Воспитательная:

— способствовать воспитанию в детях ответственности, взаимопомощи и взаимоуважения

Тип урока: закрепление полученных знаний

Оборудование: Раздаточный материал, компьютер, проектор, презентация к уроку

Ход урока

1. Оргмомент. Взаимодействие учителя и учеников

2. Тема, цель. На прошлом уроке вы познакомились с важной темой информатики.

— Какой? ( Алгоритмы)

— Что такое алгоритм? (Порядок действий или план)

3. Устный опрос.

-Кто выполняет алгоритмы? (Исполнители)

Таблица 1. Определить соответствие в таблице.

Команда

Стиральная машина

Печатать

Собака

Полоскать

Человек

Сидеть

Компьютер

Сварить картофель

— А каждый ли исполнитель может исполнить любую команду? Почему?

— Что такое система команд исполнителя?

— Какие команды выполняют эти исполнители?

4. Повторение: Типы алгоритмов. (3 минуты)

• Что такое линейный алгоритм?

• Что такое Разветвляющийся алгоритм?

• Что такое циклический алгоритм?

4. Практическая часть.

Составить алгоритмы и блок-схемы к алгоритмам.

Задание 1.

Написать алгоритм сбора съедобных грибов, и составить к этому алгоритму блок-схему.

– Какая команда будет выполняться не всегда? Когда ее нужно пропустить? (команда «сорви гриб» не выполняется, если гриб несъедобный.) обвести прямоугольник с этой командой зеленым карандашом.

– Есть ли цикл в этом алгоритме? Какие команды будут выполняться больше одного раза? («найди гриб», «гриб съедобный», «сорви гриб», «все грибы обошел?».)

– Сколько раз будут выполняться эти 5 команд? («хитрость этого вопроса в том, что команды в цикле будут выполняться не одинаковое число раз: сорвать гриб нужно столько раз, сколько будет найдено съедобных грибов, а остальные 4 команды нужно выполнять столько раз, сколько будет найдено всех грибов.)

– В каком ромбе записано условие повтора?

(во втором ромбе, который нужно обвести красным карандашом.)

Задание 2.

Составить алгоритм разбора фасоли из мешка. Если фасоль белая, то её положить в круглую корзину, а если не белая, то в овальную корзину.

(Учесть, что задание допускает разное расположение команд на схеме).

Ответить на вопросы:

– Какие команды будут выполняться не всегда?

– Какие команды будут выполняться больше одного раза?

– Сколько раз будет выполнена каждая из этих команд?

– Какой вопрос на схеме является условием повтора?

Задание 3.

Составь блок-схему алгоритма для решения задачи.

Красная Шапочка гуляла по лесу и собирала цветочки. Она сорвала 5 колокольчиков, 6 незабудок и 4 василька. Вдруг сзади кто-то захихикал. Красная Шапочка оглянулась и увидела Серого Волка.

— Милая Красная Шапочка, поделись со мной цветами: если у тебя больше 7 цветочков, дай мне 5, а иначе подари, хотя бы 3.

Сколько цветов осталось в букете у Красной Шапочки?

4. Физкультминутка (3 мин)

5. Самостоятельная работа на компьютере по составлению алгоритмов и блок-схем. (15 мин)

8. Домашнее задание: составить текстовый и графические алгоритмы лепки снеговика.

9. Подведение итогов урока

Отлично поработали на уроке.

Получили «5»

Получили «4»

Чему вы сегодня научились?

Что вам сегодня понравилось?

– Закрепили знания о ветвлениях и циклах в алгоритмах.

– Научились отличать условие ветвления от условия повтора.

Сегодня вы научились составлять алгоритмы с ветвлениями и циклами.

Алгоритмы и исполнители. Информатика. 9 класс. Разработка урока

Тип урока: изучение нового материала.

Цели:

• образовательные: познакомить учащихся с понятиями алгоритм, алгоритмизация, исполнители алгоритмов и система команд исполнителя; перечислить и проанализировать свойства алгоритма; познакомить учащихся с формами записи алгоритмов.
• воспитательные: воспитывать аккуратность, внимательность, точность и дисциплинированность.
• развивающие: развитие внимания, восприятия, самостоятельного анализа, познавательного интереса у учащихся, умения обобщать и сравнивать

Задачи: организовать и направить познавательную деятельность обучающихся на понимание сути алгоритмов, их свойств, способов описания; показать связь данной темы с практикой; применять знания при создании алгоритмов и оценке существующих алгоритмов; формирование умения четко организовать самостоятельную и групповую работу.

Использованные источники: Ю.А.Быкадоров, Информатика и ИКТ. 9 класс, учебник для общеобразовательных учреждений, М.: Дрофа. 2013 г.; О. Н. Масленикова, Информатика и ИКТ. 9 класс. Методическое пособие к учебнику Ю. А. Быкадорова «Информатика и ИКТ. 9 класс», М.: Дрофа. 2013 г.  

Здравствуйте ребята.

Для того, чтобы узнать тему сегодняшнего урока нужно разгадать ребус.

И так, кто уже готов назвать тему нашего урока? (Ответы учащихся…)

Молодцы! Правильно отгадали!

Тема нашего урока «Алгоритмы и исполнители».

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

С понятием «алгоритм» вы уже знакомились на других предметах и в своей повседневной деятельности нам постоянно приходится сталкиваться с разнообразными правилами, предписывающими последовательность действий, цель которых состоит в достижении некоторого необходимого результата. Подобные правила очень многочисленны. Например, мы обязаны следовать вполне определенной системе правил, чтобы найти корни квадратного уравнения, приготовить кофе и т.

• Под алгоритмом понимают понятное и точное предписание исполнителю выполнить конечную последовательность действий для достижения поставленной цели.

А теперь давайте немного поговорим об истории происхождения слова алгоритм.Мой помощник, ваш одноклассник, подготовил историческую справку о происхождении слова «алгоритм», для этого он использовал – учебник, справочники, интернет-ресурсы.

Ученик. Историческая справка. Происхождение слова «алгоритм»

Правила выполнения арифметических действий над целыми числами и простыми дробями в десятичной системе счисления впервые были сформулированы выдающимся средневековым ученым по имени Мухаммед ибн Муса ал-Хорезми (в переводе с арабского это означает «Мухаммед, сын Мусы из Хорезма»), сокращенно Ал-Хорезми.

Ал-Хорезми жил и творил в IX веке. Арабский оригинал его арифметического труда утерян, но имеется латинский перевод XII века, по которому Западная Европа ознакомилась с десятичной позиционной системой счисления и правилами выполнения в ней арифметических действий.

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

В латинском переводе книги Ал-Хорезми правила начинались словами «Алгоризми сказал». С течением времени люди забыли, что «Алгоризми» — это автор правил, и стали сами эти правила называть алгоритмами. Постепенно «Алгоризми сказал» преобразовалось в «алгоритм гласит».

Таким образом, слово «алгоритм» происходит от имени ученого Ал-Хорезми. Как научный термин первоначально оно обозначало лишь правила выполнения действий в десятичной системе счисления. С течением времени это слово приобрело более широкий смысл и стало обозначать любые точные правила действий. В настоящее время слово «алгоритм» является одним из важнейших понятий науки информатики.

Процесс создания алгоритмов называется – алгоритмизацией.

Всякий алгоритм составляется в расчете на определенного исполнителя. Им может быть человек, робот, компьютер и др.

• Исполнитель алгоритма – это человек или автоматическое устройство, которое способно воспринимать и исполнять алгоритм.

Запишите исполнителей для приведённых ниже видов работ:

• Уборка мусора во дворе – дворник
• Перевозка пассажиров в поезде – машинист
• Приём экзаменов в школе – учитель
• Приготовление еды в ресторане – повар
• Выполнение домашнего задания – ученик

Чтобы составить алгоритм для исполнителя, нужно знать, какие команды исполнитель может понять и исполнить, а какие нет.

• Система команд исполнителя (СКИ) – это перечень элементарных предписаний (команд), которые исполнитель может исполнять.

Пример. Алгоритм определения периметра прямоугольника:

Дано: А, В — длины сторон прямоугольника.

Найти: Р – периметр прямоугольника.

Математическая модель: Р = (А + В) 2

1. Задать числовые значения А, В.
2. Сложить А и В. Результат обозначить X.
3. Умножить X на 2. Результат обозначить Р.
4. Записать в качестве ответа значение Р.
5. Конец.

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

Приведите еще примеры алгоритмов. Ответы учащихся …

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

Алгоритм обладает следующими свойствами:

• Целенаправленность – любой алгоритм направлен на достижение определенной цели. Чаще всего целью алгоритма является получение результата при решении какой-нибудь задачи.
• Дискретность – алгоритм состоит из элементарных предписаний (команд).
• Понятность – элементарные предписания (команды) алгоритма должны быть точно сформулированы и однозначно понятны исполнителю, а исполнитель должен быть в состоянии их выполнить.
• Однозначность – после исполнения очередного элементарного предписания (команды) исполнителю точно определено, что делать дальше.
• Массовость – алгоритм можно использовать для решения той же задачи при других допустимых исходных данных.

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

Рассмотрим их:

1. Словесная форма – это форма описания алгоритма на естественном языке. Если алгоритм предназначен для человека, то в качестве предписаний можно использовать привычные для человека предложения и фразы.

Правила записи алгоритмов в словестной форме просты: предписания записываются одно за другим и нумеруются; в записи алгоритма могут использоваться служебные слова Начало и Конец.

Пример: Алгоритм нахождения большего из двух данных чисел.

1. Начало.
2. Из числа А вычесть число В.
3. Если получилось отрицательное значение, то сообщить, что число В больше.
4. Если получилось положительное значение, то сообщить, что число А больше.
5. Если получился ноль, сообщить, что числа равны.
6. Конец.

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

2. Для более наглядного представления алгоритма используется графическая форма. Графическая форма – изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.

3. При записи алгоритма в словесной и в графической форме допускается определенный произвол при изображении команд. Вместе с тем такая запись точна на столько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы – компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. Такой язык принято называть языком программирования, а форму представления алгоритма — программной. То есть программная форма записи алгоритма – это запись на языке программирования.

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

Примерные вопросы:

1. Приведите примеры известных Вам алгоритмов.
2. Запишите алгоритм заварки чая.
3. Перечислите основные свойства алгоритмов и проиллюстрируйте их примерами.
4. Имеются два кувшина ёмкостью 3 л и 8 л. Напишите алгоритм для того, чтобы набрать из реки 7 л воды (можно пользоваться только этими кувшинами).
5. Какие Вы знаете формы описания алгоритмов?
6. Нужно поджарить три куска хлеба на сковороде, вмещающей только два таких куска. На поджаривание каждой стороны уходит 2 минуты. Можно ли поджарить хлеб меньше чем за 8 минут? Если да, то составить алгоритм.
7. Мачеха велела Золушке принести ровно 3 л. воды, а в доме всего два ведра: одно пятилитровое (ведро М), а другое девятилитровое (ведро Б) . Как же быть? Помогите Золушке. Составьте алгоритм решения задачи.

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

Домашнее задание: Домашним заданием для вас будет изучение §1 на стр. 3–6 и ответы на вопросы на стр. 7. Составить алгоритм старинной русской задачи: некий человек должен перевезти в лодке через реку волка, козу и капусту. За один перевоз он может перевезти только кого-то одного. Составьте алгоритм перевоза так, чтобы никто никого не съел.

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

Как сдать ЕГЭ по информатике на 100 баллов — Учёба.

Елизавета Беримская,

преподаватель Московской школы программистов,

ведущий эксперт ЕГЭ по информатике,

заместитель председателя предметной комиссии ЕГЭ по информатике МО

В 2021 году ЕГЭ по информатике впервые будет проводиться в компьютерной форме. По вашему мнению, экзамен в результате этого стал сложнее или проще?

Могу сказать, что перехода на компьютерную форму все очень ждали и дети в том числе. Конечно же для школьников, которые выбрали ЕГЭ по информатике и собираются поступать в вузы на специальности «Программирование», «Информатика и вычислительная техника», «Информационные системы», удобнее сдавать экзамен за компьютером, потому что это для них привычный инструмент. Многие ребята уже пишут собственные программы и им очень тяжело готовиться к письменному экзамену, где код программы нужно было записывать и проверять на бумаге.

Учащиеся, которые хорошо умеют программировать, получают преимущество на «компьютерном» ЕГЭ, по сравнению с «бумажным», потому что им не нужно тратить время на перепроверку программ, написанных на листочке. Они могут запустить их на компьютере и проверить на работоспособность, а освободившееся время потратить на перепроверку тестовой части.

Но здесь есть и опасность. Ребятам, которые хорошо владеют компьютером на уровне пользователя, будет казаться, что все это очень просто. В прошлые годы на ЕГЭ по информатике около 10% детей не могли преодолеть минимальный порог, то есть получали «двойку». Особые затруднения вызывали теоретические вопросы, хотя многие из этих школьников отлично знают компьютер, заядлые геймеры и даже ведут школьные сайты. Материал для ЕГЭ крайне обширный, в работе затрагивается большой круг тем. Этот экзамен нельзя сдать даже на минимальный результат, если ты просто умеешь пользоваться компьютером. Нужно готовиться долго и основательно, знать специфику и формат каждого вопроса.

Как сейчас обстоит дело с информатикой в общеобразовательных школах? Насколько хорошо школьники знают этот предмет?

В школьных учебниках по информатике есть темы, которые рассматриваются на ЕГЭ, но конечно не все. Если говорить об уроках информатики в районной школе, то там дают минимальный уровень, которого достаточно, чтобы просто сдать экзамен и преодолеть порог в 42 балла из 100. В спецшколах с углубленным изучением информатики, где на занятия по предмету отведено значительное количество часов, уже можно рассчитывать на 60-70 баллов — это уровень увлеченных предметом детей.

Но, когда речь идет о поступлении на IT-направления в топовые вузы, результат требуется совсем другой. Так, например, в 2020 году для зачисления на факультет компьютерных наук НИУ ВШЭ необходимо было продемонстрировать 303 балла (3 ЕГЭ + индивидуальные достижения), в Физтех-школу прикладной математики и информатики МФТИ — 301 балл, на программу «Программная инженерия» в МГТУ им. Баумана — 289 баллов.

Чтобы получить высокобалльный результат на ЕГЭ по информатике (от 85 баллов и выше), нужна дополнительная работа с преподавателем на курсах или индивидуально. Логично, что абитуриент IT-специальностей должен знать больше, чем школьный уровень информатики, ведь это его будущая профессия. Когда нужно начинать готовиться, чтобы получить хороший результат? По информатике за год можно подготовиться точно, но только в том случае, если к сентябрю — моменту начала подготовки — у школьника имеется хорошая база и есть навыки программирования. Если базы нет, готовиться следует начинать заранее. В 11-м классе необходимо сфокусироваться на отработке типов экзаменационных заданий, а всю теорию нужно выучить до этого. Минимум четыре академических часа в неделю на дополнительные занятия плюс школьные уроки — эффективная нагрузка, гарантирующая результат.

По вашему опыту преподавания, какие разделы информатики самые сложные для школьников? И какие темы самые простые?

Традиционно самые сложные задания связаны с алгеброй логики, в школе ей уделяется не так много внимания. К этой теме относятся высказывания, логические операции, истинность логического выражения. Суперсложная задача прошлого года (№ 23) была на логические уравнения. В Московской области ее не сделал ни один выпускник, а в Москве всего несколько человек справились с ней, в целом же процент выполнения этого задания был ничтожным. Именно поэтому впервые на ЕГЭ по информатике шкала перевода первичных баллов в тестовые была составлена таким образом, что можно было не решить одну задачу и все-равно получить 100 баллов. Только благодаря этому в 2020 году у нас были 100-балльники по информатике. В этом году эту задачу из экзамена убрали. Но по теме алгебры логики в работе все же остались две задачи, правда они более простые.

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

Самым сложным на ЕГЭ по информатике по-прежнему остается последнее задание № 27. Это творческая задача на анализ алгоритмов. Школьник должен самостоятельно придумать свой алгоритм. В прошлые годы проверять это задание экспертам было непросто. Способы ее решения были настолько разные, что трудно было сразу понять: правильно ли составлен алгоритм, это неверный ход решения или просто изюминка в коде? Приходилось проверять на тестах. В этом году справиться с этой задачей выпускникам будет гораздо легче. Они пишут программу на компьютере, запускают ее и сразу видят — получился результат или нет. Если нет, школьник может еще раз просмотреть код, найти и тут же исправить ошибки. И так до получения результата.

Если посмотреть на статистику сдачи экзамена, можно увидеть, что часто у детей возникают ошибки на пустом месте, например, в таком задании, как технология обработки графической информации. Как кодируется графическая информация, как рассчитывается объем графического файла, какое количество цветов можно использовать при кодировании — это теоретические вопросы, на которые школьник мало обращает внимание при подготовке, это не так интересно. Когда выпускник решил на ЕГЭ все сложные задачи правильно, а на такие элементарные вопросы не ответил, получается очень обидный результат — 96, 97, 98, 99 баллов — почти 100, но не 100.

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

Какие языки программирования надо знать, чтобы сдать ЕГЭ по информатике?

Я являюсь экспертом ЕГЭ по информатике уже 11 лет и вижу, как меняется тенденция в использовании языков. Составители ЕГЭ не ограничивают школьника каким-то одним языком программирования, а разрешают ему использовать в задачах тот язык, которым он владеет лучше всего. В начале самым популярным был бейсик, потом его почти не осталось, и лидерскую позицию занял Паскаль. Сейчас в Москве процент школьников, которые выбирают на ЕГЭ Паскаль — очень маленький (здесь в школе проходят Python), в МО и других регионах Паскаль еще применяется, потому что на нем программируют в школе. В целом же тенденция такова, что все больше ребят пишут программы на самых современных языках — Python и С++. Хотя Паскаль очень хороший как учебный язык. Но в связи с глобальным развитием сферы IT-разработки, дети уже в школе хотят изучать то, что им в будущем пригодится на практике, чем они будут заниматься и в университете, и на работе в будущем. Таким образом большинство школьников выбирают на ЕГЭ Python и C++, последний еще и универсальный язык, на котором решаются все олимпиадные задачи.

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

Задание № 9

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

Это задание на электронные таблицы, и оно очень перекликается со всеми задачами, которые были у детей в школе на информатике с 7-8 класса. Школьнику нужно здесь продемонстрировать совершенно стандартные навыки работы с таблицей. Я уверена, что это задание будет одним из самых простых для решения, с высоким процентом выполнения.

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

Задание № 10

С помощью текстового редактора необходимо определить, сколько раз, не считая сносок, встречается слово «долг» или «Долг» в тексте романа в стихах А.С. Пушкина «Евгений Онегин». Другие формы слова «долг», такие как «долги», «долгами» и т.д., учитывать не следует. В ответе нужно указать только число.

Это простое задание, в редакторе Word надо с помощью функции «Найти» подсчитать, сколько раз встречается слово в тексте. Дети знакомы с текстовым редактором со средней школы. Они учатся не только печатать и форматировать текст, но и изучают различные функции, что поможет им при выполнении этого задания.

При работе с текстовыми редакторами обратите внимание на функции подсчета статистики в тексте.

Задание № 16

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 1 при n = 1;

F(n) = n + F(n − 1), если n — чётно,

F(n) = 2 × F(n − 2), если n > 1 и при этом n — нечетно.

Чему равно значение функции F(26)?

Это задача на рекурсивные алгоритмы. В общеобразовательной школе такие алгоритмы не изучают. В курсе информатики есть о них упоминание, но нет отработки навыков. Все прошлые годы на ЕГЭ по информатике это задание (№ 11) организаторами считалось несложным, базовым. Тем не менее с ним справлялись очень мало детей. В этом году в задании необходимо самостоятельно написать/запрограммировать алгоритм в среде Паскаль, Python или С++ .

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

Задание № 17

Рассматривается множество целых чисел, принадлежащих числовому отрезку, которые делятся, например, на 3 и не делятся на 7, 17, 19, 27. Нужно найти количество таких чисел и максимальное из них.

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

В вопросе задан числовой промежуток, нам нужно систематично проверить/проанализировать каждое число — на что оно делится или не делится. Здесь необходимо знать признаки делимости, что такое остаток, деление нацело, подсчет количества, подсчет суммы, подсчет минимума и максимума в диапазоне. Вот эти первичные стандартные алгоритмы для работы с целыми числами в этой задаче и проверяются.

Задание № 24

Текстовый файл состоит не более чем из 10 в 6-ой степени символов X, Y и Z. Необходимо определить максимальное количество идущих подряд символов, среди которых каждые два соседних различны. Для выполнения этого задания следует написать программу.

Задача на работу с символьными данными — текстами, это отдельный раздел в программировании. Есть специальные алгоритмы для работы с таким типом данных — это алгоритмы правильного считывания, анализа (какой символ считан), подсчета количества и различных признаков.

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

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

Задание № 25

Требуется написать программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа нужно записать эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.

Это первая в работе задача на два балла, задания № 1-24 оцениваются в один балл. Задача сложная, здесь проверяется умение самостоятельно писать программу. Она связана с математикой, с понятием делителей числа. Здесь уже используются как алгоритм вложенные циклы — когда внутри одного цикла есть еще циклы, структура более сложная.

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

Задание № 26

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

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

Задание проверяет знание алгоритмов сортировки. Их существует несколько, в том числе «пузырек», алгоритм вставками, бинарный поиск. Чтобы решить задачу, школьник должен уметь использовать как минимум один из них.

Задание № 27

Предлагается набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.

Последняя задача экзамена перекочевала из ЕГЭ прошлых лет, только теперь ее нужно выполнить с помощью программного обеспечения. Здесь требуется написать объемную программу. Если в предыдущих заданиях были программы, которые укладывались в 10 строк, то эта задача в своем эталонном варианте занимает от 20 до 40 строчек кода.

Задача непредсказуемая и всегда разная, здесь может понадобиться знание комбинаторики, анализа данных. Процент выполнения этой задачи крайне низок. В прошлом году она максимально оценивалась в 4 балла (в этом году — в 2 балла) и такой результат за нее получили всего 5% школьников, а 53% участников экзамена получили за нее 0 баллов.

В ответе необходимо указать два числа: значение искомой суммы для файла А и для файла B. В формулировке задания есть предупреждение: «Для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго». Если школьник напишет эффективный алгоритм, он получит ответ и для файла A, и файла B (2 балла). Если он напишет неэффективный (переборный) алгоритм, то он получит значение только для файла A (1 балл), поскольку программа будет долго выполняться и времени экзамена не хватит на получение результата.

Что нужно делать школьнику, чтобы получить 100 баллов? Реально ли это?

Такие результаты всегда есть, но ничего не бывает просто так, эти ребята работали очень много. Случайно 100 баллов на ЕГЭ не получишь никогда. Это огромный труд. В информатике нет ни одной пустой задачи, например, воспроизвести определение или объяснить понятие. Здесь надо решать задачи и писать программы. Если вы решили связать свое будущее с программированием, начинайте готовиться заранее, пусть ЕГЭ по информатике станет для вас базой в вашей будущей профессии. Учите теорию, разбирайтесь с сетями, масками сетей, работайте с текстовыми редакторами и таблицами, тренируйтесь в написании алгоритмов. Если напряженно работать и построить грамотную траекторию подготовки по всем темам, то возможно все, и 100 баллов — это только начало.

Михаил Кормановский,

выпускник Московской школы программистов,

студент Московского государственного технического университета им. Н.Э.Баумана,

сдал ЕГЭ по информатике на 100 баллов

В каком отделении Школы программистов ты учился?

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

Чем тебе помогла Школа программистов при подготовке к ЕГЭ?

Школа дает очень хорошую базу для будущего экзамена и работы. Я поступил в школу в 8 классе. Первые два года подготовки — это те предметы, которые может быть кому-то покажутся ненужными, некоторые будут сомневаться, пригодится ли мне дискретная математика или система счисления. Но без базовой подготовки, которая здесь дается, ничего не получится. На первых двух курсах вы получите очень много знаний, которые помогают — дискретная математика, система счисления, алгебра логики — это основы основ, без которых на ЕГЭ делать нечего. Программирование, алгоритмы, связанные с обработкой чисел и последовательностей — это то, что любят составители ЕГЭ. И конечно же, курсы алгоритмов и курс компьютерных сетей — все, что связанно с IP адресами, как работает интернет, как оценивать эффективность, как оценивать сложность — это все изучается в первые два года в ШП и это очень хорошая база для подготовки.

Какова доля удачи и везения при сдаче ЕГЭ по информатике?

Есть люди, которые уверены в том, что они смогут угадать, что попадется на ЕГЭ. Но на самом деле на экзамене по любому предмету может быть абсолютно все, даже то, что вы никогда не видели ни в одном «пробнике». Здесь решает не столько удача, сколько подготовленность и даже не столько умение и количество решенных задач (1000, 2000), а навыки, знание методов решения и умение выбрать правильный путь к решению конкретной задачи, также важна еще психологическая составляющая. Если ты обладаешь всеми навыками, то на экзамен приходишь как к себе домой.

Можешь дать совет выпускникам, которые будут сдавать информатику? Как им достичь таких же успехов?

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

Линейные алгоритмы паскаль примеры

Линейный алгоритм

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

Структура программы на языке Паскаль

Прежде чем самостоятельно писать программы, разберем ее структуру на примере. Ниже приведен код программы, кото­рая вычисляет сумму двух чисел и выводит ее на экран.

program primer1;    
var х,у,z:integer; { описание переменных }
begin	{ начало программы }
  х := 3;	{ установка значения х }
  у := 5;	{ установка значения у }
  z := х + у;	{ вычисление суммы }
  write(z);	{вывод результата вычисления на экран }
end.	{ конец программы }

Текст программы начинается со слова program. После него записывается имя программы. Данная строка носит информативный характер и ее можно не писать.

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

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

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

Комментарии в программе можно записывать внутри фигурных скобок. Они игнорируются во время выполнения программы. Эти пояснения вы пишите только для себя.

В нашем примере переменные с именами X и Y используются для хранения исходных данных. Переменная с именем Z используется для хранения результата вычислений.

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

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

Принадлежность переменной к типу integer означает, что она может хранить только целые числа. Если требуется хранить действительные (дробные) числа, тогда используется тип real.

Все что находится между служебными словами Begin и end — тело программы. Здесь записываются основные команды.

Оператор присваивания значений переменным имеет следующую структуру: переменная := выражение

Значок : = (двоеточие, равно) читается как «присвоить».
Умножение обозначается символом * (звездочка),  деление — символом / (слеш).

Вывод результата выполняет команда write.

Каждая строка содержащая команду на языке Паскаль обязательно заканчивается символом «точка с запятой».

Команды ввода и вывода

Команда Read

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

Модифицируем код программы из примера выше.

program primer1;    
var х,у,z:integer; { описание переменных }
begin	{ начало программы }
  read(x,y);	{ ввод значений х и y с клавиатуры }
  z := х + у;	{ вычисление суммы }
  write(z);	{вывод результата вычисления на экран }
end.	{ конец программы }

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

При работающей программе в системе программирования PascalABC появится строка ввода данных. Там и пишутся значения переменных.

Команда Write

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

program primer1;    
var х,у,z:integer; { описание переменных }
begin	{ начало программы }
  writeln('Вычисление суммы двух чисел');  
  write('Введите два целых числа через пробел'); 
  readln(x,y);	{ ввод значений х и y с клавиатуры }
  z := х + у;	{ вычисление суммы }
  write('Сумма = ',z);	{вывод результата вычисления на экран }
end.	{ конец программы }

Теперь посмотрите, как добавленные строки повлияли на работу программы.

У нас появились подсказки. Посмотрите на команду write. В качестве ее аргумента был использован текст, заключенный в апострофы. И еще, появилось окончание ln у оператора write. Именно оно заставляет последующий вывод информации делать с новой строки. Это же окончание можно использовать совместно с оператором read.

Также поменялся вывод результата. Здесь тоже появилась подсказка.

Примеры программ на паскале — задания на линейные алгоритмы

Задание 1. Модифицировать программу так, чтобы она вычисляла и выводила на экран сумму и произведение трех целых чисел.

Решение:

program zadanie1;    
var х,у,k,z,p:integer; { описание переменных }
begin	{ начало программы }
  writeln('Вычисление суммы и произведения трех чисел');  
  write('Введите три целых числа через пробел'); 
  readln(x,y,k);	{ ввод значений х,y,k с клавиатуры }
  z := x + y + k;	{ вычисление суммы }
  p := x * y * k;       { вычисление произведения }
  write('Сумма = ',z);	{вывод результата сложения на экран }
  write('Произведение = ',p);	{вывод результата произведения на экран }
end.	{ конец программы }

Задание 2. Дана длина ребра куба а. Найти объем куба V=a³  и площадь его поверхности S=6a².

Решение:

program zadanie2;    
var a,v,s:real; { описание переменных }
begin	{ начало программы }
  writeln('Вычисление объема и площади поверхности куба');  
  write('Введите длину ребра куба'); 
  readln(a);	{ ввод значения a с клавиатуры }
  v := a * a * a;	{ вычисление объема }
  s := 6 * a * a;       { вычисление площади }
  write('Объем куба = ',v);	{вывод результата объем куба }
  write('Площадь поверхности = ',s);	{вывод результата площадь поверхности }
end.	{ конец программы }

Посмотрите еще примеры линейных алгоритмов.

Хотите подробнее узнать о системе PascalABC и начать писать в ней свои первые программы, тогда статья «Знакомство с PascalABC» для вас.

Следующая тема для изучения Условный оператор

Тест «Линейный алгоритм»

Лимит времени: 0

Информация

Проверь свои знания по теме «Линейный алгоритм»

Вы уже проходили тест ранее. Вы не можете запустить его снова.

Тест загружается…

Вы должны войти или зарегистрироваться для того, чтобы начать тест.

Вы должны закончить следующие тесты, чтобы начать этот:

Правильных ответов: 0 из 5

Ваше время:

Время вышло

Вы набрали 0 из 0 баллов (0)

Рубрики

1. Линейный алгоритм 0%

1. С ответом
2. С отметкой о просмотре

Урок 2. базовые алгоритмические структуры — Информатика — 11 класс

Информатика, 11 класс. Урок № 2.

Тема — Базовые алгоритмические структуры

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

Глоссарий по теме: следование, ветвление, повторение, цикл с предусловием, цикл с постусловием, цикл с параметром.

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса

— М.: БИНОМ. Лаборатория знаний, 2017

Дополнительная литература по теме урока:

И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова. Информатика и ИКТ. Профильный уровень: учебник для 11 класса — М.: БИНОМ. Лаборатория знаний, 2012

Теоретический материал для самостоятельного изучения

В 1969 году нидерландский ученый Эдсгер Дийкстра доказал важную теорему. Суть ее в том, что для решения любой логической задачи можно составить алгоритм, используя лишь три алгоритмических структуры: следование, ветвление и повторение. Эти структуры называют базовыми.

Самой простой структурой является «следование».

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

Алгоритм, основанный на конструкции «следование» называется линейным алгоритмом. Примером такого алгоритма может служить алгоритм вычисления дискриминанта квадратного уравнения, блок-схема которого приведена на рисунке 1.

Рис. 1

Следующей конструкцией является «ветвление». Она встречается, если действия алгоритма зависят от некоторого условия.

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

Существуют полная и неполная формы ветвления.

В полной форме если условие выполняется, то алгоритм переходит к выполнению первой серии команд, а если не выполняется — то ко второй.

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

Алгоритм, основанный на конструкции «ветвление» называется разветвляющимся алгоритмом. Примером такого алгоритма может служить алгоритм нахождения корней квадратного уравнения, блок-схема которого приведена на рисунке 2.

Рис. 2

И, наконец, последняя алгоритмическая конструкция — «повторение».

Алгоритм реализован с использованием алгоритмической конструкции «повторение», если некая группа подряд идущих шагов алгоритма (она называется телом цикла) может выполняться многократно в зависимости от входных данных.

Алгоритм, содержащий конструкцию «повторение» называется циклическим алгоритмом.

Существует несколько разновидностей циклических алгоритмов.

Первый — цикл с заданным условием продолжения работы (цикл с предусловием или цикл-пока).

Второй — цикл с заданным условием окончания работы (цикл с постусловием или цикл-до).

И третий — цикл с заданным числом повторений (цикл с параметром).

Доказано, что при решении задач можно ограничиться только одним циклом — циклом с предусловием. Но в ряде случаев цикл с постусловием или цикл с параметром делают решение задачи легче.

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

Учебный курс «Информатика»

ОГЭ по информатике: Исполнители алгоритмов

Пример 1.

Решение:

1. Вычислим перемещение исполнителя за одно выполнение тела цикла по оси ох:
     -2 + 3 + (-4) = -3

2. Так как цикл выполнялся три раза, общее перемещение по оси ох составляет 3 * (-3) = -9

3. Аналогично мы можем вычислить общее перемещение исполнителя по оси оу:
     3 * (-3 + 2 + 0) = 3 * (-1) = -3

Итак, алгоритм:

Повтори 3 раз
    Сместиться на (-2,-3) 
    Сместиться на (3,2) 
    Сместиться на (-4,0)
конец

можно заменить одной командой: Сместиться на (-9,-3)

Ответ: 1)

Пример 2.

Решение:

Это легкая задача. Один из вариантов решения может быть таким:
65 → 64 → 32 → 16 → 8 → 4

Ответ: 21111

Пример 3.

Решение:

Запишем в общем виде число: abc

Автомат на шаге 1 вычисляет a+b, b+c. На втором шаге автомат записывает эти суммы в порядке невозрастания.
Например, пусть дано число 197. Шаг первый: 1+9=10, 9+7=16. Шаг второй: записываются полученные числа 10 16 в порядке невозрастания : 1610

Еще пример: пусть на вход автомата поступило число 999. Шаг первый: 9+9=18, 9+9=18. Шаг второй: 1818

Как мы видим, максимальная сумма от сложения двух разрядов не превышает 18.

Итак, разберем приведённые выше числа: 1616  169  163  1916  1619  316  916  116.
1616 можно получить в результате работы автомата, например из чисел 888, 979, 797.
169 можно получить из таких чисел, как 881, 188, 972, 790.
163 никак получить нельзя, так как нельзя подобрать среднее число таким образом, чтобы оно входило в сумму 16 и в сумму 3 одновременно.
1916 получить нельзя, так как максимальная сумма двух десятичных цифр равна 18 (9+9).
1619 получить нельзя, так как сумму 19 невозможно получить из двух цифр и нарушен порядок записи — 16 и 19 записаны по возрастанию, а надо по убыванию.
316 нарушен порядок записи.
916 нарушен порядок записи. 
116 может получиться в результате работы автомата, например из чисел 560,651, 156, 742, 247

Ответ: 3 (указываем количество «правильных» чисел).

Пример 4.

Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она чётна, то удаляется правый символ цепочки, а если нечётна, то в начало цепочки добавляется буква Б. В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А <nobr>–</nobr> на Б; Б <nobr>–</nobr> на В и т.д., а Я <nobr>–</nobr> на А).

Получившаяся таким образом цепочка является результатом работы описанного алгоритма.

Например, если исходной была цепочка АВС, то результатом работы алгоритма будет цепочка ВБГТ, а если исходной была цепочка КРОТ, то результатом работы алгоритма будет цепочка ЛСП.

Дана цепочка символов СТОП. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т.е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)?

Русский алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

Решение:

1. Длина цепочки символов СТОП равна 4
2. Длина 4 — число чётное, удаляем символ справа: СТО
3. Заменяем каждую букву на следующую букву в алфавите: ТУП

Применим к результату ТУП  данный алгоритм ещё раз:

1. Длина цепочки символов ТУП равна 3
2. Длина 3 — число нечётное, добавляем в начало цепочки букву Б: БТУП
3. Заменяем каждую букву на следующую букву в алфавите: ВУФР

Ответ: ВУФР

Пример 5.

Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды:
Вперёд n (где n – целое число), вызывающая передвижение Черепашки на n шагов в направлении движения;
Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори k [Команда1 Команда2 Команда3] означает, что последовательность команд в скобках повторится k раз.

Черепашке был дан для исполнения следующий алгоритм:
Повтори 5 [Вперёд 100 Направо 120]

Какая фигура появится на экране?

1. правильный пятиугольник
2. правильный треугольник
3. правильный шестиугольник
4. незамкнутая ломаная линия

Решение, 1 способ: 

Выполнив первый раз команды [Вперёд 100 Направо 120], мы получим линию длиной 100 и развернем Черепашку на 120 градусов  по часовой стрелке:

Выполнив второй раз эти же команды, мы в целом получим две линии:

Выполнив третий раз эти команды, получим три линии:

Четвертое выполнение повторяет первое, пятое выполнение повторяет второе (то есть рисуют линию поверх старых).

Итак, мы получили треугольник. Минус этого метода в том, что надо точно поворачивать на угол, что в условиях экзамена сложно.

Решение, 1 способ: 

Так черепашка поворачивает на один и тот же угол (120 градусов по часовой стрелке), то, возможно, полученная фигура — правильный многоугольник (треугольник, четырехугольник, пятиугольник и т.д.).

Существует формула для определения внутреннего угла любого правильного многоугольника:

внутренний угол = (N-2)*180 / N, где N — число вершин многоугольника

В нашем случае внутренний угол равен 60 градусов:

Подставим значение угла в выражение:
60 = (N — 2) * 180  / N

Проверим вариант ответа № 1 — правильный пятиугольник:
60 = (5-2) *180 /5
60 = 3*180 /5 
60 = 108   Неверно! 

Проверим вариант ответа № 2 — правильный треугольник:
60 = (3-2) *180 /3
60 = 60   Верно!

Ответ: 2

Пройти тест по этой теме

ОГЭ по информатике

Информатика: алгоритмы

Алгоритмы

Вы, возможно, слышали термин алгоритм недавно, будь то онлайн или, возможно, в каком-то разговоре о технологиях. Это слово часто используют, но что именно оно означает?

Посмотрите видео ниже, чтобы узнать больше об алгоритмах.

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

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

Сначала вам нужно вскипятить кастрюлю с водой . Как только он закипит, добавьте спагетти и готовьте в течение заданного времени, периодически помешивая.Как только он закончится, вы сливаете воду , тогда готово, чтобы подавали с соусом по вашему выбору.

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

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

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

Все эти алгоритмы встроены прямо в код приложения. Если в коде будет какая-либо ошибка , приложение не сможет правильно следовать этим алгоритмам, а это означает, что вы не получите свои указания.

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

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

/ ru / информатика / аппаратно-программное обеспечение / содержание /

3 основных примера алгоритмов, которые вы должны знать

Есть определенные алгоритмы, которые возникают снова и снова. В этом руководстве мы рассмотрим три наиболее распространенных: поиск, сортировку и добавление / удаление из связанного списка. Идеи, связанные с этими примерами алгоритмов, пронизывают многие другие алгоритмы. Понимание этих трех примеров поможет нам построить прочный фундамент, чтобы мы могли уверенно решать будущие проблемы алгоритмов!

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

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

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

  def binary_search (arr, значение, смещение = 0)
  mid = (обр.длина) / 2
  
  если значение  arr [mid]
     binary_search (arr [(mid + 1) ..- 1], значение, смещение + mid + 1)
  
  еще
     смещение возврата + середина
  конец

конец 
 

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

Сортировка слиянием, использует аналогичную методологию «разделяй и властвуй» для эффективной сортировки массивов. См. Следующие шаги, чтобы узнать, как реализована сортировка слиянием.

1. Вернуть, если массив состоит только из одного элемента, потому что он уже отсортирован.
2. Разделите массив на две половины до тех пор, пока его нельзя будет больше разделить.

1. Объединяйте меньшие массивы в отсортированном порядке, пока не получите исходный отсортированный массив.

Чтобы реализовать сортировку слиянием, мы определим два метода. Один позаботится о разделении массива, а другой — о слиянии двух несортированных массивов обратно в один отсортированный массив. Мы вызываем метод разделения ( merge_sort ) рекурсивно до тех пор, пока наш массив не станет длиной всего в один элемент. Затем мы объединяем их вместе и, наконец, возвращаем наш отсортированный массив. См. Ниже:

  def merge_sort (массив)
  вернуть массив, если array.length == 1

  mid_point = массив.длина / 2
  left = array [0 ... mid_point]
  справа = массив [средняя_точка ..- 1]

  слияние (сортировка слияния (слева), сортировка слияния (справа))

конец 
 

  def слияние (слева, справа)
    merged_arr = []

    пока слева. пусто? && right.empty?
      если left.length == 0
        merged_arr << right.shift
      elsif right.length == 0
        merged_arr << left.shift
      elsif left [0] <= right [0]
        merged_arr << left.сдвиг
      elsif right [0] <= left [0]
        merged_arr << right.shift
      конец
    конец
    merged_arr
конец 
 

Merge Sort имеет временную сложность O (nlogn) , что является наилучшей возможной временной сложностью для алгоритма сортировки. Разделяя и завоевывая, мы резко повышаем эффективность сортировки, которая уже является дорогостоящим в вычислительном отношении процессом.

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

Связанный список состоит из узлов, каждый из которых имеет фрагмент данных и указатель на следующий узел. Мы представляем это в Ruby, создав структуру Node с двумя аргументами: : данные и : next_node . Теперь нам просто нужно определить два метода: insert_node и delete_node , которые принимают головной узел и местоположение , куда вставлять / удалять.Метод insert_node имеет дополнительный аргумент, node , который является структурой узла, которую мы хотим вставить. Затем мы зацикливаемся, пока не найдем место, в которое мы хотели бы вставить или удалить. Когда мы прибудем в желаемое место и переставим указатели, чтобы отразить нашу вставку / удаление.

  Узел = Struct.new (: data,: next_node)

def insert_node (голова, узел, расположение)
  current_node = голова
  current_location = 0

  до current_location == location
    предыдущий_узел = текущий_узел
    текущий_узел = текущий_узел.next_node
    current_location + = 1
  конец

  если предыдущий_узел
    previous_node.next_node = узел
    node.next_node = текущий_узел
  еще
    node.next_node = текущий_узел
  конец

  глава

конец

def delete_node (голова, местоположение)
  current_node = голова
  current_location = 0

  до current_location == location
    предыдущий_узел = текущий_узел
    current_node = current_node.next_node
    current_location + = 1
  конец

  если предыдущий_узел
    предыдущий_узел.next_node = current_node.next_node
  еще
    head = current_node.next_node
  конец

  глава
конец 
 

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

Шаг 1. Начать
Шаг 2: Объявите переменные num1, num2 и sum.Шаг 3: Считайте значения num1 и num2.
Шаг 4: сложите num1 и num2 и присвойте результат сумме.
        сумма ← число1 + число2
Шаг 5: Показать сумму
Шаг 6: Остановить
 

Шаг 1. Начать
Шаг 2: Объявите переменные a, b и c.
Шаг 3: Считайте переменные a, b и c.
Шаг 4: Если a> b
           Если a> c
              Отобразите наибольшее число.
           Еще
              Отображение c - наибольшее число.
        Еще
           Если b> c
              Дисплей b - это наибольшее число.Еще
              Дисплей c - наибольшее число.
Шаг 5: Остановить
 

Шаг 1. Начать
Шаг 2: Объявите переменные a, b, c, D, x1, x2, rp и ip;
Шаг 3: вычислить дискриминант
         D ← b2-4ac
Шаг 4: Если D ≥ 0
              r1 ← (-b + √D) / 2a
              r2 ← (-b-√D) / 2a
              Отобразите r1 и r2 как корни.
        Еще
              Вычислить действительную и мнимую часть
              rp ← -b / 2a
              ip ← √ (-D) / 2a
              Отображать rp + j (ip) и rp-j (ip) как корни
Шаг 5: Остановить
 

Шаг 1. Начать
Шаг 2: Объявите переменные n, факториал и i.Шаг 3. Инициализируйте переменные
          факториал ← 1
          я ← 1
Шаг 4: Считайте значение n
Шаг 5: повторяйте шаги, пока i = n
     5.1: факториал ← факториал * i
     5.2: я ← я + 1
Шаг 6. Отобразите факториал
Шаг 7. Остановить
 

Шаг 1. Начать
Шаг 2: Объявите переменные n, i, flag.
Шаг 3. Инициализируйте переменные
        флаг ← 1
        я ← 2
Шаг 4: Прочтите n от пользователя.
Шаг 5: повторяйте шаги, пока i = (n / 2)
     5.1 Если остаток от n ÷ i равен 0
            флаг ← 0
            Перейти к шагу 6
     5.2 я ← я + 1
Шаг 6: Если flag = 0
           Дисплей n не простой
        еще
           Дисплей n - простое число
Шаг 7. Остановить
 

Шаг 1. Начать
Шаг 2: Объявите переменные first_term, second_term и temp.
Шаг 3. Инициализируйте переменные first_term ← 0 second_term ← 1
Шаг 4. Отобразите first_term и second_term
Шаг 5: повторяйте шаги до тех пор, пока second_term ≤ 1000.
     5.1: температура ← second_term
     5.2: second_term ← second_term + first_term
     5.3: first_term ← temp
     5.4: Отображение second_term
Шаг 6: Остановить