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

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

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

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

Пример Один литр молока стоил 10200 рублей. Сегодня он подорожал на 5%. Сколько стоят 3 литра молока после подорожания?

алг abc (арг цел a,b,c)

дано |

надо |

нач

¦ а:=10200

c:=0.05

b:=3*int(a*c+a) , где int()- выделяет целую часть числа,

¦ вывод b записываемого в скобках

кон

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

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

Пример:

Даны a, в, c, - вывести те значения переменных, которые меньше 0

алг abc (арг цел a,b,c)

дано |

надо |

нач цел k

¦ k:=0;

¦ вывод('Ответ:')

¦ если a

¦ ¦то вывод(a)

¦ ¦ k:=k+1

¦ все

¦ если b

¦ ¦то вывод (b)

¦ ¦ k:=k+1

¦ все

¦ если c

¦ ¦то вывод(c)

¦ ¦ k:=k+1

¦ все

¦ если k=0

¦ ¦то вывод('Нет отрицательных чисел')

¦ все

кон

Проверка программы: - ввод значений переменных

а) (a

б) (a

с) (а 0) и (в 0) и (с 0);

1. ввод значений переменных, больших 0.

3.Циклические алгоритмы.

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

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

Примечания:

• Если при первой проверке условия оно будет «ложь», то цикл не выполняется ни разу.

• Если условие всегда «истина» - имеем бесконечно исполняемый цикл.

АЛГОРИТМ РАБОТЫ

1. Счетчику присваивается начальное значение .

2. Проверка: счетчик

3. Тело цикла.

4. Изменяется значение счетчика на шаг .

5 Переход к шагу 2.

6. Выход из цикла .

б) Цикл с предусловием

АЛГОРИТМ РАБОТЫ.

1. Проверяется условие. Если условие = «истина» , то переход к шагу 2, иначе переход к шагу 4.

2 Выполняется тело цикла.

3 К шагу 1.

4 Выход из цикла.

в) Цикл с постусловием

АЛГОРИТМ РАБОТЫ.

1. Выполняется тело цикла

2. Проверяется условие. Если условие = «истина» , то переход к шагу 3, иначе переход к шагу 1.

3. Выход из цикла.

Примеры:

a) Найти 5!, т.е. произведение чисел

от 1 до заданного числа 5

алг факториал ( вещ s )

дано

надо s

нач цел i

s:=0

для i от 1 до 5

нц

s := s *i

кц

кон

б) Найти факториал числа n,.т.е. n!

алг факториал ( арг цел n, рез цел p)

арг! n

рез! p

нач цел i,

p:=1

i:=1

нц пока i

p:=p*i

i:=i+1

кц

Алгоритмический язык КУМИР

При записи алгоритма в виде псевдокода используются команды КУМИРА (русского алгоритмического языка). К ним относятся алг, нач, кон, если, пока, для, ввод, вывод, выбор и некоторые другие.

Общий вид алгоритма:

алг имя-алгоритма (аргументы и результаты)

дано! (условия применимости либо можно уточнить аргументы)

надо! (комментарий - можно уточнить результирующие переменные )

нач описание промежуточных величин

тело алгоритма (последовательность команд)

кон

ТИПЫ ВЕЛИЧИН

Типы переменных: Таблицы

целые цел целые цел таб

вещественные вещ вещественные вещ таб

логические лог логические лог таб

символьные сим символьные сим таб

литерные лит литерные лит таб

Пример описания: цел i, j, вещ x, лит t, вещ таб а[1:50]

Виды величин

аргументы (арг) описываются в заголовке алгоритма

результаты (рез) описываются в заголовке алгоритма

промежуточные описываются в строке нач алгоритма

Название операции или функции Форма записи

сложение х + у

вычитание х - у

деление х * у

возведение в степень х ** у

корень квадратный sqrt(x)

абсолютная величина abs(x)

знак числа (-1, 0 или 1) sign(x)

синус sin(x)

