Алгоритмизация и программирование. Лекция 2

1.

Федеральное государственное автономное образовательное учреждение высшего
образования «Крымский федеральный университет имени В.И. Вернадского»
физико-технический институт
алгоритмизация программирование
© Полетаев Дмитрий Александрович, кандидат
физико-математических
наук,
доцент
кафедры
радиофизики и электроники физико-технического
института Крымского федерального университета имени
В.И.
Вернадского
руководитель
студенческого
конструкторского бюро
e-mail: poletaevda@cfuv.ru
https://vk.com/dmltry

2.

краткая история и особенности
языка си
•разработан Dennis Ritchie в bell labs (с 1969 по
1973)
•первое применение – портирование ос unix на
компьютерную систему PDP-11
достоинства:
•переносимость
•минимализм
•прямой доступ к памяти
•эффективность
2

3.

cведения, необходимые для написания
программы:
структура программы
типы и структуры данных, имеющиеся в алгоритмическом
языке, их описание, допустимые операции
операторы преобразования данных: присваивания, операторы
ввода и вывода.
правила записи алгоритма - программирование основных
алгоритмических структур
язык программирования – инструмент
для решения задач!!!
3

4.

4
структура простейшей программы на
любом алгоритмическом языке
заголовок
ограничитель
описания – неисполняемые
инструкции языка
операторы – исполняемые
инструкции языка
ограничитель

5.

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

6.

6
алфавит языка си
•латинские буквы: A–Z, a–z
•цифры: 0−9
•символ пробела
•управляющие символы: табуляции,
перевод страницы, новая строка, возврат
•каретки
•29 символов, таких как + − , “ / ? и др.

7.

7
комментарии в си
в любом месте программы, там, где
может стоять пробел, допускается
запись комментария:
/*не скупитесь писать комментарии к
программам!!!*/
//подумайте о своих товарищах,
//которым эти программы разбирать!!!

8.

8
переменные в си
•имена переменных состоят из латинских
букв, цифр и знака подчеркивания (_),
первый символ не может быть цифрой
•имена переменных не могут совпадать с
зарезервированными словами (void, int и др.)
•переменные регистрозависимые, т.е. A и a –
разные переменные
•желательно, но необязательно, чтобы
переменные имени осмысленные названия

9.

9
основные типы переменных в си
БАЗОВЫЕ ТИПЫ:
int – целый
float – вещественный одинарной точности
double – вещественный двойной точности
char – символьный
КВАЛИФИКАТОРЫ:
short – короткий
long – длинный
signed – со знаком
unsigned – без знака

10.

целые типы
10
тип данных
размер,
байт
2
unsigned int, unsigned,
unsigned short int
int, signed int, short int,
short
unsigned long
long, long int
unsigned char
char, signed char
диапазон значений
0...65535
2
-32768...32767
4
4
1
1
0...4294967295
-2147483648...2147483647
0...255
-128...127
?
зачем такое количество
разных переменных???
вещественные типы
тип данных
размер,
байты
диапазон
порядка
число цифр
мантиссы
float
4
-38...+38
7
double
8
-308...+308
15
long double
10
-4932...+4932
19

11.

11
описание переменных в си
тип список_имен_переменных;
тип имя1, имя2,…,имяi,…, имяN;
тип имя=значение /*инициализация переменной*/
Пример:
float a, b=1.5, _b=0.5, b1; int n=10,i=0, j, ik=1;

12.

переменные char в си
12
переменная типа char может быть целочисленной и символьной (символы из
таблицы ascii)

13.

13
описание констант в си
константы в си — это фиксированные значения, которые не
могут изменяться программой
они могут быть таких же типов, как и переменные
Пример:
const float a=1.0;
const float b=1.5;
const float _b=0.5;
const int n=10;
?
зачем константы, если
можно те же самые
величины задать
переменными???

14.

преобразование данных в си
int a=1;
double b=0;
b=a;
double c=b;
=
int a=0;
double b=1.5;
a=b;
int a=1;
double c=0;
c=(double) a;
?
что тут не так???
14

15.

