1. Алгоритмизация

Алгоритм – понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи.
Исполнитель – это тот объект или субъект, для управления которым составлен алгоритм. СКИ (система команд исполнителя) – это вся совокупность команд, который исполнитель умеет выполнять (понимает).

Свойства алгоритма:

1.      Понятность – алгоритм можно строить только из команд, входящих в СКИ исполнителя.

2.      Точность – каждая команда алгоритма управления определяет однозначное действие исполнителя. Пример неоднозначности «Казнить нельзя помиловать».

3.      Конечность - выполнение алгоритма должно приводить к результату за конечное число шагов.

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

5.      Массовость – возможность применения алгоритма для решения целого класса конкретных задач. Например, правильнее составить алгоритм для решения уравнения ax+b=0, чем для решения уравнения 5х+8=0, т.к. в первом случае меняя исходные данные a и b можно решить любое уравнение данного типа.

Этапы решения задач на ЭВМ:

1.      Постановка задачи (что дано, и что требуется найти).

2.      Математическая формализация (создание математической модели).

3.      Построение алгоритма.

4.      Составление программы на языке программирования.

5.      Отладка и тестирование программы.

6.      Эксплуатация (применение).

 

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

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


Структура “следование”


Полная развилка


Неполная развилка


Цикл с предусловие (цикл ПОКА)


Цикл с постусловием (цикл ДО)



 

Цикл с параметром

 

На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.

Начало и конец алгоритма на блок-схемах обозначают овалом, вводимые и выводимые переменные записываются в параллелограмме.

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

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

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

Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?

1. Ввести v1, v2, v3, t1, t2, t3.

2. S1 := v1 * t1.

3. S2 := v2 * t2.

4. S3 := v3 * t3.

5. S := S1 + S2 + S3.

6. Вывести значение S.

7. Конец.

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

Развилка

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

Пример 2. Вычислить значение функции

1. Ввести x.

2. Если x£–12, то y:=–x2

3. Если x<0, то y:=x4

4. y := x–2

5. Вывести y

6. Конец

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

Циклы

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

Пример 3. Дана последовательность, общий член которой определяется формулой

An=(n-1)/n2

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

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

1. Ввести e

2. S := 0

3. A := 1/4

4. n := 3

5. Сравнить А с e. Если A>=e, переход к п. 10

6. S := S + A

7. A := (n-1)/(n*n)

8. n := n + 1

9. Переход к п. 5

10. Вывод S

11. Конец

Цикл с предусловием (цикл «До»).

начало

конец

X ч/з RND

 

да

  A>X

    N=0

нет

 A, N

     A

 

Мое число <

N=N+1

  A=X

да

нет

Мое число >
Пример 3. Цикл с постусловием (цикл «Пока»). Составьте блок-схему алгоритма игры «Угадай число» в диапазоне от 1 до 100.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Пример 4. Найти произведение первых k натуральных чисел, кратных трём.

При составлении алгоритма учтем, что первое натуральное число, кратное 3, есть тройка, а все последующие больше предыдущего на 3.

1. Ввод k

2. P := 1 {здесь накапливаем произведение}

3. T := 0 {здесь будут числа, кратные 3}

4. I := 1

5. Если I > k, переход к п. 10

6. T := T + 3

7. P := P * T

8. I := I + 1

9. Перейти к п. 5

10. Вывод P

11. Конец

Цикл с параметром.

Вопросы и задания.

1.      Сформулируйте определение алгоритма и ОАС.

2.      Перечислите способы записи алгоритмов.

3.      Перечислите свойства алгоритма и объясните их суть.

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

5.      Составьте алгоритм вычисления площади треугольника по формуле Герона P=1/2(A+B+C) – периметр, S=SQR(P(P*A)(P*B)(P*C)), SQR – квадратный корень. Алгоритм запишите в виде блок-схемы.

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

         -1 при х<0,

    0 при x=0

           1 при x>0

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

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

