Table of Contents

Обработка последовательностей

Типы Данных в C
Ввод и Вывод (fscanf, printf)
Что такое указатели?

Размер указателя
Пример работы с указателями

Организация Кода: Header (.h) и Source (.c) Файлы
Компиляция в GCC и Объектные Файлы
Решённые Задачи Раздела

10Ex: Подсчёт чисел в диапазоне
22Ex: Проверка строгой возрастающей последовательности
45Ex: Вычисление многочлена и его производной
46Ex: Аналогичная задача с убывающими степенями

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Обработка последовательностей

Раздел «Обработка последовательностей» посвящён задачам, в которых необходимо определить различные характеристики числовой последовательности за один проход файла. Это значит, что считывать данные нужно построчно (или поэлементно) при помощи стандартных функций ввода/вывода языка C, например fscanf, и сразу же обрабатывать результаты, не сохраняя всю последовательность целиком.

Типы Данных в C

В языке C существуют следующие базовые типы данных, наиболее используемые при решении подобных задач:

int — целое число (диапазон зависит от конкретной платформы и компилятора).
double и float — числа с плавающей точкой.
- При обработке вещественных значений (например, для вычисления среднего) обычно применяют double для более точных вычислений.
char — символьный тип. В задачах с числами обычно не требуется, но может использоваться для чтения отдельных символов.
long, short — целочисленные типы с расширенным или уменьшенным диапазоном значений относительно int.

Особенность: в C нет автоматической переработки (приведения) типов, поэтому важно корректно использовать соответствующие спецификаторы форматирования при вводе и выводе.

Ввод и Вывод (fscanf, printf)

Чтение из файла
- Для последовательности неизвестной длины обычно используют конструкцию:
```
double x;
while (fscanf(file, "%lf", &x) == 1) {
    // обработка x
}
```
  Если нужны целые числа, меняют спецификатор на "%d" и тип переменной на int.
- Важно проверять результат fscanf: если он возвращает 1, значит число считано успешно.
Вывод на экран
- Функция printf выводит данные в стандартный поток вывода (консоль).
- Для double применяется формат "%lf", для int — "%d".
- Пример:
```
printf("Среднее значение: %.3lf\n", avg);
```
  Выведет число avg с тремя знаками после запятой.

Что такое указатели?

Указатель — это переменная, которая хранит адрес другой переменной в памяти. Например, если переменная x хранит значение, то указатель на x будет содержать адрес памяти, где это значение хранится. Указатели особенно полезны для передачи больших данных в функции, работы с массивами и динамической памяти.

Размер указателя

Размер указателя в языке C зависит от архитектуры системы. Обычно:

На 32-битной системе указатель занимает 4 байта.
На 64-битной системе указатель занимает 8 байт.

Это справедливо для всех типов указателей: указатель на int, double или массивы имеет одинаковый размер, поскольку он хранит только адрес.

Пример работы с указателями

Объявление указателя:

int x = 10;
int *ptr = &x;  // ptr хранит адрес переменной x

Изменение значения через указатель:
```
*ptr = 20;  // Теперь x равно 20
```

Передача указателя в функцию:

void changeValue(int *p) {
    *p = 50;  // Изменяем значение переменной, на которую указывает p
}

int main() {
    int x = 10;
    changeValue(&x);  // Передаём адрес переменной
    printf("%d", x);  // Вывод: 50
    return 0;
}

Организация Кода: Header (.h) и Source (.c) Файлы

При разработке на C принято разделять код на заголовочные файлы (.h) и исходные файлы (.c):

Заголовочные файлы (.h)
- Содержат объявления функций, типов данных (структур, перечислений), констант и т. д.
- Позволяют избежать дублирования объявлений и упрощают повторное использование кода в разных .c файлах.
- Пример структуры заголовочного файла:
```
// myfunctions.h
#ifndef MYFUNCTIONS_H
#define MYFUNCTIONS_H

void processNumber(double x);
// другие объявления

#endif
```
Исходные файлы (.c)
- Содержат определения функций, объявленных в .h файлах, а также логику программы.
- В начале обычно подключают нужные заголовочные файлы:
```
// myfunctions.c
#include <stdio.h>
#include "myfunctions.h"

void processNumber(double x) {
    // реализация
}
```
- При сборке большие проекты можно разбивать на несколько .c файлов, каждый со своим набором функций.

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

Компиляция в GCC и Объектные Файлы

Компиляция
- Простейший пример компиляции одного файла:
```
gcc main.c -o main
```
  В результате будет создан исполняемый файл main.
- Для нескольких .c файлов:
```
gcc -c file1.c       // создаёт file1.o
gcc -c file2.c       // создаёт file2.o
gcc file1.o file2.o -o program
```
Объектные Файлы
- При опции -c компилятор генерирует объектные файлы (расширение .o или .obj). Они содержат машинный код, готовый к связыванию, но ещё не образуют полноценного приложения.
- На этапе линковки все объектные файлы, а также необходимые библиотеки объединяются в один исполняемый файл.