тема «ввод-вывод» функция printf () в си
15
int printf(const char *format, список аргументов для
подстановки);
для различных типов необходимо использовать
различные спецификации преобразования:
%d – для вывода целых чисел;
%c – для вывода символа;
%f – для вывода вещественного числа в виде целой и дробной части;
(для переменной типа double применяется модификатор типа %lf)
%e – для вывода вещественного числа в виде мантиссы и порядка;
%g – для вывода вещественного числа в виде %f или %e в зависимости от
значения числа;
%u – для вывода беззнакового целого числа в десятичной системе
счисления;
%o – для вывода беззнакового целого числа в восьмеричной системе
счисления;
%x – для вывода беззнакового целого числа в шестнадцатеричной системе
счисления;
%s – для вывода символьной строки.

16.

тема «ввод-вывод» функция scanf () в си
int scanf(const char *format, arg-list);
для различных типов необходимо использовать
различные спецификации преобразования:
%d – для ввода целых чисел;
%c – для ввода символа;
%f – для ввода вещественного числа в виде целой и дробной части;
(для переменной типа double применяется модификатор типа %lf)
%e – для ввода вещественного числа в виде мантиссы и порядка;
%g – для ввода вещественного числа в виде %f или %e в зависимости от
значения числа;
%u – для ввода беззнакового целого числа в десятичной системе
счисления;
%o – для ввода беззнакового целого числа в восьмеричной системе
счисления;
%x – для ввода беззнакового целого числа в шестнадцатеричной системе
счисления;
%s – для ввода символьной строки.
16

17.

тема «операторы» в си
17
операторы выполняют различные действия для различных типов
переменных!!!
базовые операторы:
арифметические: +, -, *, /, %(остаток от деления)
int a=1;
a=a+1; // сокращенная форма a+=1;
логические: >, >=, <, <=, ==, !=, &&(логическое и), ||(логическое или),
!(отрицание)
побитовые: &(побитовое И), |(побитовое или), ^(исключающее или),
<<(сдвиг влево), >>(сдвиг вправо), ~(дополнение)
пример:
int a=1;
a=a<<2;

18.

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

19.

тема «операторы» в си
приоритет операторов
наивысший
самый низкий
() [] -> .
! ~ ++ -- + - * (type) sizeof
*/%
+<< >>
< <= > >=
== !=
&
^
|
&&
||
?:
= += -= *= /= %= &= ^= |= <<=
>>=
19

20.

тема «операторы» в си
20
дополнительные операторы (находятся в Библиотеке math.h)
#include <math.h> // подключение Библиотеки
sin(x) //– синус (аргумент в радианах);
cos(x) //– косинус (аргумент в радианах);
tan(x) //– тангенс (аргумент в радианах);
asin(x) //– арксинус (результат в радианах);
acos(x) //– арккосинус (результат в радианах);
atan(x) //– арктангенс (результат в радианах);
sinh(x) //– гиперболический синус;
cosh(x) //– гиперболический косинус;
tanh(x) //– гиперболический тангенс;
log10(x) //– десятичный логарифм;
pow10(x) //– возведение числа 10 в степень x;
log(x) //– натуральный логарифм;
exp(x) //– экспонента;
sqrt(x) //– квадратный корень;
pow(x,y) //– возведение x в степень y;
fabs(x) //– абсолютная величина для double;
abs(x) //– абсолютная величина для int
практически все
данные функции
требуют аргумент
типа double!!!

21.

тема «условие» в си
не стесняйтесь
if (условие)
ставить больше
{}/ / оператор 1; фигурных
Да
else
скобок!!!
{} // оператор 2;
оператор 1
21
условие?
Нет
оператор 2
пример: определить знак числа
полная форма
int a=4;
if (a>0) {printf (“a>0”);}
else {printf (“a<0”);}
сокращенная форма
int a=4;
a>0 ? printf (“a>0”) : printf (“a<0”);

22.

тема «условие» в си
switch - выполнение кода при равенстве
выражения одной из численных констант
switch (переменная)
{
case значение_переменной1:
действие 1;
break;
case значение_переменной2:
действие 2;
break;
default:
действие 3;
break;
}
22
эквивалентный код:
if (переменная==
значение_переменной1)
{действие 1;}
else
{
if (переменная==
значение_переменной2)
{действие 2;}
else {действие 3;}
}

23.

тема «циклы» в си
23
цикл с параметром
for (expr1; expr2; expr3) {body}
цикл с постусловием
do
{body}
while (expr);
цикл с предусловием
while (expr)
{body}

24.

тема «циклы» в си
for(инициализация; условие продолжения выполнения
цикла; приращение)
{операторы;}
for(int i = 0; i < 2; i++)
{
}
24

25.

