Основы алгоритмизации. Рабочая тетрадь. 8-9 класс
методическая разработка по информатике и икт (9 класс) по теме

Информатика

Основы алгоритмизации

Рабочая тетрадь

Санкт-Петербург

2012-2013

АЛГОРИТМ И БЛОК-СХЕМА

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

Слово “алгоритм “ произошло от латинского слова algorifmi. В IX веке математик Мухаммед ибн Муса ал-Хорезми впервые в истории математики ввёл общие правила решения квадратных уравнений. В Европе при переводе имя автора переделали в Алгоритми. Ссылки на рецепты решений из книги Мухаммеда европейские авторы начинали со слов: "Так говорил Алгоритми ...". С течением времени сами рецепты для решения математических задач стали называть алгоритмами.

Точное математическое определение понятия "алгоритм" было выработано лишь в тридцатых годах XX века. Почему же до этого времени математики довольствовались интуитивным понятием алгоритма? Это связано с тем, что обычно понятие алгоритма встречалось в связи с конкретным решением задачи. Об алгоритме говорили лишь тогда, когда предлагался способ решения какого-либо класса задач. В начале XX века в математике накопилось большое количество задач, которые не поддавались решению, несмотря на то, что над ними думали первоклассные ученые. Возникло подозрение, что для некоторых из этих задач вообще не существует разрешающего алгоритма. Утверждение о неразрешимости того или иного класса задач можно было вывести, только имея точное определение алгоритма, надо было знать, не существование чего требуется доказать. Понятие алгоритма является не только центральным понятием теории алгоритмов, не только одним из главных понятий математики вообще, но одним из главных понятий современной науки. Более того, сегодня, с наступлением эры информатики, алгоритмы становятся одним из важнейших факторов цивилизации.

Исполнитель алгоритма - это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Исполнителя характеризуют:

• среда;
• элементарные действия;
• система команд;
• отказы.

Среда (или обстановка) — это «место обитания» исполнителя. Например, для исполнителя Робота среда — это бесконечное клеточное поле. Стены и закрашенные клетки тоже часть среды, а их расположение и положение самого Робота задают конкретное состояние среды.

Система команд. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка - системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. Например, команда Робота «вверх» может быть выполнена, если выше Робота нет стены. Ее результат — смещение Робота на одну клетку вверх.

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

Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.

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

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

Основные свойства алгоритмов следующие:

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

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

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

