Презентация на тему Программирование на языке Си

Структурное программирование
на языке Си
Тема 1. Теория
© К.Ю. Поляков, 2007-2009

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

Этапы разработки программ
Разработка модели данных
формальная модель
типы данных (массивы, структуры, …)
взаимосвязь между данными
Разработка алгоритма
выбор существующего или разработка нового
возможен возврат к шагу 2
Разработка программы
Языки: C, C++, Visual Basic, Delphi (Паскаль), `…
Отладка программы (поиск и исправление ошибок)
debug – извлечение жучков (bug), 1945, MAРK-I
отладчик (точки останова, пошаговый режим, просмотр переменных)
профайлер (сколько выполняется каждая из процедур)

Этапы разработки программ
Тестирование программы (проверка на исходных данных, для которых известен результат)
альфа-тестирование: внутри фирмы (тестеры)
бета-тестирование: в других организациях, распространение через Интернет
Разработка документации
справочная система
руководство пользователя (User Manual)
руководство разработчика
Сопровождение (техническая поддержка)
исправление ошибок, найденных заказчиком
обучение и консультирование заказчика
новые версии по льготной цене

Методы проектирования программ
основная
программа
процедуры
1-ого уровня
процедуры
2-ого уровня
снизу вверх
сверху вниз

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

Проектирование «сверху вниз»
метод последовательного уточнения:
начинаем с основной программы;
она разбивается на подзадачи, для каждой из которых пишется процедура-«заглушка»;
реализуем каждую из процедур тем же способом.
меньше вероятность принципиальной ошибки (начали с главного)
проще структура программы
удобно распределять работу в команде
в разных блоках могут быть реализованы похожие операции (можно было решить одной общей процедурой), особенно в команде

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

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

Модуль
Модуль – это программный блок (процедура или функция), отделенный от кода других модулей, который полностью решает самостоятельную задачу своего уровня.
работа модуля не зависит от того, откуда он вызывается, и от того, сколько раз он вызывался до этого
размер модуля не более 50-60 строк (1 страница)
модуль имеет один вход и один выход
модуль начинается с «шапки»-комментария (входные данные, результаты, какие модули использует)
имена переменных – смысловые
в одной строке – один оператор
«трюки» – долой

Оформление текста программы
Шапка – комментарий в начале процедур и функций.
//----------------------------------------
// Sum сумма элементов массива
// Вход: A[] – массив целых чисел
// n - размер массива
// Выход: S = A[0]+A[1]+...+A[n-1]
// Вызывает: -
//----------------------------------------
int Sum ( int A[], float n )
{
...
}

Оформление текста программы
Отступы – тело цикла, условного оператора, оператора выбора и т.п. сдвигается вправо на 2-3 символа.
for(i=0;i
k++;}
for ( i=0; i
{
j=0;
while ( j < i )
{
j++;
k = k % N;
}
k++;
}
легче читать текст программы
видны блоки
просто найти ошибки со скобками (лишняя, не хватает)

Оформление текста программы
«говорящие» имена функций, процедур, переменных: Sum, ShowMenu, count, speed.
пробелы в операторах
выделение пустыми
строками и
комментариями
важных блоков
for(i=0;i
for ( i=0; i
a += 10;
// ввод данных
printf( "Введите число\n" );
scanf ( "%d", &n );
//вычисления
n2 = n*n;
// вывод результата
printf ( "Его квадрат %d", n2 );

Структурное программирование
на языке Си
Тема 2. Проект
© К.Ю. Поляков, 2007-2009

Проект «Графики функций»
построить координатные
оси и сделать их разметку
построить графики
заданных функций (по вариантам)

Проект «Графики функций»
найти точки пересечения
графиков, используя
численные методы
заштриховать
образованную замкнутую
область
x=3,58
y=2,14
x=1,40
y=1,55

Проект «Графики функций»
вычислить площадь этой
области двумя способами
оформить отчет по работе
S1=3,014
S2=3,025

Структура программы
#include
#include
#include
#include
main()
{
initwindow(800,600);
getch();
closegraph();
}
глобальные константы и переменные
процедуры и функции
основная программа

Разбивка программы на этапы
Axes(); // оси координат
Plot(); // графики функций Cross(); // точки пересечения графиков
Hatch(); // штриховка
Area(); // площадь (способ 1)
Area2(); // площадь (способ 2)
Основная программа
Процедуры-заглушки
//------------------------------------
// Axes оси координат
//------------------------------------
void Axes()
{
}

Структурное программирование
на языке Си
Тема 3. Графики функций
© К.Ю. Поляков, 2007-2009

Функции, заданные в явном виде
y = f (x)

Функции, заданные в неявном виде
f (x, y) = 0
пример: уравнение эллипса

полюс
Полярные координаты
А(ρ, ϕ)
ϕ - полярный угол
ρ - полярный радиус
Примеры:
Описание фигур, полученных при вращении объектов.
ρ = f (ϕ)
ρ = R
окружность
ρ = a ∙ϕ
спираль Архимеда
O
O
ρ = a∙sin(2ϕ/3)
«роза»

Полярные координаты
Переход к декартовым координатам

Описание в параметрической форме
t – независимый параметр («время»)
Описание фигур, полученных при сложном движении объектов.
x = f1 (t)
y = f2 (t)
Циклоида – траектория точки на ободе колеса при вращении
R
y
x
0

Системы координат
Математическая
Экранная
Преобразование координат:
X0, Y0 – экранные координаты
точки (0,0)
k – масштаб (во сколько раз растягивается единичный отрезок)

Структура программы
#include
#include
#include
#include
const int X0 = 100, Y0 = 400, // начало координат k = 80; // масштаб
main()
{
initwindow(800, 600);
getch();
closegraph();
}
глобальные переменные
процедуры и функции
основная часть

Перевод в экранные координаты
//-----------------------------------------
// SCREENX – перевод X в координаты экрана
//-----------------------------------------
int ScreenX (float x)
{
return X0+k*x;
}
//-----------------------------------------
// SCREENY – перевод Y в координаты экрана
//-----------------------------------------
int ScreenY (float y)
{
return Y0-k*y;
}

Оси координат
void Axes()
{
line ( X0, 0, X0, 599 );
line ( 0, Y0, 799, Y0 );
}

Разметка оси X («черточки»)
(xЭ, Y0−2)
(xЭ, Y0+2)
Число меток на [0, xmax]:
длина 800 – X0
единичный отрезок k
void Axes()
{
int i, xe;
...
for (i = 1; i <= (800-X0)/k; i++) {
xe = ScreenX(i);
line ( xe, Y0-2, xe, Y0+2 );
}
}
переходим к экранным координатам

Разметка оси X (числа)
1
xЭ
(xЭ, Y0+2)
Вывод символьной строки в графическом режиме:
outtextxy(x, y, s);
void Axes()
{
char s[5];
...
for (i = 1; i <= (800-X0)/k; i++) {
...
sprintf ( s, "%d", i );
outtextxy ( xe-4, Y0+3, s );
}
}
координаты левого верхнего угла
(xЭ-4, Y0+3)
8 на 8
перевести целое число i в строку s
строка:
char s[5];
вывести строку s на экран
с запасом…

Оси с разметкой (полностью)
void Axes()
{
int i, xe, ye;
char s[5];
line ( X0, 0, X0, 599 );
line ( 0, Y0, 799, Y0 );
for (i = 1; i <= (800-X0)/k; i++)
{
xe = ScreenX(i);
line ( xe, Y0-2, xe, Y0+2 );
sprintf ( s, "%d", i );
outtextxy ( xe-4, Y0+3, s );
}
...
}

Задания
«4»: Сделать разметку осей полностью (не только положительной части оси X).
«5»: Сделать задание на «4», использовав только 2 цикла (1 цикл для каждой оси).

Построение графика по точкам
Границы области «видимости»:

Вывод точки с проверкой
//----------------------------------------
// POINT вывод пикселя с проверкой и
// пересчетом координат
//----------------------------------------
void Point ( float x, float y, int color )
{
int xe, ye;
xe = ScreenX(x);
ye = ScreenY(y);
if ( xe >= 0 && xe < 800 &&
ye >= 0 && ye < 600)
putpixel(xe, ye, color);
}
если точка (xЭ, yЭ) в пределах экрана…
координаты в математической системе
цвет точки

Описание функций
//-----------------------------------------
// F1, F2
// Вход: x
// Выход: y = f(x)
//-----------------------------------------
float f1 ( float x )
{
return sqrt(x+1);
}
float f2 ( float x )
{
return 4*sin(x-1);
}

Области определения
//----------------------------------------
// ODZ1 – область определения f1(x)
// Вход: x
// Выход: 1, если x входит в ОДЗ
// 0, если x не входит в ОДЗ
//----------------------------------------
int odz1 ( float x )
{
return ( x >= -1 );
}
не нужно!
if ( x >= -1 ) return 1;
else return 0;

Вывод графика функции
//----------------------------------------
// PLOT вывод графиков функций
//----------------------------------------
void Plot ()
{
float xmin = - 1.* X0 / k,
xmax = (800. - X0) / k;
float x,
h = (xmax - xmin) / 1000;
}
чтобы не отбрасывать остаток
границы видимой части
шаг по x
for ( x = xmin; x <= xmax; x += h)
if ( odz1(x) )
Point(x, f1(x), LIGHTRED);

Общее расположение
float f1 ( float x ) { return sqrt( x + 1 ); }
int odz1 ( float x ) { return x >= -1; }
...
void Point(float x, float y, int color)
{
...
}
...
void Plot()
{
...
for ( x = xmin; x <= xmax; x += h)
if ( odz1(x) )
Point(x, f1(x), LIGHTRED);
}

Задания
«4»: Построить графики в соответствии с заданием.
«5»: Построить графики, соединив точки линиями.

Структурное программирование
на языке Си
Тема 4. Точки пересечения
© К.Ю. Поляков, 2007-2009

Точки пересечения
f1 (x*) = f2 (x*)
a
b
f1 (x*) – f2 (x*) = 0
f (x*) = 0
Пример:
Проблема:
уравнение сложно (или невозможно) решить аналитически
(получить формулу для x*)
Точка пересечения:

Методы решения уравнений
f (x) = 0
Точные (аналитические)
Приближенные
графические
численные
(методы последовательного приближения):
по графику найти интервал [a, b], в котором находится x*
(или одно начальное приближение x0)
по некоторому алгоритму уточнить решение, сужая интервал, в котором находится x*
повторять шаг 2, пока не достигнута требуемая точность:
b – a < ε

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

Метод прямого («тупого») перебора
Задача: найти решение уравнения f (x) = 0 на интервале [a, b] с заданной точностью ε (чтобы найденное решение отличалось от истинного не более, чем на ε).
Алгоритм:
разбить интервал [a, b] на полосы шириной ε
найти полосу [a*, b*], в которой находится x*
решение – a* или b*

Есть ли решение на [a, b]?
есть решение
нет решения
нет решения

Метод дихотомии (деление пополам)
Найти середину отрезка [a,b]: c = (a + b) / 2;
Если f(c)*f(a)<0, сдвинуть правую границу интервала b = c;
Если f(c)*f(a)≥ 0, сдвинуть левую границу интервала a = c;
Повторять шаги 1-3, пока не будет b – a ≤ ε.

Метод дихотомии (деления пополам)
простота
можно получить решение с любой заданной точностью
нужно знать интервал [a, b]
на интервале [a, b] должно быть только одно решение
большое число шагов для достижения высокой точности
только для функций одной переменной

Метод дихотомии (в программе)
//----------------------------------------------
// Solve находит точку пересечения на [a,b]
// Вход: a, b – границы интервала, a < b
// eps - точность решения
// Выход: x – решение уравнения f1(x)=f2(x)
//----------------------------------------------
float Solve ( float a, float b, float eps )
{
float c, fa, fc;
while ( b - a > eps )
{
c = (a + b) / 2;
fa = f1(a) - f2(a);
fc = f1(c) - f2(c);
if ( fa*fc < 0 ) b = c;
else a = c;
}
return (a + b) / 2;
}

Метод дихотомии (в программе)
float xc1, xc2;
...
float Solve ( float a, float b, float eps )
{
...
}
...
void Cross ()
{
char s[20];
sprintf(s, "x=%.2f", xc1);
outtextxy ( 150, 100, s );
sprintf(s, "y=%.2f", f1(xc1));
outtextxy ( 150, 120, s );
...
}
глобальные переменные: абсциссы точек пересечения
найти решение на интервале [1,2] с точностью 0,0001
xc1 = Solve ( 1, 2, 0.0001 );
вывод на экран через символьную строку
… и значение y!
то же самое для остальных точек

Структурное программирование
на языке Си
Тема 5. Штриховка
© К.Ю. Поляков, 2007-2009

Штриховка (две функции)
x
y
xс2
xс1
y = f1 (x)
y = f2 (x)
void Hatch()
{
const int N = 10;
float x, h = (xc2 - xc1) / (N + 1);
int xe, yUp, yDown;
for (x = xc1+h; x < xc2; x += h )
{
xe = ScreenX ( x );
yUp = ScreenY ( f1(x) );
yDown = ScreenY ( f2(x) );
line ( xe, yUp, xe, yDown );
}
}
экранная координата x
экранные координаты границ области по оси y
шаг по x

Штриховка (составная нижняя граница)
x
y
xс3
xс1
xс2
N линий
y = f1 (x)
y = f2 (x)
y = f3 (x)
//----------------------------
// Down нижняя граница области
//----------------------------
float Down ( float x )
{
if ( x < xc2 )
return f2(x);
else return f3(x);
}

Штриховка (общий случай)
float Up ( float x ) { ... }
float Down ( float x ) { ... }
...
void Hatch()
{
const N = 10;
float x, h = ( ? ) / (N + 1);
int xe, yUp, yDown;
for ( ? ; x += h )
{
xe = ScreenX ( x );
yUp = ScreenY ( ? );
yDown = ScreenY ( ? );
line ( xe, yUp, xe, yDown );
}
}
xc3 - xc1
x = xc1+h; x < xc3;
Up(x)
Down(x)

Структурное программирование
на языке Си
Тема 6. Вычисление площади
© К.Ю. Поляков, 2007-2009

Метод (левых) прямоугольников
y = f1 (x)
y = f2 (x)
S1
S2
S3
S4
void Area()
{
float x, S = 0, h=0.001;
char out[20];
for ( x = xc1; x < xc2; x += h)
S += h*(f1(x) – f2(x));
sprintf ( out, "S=%7.3f", S );
outtextxy ( 300, 300, out );
}
for ( x = xc1; x < xc2; x += h )
S += f1(x) – f2(x);
S *= h;

Метод (правых) прямоугольников
x
y
xс2
xс1
y = f1 (x)
y = f2 (x)
S1
S2
S3
S4
void Area()
{
float x, S = 0, h=0.001;
char out[20];
for ( x = xc1; x < xc2; x += h)
S += h*(f1(x+h) – f2(x+h));
sprintf ( out, "S=%7.3f", S );
outtextxy ( 300, 300, out );
}
for ( x = xc1; x < xc2; x += h )
S += f1(x+h) – f2(x+h);
S *= h;

Метод (средних) прямоугольников
x
y
xс2
xс1
y = f1 (x)
y = f2 (x)
S1
S2
S3
S4
void Area()
{
float x, S = 0, h=0.001;
char out[20];
for ( x = xc1; x < xc2; x += h)
S += h*(f1(x+h) – f2(x+h));
sprintf ( out, "S=%7.3f", S );
outtextxy ( 300, 300, out );
}
for ( x = xc1; x < xc2; x += h )
S += f1(x+h/2) – f2(x+h/2);
S *= h;
левые (правые):
средние

Метод трапеций
x
y
xс2
xс1
y = f1 (x)
y = f2 (x)
for ( x = xc1; x < xc2; x += h )
S += f1(x) – f2(x) +
f1(x+h) – f2(x+h);
S *= h/2;
S =( f1(xc1) - f2(xc1)
+ f1(xc2) - f2(xc2) )/2.;
for ( x = xc1+h; x < xc2; x += h )
S += f1(x) – f2(x);
S *= h;

Метод Монте-Карло
Применение: вычисление площадей сложных фигур (трудно применить другие методы).
Требования: необходимо уметь достаточно просто определять, попала ли точка (x, y) внутрь фигуры.
Пример: заданы 100 кругов (координаты центра, радиусы), которые могу пересекаться. Найти площадь области, перекрытой кругами.

Метод Монте-Карло
Вписываем сложную фигуру в другую фигуру, для которой легко вычислить площадь (прямоугольник, круг, …).
Равномерно N точек со случайными координатами внутри прямоугольника.
Подсчитываем количество точек, попавших на фигуру: M.
4. Вычисляем площадь:
Всего N точек
На фигуре M точек
Метод приближенный.
Распределение должно быть равномерным.
Чем больше точек, тем точнее.
Точность ограничена датчиком случайных чисел.
!

Случайное число в заданном интервале
//-----------------------------------------
// randF – случайное вещественное число
// в заданном интервале
//-----------------------------------------
float randF ( float a, float b)
{
return (b-a)*rand() / RAND_MAX + a;
}
rand()
rand()/RAND_MAX
1.*rand()/RAND_MAX
1.*rand()/RAND_MAX + a
(b-a)*rand()/RAND_MAX + a
целое [0, RAND_MAX]
всегда 0!!!
[0,1]
[a,a+1]
[a,b]

Проверка точки (внутри или нет?)
//-----------------------------------------
// Inside – определяет, находится ли точка
// внутри фигуры
// Вход: x, y – координаты точки
// Выход: 1, если точка внутри фигуры,
// 0, если точка вне фигуры
//-----------------------------------------
int Inside ( float x, float y )
{
if ( Down(x) <= y && y <= Up(x) )
return 1;
else return 0;
}
int Inside ( float x, float y )
{
return (Down(x) <= y && y <= Up(x));
}

Метод Монте-Карло (реализация)
//----------------------------------------------------
// Area2 – вычисление площади методом Монте-Карло
//----------------------------------------------------
void Area2 ()
{
int i, N = 200000, M = 0;
float
float x, y, S;
char out[20];
for (i=1; i<=N; i++)
{
x = randF ( x1, x2 );
y = randF ( y1, y2 );
if ( Inside(x,y) ) M++;
}
S = (x2-x1)*(y2-y1)*M/N;
sprintf(out, "S=%7.3f", S);
outtextxy(300, 320, out);
}
x1 = xc1, x2 = xc2, y1 = 1, y2 = 4;
границы прямоугольника (у каждого свои!)
S = (x2-x1)*(y2-y1)*M/N;
вычисление площади
если на фигуре, увеличить счетчик

Структурное программирование
на языке Си
Тема 7. Оформление отчета
© К.Ю. Поляков, 2007-2009

Титульный лист

Графики функций
«скриншот» (screenshot) – «снимок» экрана
через Редактор формул (Вставка – Объект – Microsoft Equation)

Как получить копию экрана?
Поменять цвета так, чтобы все линии и текст были белые.
Запустить программу (она должна все нарисовать).
Нажать клавишу PrtScr (Print Screen – «снимок» экрана) на клавиатуре или комбинацию Alt+PrtScr («снимок» активного окна).
В графическом редакторе (Paint): Правка – Вставить.
Перевести в черно-белую палитру (Рисунок – Атрибуты – Палитра – Черно-белая).
Инверсия (черный ↔ белый), Рисунок – Обратить цвета.
Выделить нужную часть рисунка.
Вставить в отчет через буфер обмена (Ctrl+C, Ctrl+V).

Структура программы

Текст программы
шрифт Courier New,
(моноширинный)
размер 10 пт