косинус cos(x)

тангенс tg(x)

котангенс ctg(x)

арксинус arcsin(x)

арккосинус arccos(x)

арктангенс arctg(x)

арккотангенс arcctg(x)

натуральный логарифм ln(x)

десятичный логарифм lg(x)

степень числа e(e=2.718281) e^x exp(x)

минимум из чисел х или у min(x,y)

максимум из чисел х или у max(x,y)

остаток от деления х на у (х, у - целые) mod(x,y)

частное от деления х на у (х, у - целые) div(x,y)

целая часть числа х int(x)

случайное число в диапазоне от 0 до х rnd(x)

Команды алгоритмического языка:

Присваивание: имя величины:=выражение

Команда ПОКА (последовательность команд в теле цикла выполняется до тех пор, пока выполняется условие):

нц пока условие

тело цикла ( последовательность команд

кц

Команда ДЛЯ (последовательность команд в теле цикла выполняется до тех пор, пока i пробегает все значения от iнач до iкон с шагом 1:

нц для i от iнач до iкон

тело цикла (последовательность команд)

кц

Здесь i - параметр цикла, iнач, iкон - произвольные целые числа или выражения с целыми значениями.

Команда ЕСЛИ (полная и неполная формы) позволяет при выполнении алгоритма выбрать один из двух вариантов действий ЭВМ:

если условие если условие

то серия 1 то серия1

иначе серия2 все

все

Если условие исполняется, то выполнять серию действий 1, иначе выполнять серию действий 2.

Команда ВЫБОРА (полная и неполная формы) применяется, если нужно выполнить один из многих вариантов:

выбор выбор

при условие 1: серия1 при условие 1: серия1

при условие 2: серия 2 при условие 2: серия 2

. . . . . .

при условие n: серия n при условие n: серия n

иначе: серия n+1 все

все

Команды ввода - вывода величин:

ввод имена величин

вывод имена величин, тексты, выражения

Примеры записи алгоритмов:

1. Найти площадь круга для заданного радиуса

алг круг (вещ рад, вещ пл)

арг!рад

рез! пл

нач вещ пи

| пи:=3.14159

| пл:=пи*рад*рад

кон

2 Найти меньшее из двух чисел:

алг МИД (вещ a, b, вещ y)

арг a, b

рез y

нач

| если ab

| | то y:=a

| иначе y:=b

все

кон

3 Найти сумму двузначных чисел, кратных 2.

алг двузначные ( рез цел сум)

арг!

рез! сум

нач нат i,

сум:=0

i:=10

нц пока i

cум:=сум+i

i:=i+2

кц

кон

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

Алг перевоз

нач

пока на первом берегу есть туристы

нц

двум мальчикам плыть на второй берег

первому мальчику остаться на втором берегу

второму мальчику плыть на первый берег

второму мальчику остаться на втором берегу

туристу плыть на второй берег

первому мальчику плыть на первый берег

нц

кон

5. Составить и записать алгоритм отгадывания задуманного числа из интервала от 1 до N

а) алг отгадывание_числа

нач цел ответ

пока в интервале = 2 целых чисел

нц

делить интервал пополам

ввод ответ

если задуманное число в первой половине

то считать первую половину интервалом

иначе считать вторую половину интервалом

все

кц

кон

б) алг отгадывание_числа

нач цел ответ,число

число:=rnd(N)

пока ответчисло

нц

ввод ответ

если ответчисло

то вывод ("меньше")

иначе если ответ

то вывод ("больше")

иначе вывод ("угадал")

все

все

кц

кон

6. Ивана Александровича Хлестакова пригласили управлять департаментом. В первый день к нему прибыло 1000 курьеров, а в каждый последующий - в 2 раза больше, чем в предыдущий. Иван Александрович согласился тогда, когда к нему прибыло не менее 30000 курьеров. На какой день это произошло?

aлг Хлестаков ( рез цел N, )

нач цел I

N:=1

I:= 1000