Результативность (или конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.

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

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

• словесная;
• табличная;
• графическая;
• программа.

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

Словесный способ не имеет широкого распространения, так как такие описания:

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

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

Графический способ подразделяется на:

• рисунок;
• граф-схемы;
• блок-схемы.

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

Можно представить алгоритм в виде схемы или графа — вторая, более строгая, формализованная форма

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

Граф — геометрический объект, состоящий из вершин и соединяющих вершины линий и дуг.

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

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

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

Чаще всего используются блоки следующих типов:

I. ЛИНЕЙНЫЕ АЛГОРИТМЫ.

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

Блок-схема базовой структуры следование.

выход

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

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

Продукты: 250 г очищенных грецких орехов,0,8 л молока, 120 г сахара.

1. ____________________________________________________________________________

2. ____________________________________________________________________________

3. ____________________________________________________________________________

4. ____________________________________________________________________________

5. ____________________________________________________________________________

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

1._____________________________________________________________________________

2. ____________________________________________________________________________

3. ____________________________________________________________________________

4. ____________________________________________________________________________

5. ____________________________________________________________________________

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

Задача 4. Дана длина ребра куба. Составьте блок-схему алгоритма нахождения площади грани, площади полной поверхности и объема этого куба.

Задача 5. Дано а. Не используя никаких функций и операций, кроме умножения, получить а8за три операции. Заполните шаблон, используя таблицу значений при а = 2

Задача 6. Составьте алгоритм для нахождения расстояния между двумя пешеходами, идущими навстречу друг другу, начавшими путь одновременно.

Lo - начальное расстояние,

V1 - скорость первого пешехода,

V2 - скорость второго пешехода,

Т - время движения,

L1 - текущее расстояние.

1. _______________________________________________________________________
2. _______________________________________________________________________
3. _______________________________________________________________________
4. _______________________________________________________________________
5. _______________________________________________________________________

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

Задача 8. Найти произведение цифр заданного четырехзначного числа n. Заполните шаблон, используя таблицу значений при n= 8341.

Блок-схема:

Задача 9. По заданнойблок схеме алгоритмазаполните таблицу значений (R1 =3, R2= 5) ивосстановите условие задачи.

II. РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ.

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

Блок-схемы базовых структур.

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

1.        ________________________________

2.        ________________________________

3.        ________________________________

4.        ________________________________

5.        ________________________________

Задача 2. В блок-схеме алгоритма вычисления значения функции

Задача 3. Кровяное давление у старшеклассников считается нормальным, если верхняя его граница Н < 100, нижняя h > 60 и H-h > 30. Составьте алгоритм, который в зависимости от измеренных значений Н и h выдает одно из следующих значений: «нормальное», «повышенное», «пониженное».

Воспользуйтесь шаблоном.

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

Задача 5. Какое значение получит переменная Z в результате выполнения следующего алгоритма?

Задача 6. Заполните шаблон блок-схемы алгоритма исследования квадратного уравнения  ах2 + bх + с = 0 (а ≠0)

Задача 7. Определить, принадлежит ли точка (х, у) круговому кольцу с центром в начале координат и внутренним радиусом r, а внешним R.

Заполните таблицу значений для х = 3; у = 4; r= 1,5; R = 3, используя блок-схему алгоритма.

Задача 8. Найти значение;

В шаблоне блок-схемы алгоритма расставьте «да» или «нет» и заполните пустые блоки.

Задача 10. По заданной блок-схеме алгоритма нарисуйте график функции.

Задача 11. Дан график функции. Восстановите вид функции и составьте блок-схему алгоритма для вычисления ее значений в зависимости от заданного х.

Задача 12. Заполните пустые блоки в шаблоне алгоритма, с помощью которого можно вычислить дату следующего дня (високосные года не рассматривать).

d,m,g

m

m=12

d<2

d=d+1

m=3

m=m+1

g=g+1

d=1

d,m,g

Задача 13. Даны произвольные числа а, Ь, с. Составьте блок-схему алгоритма, который выдает значение 0, если нельзя построить треугольник с такими длинами сторон, иначе выдает 3, 2 или 1, в зависимости от того, равносторонний это треугольник, равнобедренный или какой-либо иной.

Заполните таблицу значений при   а = 5, b = 4, с = 10;

при   а = 5, b = 4, с - 5.

К=1

К=0

К=2

К=3

III. ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ.

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

Цикл называется арифметическим, если число повторений цикла известно заранее или может быть вычислено.

Блок-схема базовой структуры. Цикл с параметром.

Проверка условия окончания цикла

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

Блок-схемы базовых структур

.

Задача 1. Составьте блок-схему алгоритма нахождения площади треугольников, заданных сторонами a, b, (c+k), где к = 1,2,...15. Воспользуйтесь словесным алгоритмом. (а, b, с, k- такие, что треугольники существуют).

1. Задать а, b, с.
2. k:=1.
3. Если к≤15, то п.4, иначе п.9.
4. d:=c + k.
5. р := (a + b + d)/2,
6. s := .
7. Вывод s.
8. k :=k+ 1, переход к п.З.
9. Конец.

Задача 2. Заполните пустые блоки в шаблоне алгоритма вычисления суммы n первых натуральных чисел.

Выполнить алгоритм для n = 3, результат записать в таблицу значений:

Задача 3. По словесному алгоритму вычисления 2n составьте блок-схему алгоритма (n - натуральное число).

1. Задать n.
2. р:=1.
3. i:=1.
4. Если i < n, то п.5, иначе п.7.
5. р := р • 2.
6. i := i + 1, перейти к п.4.
7. Вывод р.
8. Конец.

Задача 4. Составьте блок-схему алгоритма вычисления n корней

                                                                          n корней

Задача 5. Составьте блок-схему алгоритма вычисления S = т(т + 1)(т + 2)...(т + n),   где   т,   n - заданные натуральные числа.

Задача 6.  Дана блок-схема вычисления значений функции

для х [-3; 3], h = 0,5.

На координатных осях отметьте данные значения аргумента х и полученные значения функции у. По полученным точкам постройте график функции y

Задача 7. Разделить натуральное число х на натуральное число у. Получить в качестве результат частное от деления q и остаток r, т. е. представить число в виде х = q*у+ r, где r < у; q, r - целые числа. Операцией деления не пользоваться.

Составьте блок-схему алгоритма по таблице значений для х = 9, у = 2.

Задача 8. Составьте блок-схему алгоритма, который выдает 1, если заданное число простое и 0 - в противном случае.

Число называется простым, если все его делители 1 и оно само.

Указание. Делители числа лежат в интервале от 2 до  (k - заданное число).

Задача 9. Ученик в первый день выучил 5 английских слов. В каждый следующий день он выучивал на 2 слова больше, чем в предыдущий. Сколько английских слов выучит ученик в 10-ый день занятий?

Приведен словесный алгоритм этой задачи.

1. а:=5.
2. d:=1
3. Если d < 10, то п.4, иначе п.6.
4. а:=а + 2.
5. d := d + 1, перейти к п.З.
6. Вывод а.
7. Конец.

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

Задача 10. Составьте блок-схему алгоритма нахождения максимального числа среди заданных n чисел (n  2).

Задача 11. По блок-схеме алгоритма восстановите условие задачи.

Задача 12. Заполните шаблон блок-схемы для определения сколько раз в заданном числе встречается цифра 5.

Заполните таблицу значений для к = 515.

Задача 13. Известна знаменитая изобретателе шахматной игры.

Царь Шерам, которому была преподнесена в подарок эта игра, захотел наградить изобретателя Сете и разрешил ему выбрать награду самому. «Дай мне, - сказал мудрец, - только несколько пшеничных зерен. Причем ровно столько, сколько поместится на шахматной доске, если ты на первую клетку положишь одно зернышко, то на вторую - два зернышка и так далее: на каждую клетку вдвое больше, чем на предыдущую». Царь был рассержен из-за этой слишком скромной просьбы мудреца. Но как же он был удивлен, когда ему не хватило запасов пшеницы всей Индии, чтобы ее выполнить.

Математики царя Шерама подсчитали, что количество зерен на последней клетке выражается не поддающимся воображению гигантским числом. Зерно занимало бы два амбара длиной от Земли до Солнца.

Составьте блок-схему алгоритма, который бы определял, сколько клеток смог заполнить царь Шерам своей пшеницей. (Тонна пшеницы состоит из 4000000 зерен).

Задача 14. Составьте блок-схему алгоритма нахождения 13-ого члена последовательности, заданной формулой общего члена хп-п • хп-\ + \1п, х0 = 1, п = 1,2...

В заданном шаблоне блок-схемы заполните блоки и расставьте соединительные стрелки.

Словесный алгоритм.

1. Задать п.
2. хо:=\.
3. /:=1.
4. Если i < п, то п. 5, иначе п. 8.
5. х :- i • х0 + Ш .
6. i:=i+\.
7. х0 := х, перейти к п. 4.
8. Вывод х.
9. Конец.