Алгоритм. Основные свойства алгоритмов. Описание алгоритмов

Алгоритм. Основные свойства алгоритмов. Описание алгоритмов

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

Алгоритм: задача шаг шаг результат

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

1.Массовость. Алгоритм обладает свойством массовости, если он может быть применён для решения задачи с различными исходными данными.

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

3. Однозначность (определённость). При выполнении одинаковых исходных данных получается одинаковый результат.

4. Эффективность (оптимальность).

Критерии оптимальности:

- время выполнения;

- требующийся объём памяти.

Описание алгоритма

Естественный язык с Описание алгоритма Специализированные

использованием мат. с помощью блок- схемы языки

формул

-текст Блок-схема

-последовательность Начало

шагов Условие

Ввод, вывод

Операторный блок

Конец

Блок передачи

Вызов функции

Комментарий

Стрелки (направление)

Размеры:

-высота блоков Начало и Конец в 2 раза меньше, чем основные блоки;

-все блоки должны иметь одинаковую ширину;

-высота основного блока – половина ширины;

-все блоки должны иметь одинаковые размеры.

Понятие о структурном программировании

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

Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:

последовательное исполнение — однократное выполнение операций в том порядке, в котором они записаны в тексте программы;

ветвление — однократное выполнение одной из двух или более операций, в зависимости от выполнения некоторого заданного условия;

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

Повторяющиеся фрагменты программы могут оформиться в виде подпрограммы.

Разработка программы ведётся пошагово, методом сверху вниз.

Достоинства структурного программирования:

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

-сильно упрощается процесс тестирования и отладки программы;

-структурированная программа является хорошим описанием блок-схемы.

Порядок выполнения программ на языке C

-построение блок-схемы

-написание кода

-проверка/компиляция

-запуск

Пример программы

#include <stdio.h>

#include <conio.h>

main()

{

int a, b, c; // объявление переменных

printf ( "Введите два целых числа \n" ); // подсказка для ввода

scanf ( "%d%d", &a, &b ); // ввод данных

c = a + b; // вычисления (оператор присваивания)

printf ( "Результат: %d + %d = %d \n", a, b, c ); // вывод результата

getch(); Задержка до нажатия любой клавиши выполняется функцией getch().

}

.

Условный операторы.

Оператор IF - ELSE используется при необходимости сде-

лать выбор. Формально синтаксис имеет вид

IF (выражение)

оператор-1

ELSE

оператор-2,

Где часть ELSE является необязательной. Сначала вычисля-

ется выражение; если оно "истинно" /т.е. значение выражения

отлично от нуля/, то выполняется оператор-1. Если оно ложно

/значение выражения равно нулю/, и если есть часть с ELSE,

то вместо оператора-1 выполняется оператор-2.

Позволяют организовать ветвления в программе

If – else позволяет выбрать один оператор или группу операторов из двух

If позволяет выполнить оператор или группу операторов или пропустить

If(x>3)

y=2

ELSE свя-

зывается с ближайшим предыдущим IF, не содержащим ELSE.

Например, в

IF ( N > 0 )

IF( A > B )

Z = A;

ELSE

Z = B;

Оператор switch

Если надо выбрать один из нескольких вариантов в зависимости от значения некоторой

целой или символьной переменной, можно использовать несколько вложенных операторов if,

но значительно удобнее использовать специальный оператор switch

Оператор множественного выбора switchсостоит из заголовка и тела оператора, заклю-

ченного в фигурные скобки.

В заголовке после ключевого слова switchв круглых скобках записано имя переменной

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

жду несколькими вариантами.

Каждому варианту соответствует метка case, после которой стоит одно из возможных

значений этой переменной и двоеточие; если значение переменной совпадает с одной из

меток, то программа переходит на эту метку и выполняет все последующие операторы. Оператор breakслужит для выхода из тела оператора switch.

Если значение переменной не совпадает ни с одной из меток, программа переходит на

метку default(по умолчанию, то есть если ничего другого не указано). Можно ставить две метки на один оператор, например, чтобы программа реагировала как

на большие, так и на маленькие буквы, надо в теле оператора switchнаписать так:

case 'а':

case 'А':

printf("\nАнтилопа"); break;

case 'б':

case 'Б':

printf("\nБарсук"); break;

и так далее

scanf("%c", &c); // ввести букву