тема «циклы» в си
цикл с постусловием
код си:
do
{ тело цикла;}
while (условие);
тело цикла
нет
условие?
да
тело цикла выполняется хотя бы
один раз.
25

26.

тема «циклы» в си
цикл с предусловием
код си:
условие?
нет
while (условие)
{ тело цикла;}
да
тело цикла
тело цикла - один оператор, простой или
составной.
тело цикла может не выполниться ни
разу.
26

27.

тема «циклы» в си
инструкции перехода
break;
прерывание всех
итераций
пример:
for(int i=0; i<10; i++) {
scanf(“%d”,&i);
if( i == 5) break;
}
если i равно 5
прерываем цикл
continue;
переход к следующей
итерации
пример:
for(;;) {
scanf(“%d”,&i);
if (i>0) continue;
printf(“%d”, i);
}
выводить введенные
числа кроме 0
27

28.

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

29.

тема «массивы» в си
29
объявление одномерного статического массива
тип имя_массива[размер-константа];
int a[4]; // одномерный статический массив целых чисел длины 4
// нумерация элементов от 0 до 3
номер элемента
0-й
1-й
2-й
3-й
имя элемента
a[0]
a[1]
a[2]
a[3] …
адрес элемента
0108 010a 010c 010e …
int a[10];
a[i] = i*i; // присваивание элемента массива
…

30.

тема «массивы» в си
одномерный массив одномерных массивов.
объявление
тип имя_массива[размер1][размер2];
int b[3][10]; // матрица с 3 строками и 10 столбцами
30

31.

тема «массивы» в си
методы сортировки
сортировка - расположение элементов
множества в порядке расположения
некоторого ключа.
ограничения:
1. рассматриваются внутренние сортировки - все упорядочиваемые
значения помещаются в оперативной памяти.
2. сортируем одномерные массивы.
31

32.

тема «массивы» в си
ПРОСТЕЙШИЕ МЕТОДЫ
СОРТИРОВКИ
СОРТИРОВКА
ПОСРЕДСТВОМ ВЫБОРА
ОБМЕННАЯ
СОРТИРОВКА
СОРТИРОВКА
С ПОМОЩЬЮ ПОДСЧЕТА
МЕТОД
ВСТАВОК
32

33.

тема «массивы» в си
сортировка выбором
1 шаг. Выбираем наименьший элемент, переставляем его с первым (с
номером 0).
… imin … n-1
a[0] a[1] … a[imin] … a[n-1]
0
1
2 шаг. Среди элементов со 2-го (номер 1) по n-й (номер n-1) выбираем
наименьший элемент, переставляем его со вторым (с номером 1).
… imin … n-1
a[0] a[1] … a[imin] … a[n-1]
0
1
33

34.

тема «массивы» в си
сортировка посредством выбора
k-й шаг. Среди элементов со k-го (номер k-1) по n-й (номер n-1) выбираем
наименьший элемент, переставляем его с k-м
(с номером k-1).
0
k-2
k-1
a[0] … a[k-2] a[k-1]
… imin … n-1
… a[imin] … a[n-1]
(n-1)-й шаг. Среди элементов со (n-1)-го (номер n-2) по n-й (номер n-1)
выбираем наименьший элемент, переставляем его с (n-1)-м (с номером n2).
… n-3 n-2 n-1
a[0] … a[n-3] a[n-2] a[n-1]
0
34

35.

тема «массивы» в си
35
обменная сортировка
Просмотр массива и сравнение соседних элементов.
a[i]>a[i+1] - инверсия, элементы необходимо поменять местами.
За один просмотр хотя бы один элемент занимает нужное место:
максимальный элемент поднимается «наверх»
«метод пузырька»
Процесс повторяется, пока есть инверсии.
Признак наличия инверсий (флажок):
n-1
…
1, есть _ инверсии
F
0, нет _ инверсий
max
1
0

36.

тема «массивы» в си
метод вставок
Элементы просматриваются по одному и каждый вставляется на свое место
среди ранее упорядоченных
1-й шаг
0
…
1
0
1
2
…
1
…
Одно сравнение,
возможен сдвиг
n-1
n-1
2-й шаг
0
(n-1)-й шаг
n-2
n-1
Максимально
2 сравнения, возможен
сдвиг
Максимально
(n-1) сравнение,
возможен сдвиг
36

37.

