- •Тема 1. Основные этапы решения задач на эвм 5
- •Тема 2. Жизненный цикл программы. Критерии качества программы. 15
- •Тема 3. Схемы алгоритмов, данных, программ 29
- •Тема 1. Основные этапы решения задач на эвм Постановка задачи разработки программного обеспечения
- •Анализ формальной постановки задачи
- •Выбор или разработка математической модели и метода решения
- •Разработка алгоритма
- •Базовые структуры алгоритма
- •3.2. Цикл с постусловием.
- •Тема 2. Жизненный цикл программы. Критерии качества программы.
- •Техническое задание и спецификация программы
- •Разработка проекта программной системы
- •Программирование (кодирование) или программная реализация алгоритмов
- •Тестирование и отладка
- •Эксплуатация и сопровождение
- •Критерии качества программного обеспечения
- •Тема 3. Схемы алгоритмов, данных, программ
- •Символы данных
- •Отображает данные, вводимые в ручную, во время обработки с устройств любого типа (клавиатура, переключатели, кнопки, световое перо, полоски со штрих кодом и т.Д.).
- •Символы процесса
- •Символы линий
- •Специальные символы
- •Правила применения символов в схемах
- •Правила выполнения соединений
- •Специальные условные обозначения
- •Тема 4. Язык программирования высокого уровня Си Общие сведения о языке Си
- •Алфавит языка Си
- •Грамматика для описания языка, синтаксические диаграммы
- •Структура программы на языке Си
- •Void main() //функция main
- •Имена объектов в программе
- •Выражения, операции и приоритеты
- •Тема 5. Стандартные типы данных
- •Тема 6. Составные типы данных Данные регулярного типа (массивы)
- •Int b [n]; // вектор из 10 целых элементов
- •9 Strcpy(s1,&s2[k]); //копирует правую подстроку из s2 в s1
- •9 Strncpy(s1,&s[2],n); //копирует среднюю подстроку из s2 в s1
- •Void main() /*пример функции*/
- •If(strcmp(s, "пароль"))
- •If(!strсmp("quit", s)) break;
- •Данные комбинированного типа (структуры)
- •Int month;
- •Int year;
- •Перечисления
- •Объединения
- •Указатели
- •Void *addres;
- •Int arrey[25];
- •Тема 7. Представление основных управляющих структур программирования Оператор присваивания
- •Составной оператор
- •Оператор перехода Goto
- •Условный оператор If
- •Оператор выбора switch
- •Операторы цикла while, do – while, for
- •Int I,j,imax,jmax,imin,jmin;
- •Операторы прерывания циклов
- •If (!flag) printf("Отрицательных чисел нет"); Форматированный ввод данных
- •Форматированный вывод данных
- •Преобразование типов
- •Инициализация данных
- •Тема 8. Функции
- •Определение функций в языке Си
- •Int rus (unsigned char r)
- •Void change (int X, int y)
- •Void change (int *X, int *y)
- •Вызов функций в языке Си
- •Int *fun (intx,int *y);
- •Int main()
- •Рекурсивные функции
- •Int nodWhile (int m, int n)
- •Int nodWhile (int m, int n)
- •Int main()
- •Int fCalculated[nFib];
- •Int FibDinam (int n)
- •Int main()
- •Int Summa(int n, int a[100])
- •Int main()
- •Тема 9. Файлы
- •Int fseek(file *fp, long count, int access);
- •Int ferror(file *fp);
- •Int remove(char *file_name);
- •Void rewind(file *fp);
- •Int main()
- •Тема 10. Приемы программирования. Примеры алгоритмов Алгоритмы сортировки
- •Исходный массив
- •Void SortBubble (int count, int* pArr)
- •Исходный массив
- •Void SortSelect(int count, int* pArr)
- •Int i1,temp;
- •Int jmax;
- •Void SortInsert (int count, int* pArr)
- •Int temp, j;
- •Алгоритмы поиска
- •Int bfSearch(char *s, char *p)
- •Int bmtarr[255];
- •Int bmSearch(int startpos, char *s, char *p)
- •Int BinarySearch (int lb, int ub, int key, int* pArr)
- •Динамические структуры данных
- •Линейные списки
- •Int value; // значение элемента
- •Void PrintSearchList (list head, int val)
- •If (lfound) printf("Элемент в списке найден!");
- •Стек, очередь, дек
- •Int prior(char);
- •Void main(void)
- •Int k, point;
- •Int prior(char a)
- •Деревья
- •Int info; //информационное поле
- •Приложение 1. Стандартные библиотеки языка Си
- •Приложение 2. Примеры реализации алгоритмов
- •Int main()
- •Int arr[10]; // Массив arr из 10 целочисленных элементов
- •Int I; // Счетчик для циклов
- •Int main()
- •Int main()
- •Int main()
- •Int Temp;
- •Int CurrentYear, Diff, Day1, Day2, Month1, Month2, I, Visokos;
- •Int main()
- •InsertSort(d, max); // Сортируем массив b методом вставок
- •Int number;
- •Int main()
- •Не рекурсивный алгоритм решения задачи Ханойская башня.
- •Int main()
- •Рекурсивный алгоритм решения задачи Ханойская башня.
- •Void move(int I, int j, int d)
- •Void hanoy(int I, int j, int k, int d)
- •Int main()
- •Int Cubic(double *X,double a,double b,double c);
- •Int Cubic (double *X, double a, double b, double c)
- •Void lu_backsub (double **a, int n, int *indx, double *b)
- •Void lu_invert (double **a, int n, int *indx, double **inv, double *col)
- •Int BracketRoot (double x0, double *a, double *b, double d0, double di, double dmax, double (*fun)(double));
- •Int BracketRoot (double x0, double *a, double *b, double d0,
- •Int main()
- •Int expo, I;
- •If (expo & 1)
- •Int main()
- •Приложение 3. Лабораторные работы Лабораторная работа №1
- •Лабораторная работа №2
- •Лабораторная работа №3
- •Лабораторная работа №4
- •Лабораторная работа №5
- •Лабораторная работа №6
- •Лабораторная работа №7
- •Лабораторная работа №8
- •Лабораторная работа №9
- •Лабораторная работа №10
- •Лабораторная работа №11
- •Лабораторная работа №12
- •Список литературы
Базовые структуры алгоритма
Большинство алгоритмов содержит действия по присваиванию некоторой переменной значения другой переменной или значения некоторого выражения. Обычно для операции присваивания используется специальное обозначение «:=» или «←». Операция присваивания выполняется справа налево, т.е. сначала вычисляется значение выражения в правой части операции присваивания, а затем полученное значение присваивается переменной, стоящей в левой части операции присваивания. Слева от знака присваивания всегда должна стоять переменная, которой присваивается значение выражения, стоящего справа: «переменная» := «выражение». В частном случае слева и справа от знака присваивания может стоять одна и та же переменная. Например, если оператор присваивания имеет вид х := х+h (см.пример 2), и до его выполнения х, h имеют значения соответственно 6 и 0.5, то после его выполнения h остаётся неизменным, а х будет иметь значение 6.5. Операции присваивания в схемах алгоритмов записываются как правило внутри блоков «процесс» (см.далее).
Основные блоки, используемые в блок-схемах алгоритмов, приведены в Таблице 1.
Таблица 1.
Основные структурные блоки
Символ |
Название |
Назначение |
Терминатор или пуск-останов (начало-конец) |
Обозначает начало или конец алгоритма |
|
Ввод-вывод |
Преобразует данные в форму, пригодную для ввода или вывода информации |
|
Решение или проверка условия |
Выбор направления алгоритма в зависимости от некоторых условий |
|
Процесс (обработка) |
Выполнение определенной операции или группы операций |
|
Комментарий |
Сопровождает блок для более детального его описания, если оно не поместилось внутри символа |
|
Символ-соединитель |
Используется для обрыва линии и продолжения ее в другом месте. |
Блоки ввода-вывода информации и обработки (выполнения действий) имеют один вход и один выход, блок начала имеет один только выход, а блок конца работы – только вход. Блок решения (условия) имеет один вход и два выхода, один из которых помечен словом “да“ (или 1, или «+» – соответствует переходу при выполнении условия), а второй - словом “нет“ (или 0, или «–»). Последовательность прохождения блоков (передачи управления) определяется стрелками и начинается с блока начала работы. Если направление передачи управления совпадает с естественным (слева-направо, сверху-вниз), то стрелка на дуге, соединяющей смежные блоки, может не ставиться.
Если в пределах страницы на схеме неудобно проводить линию передачи управления, то её можно прервать на выходе передающего блока, поставить в точке разрыва кружок с уникальной для этой страницы буквой (именем) внутри, а перед входом принимающего блока поставить кружок с той же буквой и тем самым соединить их. Таким образом, символ-соединитель имеет один вход в месте разрыва и один выход в месте соединения. Он отображает выход в часть схемы и вход из другой части схемы. Для каждой «оборванной» линии внутри символа-соединителя должно содержаться одно и то же уникальное обозначение.
Для решения прикладной задачи всегда можно составить несколько разных алгоритмов. Из этих возможных алгоритмов нужно выбрать самый хороший для дальнейшей программной реализации. Чтобы оценить насколько «хорош» алгоритм, анализируются следующие характеристики: простота и легкость понимания алгоритма, скорость выполнения и требуемый объём памяти. Наиболее важными в настоящее время являются простота и легкость понимания. Причина этого – большое количество создаваемых алгоритмов и программ, необходимость обмена алгоритмами и программами между людьми, предприятиями, организациями и государствами. Для того чтобы алгоритм был простым и легко понимаемым, его рекомендуется строить, используя 3 основных структуры:
1. Последовательность (последовательное соединение).
Выполняется несколько последовательных команд (операторов). На рис.2 они обозначаются буквами А и В.
Рис.2.
Последовательность действий
2. Условие (проверка условия).
-
Условие с двумя вариантами действий. Если истинно условие, то выполняется блок (оператор) А, иначе выполняется блок В (оператор В) (рис.3).
Рис.3.Условие
с двумя вариантами действий
2.2. Условие с одним вариантом действий. Если истинно условие, то выполняется блок (оператор) А, иначе ничего не выполняется и управление передается следующему оператору (рис.4).
3. Цикл (циклическое повторение).
3.1. Цикл с предусловием.
В начале цикла проверяется условие и после этого циклически выполняется некоторое действие А (блок операторов) до тех пор, пока условие все еще верно (истинно). Как только условие становится ложным, цикл завершается (рис.5).
На
алгоритмическом языке На языке
программирования Си Паскаль Начало цикла пока Условие
выполнять A;
Конец цикла while (Условие)
{ A; }
while
Условие do
begin A
end;