пока I

нц

N:=N+1

I:=I*2

кц

вывод N

кон

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

алг БИТ (вещ а, b, c, вещ z)

арг a, b, c

рез z

нач

| БИД ( a ,b, z )

| БИД (z, c, z)

кон

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

алг БИД (вещ a, b, вещ y)

арг a, b

рез y

нач

| если a=b

| | то y:=a

| иначе y:=b

| все

кон

ПРИЛОЖЕНИЕ 1

Краткие характеристики языков программирования

FORTRAN и СOBOL. Язык фортран, (разработан в 50-х гг.) - исторически первый язык высокого уровня, активно используется и на ПК . Применяется главным образом при разработке прикладных систем, ориентированных на научные исследования и другие области народного хозяйства, где уже накоплены обширные стандартные библиотеки программ решения вычислительных задач. Имеется несколько версий этого языка, из которых наиболее популярна версия «фортран-77».

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

BASIC (бейсик). язык прост в освоении и использовании. Разработан в середине 60-х годов сотрудниками Дартмутского колледжа Дж. Кемени и Т. Курцем. Считается самым распространенным в мире языком программирования, имеет много диалектов. Имеются удобные функции для работы с экраном дисплея, клавиатурой, принтером, внешними накопителями. Стандартная система программирования на основе языка бейсик состоит из двух главных компонентов - редактора, позволяющего составлять и модифицировать программы, и интерпретатора, исполняющего подготовленные программы. Исполнение программы начинается, когда пользователь дает команду RUN; с этого момента и до конца работы программы текст ее уже не меняется. Пользователь только наблюдает за результатом интерпретации, в ходе которой может происходить диалог между человеком и машиной. В режиме интерпретации каждый оператор языка сначала читается системой, анализируется работающей программой и лишь после этого выполняется. В трансляторах компилирующего типа, в отличие от этого, все стадии чтения и анализа осуществляются заранее - на этапе компиляции, а при исполнении работает готовая программа в машинных кодах, сформированная на этапе компиляции. Чтобы сохранить преимущества языка бейсик и в то же время дать возможность построения эффективных, быстро работающих программ, созданы бейсик-компиляторы.

PASCAL и С (паскаль и си). Паскаль создан в 1978 году Никлаусом Виртом. Эти языки чаще всего используются профессиональными системными программистами для разработки системных и прикладных программ. Оба этих языка позволяют работать с данными сложной структуры; оба имеют развитые средства для выделения отдельных частей программ в процедуры. Трансляторы работают в режиме компиляции. Важным средством для построения больших программных систем является модульность, т.е. возможность независимой разработки отдельных частей программ и последующего их связывания в отдельную систему. Программы на паскале легко читаются, они структурированы. Развитием языка Паскаль, выполненным под Windows, является язык DELPHI. В нем программа составляется из отдельных блоков, подготовленных ЭВМ.

Язык си с момента своего появления (1972г.) был ориентирован на разработку системных программ и для переноса программного обеспечения с одной ЭВМ на другую . В этом языке имеются более гибкие средства для эффективного использования особенностей аппаратуры, чем в паскале. Программы, как правило, более компактны и работают быстрее, чем программы, полученные с помощью паскаль- трансляторов. Синтаксис языка си менее прозрачен, чем у паскаля; возможностей для внесения ошибок больше; чтение текстов программ требует определенного навыка.

MODULA-2. Наследует лучшие черты паскаля, (автор – также Н. Вирт) в том числе его синтаксис, обладает лучшими средствами для разработки больших программных комплексов и позволяет более эффективно использовать особенности аппаратуры. В языке явно сформулированы средства оформления программных модулей и организации взаимодействия между ними, в том числе на основе так называемых сопрограмм, работающих псевдопараллельно. Явными операторами задается экспорт и импорт внешних объектов.

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