тема «массивы» в си
37
сортировка с помощью подсчета
Предполагается, что в исходном массиве нет равных элементов. Каждый
элемент сравнивается с остальными. Для каждого элемента подсчитывается
число элементов, меньших его
(т.н. ключ). Значение ключа определяет место элемента в упорядоченном
массиве.
0 1 … i … j … n-1
массив a
массив k
(ключи)
0 1 … i … j … n-1
в начале k заполнен
нулями

38.

тема «строки» в си
строка – символьный одномерный массив, который
завершается нулевым символом '\0'.
объявляя массив str, предназначенный для хранения
10-символьной строки, следует использовать 11 char
char str[11]; // резервируется место для '\0'
строковый литерал – список символов, заключенный
в двойные кавычки
“hello” // в памяти
“” – нулевая строка, состоит только из '\0'
38

39.

тема «строки» в си
39
в Библиотеке stdio.h
ввод строк:
char s[13];
scanf(“%s”, s); // - считывает строку до пробела
gets(s); // – считывает строку, включая пробел
s[1]=getchar(); //– считывает символ, введенный с клавиатуры
sscanf ({массив}, {остальное как в обычном scanf}); //– ввод
значений не с клавиатуры, а из массива (строки)

40.

тема «строки» в си
40
в Библиотеке stdio.h
вывод строк:
char s[13];
printf(“%s”, s); // - выводит строку
puts(s); // – выводит строку и переводит курсор на новую строку
putchar(s[1]); //– выводит символ, не переводя курсор на новую
?
зачем отдельные
функции printf и puts???

41.

тема «строки» в си
41
в Библиотеке stdlib.h
конвертирование:
char s[13];
int atoi (s); // - строку в целое
long atol (s); // - строку в длинное целое
double atof (s); // - строку в вещественное
обратное преобразование
int i=0;
double d=0;
itoa (i, s, {основание системы счисления}); // - целое в строку
ltoa (I, s, {основание системы счисления}); // - длинное целое в строку
ftoa (d, s); // - вещественное в строку

42.

тема «строки» в си
в Библиотеке string.h
char s1[13], s2[13];
int i=strlen (s1);// – выдает длину строки s1, без нулевого символа
strcpy (s1, s2); // – копирует строку s2 в строку s1
(результат записывается в s1)
strncpy (s1, s2, int n); //– делает все тоже самое, что и предыдущая, но в
//количестве n символов
strcat (s1, s2); // – добавляет в строку s1 строку s2
strncat (s1, s2, int n); //– делает все тоже самое, что и предыдущая, но в
//количестве n символов
strcmp(s1, s2); //- сравнивает строки (результат int)
42

43.

тема «файлы» в си
файл – это поименованная совокупность байт
файлы предназначены только для хранения информации, а
обработка этой информации осуществляется только при
переносе в память компьютера
файл, не содержащий ни одного элемента, называется пустым
текстовый файл
бинарный файл
не применяются первые
31 символ кодовой
таблицы ascii, а символы
конца строки 0x13
(возврат каретки, CR) и
0x10 (перевод строки LF)
преобразуются при вводе
в одиночный символ
перевода строки \n
преобразования не
выполняются, чтение
продолжается, пока не
встретится
физический конец
файла
43

44.

тема «файлы» в си
44
в Библиотеке stdio.h
FILE *f; // - задание типа переменной «файл»
f=fopen (“путь к файлу”, “доступ”); // - связь указателя на файл и его
физического местоположения, указание режима открытия
режимы открытия:
r (r+) – файл открывается для чтения (чтения и записи);
w (w+) – открывается пустой файл для записи (чтения и записи), если
файл с таким именем существует, он стирается;
a (а+) – файл открывается для дополнения в конец (чтения и дополнения)
режим открытия может также содержать символы t (текстовый файл) и b
(двоичный файл), указывающие дополнительно на вид открываемого
файла: rb, wb, ab, rt, at, rb+, wb+, ab+
fclose(f); // - закрытие файла
rewind(f); // - установка указателя на начало файла
feof(f); // - функция, сигнализирующая о достижении
чем отличается
конца файла
?
r+ от w+???

45.

тема «файлы» в си
в Библиотеке stdio.h
чтение из файла
FILE *f; char s[13];
f=fopen (“путь к файлу”, “r”);
fread (s, 1,13,f); // - считывает строку из файла f по одному символу 13 раз
fscanf(f, “%s”, s); // - считывает строку из файла до пробела
fgets(s,13,f); // – считывает строку, длинной 13 символов (включая нулевой
символ) из файла, //включая пробел
s[1]=fgetc(f); //– считывает символ из файла
45