switch ( c ) // заголовок оператора выбора

{

case 'а': printf("\nАнтилопа"); break;

case 'б': printf("\nБарсук"); break;

case 'в': printf("\nВолк"); break;

default: printf("\nНе знаю я таких!"); // по умолчанию

}

Оператор цикла while

Очень часто заранее невозможно сказать, сколько раз надо выполнить какую-то опера-

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

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

Цикл whileиспользуется тогда, когда количество повторений цикла заранее неизвестно

и не может быть вычислено.

• Цикл whileсостоит из заголовка и тела цикла.

• В заголовке после слова whileв круглых скобках записывается условие, при котором

цикл продолжает выполняться. Когда это условие нарушается (становится ложно), цикл

заканчивается.

Если условие неверно в самом начале, то цикл не выполняется ни разу (это цикл с преду-

словием).

• Если условие никогда не становится ложным (неверным), то цикл никогда не заканчива-

ется; в таком

// выводим числа от 0 до 4:

int i = 0;

while( i < 5 )

{

printf( "%d ", i );

i++;

}

Оператор цикла do-while

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

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

Для этого используется цикл с постусловием(то есть условие проверяется не в начале, а в

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

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

Цикл состоит из заголовка do, тела цикла и завершающего условия.

• Условие записывается в круглых скобках после слова while, цикл продолжает выпол-

няться, пока условие верно; когда условие становится неверно, цикл заканчивается.

• Условие проверяется только в конце очередного шага цикла (это цикл с постусловием),

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

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

ния очередного шага цикла. Для этого используют специальный оператор break. Можно также

сказать компьютеру, что надо завершить текущий шаг цикла и сразу перейти к новому шагу (не

выходя из цикла) — для этого применяют оператор continue.

do { // начало цикла

printf ( "\nВведите натуральное число:" );

scanf ( "%d", &N );

}

while ( N <= 0 ); // условие цикла «пока N <= 0»

Оператор цикла for

Цикл forиспользуется тогда, когда количество повторений цикла заранее известно или

может быть вычислено.

• Цикл forсостоит из заголовка и тела цикла.

• В заголовке после слова forв круглых скобках записываются через точку с запятой три

выражения:

o начальные значения: операторы присваивания, которые выполняются один раз перед

выполнением цикла;

o условие, при котором выполняется следующий шаг цикла; если условие неверно,

работа цикла заканчивается; если оно неверно в самом начале, цикл не выполняется ни

одного раза (говорят, что это цикл с предусловием, то есть условие проверяется перед

выполнением цикла);

действия в конце каждого шагацикла (в большинстве случаев это операторы при-

сваивания).

for ( i = 1; i <= N; i ++) // цикл: для всех i от 1 до N

{

printf ( "Квадрат числа %d равен %d\n", i, i*i);

}

Пример бесконечного цикла:

FOR (;;) {

...

}

является бесконечным циклом, о котором предполагается, что

он будет прерван другими средствами (такими как BREAK или

RETURN).

Вложенные циклы

for( выражение1; выражение2; выражение3 )

for( выражение4; выражение5; выражение6 )

оператор;

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

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

Пример(Ввод b вывод матрицы)

for(i=0;i<n;i++) //ввод

for(j=0;j<n;j++)

{

printf("Введите массив a[%d][%d]",i,j);

scanf("%d",&a[i][j]);

}

for(i=0;i<n;i++) //вывод

{

for(j=0;j<n;j++)

printf("%d ",a[i][j]);

printf("\n");

}

Одномерный массив.

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

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

задается константой вот так:

int a[5];

Элементы массива запоминаются в памяти последовательно.

a[0]

a[1]

. . .

a[4]

Свойства одномерного массива:

-один и тот же тип

-все элементы в памяти располагаются друг за другом

-индекс первого элемента - 0

-имя массива определяет адрес начала массива (адрес первого элемента - const).

Реализация ввода элементов массива:

int a[5], i;

for( i=0; i<5; i++ )

{

printf( "\n эл-т %d: ", i );

scanf( "%d", &a[i] );

}

Инициализация массива при описании:

int x[4] = { 5, 2, 1, 8 };

// размерность можно не указывать:

int x[ ] = { 5, 2, 1, 8, 9, 75 };

int A[4] = { 2 }; // последние три элементы равны 0

Двумерные массивы

Имя двумерного массива является указателем константы на массив указателей констант.

int x[3][4]

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

int [i][j]

Первый индекс – номер строки, второй индекс – номер столбца. Количество байт памяти, которое необходимо для хранения массива, вычисляется по формуле

Колич. байт = <размер типа данных>*<колич. строк>*<колич. столбцов>

В памяти компьютера массив располагается непрерывно по строкам, т.е. а[0][0], a[0][1], a[0][2], a[1][0].

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

#include <stdio.h>

const int n = 10;

int main(void)

{

int i, j, a[n][n];

for ( i = 0; i < n; i ++ )

for ( j = 0; j < n; j ++ )

{ // цикл по всем элементам

printf("Введите a[%d][%d] ", i ); // подсказка для ввода A[i]

scanf ("%d", &a[i][j]); // ввод A[i]

}

for ( i = 0; i < n; i ++ )

{

for ( j = 0; j < n; j ++ )

printf(“%d”, a[i][j])

printf(“\n”);

}

}

Метод пузырька

Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно, то

меняем их местами. Далее так же рассматриваем следующую пару элементов и т.д. Когда мы обработали пару (A[0], A[1]), минимальный элемент стоит на месте A[0]. Это значит, что на следующих этапах его можно не рассматривать.

Сделав N-1проходов, мы установим на место элементы с A[0]по A[N-2]. Это значит, что последний элемент, A[N-1], уже тоже стоит на своем месте (другого у него нет).

#include <stdio.h>

const int N = 10;

main()

{

int i, j, A[N], c;

// здесь надо ввести массив A

for ( i = 0; i < N-1; i ++ ) // достаточно поставить N-1 элементов

for ( j = N-2; j >= i; j - - ) // идем с конца массива в начало

if ( A[j] > A[j+1] ) // если они стоят неправильно, ...

{

c = A[j]; A[j] = A[j+1]; // переставить A[j] и A[j+1]

A[j+1] = c;

}

printf("\n Отсортированный массив:\n");

for ( i = 0; i < N; i ++ )

printf("%d ", A[i]);

}

Операции над указателями

· присваивание

· операция сравнения, сложения, вычитания.

Можно сравнивать указатели одинакового типа. Важной особенностью арифметических операций с указателями является то, что физическое увеличение или уменьшение значения указателя зависит от его типа.(*p++ увеличится на 4)

Строки символов

- строки – константы.

- массивы char

-указатели на char

- Массивы строк

Функции для строк

Для работы со строковыми функциями типа strcpy() нужно включить заголовочный файл STRING.H с помощью следующей строки:

#include <string.h>

1) strlen( строка )