9.       Определить средний рост школьников 8-х классов (просуммировать рост всех школьников, которым на данный момент его измерили и разделить на количество школьников). Условие прекращения R(рост)=0, т.к. заранее неизвестно количество школьников. Алгоритм запишите в виде блок-схемы.

10.  По следующему словесному описанию алгоритма восстановите формулу:

1.      сложить х с 1, результат обозначить А1;

2.      сложить А1с1, результат обозначить А2;

3.      сложить А2 с 1, результат обозначить А3;

4.      разделть 1 на А1, результат обозначить В1;

5.      разделить 2 на А, результат обозначить В2;

6.      разделить 3 на А3, результат обозначить В3;

7.      сложить В1 и В2, результат обозначить С;

8.      сложить В3 и С, результат считать значением y.

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

 

начало

конец

K=0; S=0

     R

да

 R<>0

K=K+1

нет

S=S+R

C=S/K

     C
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


2. СИМВОЛЬНЫЕ ПЕРЕМЕННЫЕ

 

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

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

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

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

Символьная функция - это функция, значениями которой являются строки символов. Имя символьной функции тоже оканчивается знаком $.

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

Кроме того, для строк определена операция сравнения. Строки считаются равными, если их длины равны и коды всех символов попарно совпадают. Если одна из строк совпадает с началом другой (но короче ее), то она меньше. В остальных случаях все решает код первого несовпадающего символа - меньше та строка, у которой он меньше.

Значения символьной переменной могут задаваться при помощи оператора присваивания, оператора INPUT и совместного использования операторов READ и DATA.

 

Пример 1

A$="Урок "

READ B$

DATA "информатика"

C$=A$+LEFT$(B$,10)+"и"

PRINT C$

В результате выполнения этого фрагмента программы будет напечатано:

Урок информатики

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

ASC(строка) выдает код первого символа строки.

Пример 2

PRINT "Код буквы F равен "; ASC("F")

Этот оператор выдаст на экран текст:

Код буквы F равен 70

CHR$(число) обратная функции ASC. Она трактует заданное число как код символа и выдает символьную строку, состоящую из одного этого символа.

Пример 3

PRINT "Буква с кодом 70 - это "; CHR$(70)

Этот оператор выдаст на экран текст:

Буква с кодом 70 - это F

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

Пример 4

S$="7 X 8 = " + STR$(7*8)

Этот оператор присваивает символьной переменной S$ значение "7 Х 8 = 56".

VAL(строка)- переводит число из символьного представления в числовое
A=VAL(“123”) →что соответствует A=123

LEN(строка) выдает длину значения символьного выражения.

Пример 5

S$=" Победа ”

PRINT LEN(S$)

Будет напечатано число 9 (пробелы учитываются при подсчете длины так же, как любые другие символы). Длина пустой строки равна нулю.

LEFT$(строка, число) выдает в качестве своего значения начальный отрезок заданной строки, т.е. заданное (вторым аргументом функции - число) количество символов слева.

RIGHT$(строка, число) выдает в качестве своего значения конечный отрезок заданной строки, т.е. заданное (вторым аргументом функции число) количество символов справа.

Пример 6

PRINT LEFT$("ИНФОРМАЦИЯ",7)+RIGHT$("МАТЕМАТИКА",4)

Этот оператор выдаст на экран строку

ИНФОРМАТИКА

MID$ (строка, число1, число2) обобщает две предыдущие и позволяет получить любую подстроку заданной строки. Число1 задает начальную позицию слева подстроки в заданной строке, а число2 - длину подстроки. Если заданная начальная позиция находится за пределами строки или заданная длина неположительна, выдается пустая строка. Если третий аргумент опущен или его значение превосходит количество символов от заданной позиции до конца строки, то выдаются все эти символы.

Пример 7

X$="ПОБЕДА"

FOR I=2 TO 5

PRINT MID$(X$,I,4)

NEXT I

END

Эта программа печатает:

ОБЕД

БЕДА

ЕДА

ДА

 

Hosted by uCoz