LISP и PROLOG. Язык лисп в основном используется для построения программ с использованием методов искусственного интеллекта. Особенность этого языка состоит в удобстве динамического создания объектов. В качестве порождаемых программой объектов могут фигурировать сами программы (функции), которые внешне ничем не отличаются от данных. Это открывает неожиданные возможности, которых нет в других языках программирования , например, построение адаптирующихся и самоизменяющихся программ и др. Память в лиспе используется динамически - когда создается новый объект, для него из «свободной» памяти берется ровно столько ячеек, сколько нужно для хранения всех элементов; при этом не требуется заблаговременного резервирования памяти, как в других языках (например, в паскале). При уничтожении объекта занятая им память автоматически освобождается. Большинство экспериментальных систем искусственного интеллекта - для анализа визуальных сцен, управления роботами, анализов текста на естественном языке и др. - разрабатывается с помощью языка лисп .

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

ADA. Создан в 1980году. Считается универсальным языком для разработки как системных, так и прикладных программ, в первую очередь для решения задач реального времени. Назван в честь Ады Лавлейс – первой программистки в истории.

ПРИЛОЖЕНИЕ 2

ПРИМЕРЫ ЗАПИСИ НЕКОТОРЫХ АЛГОРИТМОВ

1 Дан текст . Составить алгоритм подсчета количества предложений в тексте, cчитая, что предложение заканчивается одним из символов: точкой, вопросительным знаком , восклицательным знаком.

алг РИТМ (лит T, цел K)

арг T

рез K

нач цел p

если длин(T)0

то для p от 1 до длин (T)

нц

выбор

при (T[p:p]=“.”) или (T[p:p]=“?”) или (T[p:p]=“!”):k:=k+1
все

кц

все

кон

2. Алгоритм решения квадратного уравнения A x²+Bx+C=0 (A0)

алг КВУР (вещ A, B, C, X₁, X₂, лит T)

арг ! A, B, C

рез ! x₁, x₂, T

нач вещ D, y

D:=B*B-4*A*C

если D=0

то y:=SQRT(D)

x₁:=(-B-y)/(2*A)

x₂:=(-B+y)/(2*A)

T:=“ЕСТЬ РЕШЕНИЯ”

иначе T:=“НЕТ РЕШЕНИЙ”

все

кон

3. Алгоритм упорядочения элементов линейной таблицы A[1:n] по неубыванию значений элементов.

алг SORT (нат n, вещ таб A[1:n])

арг! n, A

рез! А

нач нат k, i, вещ c

нц для k от 1 до n - 1

нц для i от k+1 до n

если A[k]A[i]

то c:=A[k]; A[k]:=A[i]; A[i]:=c

все

кц

кц

кон

4. Даны две линейные таблицы ГР1[1:35] и ГР12[1:37] , содержащие оценки учащихся двух параллельных групп по информатике. Требуется определить количество хороших и отличных оценок в каждой группе.

РЕШЕНИЕ. Составим вспомогательный алгоритм , определяющий количество четверок и пятерок в линейной таблице ГР[1:n], где n -количество учеников в группе.

Алг ПОИСК (цел n, цел таб ГР[1:n], цел T4, T5)

арг !n, ГРУППА

рез ! T4 , T5

нач нат i

T4:=0; T5:=0

нц для i от 1 до n

выбор

при ГР [i]=4: T4:=T4+1

при ГР [i]=5: T5:=T5+1 все

кц

кон

В алгоритме ПОИСК параметры n, ГР, T4, T5 являются формальными .Используем алгоритм ГРУППА для решения поставленной задачи. Переменным T14, T15, T24, T25 соответствует количество четверок и пятерок в первой и второй группах соответственно.

Алг ОТМЕТКИ (цел таб ГР1 [1:35], ГР2 [1:37], цел T14 , T15 , T24 , T25)

арг ГР1 , ГР2

рез T14 , T15 , T24 , T25

нач

ПОИСК(35,ГР1[1:35], T14, T15 )

ПОИСК(37,ГР2, T24 , T25)

кон

1