Лекция 4.

1. Последовательности.

Задача 1. (в списке 12) Сколько раз в последовательности
встречается фрагмент 1 2 1 3?

fscanf() возвращает количество прочитанных элементов

#include <stdio.h>

int main(void) {
    double a, b, c, d;
    int counter = 0;
    FILE *IN;
    IN = fopen("input.txt", "r");
    if (IN == NULL) {
        printf("File not opened\n");
        return -1;
    }
    if (fscanf(IN, "%lf%lf%lf", &a, &b, &c) != 3) {
        printf("Not enough numbers\n");
        return -1;
    }
    while (fscanf(IN, "%lf", &d) == 1) {
        if ((a == 1) && (b == 2) && (c == 1) && (d == 3)) {
            ++counter;
        }
        a = b;
        b = c;
        c = d;
    }
    fclose(IN);
    printf("Number of fragments: %d\n", counter);
    return 0;
}


2. Массивы (векторы, таблицы, arrays)


Задача 2. Найти, сколько раз в последовательности
встречается фрагмент:
1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10

Hardcode constant values - зашивать в код константы

Фрагмент можно поместить в массив (таблица) - набор
переменных, имеющих общее имя и отличающихся по номерам
(индексам).

double array[20];
int n = 20;
array[0] = 1;
array[1] = 2;
...
array[19] = 10;
array[20] = 0; /* Ошибка, которую не находит компилятор */
if ((n < 0) || (n >= 20)) {
    printf("Invalid n value: %d\n", n);
    return -1;
}
array[n] = -1; /* Компилятор не знает, чему равно n */

Выход за границу массива - компилятором не диагностируется
C - для системного программирования

Компилятор:
Текст на C -> Текст на Ассемблер ->
Бинарный машинный код (загрузочный, или загружаемый файл)
Пример - a.out или a.exe

int i;
for (i = 0; i < 10; i++) {
    array[2 * i] = 1;
    array[2 * i + 1] = i;
}


#include <stdio.h>

int main(void) {
    double array[20], fragment[20];
    int counter = 0, i, equal;
    FILE *IN;
    IN = fopen("input.txt", "r");
    if (IN == NULL) {
        printf("File not opened\n");
        return -1;
    }
    for (i = 0; i < 10; i++) {
        fragment[2 * i] = 1;
        fragment[2 * i + 1] = i;
    }    /* Читаем 19 чисел */
    for (i = 0; i < 19; i++) {
        if (fscanf(IN, "%lf", &array[i]) != 1) {
            printf("Not enough numbers\n");
            fclose(IN);
            return -1;
        }
    }
    while (fscanf(IN, "%lf", &array[19]) == 1) {
        equal = 1;
        for (i = 0; i < 20; i++) {
            if (array[i] != fragment[i]) {
                equal = 0;
                break;
            }
        }
        if (equal) {
            ++counter;
        }
        for (i = 0; i < 19; i++) {
            array[i] = array[i+1];
        }
    }
    fclose(IN);
    printf("Number of fragments: %d\n", counter);
    return 0;
}


double x, y;
/* if (x == y) */
if ((x >= y) && (x <= y))


Задача 3. Отсортировать элемента массива

#include <stdio.h>

void sort(double ar[], int sz);

int main(void) {
    double array[1000];
    int i, size = 0;
    FILE *IN, *OUT;
    IN = fopen("input.txt", "r");
    if (IN == NULL) {
        printf("File not opened\n");
        return -1;
    }
    /* while (fscanf(...) == 1) {
        if (N >= 1000) { */
    for (i = 0; i < 1000; i++) {
        if (fscanf(IN, "%lf", &array[i]) != 1)
             break;
        ++size;
    }
    fclose(IN);
    sort(array, size); /* Имя массива == адрес массива */
    OUT = fopen("output.txt", "w");
    if (OUT == NULL) {
        printf("File output.txt not opened\n");
        return -1;
    }
    for (i = 0; i < size; i++) {
        fprintf(OUT, "%lf\n", array[i]);
    }
    fclose(OUT);
    return 0;
}


/* по возрастанию
Первый проход:
10 9  8 7 6 5 4 3 2 1
9  10 8 7 6 5 4 3 2 1
9  8 10 7 6 5 4 3 2 1
...
9  8  7 6 5 4 3 2 1 10

Второй проход:
9  8 7 6 5 4 3 2 1 10
8  9 7 6 5 4 3 2 1 10
...
8  7 6 5 4 3 2 1 9 10

Третий проход:
8 7 6 5 4 3 2 1 9 10
...
7 6 5 4 3 2 1 8 9 10


Девятый проход:
2 1 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
*/


/* Сортировка методом пузырька */
void sort(double ar[], int sz) {
    double tmp;
    int i, j;
    for (i = 0; i < sz - 1; i++) {
        for (j = 0; j < sz - 1 - i; j++) {
            if (ar[j] > ar[j+1]) {
                tmp = ar[j];
                ar[j] = ar[j+1];
                ar[j+1] = tmp;
            }
        }
    }
}
    

Задача 4. Отсортировать массив и определить,
есть ли в нем число x


#include <stdio.h>

void sort(double ar[], int sz);
int find(double ar[], int sz, double x);

int main(void) {
    double array[1000], x;
    int i, size = 0, found;
    FILE *IN, *OUT;
    IN = fopen("input.txt", "r");
    if (IN == NULL) {
        printf("File not opened\n");
        return -1;
    }
    /* while (fscanf(...) == 1) {
        if (N >= 1000) { */
    for (i = 0; i < 1000; i++) {
        if (fscanf(IN, "%lf", &array[i]) != 1)
             break;
        ++size;
    }
    fclose(IN);
    sort(array, size); /* Имя массива == адрес массива */
    printf("Input number\n");
    scanf("%lf", &x);
    found = find(array, size, x);
    printf("Found: %d\n", found);
    return 0;
}

/* Сортировка методом пузырька */
void sort(double ar[], int sz) {
    double tmp;
    int i, j;
    for (i = 0; i < sz - 1; i++) {
        for (j = 0; j < sz - 1 - i; j++) {
            if (ar[j] > ar[j+1]) {
                tmp = ar[j];
                ar[j] = ar[j+1];
                ar[j+1] = tmp;
            }
        }
    }
}

int find(double ar[], int sz, double x) {
    int first = 0, last = sz, middle, i;
    while (first + 1 < last) {
         middle = (first + last) / 2;
         if (ar[middle] == x)
              return 1;
         else if (x < ar[middle]) {
             last = middle;
         } else {
             first = middle + 1;
         }
    }
    if (first < last) {
        return (ar[first] == x);
    }
    return 0;
}