эта функция вернет длину строки в символах (без нулевого байта). таким образом, strlen("hello") вернет 5.

2) strcpy( destination, source )

Оператор присваивания для строк не определен. Если c1 и c2 - символьные массивы, вы не сможете скопировать один в другой так:

c1 = c2; // так нельзя

Чтобы скопировать одну строку в другую, вместо использования оператора присваивания вызовите функцию копирования строк strcpy().

strcpy(c1,c2); // четкий и верный годный вариант

Оператор копирует символы, адресуемые указателем c2, в память, адресуемую указателем c1, включая нулевые байты.

Тесты. Отладка программ

Отладка это устранение ошибок.

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

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

Алгоритм. Основные свойства алгоритмов. Описание алгоритмов

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

Алгоритм: задача шаг шаг результат

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

1.Массовость. Алгоритм обладает свойством массовости, если он может быть применён для решения задачи с различными исходными данными.

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

3. Однозначность (определённость). При выполнении одинаковых исходных данных получается одинаковый результат.

4. Эффективность (оптимальность).

Критерии оптимальности:

- время выполнения;

- требующийся объём памяти.

Описание алгоритма

Естественный язык с Описание алгоритма Специализированные

использованием мат. с помощью блок- схемы языки

формул

-текст Блок-схема

-последовательность Начало

шагов Условие

Ввод, вывод

Операторный блок

Конец

Блок передачи

Вызов функции

Комментарий

Стрелки (направление)

Размеры:

-высота блоков Начало и Конец в 2 раза меньше, чем основные блоки;

-все блоки должны иметь одинаковую ширину;

-высота основного блока – половина ширины;

-все блоки должны иметь одинаковые размеры.