Глава 2. Алгоритмы и программирование
Погружаемся в мир языков программирования! Узнаем, как записывать алгоритмы на языке C, работать со структурами данных и массивами. Научимся анализировать программы и решать практические задачи.
§ 7. Запись алгоритмов на языках программирования
Введение: Язык как мост между мыслью и машиной
Представь: ты хочешь объяснить другу, как пройти к новому кафе. Ты используешь русский язык, жесты, может, карту. А теперь представь, что твой друг — это компьютер. Он не понимает ни слов, ни жестов. Ему нужен строгий, формальный язык, где каждое слово имеет одно значение, а каждая конструкция подчиняется железным правилам.
Язык программирования — это именно такой формальный язык. Это система знаков и правил, которая позволяет описать алгоритм так, чтобы компьютер мог его понять и выполнить.
💡 Интересный парадокс
Мы создаём языки программирования, чтобы общаться с машинами, но на самом деле мы общаемся друг с другом через код. Код читают другие программисты, его поддерживают, развивают. Машина лишь исполняет то, что мы описали.
Язык программирования — мост между человеческой мыслью и машинным исполнением
В этом учебнике мы продолжаем работать с языком C (Си) — одним из фундаментальных языков программирования, который лежит в основе многих современных технологий: от операционных систем (Linux, части Windows) до игровых движков и драйверов устройств.
7.1. Структурная организация данных: от битов к смыслу
Компьютер на нижнем уровне оперирует битами — нулями и единицами. Это единственный "язык", который понимает процессор. Но мы, люди, не думаем битами. Мы думаем числами, словами, изображениями, музыкой.
📊 Определение
Данные — это информация, представленная в виде, пригодном для обработки компьютером.
🤔 Как ты думаешь?
Почему мы не пишем программы на языке битов? Потому что это невероятно сложно, долго и чревато ошибками. Вместо этого мы используем абстракции — слои, которые скрывают сложность и позволяют работать с более понятными концепциями.
Простые и сложные структуры данных
Базовые "кирпичики"
- Целые числа (int, long) — для счёта, индексов, кодов
- Вещественные числа (float, double) — для измерений, координат, научных расчётов
- Символы (char) — буквы, цифры, знаки препинания
- Логические значения (bool, int) — истина/ложь, да/нет
Комбинации простых типов
- Массивы — упорядоченные последовательности элементов одного типа
- Строки — массивы символов, представляющие текст
- Структуры (struct) — объединения разнородных данных
- Графы, деревья, списки — более сложные структуры для специфических задач
Структуры данных: от простых элементов к сложным построениям
✨ Почему это важно?
Понимание структуры данных помогает:
- Выбрать правильный тип для задачи (не использовать float там, где нужен int)
- Оптимизировать память (int занимает меньше места, чем double)
- Избегать ошибок (переполнение, потеря точности)
- Понимать, как работают библиотеки и фреймворки
7.2. Основы языка C: инструменты для построения алгоритмов
Давайте разберём "анатомию" программы на C. Каждая программа — это текст, состоящий из элементов, организованных по строгим правилам.
Алфавит и базовые элементы
🔤 Алфавит
Латинские буквы (a-z, A-Z), цифры (0-9), специальные символы (;, {, }, (, ), +, -, *, /, и др.)
📚 Служебные слова
Слова с зарезервированным значением: int, if, while, return, for
🏷️ Идентификаторы
Названия переменных, функций: counter, summa, calculateAverage
📝 Правила именования
- Начинается с буквы или подчёркивания
_ - Может содержать буквы, цифры, подчёркивания
- Регистр имеет значение:
Counterиcounter— разные имена - Не должно совпадать со служебными словами
Практический совет: Имена должны быть говорящими. x — плохо. studentAge — хорошо. Код читается намного чаще, чем пишется.
Операции и выражения
➕ Арифметические операции
+ сложение
- вычитание
* умножение
/ деление
% остаток от деления (только для целых)
⚖️ Операции сравнения
== равно
!= не равно
> больше
< меньше
>= больше или равно
<= меньше или равно
🔀 Логические операции
&& логическое И (AND)
|| логическое ИЛИ (OR)
! логическое НЕ (NOT)
🎯 Приоритет операций
От высшего к низшему:
!(отрицание)*,/,%+,-<,<=,>,>===,!=&&||
💡 Пример
int result = 5 + 3 * 2; // result = 11 (не 16!)
int logic = (5 > 3) && (2 < 4); // logic = 1 (истина)
Как ты думаешь, почему важен приоритет операций? Представь, что ты пишешь формулу для расчёта итоговой оценки: (homework * 0.3 + exam * 0.7). Без правильного порядка вычислений результат будет неверным.
Структура программы на C
#include <stdio.h> // Подключение библиотеки для ввода-вывода
int main() { // Главная функция - точка входа
// Объявление переменных
int age;
float height;
// Ввод данных
printf("Введите возраст: ");
scanf("%d", &age);
// Обработка
if (age >= 18) {
printf("Вы совершеннолетний\n");
} else {
printf("Вы несовершеннолетний\n");
}
return 0; // Успешное завершение
}
🔑 Ключевые части программы
#include— директива препроцессора, подключает библиотекиmain()— обязательная функция, с неё начинается выполнение- Блок
{ }— группирует операторы ;— завершает каждую инструкциюreturn 0— код возврата (0 = успех)
Программа работает как конвейер: данные → обработка → результат
Основные операторы
| Оператор | Назначение | Пример |
|---|---|---|
| Присваивание | Присвоить значение переменной | x = 10; |
| Ввод | Считать данные | scanf("%d", &n); |
| Вывод | Вывести данные | printf("Результат: %d\n", sum); |
| Условный | Ветвление | if (x > 0) { ... } else { ... } |
| Цикл while | Цикл с предусловием | while (i < 10) { ... } |
| Цикл for | Цикл со счётчиком | for (i = 0; i < 10; i++) { ... } |
| Цикл do-while | Цикл с постусловием | do { ... } while (i < 10); |
7.3. Анализ программ: трассировочные таблицы
Один из лучших способов понять, как работает программа — это "прогнать" её вручную, пошагово отслеживая изменения переменных. Этот процесс называется трассировкой.
🎯 Зачем нужна трассировка?
- Поиск ошибок: Найти место, где программа делает не то, что мы ожидали
- Понимание логики: Увидеть, как изменяются данные на каждом шаге
- Обучение: Глубже понять работу циклов, условий, рекурсии
- Подготовка к экзаменам: Многие задачи на ЕГЭ требуют именно ручной трассировки
Пример 1: Простой цикл
#include <stdio.h>
int main() {
int a = 5;
int b = 1;
while (b <= a) {
b = b + 1;
a = a - 1;
}
printf("a = %d, b = %d\n", a, b);
return 0;
}
Трассировочная таблица (каждая строка — один шаг):
| Шаг | Команда/Условие | a | b | Комментарий |
|---|---|---|---|---|
| 1 | a = 5 |
5 | — | Инициализация |
| 2 | b = 1 |
5 | 1 | Инициализация |
| 3 | b <= a (истина) |
5 | 1 | Входим в цикл |
| 4 | b = b + 1 |
5 | 2 | |
| 5 | a = a - 1 |
4 | 2 | |
| ... | ... | ... | ... | Цикл продолжается |
| 12 | b <= a (ложь) |
2 | 4 | Выходим из цикла |
| 13 | printf(...) |
2 | 4 | Вывод |
✅ Ответ
a = 2, b = 4
Пример 2: Вложенные циклы (компактная трассировка)
Для сложных программ полная трассировка может быть громоздкой. Можно использовать контрольные точки — отмечать состояние переменных в ключевых моментах.
#include <stdio.h>
int main() {
int s = 0;
int i, j;
for (i = 1; i <= 3; i++) {
for (j = 3; j >= i; j--) {
s = s + i + j;
}
}
printf("s = %d\n", s);
return 0;
}
Контрольная точка: после каждого выполнения s = s + i + j
| Итерация | i | j | s (новое) | Вычисление |
|---|---|---|---|---|
| Начало | — | — | 0 | |
| 1 | 1 | 3 | 4 | 0 + 1 + 3 |
| 2 | 1 | 2 | 7 | 4 + 1 + 2 |
| 3 | 1 | 1 | 9 | 7 + 1 + 1 |
| 4 | 2 | 3 | 14 | 9 + 2 + 3 |
| 5 | 2 | 2 | 18 | 14 + 2 + 2 |
| 6 | 3 | 3 | 24 | 18 + 3 + 3 |
✅ Ответ
s = 24
💡 Интересное наблюдение
Внутренний цикл выполняется разное количество раз на каждой итерации внешнего цикла. Это типичная ситуация для алгоритмов обработки треугольных матриц или пирамид.
Трассировка — это детальное исследование каждого шага программы
7.4. Продвинутые приёмы анализа: когда трассировки недостаточно
Иногда программа содержит сотни или тысячи итераций. Построить полную трассировочную таблицу невозможно. Нужны другие подходы.
Метод инвариантов
📐 Определение
Инвариант цикла — это утверждение, которое остаётся истинным перед каждой итерацией цикла.
Пример:
#include <stdio.h>
int main() {
int n = 0;
int s = 400;
while (s < 2992) {
s = s + 12;
n = n + 2;
}
printf("n = %d\n", n);
return 0;
}
🔍 Анализ:
- Что делает s? Начинается с 400, каждую итерацию увеличивается на 12
- Что делает n? Начинается с 0, каждую итерацию увеличивается на 2
- Инвариант:
n = 2 * (количество итераций) - Условие выхода:
s >= 2992
📊 Вычисление:
- Количество итераций:
(2992 - 400) / 12 = 2592 / 12 = 216 - Значит,
n = 2 * 216 = 432
Проверка граничного случая:
- После 216 итераций:
s = 400 + 216 * 12 = 400 + 2592 = 2992✓ - Условие
s < 2992станет ложным ✓
✅ Ответ
n = 432
Метод аналитического разбора
Пример:
#include <stdio.h>
int main() {
int x, m, n;
printf("Введите x: ");
scanf("%d", &x);
m = 0;
n = 1;
while (x > 0) {
m = m + 1;
n = n * (x % 10);
x = x / 10;
}
printf("m = %d, n = %d\n", m, n);
return 0;
}
🔍 Что делает программа?
Разберём по шагам:
m = m + 1— счётчик, увеличивается на каждой итерацииx % 10— последняя цифра числа xn = n * (x % 10)— умножаем n на последнюю цифруx = x / 10— "отрезаем" последнюю цифру (целочисленное деление)
💡 Вывод:
- m — количество цифр в числе x
- n — произведение всех цифр числа x
📝 Задача:
Найти все пятизначные числа, для которых m = 5 и n = 25.
Решение:
- 25 = 5 × 5 × 1 × 1 × 1
- Значит, число должно содержать две пятёрки и три единицы
Комбинаторика: Количество способов расставить 2 пятёрки и 3 единицы в 5 позициях:
C₅² = 5! / (2! · 3!) = (5 · 4) / 2 = 10
Все числа:
11155, 11515, 11551, 15115, 15151, 15511, 51115, 51151, 51511, 55111
Наименьшее: 11155
Наибольшее: 55111
Аналитический подход: ищем закономерности вместо слепого перебора
✨ Ключевые выводы по §7
🤔 Проверь себя (§7)
Вопрос 1: Почему в программировании важен приоритет операций? Приведи пример ошибки, которая может возникнуть из-за неправильного понимания приоритета.
Подумай о разнице между 2 + 3 * 4 и (2 + 3) * 4. Какой результат получится в каждом случае?
Вопрос 2: Определи значение переменной result после выполнения кода:
int a = 10, b = 3, result;
result = (a / b) * b + (a % b);
Подсказка: вспомни про целочисленное деление и остаток от деления.
Вопрос 3: Программа выводит числа от 1 до N. Какой цикл ты бы выбрал — while или for? Почему?
Подумай о том, когда количество итераций известно заранее, а когда — нет.
Вопрос 4: Дана программа. Что хранится в переменной sum после выполнения? Опиши словами, что делает этот алгоритм.
int x = 123;
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
Мини-кейс: Тебе нужно написать программу, которая определяет, является ли число простым. Опиши алгоритм словами (без кода). Какие оптимизации можно применить?
Подсказка: нужно ли проверять все делители от 2 до N-1?
§ 8. Структурированные типы данных. Массивы
Введение: От одиночных величин к коллекциям
Представь: ты разрабатываешь приложение для анализа результатов турнира по киберспорту. У тебя 100 участников, и нужно хранить очки каждого.
Плохое решение:
int player1, player2, player3, ..., player100;
Это абсурд! Код будет огромным, негибким, непригодным для обработки.
Хорошее решение:
int scores[100]; // Массив из 100 элементов
📚 Определение
Массив — это структура данных, которая позволяет хранить множество элементов одного типа под одним именем, обращаясь к каждому по номеру (индексу).
🌍 Массивы повсюду
- Пиксели изображения — двумерный массив цветов
- Звуковая дорожка — массив амплитуд сигнала
- Список друзей — массив ID пользователей
- История чата — массив сообщений
Массив — упорядоченная коллекция данных с доступом по номеру
8.1. Объявление и инициализация массивов в C
Базовый синтаксис
тип_данных имя_массива[размер];
📝 Примеры:
int numbers[10]; // Массив из 10 целых чисел
float temperatures[7]; // Массив из 7 вещественных чисел
char message[100]; // Массив из 100 символов (строка)
⚠️ Важно!
- Размер массива должен быть известен на этапе компиляции (константа)
- В C индексы начинаются с 0. Массив
arr[10]имеет элементы отarr[0]доarr[9] - Обращение к
arr[10]— выход за границы массива, это ошибка!
Инициализация массива
При объявлении
int scores[5] = {85, 92, 78, 95, 88};
Частичная инициализация
int data[10] = {1, 2, 3};
// Остальные элементы = 0
Без указания размера
int values[] = {10, 20, 30, 40};
// Размер = 4 (автоматически)
В цикле
int arr[100];
for (int i = 0; i < 100; i++) {
arr[i] = i * 2;
}
8.2. Работа с элементами массива
Доступ к элементам
#include <stdio.h>
int main() {
int scores[5] = {85, 92, 78, 95, 88};
// Чтение элемента
printf("Первый элемент: %d\n", scores[0]); // 85
printf("Третий элемент: %d\n", scores[2]); // 78
// Изменение элемента
scores[2] = 80;
printf("Новый третий элемент: %d\n", scores[2]); // 80
return 0;
}
🤔 Как ты думаешь, почему индексация с нуля?
Исторически это связано с тем, что индекс — это смещение относительно начала массива. arr[0] — это "начало + 0 шагов", arr[3] — "начало + 3 шага".
Обход массива (итерация)
🔄 Классический способ:
int arr[5] = {10, 20, 30, 40, 50};
int sum = 0;
for (int i = 0; i < 5; i++) {
sum += arr[i];
}
printf("Сумма: %d\n", sum); // 150
❌ Распространённая ошибка:
for (int i = 0; i <= 5; i++) { // ОШИБКА! Выход за границы
sum += arr[i];
}
Правило: условие должно быть i < размер, а не i <= размер.
8.3. Типовые задачи на массивы
Задача 1: Поиск максимального элемента
🎯 Алгоритм:
- Предположить, что первый элемент — максимальный
- Пройти по остальным элементам
- Если нашли элемент больше текущего максимума — обновить максимум
#include <stdio.h>
int main() {
int arr[10] = {45, 78, 23, 91, 56, 12, 88, 34, 67, 50};
int max = arr[0]; // Предполагаем, что первый — максимальный
int maxIndex = 0;
for (int i = 1; i < 10; i++) {
if (arr[i] > max) {
max = arr[i];
maxIndex = i;
}
}
printf("Максимальный элемент: %d (индекс %d)\n", max, maxIndex);
return 0;
}
✅ Вывод:
Максимальный элемент: 91 (индекс 3)
Аналогично: поиск минимума, среднего арифметического, подсчёт элементов с заданным свойством.
Задача 2: Реверс массива (переворот)
💡 Идея:
Поменять местами первый и последний элементы, второй и предпоследний, и т.д.
#include <stdio.h>
int main() {
int arr[8] = {1, 2, 3, 4, 5, 6, 7, 8};
int n = 8;
// Реверс
for (int i = 0; i < n / 2; i++) {
int temp = arr[i];
arr[i] = arr[n - 1 - i];
arr[n - 1 - i] = temp;
}
// Вывод
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
// Вывод: 8 7 6 5 4 3 2 1
return 0;
}
🤔 Почему i < n / 2?
Если пройти весь массив, то элементы поменяются местами дважды и вернутся в исходное положение!
Задача 3: Подсчёт элементов, удовлетворяющих условию
Пример: Сколько чётных чисел в массиве?
#include <stdio.h>
int main() {
int arr[10] = {15, 22, 31, 44, 57, 60, 73, 86, 91, 100};
int count = 0;
for (int i = 0; i < 10; i++) {
if (arr[i] % 2 == 0) {
count++;
}
}
printf("Количество чётных чисел: %d\n", count);
return 0;
}
✅ Вывод:
Количество чётных чисел: 5
Типовые операции с массивами: поиск, фильтрация, анализ
8.4. Практическое применение: от задач к реальности
Пример 1: Анализ температур за неделю
#include <stdio.h>
int main() {
float temps[7]; // Температуры за 7 дней
float sum = 0, avg, maxTemp, minTemp;
int hotDays = 0;
// Ввод данных
printf("Введите температуры за 7 дней:\n");
for (int i = 0; i < 7; i++) {
printf("День %d: ", i + 1);
scanf("%f", &temps[i]);
sum += temps[i];
}
// Средняя температура
avg = sum / 7;
// Максимум и минимум
maxTemp = minTemp = temps[0];
for (int i = 1; i < 7; i++) {
if (temps[i] > maxTemp) maxTemp = temps[i];
if (temps[i] < minTemp) minTemp = temps[i];
}
// Подсчёт жарких дней (>25°C)
for (int i = 0; i < 7; i++) {
if (temps[i] > 25.0) hotDays++;
}
// Вывод результатов
printf("\n--- Анализ погоды ---\n");
printf("Средняя температура: %.1f°C\n", avg);
printf("Максимум: %.1f°C\n", maxTemp);
printf("Минимум: %.1f°C\n", minTemp);
printf("Жарких дней: %d\n", hotDays);
return 0;
}
🌍 Реальное применение
Метеостанции используют массивы для хранения тысяч измерений. Алгоритмы анализа — те же самые, только масштаб больше.
Пример 2: Фильтрация данных (простейший спам-фильтр)
Представим, что у нас есть массив "подозрительности" сообщений (оценка от 0 до 100). Сообщения с оценкой выше 70 — спам.
#include <stdio.h>
int main() {
int scores[10] = {25, 85, 10, 92, 45, 78, 5, 88, 60, 95};
int spamCount = 0;
printf("Сообщения-спам (оценка > 70):\n");
for (int i = 0; i < 10; i++) {
if (scores[i] > 70) {
printf("Сообщение #%d (оценка: %d)\n", i + 1, scores[i]);
spamCount++;
}
}
printf("\nВсего спама: %d из 10\n", spamCount);
return 0;
}
✅ Вывод:
Сообщения-спам (оценка > 70):
Сообщение #2 (оценка: 85)
Сообщение #4 (оценка: 92)
Сообщение #6 (оценка: 78)
Сообщение #8 (оценка: 88)
Сообщение #10 (оценка: 95)
Всего спама: 5 из 10
🔗 Связь с реальностью
Gmail, ВКонтакте, Telegram используют сложные алгоритмы машинного обучения, но базовая логика — та же: оценка каждого сообщения и фильтрация по порогу.
8.5. Двумерные массивы (матрицы) — краткий обзор
Одномерный массив — это последовательность. Двумерный массив — это таблица (матрица).
int matrix[3][4]; // 3 строки, 4 столбца
📊 Визуализация:
matrix[0][0] matrix[0][1] matrix[0][2] matrix[0][3]
matrix[1][0] matrix[1][1] matrix[1][2] matrix[1][3]
matrix[2][0] matrix[2][1] matrix[2][2] matrix[2][3]
📝 Инициализация:
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
🔄 Обход (вложенные циклы):
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
🌍 Применение:
- Изображения (двумерный массив пикселей)
- Игровое поле (шахматная доска, тетрис)
- Таблицы данных (расписание, оценки)
- Научные расчёты (линейная алгебра)
Двумерный массив — организация данных в виде таблицы с двухуровневой адресацией
✨ Ключевые выводы по §8
🤔 Проверь себя (§8)
Вопрос 1: Какой индекс имеет последний элемент массива int data[50]? Почему?
Вспомни, что индексация начинается с нуля.
Вопрос 2: Что выведет этот код?
int arr[5] = {2, 4, 6, 8, 10};
int result = arr[1] + arr[3];
printf("%d\n", result);
Вопрос 3: Напиши условие цикла для обхода массива float values[100] так, чтобы не было выхода за границы.
Подсказка: условие должно учитывать размер массива.
Вопрос 4: Дан массив оценок студентов. Как определить, сколько из них получили "отлично" (оценка >= 90)? Опиши алгоритм словами.
Какую переменную-счётчик нужно использовать? Какое условие проверять?
Мини-кейс: Ты разрабатываешь систему учёта посещаемости. У тебя 30 студентов и 5 занятий в неделю. Какую структуру данных ты выберешь для хранения информации о посещениях? Обоснуй свой выбор.
Подсказка: подумай о двумерных массивах.
🎯 Практические задания
✍️ Задание 1: Базовые операции
Напиши программу, которая:
- Создаёт массив из 10 элементов
- Заполняет его числами от 1 до 10
- Выводит все элементы
- Находит и выводит сумму всех элементов
🔍 Задание 2: Поиск элемента
Дан массив: {5, 12, 8, 19, 3, 15, 7}
Напиши программу, которая находит позицию (индекс) элемента со значением 19.
🎨 Задание 3: Анализ данных
Создай массив с оценками 10 студентов (от 0 до 100). Программа должна:
- Найти среднюю оценку
- Подсчитать, сколько студентов получили >= 60
- Вывести максимальную и минимальную оценки
🔄 Задание 4: Преобразование
Напиши программу, которая удваивает все элементы массива.
Пример:
Было: {1, 2, 3, 4, 5}
Стало: {2, 4, 6, 8, 10}
💭 Итоговое размышление
Алгоритмы и структуры данных — это не просто абстрактные концепции. Это инструменты мышления, которые помогают:
- Декомпозировать сложные задачи на простые шаги
- Оптимизировать процессы (как в коде, так и в жизни)
- Автоматизировать рутину и фокусироваться на творчестве
- Понимать логику работы цифровых систем, которые нас окружают
Каждый раз, когда ты открываешь приложение, смотришь видео, отправляешь сообщение — за кулисами работают тысячи алгоритмов, оперирующих массивами, деревьями, графами. И теперь ты знаешь, как они устроены изнутри.
🚀 Следующий шаг
От простых массивов мы перейдём к более сложным структурам — спискам, стекам, очередям, деревьям. А затем — к алгоритмам поиска, сортировки, графов. Каждая новая концепция будет опираться на то, что ты уже понял.
Продолжай исследовать! 🚀
Программирование — это путешествие от простого к сложному, от концепции к реализации