Решённые Задачи Раздела

Ниже перечислены задачи, которые реализованы (или планируется реализовать) в рамках раздела «Обработка последовательностей». Они располагаются в отдельных подкаталогах с названиями вида xxEx (например, 10Ex, 22Ex, 45Ex, 46Ex) внутри репозитория. Каждая задача решается за один проход по файлу с последовательностью.

10Ex: Подсчёт чисел в диапазоне

Суть задачи:
Определить количество чисел, попадающих в диапазон [a, b]. Границы диапазона задаются первыми двумя числами файла, остальные числа проверяются.
Идея решения:
Построчное чтение позволяет обработать файл без загрузки всех чисел в память. Проверка на попадание в диапазон выполняется для каждого числа.
Основные шаги:
1. Считать первые два числа как границы диапазона a и b.
2. Проверить, что диапазон корректен (a <= b).
3. Для каждого следующего числа проверить, попадает ли оно в диапазон, и увеличить счётчик, если да.
4. Вывести результат.

Пример кода:

#include <stdio.h>

int countBetween(FILE *file) {
    double a, b, x;
    int count = 0;

    fscanf(file, "%lf %lf", &a, &b);  // Чтение границ
    if (a > b) {
        printf("Invalid range\n");
        return -1;
    }

    while (fscanf(file, "%lf", &x) == 1) {
        if (x >= a && x <= b) {
            count++;  // Увеличиваем счётчик
        }
    }

    return count;
}

int main(void) {
    FILE *file = fopen("input.txt", "r");
    if (file == NULL) {
        printf("Error opening file\n");
        return 1;
    }

    int result = countBetween(file);
    if (result >= 0) {
        printf("Count of numbers in range: %d\n", result);
    }

    fclose(file);
    return 0;
}

На что обратить внимание:
- Использование fscanf для построчного чтения.
- Проверка корректности диапазона до начала обработки чисел.

22Ex: Проверка строгой возрастающей последовательности

Суть задачи:
Проверить, можно ли сделать последовательность строго возрастающей, изменив не более одного элемента.
Идея решения:
Алгоритм проходит последовательность и отслеживает нарушения. Если найдено одно нарушение, проверяется, можно ли его исправить. Если нарушений больше одного, преобразование невозможно.
Основные шаги:
1. Построчно считывать числа.
2. Сравнивать текущее число с предыдущим для выявления нарушений.
3. При первом нарушении проверить возможность его исправления.
4. Если нарушений больше одного, завершить с отрицательным результатом.

Пример кода:

int makeIncreasing(FILE *file) {
    int prev, curr, violations = 0;

    fscanf(file, "%d", &prev);  // Первое число
    while (fscanf(file, "%d", &curr) == 1) {
        if (curr <= prev) {
            violations++;
            if (violations > 1) return 0;  // Больше одного нарушения
        }
        prev = curr;  // Обновляем предыдущее число
    }

    return 1;  // Последовательность можно преобразовать
}

На что обратить внимание:
- Обновление переменной prev после каждой итерации.
- Нарушение фиксируется, если curr <= prev.

45Ex: Вычисление многочлена и его производной

Суть задачи:
Вычислить значение многочлена и его производной в точке x, используя коэффициенты, заданные в порядке возрастания степеней.
Идея решения:
Метод Горнера позволяет эффективно вычислить значение многочлена за один проход по коэффициентам. Производная рассчитывается одновременно с многочленом.
Основные шаги:
1. Построчно считать коэффициенты.
2. Вычислить значение многочлена методом Горнера.
3. Одновременно вычислить производную.

Пример кода:

int solvePolynomial(FILE *file, double x, double *derivative, double *polynomial) {
    double coeff;
    *polynomial = 0;
    *derivative = 0;

    while (fscanf(file, "%lf", &coeff) == 1) {
        *derivative = *derivative * x + *polynomial;  // Производная
        *polynomial = *polynomial * x + coeff;       // Многочлен
    }

    return 0;
}

На что обратить внимание:
- Последовательное обновление значений многочлена и производной.
- Метод Горнера уменьшает вычислительную сложность.

46Ex: Аналогичная задача с убывающими степенями

Суть задачи:
Аналогична предыдущей, но коэффициенты многочлена заданы в порядке убывания степеней.
Идея решения:
Старший коэффициент обрабатывается первым, а для производной текущая степень уменьшается на каждом шаге.

Пример кода:

int solutionPolynomial(FILE *file, double x, double *derivative, double *polynomial) {
    double coeff;
    int degree = -1;
    *polynomial = 0;
    *derivative = 0;

    while (fscanf(file, "%lf", &coeff) == 1) {
        degree++;
        *polynomial = *polynomial * x + coeff;
        if (degree > 0) *derivative = *derivative * x + coeff * degree;  // Производная
    }

    return 0;
}

На что обратить внимание:
- Учёт убывания степеней для производной.
- Метод Горнера остаётся основным подходом.

↑ Наверх