Алгоритм. Проектирование сверху вниз. Принцип черного ящика. Структурное программирование
1. Алгоритм
Алгоритм – это конечная последовательность действий, позволяющая по заданным исходным данным получить результат решения задачи.
Алгоритм разбивается на шаги. Для каждого шага есть конкретный исполнитель.
Исполнитель алгоритма может быть человеком или автоматом.
Вид алгоритма зависит от исходных данных.
Результат работы алгоритма с одними и теми же исходными данными не зависит от исполнителя.
2. Алгоритм , характеристики и свойства
Алгоритм имеет две характеристики.
Конечность, или результативность. Алгоритм приводит к получению результата за конечное число шагов..
Однозначность, или определенность. При одинаковых входных данных алгоритм выдает одинаковый результат.
Алгоритм также обладает следующими свойствами.
Массовость, или универсальность. Алгоритм выдает результат при любых однотипных входных данных.
Модульность, или дискретность. Алгоритм можно представить в виде последовательности более элементарных алгоритмов.
3. Проектирование сверху вниз
Основной метод создания алгоритмов — проектирование, или программирование, сверху вниз, или пошаговая детализация.Он заключается в разбиении исходной задачи на последовательность нескольких меньших подзадач. Эти подзадачи, в свою очередь, тоже распадаются на подзадачи и т.д. до тех пор, пока не останутся только элементарные алгоритмы.
При программировании сверху вниз алгоритмы и данные делятся на относительно независимые части, называемые модулями. Некоторые из модулей являются стандартными и поставляются в составе языков программирования, например, вычисление элементарных математических функций квадратный корень, логарифм, синус и т. д.
Главные модули все равно приходится проектировать программистам. Таким образом, алгоритм является деревом модулей:
одни модули вызывают другие модули, начиная с самого верхнего первого модуля, называемого корневым модулем, или головной программой.
При проектировании сколько-нибудь больших алгоритмов невозможно держать в памяти одновременно детали всех модулей алгоритма. Если модуль составлен правильно, то с ним можно обращаться как с черным ящиком.
4. Принцип черного ящика
Принцип черного ящика означает, что не имеет значения, как модуль выполняет свою функцию, какие алгоритмы скрыты у него внутри. Это не важно для остальных модулей алгоритма. Для модулей, которые обращаются к этому модулю, имеет значение только следующее:
1) какова функция модуля, т. е. что он делает;
2) описание входных и выходных данных модуля.
Правильное проектирование алгоритмов позволяет абстрагироваться от внутренней структуры модулей и рассматривать при сборке полного алгоритма только функции модулей.
5. Структурное программирование
Структурное программирование позволяет проектировать алгоритмы только из трех элементарных алгоритмов. Каждый модуль является иерархией этих элементарных алгоритмов. Алгоритм, состоящий только из этих трех элементарных алгоритмов, присутствующих на всех его уровнях, называется структурным.
Основная теорема структурного программирования утверждает, что любой алгоритм можно преобразовать к структурному виду.
Тремя элементарными структурными алгоритмами являются следующие.
1. Следование, или цепочка, или составная инструкция.
2. Выбор, или ветвление, или условная инструкция.
3. Цикл, или возврат, или циклическая инструкция.
6. Компилятор, два способа компиляции
Компилятор — программа-переводчик с языка программирования в машинные коды, а процесс перевода — это компилирование программы. Комплекс программ, включающий компилятор и другие средства написания программ, называется системой программирования.
Возможны два способа компиляции.
Первый способ называется трансляцией и заключается в компилировании сразу всей программы в машинные коды. Затем строится выполняемый файл, содержащий эту программу. И только потом программа выполняется путем запуска выполняемого файла. Благодаря трансляции получается более быстрая по времени работы программа, но выполняемый файл имеет большой объем. Кроме того, выполняемый файл запускается только на компьютере того типа, где программа была транслирована.
Второй способ. При интерпретации компьютер читает программу по одной строке и сразу выполняет эту строку. При интерпретации программу не надо переводить всю сразу в машинные коды, и поэтому она имеет маленький объем, равный объему исходного текста программы. Такая программа запускается на любом компьютере, на котором находится интерпретатор или виртуальная машина.
7. Средства изображения алгоритмов
Средства изображения алгоритмов
v словесный; v формульно-словесный; v блок-схемный;Цикл с постусловием
11. Цикл с предусловиемБезусловный циклический алгоритм (цикл с параметром)
13. Данные в языке С++ Для решения задачи в любой программе выполняется обработка каких-либо данных.… Типы данных в языке C++Операция присваивания
a=b; где a – имя переменной или элемента массива, b – выражение, переменная,…Множественное присваивание
a=b=c=3.14159/6; 16. Операции увеличения (инкремента) и уменьшения (декремента)Ввод с помощью функции scanf
Scanf(s1, s2);
Вывод с помощью функции printf
Printf(s1, s2);
%тип scanf("%f%f",&a,&b); scanf("%f%d«,&c,&d);Вывод с помощью функции cout
cout<<"X="<<X; … cout<<"x="<<x<<"y="<<y<<endl;Цикл с предусловием Оператор while
While (условие) оператор;
While условие
{
Оператор 1;
Оператор 2;
…
Оператор n;
}
29. Оператор do-while
Цикл с постусловием Оператор do-while
Do
{
Оператор;
} while (условие);
30. Оператор for
Оператор for
For(начальные_присваивания ; условие; приращение)
Оператор;
For(начальные_присваивания ; условие; приращение)
{
Оператор 1;
Оператор 2;
…
Оператор n;
}
for (i=in; i<=ik; i=i+di)
Оператор;
for (i=in; i<=ik; i+=di)
Оператор;
31. Найти сумму элементов динамического массива вещественных чисел.
#include "stdafx.h"
#include <iostream.h>
#include <malloc.h>
Int main()
{int i,n;
float *a,s;
cout<<"n=“;cin>>n;
a=(float *) malloc(n*sizeof(float));
cout << "Vvedite massiv A";
for(i=0;i<n;i++)// cin>>a[i];
cin>>*(a+i);
for(s=0,i=0;i<n;i++)//s+=a[i];
s+=*(a+i);
cout << "S="<<s;
Free(a);
32. Поиск максимального элемента и его номера for (max=X[0],nmax=0,i=1;i<n;i++)Int main()
{ float x[20];
Int i,j,n;
cout<<"Massiv xn"; for(i=0; i<n; i++) cin>>x[i]; for(j=1; j<=5; j++)Int main()
{
float b,max,a[20];
Int i,j,n,k,nom;
cout<<"n=";
cin>>n;
cout<<"Massiv an";
for(i=0;i<n;i++)
cin>>a[i];
K=n;
for(j=0;j<=k-2;j++)
{
max=a[0];nom=0;
for(i=1;i<k;i++)
if (a[i]>max)
{ max=a[i];
nom=i; }
b=a[k-1];
a[k-1]=a[nom];
a[nom]=b;
k--; }
cout<<"Massiv an";
for(i=0;i<n;i++)
cout<<"a("<<i<<")="<<a[i]<<"t";
cout<<endl;
return 0; }
35. Сортировка методом пузырька
Int main()
{
float b,max,a[20];
Int i,j,n,k,nom;
cin>>n; cout<<"Massiv an"; for(i=0; i<n; i++)Int main()
{int i,n;
float *a,s;
cout<<"n=“; cin>>n;
a=(float *) malloc(n*sizeof(float));
cout << "Vvedite massiv A";
for(i=0;i<n;i++) // cin>>a[i];
cin>>*(a+i);
for(s=0,i=0;i<n;i++) //s+=a[i];
s+=*(a+i);
cout << "S="<<s;
Free(a);
return 0; }
38. Свойства матриц
Свойства матриц
Ø если номер строки элемента совпадает с номером столбца (i = j), это означает что элемент лежит на главной диагонали матрицы; Ø если номер строки превышает номер столбца (i > j), то элемент… Ø если номер столбца больше номера строки (i < j), то элемент находится выше главной диагонали.Й способ работы с динамическими матрицами.
A=(тип *) calloc(n*m, sizeof(тип)) или A=(тип *) malloc(n*m*sizeof(тип))Й способ работы с динамическими матрицами.
Основан на использовании двойного указателя, указателя на указатель. float **a;
Это указатель на float *, или указатель на массив.
Void main()
Создали массив указателей в количестве n штук на float, каждый элемент массива, является адресом, в котором хранится указатель на float. Осталось… for(i=0;i<n;i++) a[i]=new float(m); ai,j – a[i][j]Gt;0) k--;
cout<<"k="<<k<<endl;
Free(a); return 0;
42. Сформировать вектор P(m), в который записать номера строк максимальных элементов каждого столбца. Задана матрица A(n,m). Сформировать вектор P(m), в который записать номера…Double fun(double x);
int main()
{double a, b, h, x; char s[20];
cout << "Enter the beginning and end of the segment, step-tabulation: ";
cin >> a >> b >> h;
cout << "File name? "; cin >> s;
Ofstream f;
F.open(s);
for (x=a; x<=b; x+=h)
{f.width(10); f << x;
f.width(15); f << fun(x) <<
endl; }
F.close();
system("PAUSE");
return EXIT_SUCCESS;
}
Double fun(double x)
45. Указатели, динамические массивы В Си++ существуют динамические массивы – массивы переменной длины, они… Указатель – переменная, значением которой является адрес памяти, по которому хранится объект определенного типа. При…P2++;
I++;
Операция p1++ увеличивает значение адреса на 8, операция p2++ увеличивает значение адреса на 4, а операция i++ на 2. Операции адресной арифметики выполняются следующим образом:
v операция увеличения приводит к тому, что указатель будет сcлаться на следующий объект базового типа (для p1 – это double, для p2 – float, для i – int);
v операция уменьшения приводит к тому, что указатель, ссылается на предыдущий объект базового типа.
v после операции p1=p1+n, указатель будет передвинут на n объектов базового типа; p1+n как бы адресует n-й элемент массива, если p1 – адрес начала
47. Динамические массивы. Основные понятия
48. Динамические массивы. Порядок основных действий
49. Строки
Строка – последовательность символов. Если в выражении встречается одиночный символ, он должен быть заключен в одинарные кавычки. При использовании в выражениях строка заключается в двойные кавычки. Признаком конца строки является нулевой символ ‘ ’. В СС++ в отличии от других языков программирования отсутствует тип данных строка, строки в Си можно описать с помощью массива символов (массив элементов типа char), в массиве следует предусмотреть место для хранения признака конца строки (' ').
Например, описание строки из 25 символов должно выглядеть так: char s[26];
Здесь элемент s[25] предназначен для хранения символа конца строки.
char s[7]="Привет";
Можно описать и массив строк
char m[3][25]={"Пример ", "использования", " строк"}
Определен массив из 3 строк по 25 байт в каждой.
Для работы можно использовать указатели (char *).Адрес первого символа и будет начальным значением указателя.
50. Структуры
Структура является собранием одного или более объектов(переменных, массивов, указателей, других объектов), которые для удобства работы с ними объединены под одним именем.
Определение структуры состоит из двух шагов:
• объявление структуры (задание нового типа данных определенного пользователем),
• объявление полей.
51. Файлы
Файлом называют способ хранения информации на физическом устройстве. Файл — это понятие, которое применимо ко всему — от файла на диске до терминала.
В C++ отсутствуют операторы для работы с файлами. Все необходимые действия выполняются с помощью функций, включенных в стандартную библиотеку. Они позволяют работать с различными устройствами, такими, как диски, принтер, коммуникационные каналы и т.д. Эти устройства сильно отличаются друг от друга. Однако файловая система преобразует их в единое абстрактное логическое устройство, называемое потоком.
52. Организация работы с файлами
Текстовый поток— это последовательность символов. При передаче символов из потока на экран, часть из них не выводится (например, символ возврата каретки, перевода строки).
Двоичный поток— это последовательность байтов, которые однозначно соответствуют тому, что находится на внешнем устройстве.
Объявление файла
FILE *идентификатор;
Пример
FILE *f;
53. Неформатированные файловый ввод-вывод
Функция возвращает указатель на файловую переменную или NULL при неудачном открытии файла.
Примеры.
f = fopen(s, "wb");
k = fopen("h:ex.dat", "rb");
Запись в файл
fwrite(адрес записываемой величины, размер одного экземпляра, количество записываемых величин, имя логического файла);
fwrite(&dat, sizeof(int), 1, f);
Чтение из файла
fread(&dat, sizeof(int), 1, f); 54. Форматированный файловый ввод-выводFstream
Связь файла с потоком вывода
Ofstream имя логического файла;
Связь файла с потоком ввода
Ifstream имя логического файла;
Открытие файла
Имя логического файла.open(имя физического файла);
Закрытие файла
Имя логического файла.close();
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
Double fun(double x);
int main()
{double a, b, h, x; char s[20];
cout << "Enter the beginning and end of the segment, step-tabulation: ";
cin >> a >> b >> h;
cout << "File name? "; cin >> s;
Ofstream f;
F.open(s);
for (x=a; x<=b; x+=h)
{f.width(10); f << x;
f.width(15); f << fun(x) <<
endl; }
F.close();
system("PAUSE");
return EXIT_SUCCESS;
}
Double fun(double x)
{ return x*cos(x); }
В файле abc.txt хранятся матрицы A(N,M) и B(M,K). Пусть структура файла следующая: в первой строке хранятся числа n и m, затем построчно матрица A, за тем строка, в которой хранится m и k. Затем – построчно матрица B. Найти матрицу С=A.B и записать ее в файл rez.txt.
56. Операции с двоичными файлами
Операции с двоичными файлами
При работе с двоичными файлами в параметре mode должна быть добавлена буква b: «rb+», «wb+».
Ввод-вывод при работе с двоичными файлами осуществляется с помощью функций:
fread (void *ptr, size, n, FILE *filename)
Функция возвращает количество считанных элементов.
Функция fread считывает из файла filename в массив ptr n элементов размера size.
fwrite (const void *ptr, size, n, FILE *filename)
Функция fwrite записывает в файл filename из массива ptr n элементов размера size.
Функция возвращает количество записанных элементов.
Для контроля достижения конца файла есть функция feof.
int feof(FILE * filename)
функция возвращает ненулевое значение, если достигнут конец файла.
57. Решение уравнений вида f(х)=0. Отделение корней
Отделение корней может производиться графически (путем построения графика функции f(x)) или аналитически. Для аналитического отделения корней находят все критические точки функции f(х), т. е. точки, в которых производные равны нулю или не существуют. Это можно сделать численными методами или – в несложных случаях – аналитически. Для этого f(х) дифференцируют, приравнивают производную к нулю и решают полученное уравнение относительно х. Кроме того, определяют все точки, где по тем или иным причинам (например, знаменатель обращается в нуль, под логарифмом появляется нуль и т. д.) производная может не существовать.
В этих (критических) точках или в непосредственной близости от них определяют знак функции f(хi), т. е. находят sign f(хi). Затем строят ряд знаков функции в критических точках, включая в рассмотрение и крайние точки числовой оси -¥ и +¥. Анализируют этот ряд, и по числу смен знаков определяют количество корней (равно числу смен знаков sign f(хi)) и интервалы, где локализованы эти корни. На левой и на правой границах такого интервала функция f(х) должна иметь разные знаки.
Пример. Дано уравнение: 5х–6х–3 = 0. Найти количество корней и интервалы нахождения этих корней.