46.

тема «файлы» в си
в Библиотеке stdio.h
запись в файл
FILE *f; char s[13];
f=fopen (“путь к файлу”, “w”);
fwrite(s, 1,13,f); // - записывает строку в файл f по одному символу 13 раз
fprintf(f, “%s”, s); // - записывает строку в файл
fputs(s, f); // – записывает строку в файл
fputc(s[1], f); //– записывает символ в файл
46

47.

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

48.

тема «записи» в си
формат описания:
struct имя_записи {
тип имя_элемента1;
…
тип имя_элементаN; } список_переменных;
пример
struct data{char name [30], surname [30];
float bal} a; // a – имя записи
scanf(“%s” ,a.name);
scanf(“%s” ,a.surname);
scanf(“%f” ,a.bal);
48

49.

тема «функции» в си
49
функция – часть программы, которая может вызываться из других частей
программы столько раз, сколько необходимо и возвращает значение
переменной
процедура – функция, которая не возвращает значение
функция и процедура являются подпрограммами, выполняющими одну
или несколько инструкций
функции бывают:
стандартные (находящиеся в Библиотеках)
пользовательские (написанные пользователем)
также функции делятся по типу возвращаемых значений: целочисленные,
вещественные, символьные, либо ничего не возвращающие – тип void,
которые можно считать процедурами
примеры функций
printf(“%d”,i); // - стандартная функция, возвращающая число символов,
выведенных на экран (или отрицательное значение при ошибке)
scanf(“%d”,&i); // - стандартная функция, возвращающая число
прочитанных символов (при вводе букв вместо цифр, выдается 0)

50.

тема «функции» в си
преимущества использования подпрограмм:
использование одного и того же код программы для
многих входных значений, что сокращает объем
структурированность кода программы – вся
программа разбивается на связанные блоки
!
новый тип
программирования –
сверхфункциональный!!!
50

51.

тема «функции» в си
имя пользовательской функции – идентификатор,
задаваемый программистом
имена должны составляться также как и переменные
функции должны именоваться и объявляться вне
функции main, но до позиции ее вызова!!!
локальная переменная функции объявляется и
используется только в своей функции. В разных
функциях могут быть одинаковые локальные
переменные
глобальная переменная функции объявляется в
программе и может использоваться в любой функции.
При объявлении в пользовательской функции
глобальной переменной, выдается ошибка
51

52.

тема «функции» в си
аргумент функции – конкретное значение, передаваемое функции при
вызове (может быть локальной и глобальной переменной)
52
параметр – переменная, которая принимает передаваемый функции
аргумент (является только локальной переменной)
пример:
int ( int i; int j) // - пользовательская целочисленная функция, имеющая параметры
i и j, которым будут переданы аргументы m и n, соответственно
{
int y=0; // - локальная переменная пользовательской функции
y=i*j; // - выполняемое действие в функции
return y; // - возвращаемое значение пользовательской функции
}
int k=0; // - глобальная переменная;
int main() // - стандартная функция
{
int m=0,n=0; // - локальные переменные стандартной функции
?
может ли
параметр
не равняться
аргументу???
k =f (m, n); // - вызов пользовательской функции f с аргументами m и n
return 0; // - возвращаемое значение стандартной функции
}

53.

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

54.

тема «функции» в си
общий вид рекурсии:
если (простейший случай) тогда
решить напрямую
иначе
делать рекурсивный вызов до появления простейшего
случая
пример:
int factorial (int n)
{
if (n == 0)
{
return 1; // - простейший случай
}
else
{
int value = factorial(n - 1); // - рекурсивный вызов
return n * value;
}
}
54

55.

тема «программно-аппаратные аспекты» в си 55
контроллер lpt
порта
RAM
CPU
параметры lpt:
ttl-логика («0» - 0 В, «1» - 5 В)
ток нагрузки не более 14 мА
8 выходов
5 входов
адреса в памяти:
для записи: h378
для чтения: h379

56.

тема «программно-аппаратные аспекты» в си 56
R=(Ui-Us)/I
при подключении Библиотеки
inpout32.dll
доступ к lpt порту производится с помощью функций:
Inp32(short addr); // - чтение данных из lpt по адресу addr
Out32(addr, data); // - запись в lpt данных data по адресу addr

57.

благодарю за
внимание!!!
вопросы???