Алгоритмы решения типовых задач

Лабораторная работа №3

«Алгоритмы решения типовых задач»

Цель:

1.      познакомиться с понятием алгоритма, исполнителями алгоритмов, примерами алгоритмов в жизни, алгоритмическим способом решения задач;

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

Основные понятия:

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

       В 1983 году отмечалось 1200-летие со дня рождения одного из величайших ученых Средней Азии и средневекового Востока Мухамада ибн Мусы аль-Хорезми. Он написал ряд трактатов по арифметике и алгебре, в том числе книгу "Арифметика индусскими цифрами" – о счете с помощью десяти цифр и правилах арифметических действий с числами.

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

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

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

        Алгоритм – это организованная последовательность действий.

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

Допустим, нужно решить квадратное уравнение.

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

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

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

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

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

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

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

С алгоритмами человек встречается на каждом шагу.

Пример 1. Дан угол. Необходимо провести биссектрису. (Есть способ, как, пользуясь линейкой и циркулем, можно решить эту задачу.)

Пример 2. Даны два целых числа. Необходимо найти их разность. (Имеется правило, в котором ясно изложен весь порядок действий с цифрами данных чисел.)

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

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

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

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

Задания:

Алгоритмические задачи

№1. Старик должен переправить на лодке через реку волка, козу и капусту. Лодка может выдержать только старика и одного “пассажира”. В каком порядке старик перевезет пассажиров? Не забудь, что волк может съесть козу, а коза – капусту. Найди 2 варианта решения.

Алгоритм решения задачи:

и т.д.

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

 Обозначения: 1м- один мальчик, 2м – два мальчика, 1в – один взрослый.

Практикум по решению задач

1.    Злоумышленник поменял местами действия в алгоритме вычисления среднего арифметического из квадратного корня трёх чисел:

Присвоить а значение (а²+в²+с²) /3.

Вести а,в,с

Сообщить “Среднее арифметическое квадратов равно”

Сообщить а.

Восстановите правильный порядок действий.

2. Исправьте следующий алгоритм решения уравнения (х-2) (х+2) =0:

Присвоить х значение +-2.

Сообщить “Корни уравнения равны”.

Сообщить первое значение х.

Сообщить второе значение х.

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

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

Измерить температуру.

Если температура выше 37⁰, то:

Вызвать врача.

Пойти в школу.

Несмотря на недомогание, школьник исправил этот алгоритм, добавив всего две строки. Какие строки добавил школьник?

5. Запишите в виде алгоритмов правила определения знака:

А) произведения двух действительных чисел;

Б) суммы двух действительных чисел.

6. В записи алгоритма вычисления значения выражения (х²- 5х+5) / (х⁶- 4х²+3)

Злоумышленник одно действие поставил не на свое место. Вот как стал выглядеть алгоритм:

1. ввести х
2. если х⁶- 4х² + 3=0, то:
3. сообщить “При таком х значение выражения не определено”.
4. иначе:
5. присвоить у значение (х²- 5х +5) /(х⁶- 4х²+3) .
6. конец ветвления.
7. сообщить у.

6.      Оформить отчет по лабораторной работе.

7.