Кафедра ИМО ПетрГУ | М. А. Крышень

Основы информатики и программирования

Содержание

Вводный курс по программированию для студентов 1 курса института математики и информационных технологий.

Консультации и дополнительные материалы: chat.cs.petrsu.ru, комната курса #course-inf2022:cs.petrsu.ru. Для входа используйте свой логин и пароль в вычислительной системе ИМИТ. Для доступа можно также использовать приложения, совместимые с протоколом Matrix (Element и др.), в таком случае при входе необходимо указать домашний сервер matrix.cs.petrsu.ru.

Список вопросов для зачета и экзамена

Задания лабораторных работ

Лабораторные занятия проводятся в дисплейных классах. Каждая работа засчитывается при удовлетворении всем требованиям протокола оценки и оценивается в зависимости от срока защиты. За каждую неделю задержки базовая оценка за работу уменьшается вдвое. Сроки указаны по концу недели, но фактический срок — это лабораторное занятие на соответствующей неделе (у каждой подгруппы в свой день).

Для получения зачета/допуска к экзамену должны быть сданы все работы.

Требования к защите работы

Защита работы включает в себя предоставление файлов исходного кода программы и вспомогательных файлов, демонстрацию работы и обсуждение с преподавателем.

Работающая программа является необходимым, но недостаточным условием сдачи лабораторной работы. Неспособность студента объяснить свое решение ведет к незащите работы.

  1. Программа удовлетворяет требованиям задачи
  2. Авторское решение (защищающий работу должен полностью понимать код)
  3. Качество кода
    • Контроль возвращаемых значений
    • Отсутствие потенциально опасных конструкций
    • Удобство сопровождения (препроцессорные средства)
  4. Интерфейс
    • Удобство и простота использования, следование принятым нормам
  5. Выдержаны требования стиля
    • Структурирование кода
    • Форматирование кода, отступы
    • Наименование программных объектов
  6. Код документирован
    • Присутствует заголовочный комментарий: автор, дата, описание, лицензия
    • Каждая функция снабжена комментарием с описанием аргументов и возвращаемого значения
    • Разумное внутреннее комментирование
  7. Организация проекта
    • Код программы и сопутствующие файлы размещены в отдельном каталоге
    • Подготовлен Makefile для автоматической сборки и очистки

1. Hello, Students!

4 балла до 18.09.2022
1 | 2 | 3 | 4 | 5 | 6 | 7

Пункты 1-7 выполняются вместе с инструктором.

  1. Начните работу в ОС GNU/Linux, используя выданные входное имя и пароль. В дисплейных классах установлен дистрибутив OpenSUSE, который нужно выбрать в меню загрузчика после включения компьютера.
  2. Открыв терминал, создайте в домашнем каталоге каталог inf, а в нем – каталог task1.

  3. В каталоге inf/task1 с помощью текстового редактора Emacs создайте файл main.c с следующим содержимым: 

    /**
 * main.c -- программа "Hello, students!"
 *
 * Copyright (c) 2022, First Last <student@cs.petrsu.ru>
 *
 * This code is licensed under MIT license.
 */

#include <stdio.h>

int main()
{
    /* Выводим приветствие */
    fprintf(stdout, "Hello, students!\n");

    return 0;
}
  4. Замените в заголовочном комментарии First и Last на ваши имя и фамилию, student@cs.petrsu.ru на ваш адрес электронной почты. Заголовочный комментарий должен быть также правильно оформлен в каждом исходном файле каждой следующей работы. Информация об условиях использования (MIT license) дана для примера и имеет значение, если код будет опубликован.

  5. Используя текстовый редактор, подготовьте файл Makefile (название с заглавной буквы) со следующим содержимым: 

    # цель по умолчанию (при вызове make или make task1)
# собираем программу task1 из объектного файла task1.o
task1: main.o
	gcc -g -O0 -o task1 main.o

main.o: main.c
	gcc -g -O0 -c main.c

# цель clean (при вызове make clean)
# удаляем программу и объектные файлы
clean:
	rm task1 *.o
  6. Соберите программу с помощью команды make. Команду make можно вызвать из Емакса: введите M-x compile (нажать "Alt+x", ввести "compile") и подтвердите вызов make.

  7. Проверьте работу программы в терминале: 

    user@host:~/inf/task1> ./task1
Hello, students!
user@host:~/inf/task1>

  8. Добавьте в файл Makefile цель без зависимостей indent для автоматического форматирования кода в стиле K&R, с использованием программы indent со следующими параметрами: 

    indent -kr -nut main.c
  9. Проверьте работу созданной цели: вызов make с аргументов indent должен привести к выполнению команды indent и исправлению форматирования файла, если оно было нарушено.
  10. Перезагрузите компьютер в ОС Windows.
  11. Используя клиент удаленного доступа PuTTY, настройте соединение с учебным сервером kappa (kappa.cs.petrsu.ru) и откройте терминальный сеанс.
  12. Удаленно отредактируйте текст программы в текстовом редакторе и выполните сборку.
  13. Подготовившись ответить на вопросы инструктора и продемонстрировать приобретенные навыки, сдайте работу.

2. Нужный этаж

4 балла до 2.10.2022
1 | 2 | 3 | 4 | 5 | 6 | 7

Предложена программа для вычисления номера этажа дома по номеру квартиры и числу квартир на каждом этаже. К сожалению, программа содержит ошибки.

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

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

  1. Подготовьте каталог task2 в каталоге inf.
  2. В каталоге inf/task2 с помощью текстового редактора создайте текстовый файл fixes.log для ведения журнала исправлений.

  3. В каталоге inf/task2 с помощью текстового редактора создайте файл main.c с следующим содержимым (не забудьте обновить заголовочный комментарий): 

    /**
 * floor.c -- программа для расчета нужного этажа
 *
 * Copyright (c) 2022, First Last <student@cs.petrsu.ru>
 *
 * This code is licensed under MIT license.
 */

#include<studio.h>

int Main()
{
    // Номер квартиры
    int flat_number;

    /* Число квартир на этаже */
    int flats_per_floor;

    /* Запрашиваем квартиру, в которой проживает адресат */
    printf("Введите номер интересующей квартиры: ");
    scanf("%d", &flat_number)

    /* Запрашиваем число квартир на этаже */
    printf("Введите число квартир на каждом этаже: ");
    scanf("%d", &flats_per_floor);

    /* Рассчитываем и выводим номер этажа */
    printf("Вам нужно подняться на %d этаж\n",
           flat_number / flats_per_floor, flat_number);

    return 0;
}
  4. Подготовьте файл Makefile для программы по аналогии с первым заданием.
  5. Попытайтесь собрать программу с помощью команды make.
  6. Ориентируясь по диагностическим сообщениям, последовательно идентифицируйте, зафиксируйте в журнале и исправьте недочеты, добиваясь отсутствия предупреждений и сообщений об ошибках.

  7. Убедившись в отсутствии предупреждений и ошибок, включите дополнительные проверки, добавив в файл Makefile ключи компилятора -Wall и -Wextra: 

    main.o: main.c
	gcc -g -O0 -c -Wall -Wextra main.c
  8. Исправив код и зафиксировав изменения в журнале, устраните новые предупреждения компилятора.
  9. Включите проверку строгого соответствия стандарту C89, добавив ключи компилятора -pedantic -pedantic-errors -ansi, объясните, что изменилось в диагностике, зафиксируйте в журнале.
  10. Измените используемую версию стандарта на более современную, заменив ключ -ansi на -std=c11, объясните, почему исчезло диагностическое сообщение.

  11. Запустив программу, убедитесь, что, для восьмой квартиры в доме с четырьмя квартирами на этаже, программа верно печатает номер этажа. 

    user@host:~> ./floor 
Введите номер интересующей квартиры: 8
Введите число квартир на каждом этаже: 4
Вам нужно подняться на 2 этаж
user@host:~>
  12. Подберите тестовые данные, на которых программа работает неверно.
  13. Проанализируйте и исправьте формулу для вычисления нужного этажа. Внимание: исправления должны затрагивать только формулу расчета нужного этажа. Для составления правильной формулы достаточно операций целочисленного деления (/), сложения и вычитания, условный оператор использовать не следует.
  14. Подготовьтесь ответить на вопросы инструктора и сдайте работу. Представляя результаты работы преподавателю вам необходимо продемонстрировать навыки:
    • уверенного чтения и интерпретации диагностических сообщений и использования диагностики для обнаружения дефектов в коде программы (на примере собранных в файле fixes.log диагностических сообщений);
    • планирования тестирования программы и подготовки достаточного количества тестовых наборов данных для проверки ее корректности (на примере тестовых данных для программы расчета нужного этажа).

3. Проблема 196

4 балла до 16.10
1 | 2 | 3 | 4 | 5 | 6 | 7

Пусть задано некоторое натуральное число. Будем применять к нему следующий алгоритм «перевернуть и сложить»:

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

Для некоторых начальных чисел палиндром будет получен довольно быстро, например, для числа 119 потребуется всего два шага:

  1. 119 + 911 = 1030
  2. 1030 + 301 = 1331

Однако, для произвольно выбранного натурального числа неизвестно, приведет ли когда-нибудь операция «перевернуть и сложить» к палиндрому. Первым таким числом является 196, поэтому задача получила название Проблема 196. Числа, для которых операция «перевернуть и сложить» никогда не даст палиндром, называются числами Лишрел. Так как не существует ни одного строго доказанного числа Лишрел, все числа, для которых даже с помощью современных компьютеров не удалось пока получить палиндром, считаются кандидатами в числа Лишрел. Последовательность кандидатов в числа Лишрел называется последовательностью Лишрел. В энциклопедии целочисленных последовательностей Нила Слоана последовательность Лишрел представлена под номером A023108.

Напишем программу для нахождения последовательности Лишрел среди чисел отрезка натуральных чисел, не превосходящих заданного значения, считая кандидатами в числа Лишрел все числа для которых не удается получить палиндром в пределах границ типа данных long. Гарантируется, что входное значение верхней границы отрезка находится в пределах границ типа данных long.

Декомпозиция задачи

Так как в задаче необходимо вывести кандидаты в числа Лишрел из отрезка натуральных чисел вплоть до заданного значения, то на первом шаге декомпозиции можно выделить две подзадачи:

  1. Получаем значение верхней границы рассматриваемой последовательности N.
  2. Выводим все кандидаты в числа Лишрел из отрезка 1, 2, …, N

Шаблон кода программы: 

int main()
{
    /* Получаем значение верхней границы рассматриваемой последовательности N */

    /* Выводим все кандидаты в числа Лишрел из отрезка 1, 2, ..., N */

    return 0;
}

Решение первой подзадачи:

  1. Определяем переменную для хранения верхней границы последовательности.
  2. Запрашиваем и читаем ее значение.

В коде программы: 

#include <stdio.h>

int main()
{
    /* Получаем значение верхней границы последовательности */
    long last_number;

    printf("Введите верхнюю границу отрезка поиска чисел Лишрел: ");
    scanf("%ld", &last_number);
 
    /* Выводим все кандидаты в числа Лишрел из отрезка
       1, 2, ..., last_number */

    return 0;
}

Решение второй подзадачи пока неочевидно. Будем полагать, что оно может быть получено в результате выполнения некоторой, пока не реализованной подпрограммы (функции) поиска и печати чисел-кандидатов show_lychrel_candidates(). Очевидно, что мы должны передать в эту функцию значение верхней границы поиска. При этом подпрограмма самостоятельно печатает числа-кандидаты и ничего не возвращает в качестве результата. Разместив прототип функции в начале файла исходного кода, создадим пустую заготовку функции – мы наполним ее содержанием на следующем шаге декомпозиции: 

#include <stdio.h>

/* Выводит все кандидаты в числа Лишрел из отрезка
   1, 2, ..., last_number */
void show_lychrel_candidates(long last_number);

/* Основная функция */
int main()
{
    /* Получаем значение верхней границы последовательности */
    long last_number;
    printf("Введите верхнюю границу отрезка поиска чисел Лишрел: ");
    scanf("%ld", &last_number);

    /* Выводим все кандидаты в числа Лишрел до last_number */
    show_lychrel_candidates(last_number);

    return 0;
}

void show_lychrel_candidates(long last_number)
{
    /* TODO: реализация функции */
}

Теперь рассмотрим задачу вывода всех кандидатов в заданном отрезке. Решение этой задачи сводится к решению подзадач:

  • Проверим каждое число в заданном отрезке:
    • если число является кандидатом в числа Лишрел, напечатаем его.

Таким образом, необходимо выполнить перебор чисел отрезка с проверкой каждого из них, то есть организовать цикл: 

void show_lychrel_candidates(long last_number)
{
    long number;
    
    /* Проверим каждое число в заданном отрезке: */
    for (number = 1; number <= last_number; number++) {
        /* Если оно является кандидатом в числа Лишрел, напечатаем его */       
        
    }
}

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

/* Проверяет, является ли number кандидатом в числа Лишрел */
int is_lychrel_candidate(long number);

/* Выводит все кандидаты в числа Лишрел из отрезка
   1, 2, ..., last_number */
void show_lychrel_candidates(long last_number)
{
    long number;

    /* Проверим каждое число в заданном отрезке: */
    for (number = 1; number <= last_number; number++) {
        /* Если оно является кандидатом в числа Лишрел, напечатаем его */
        if (is_lychrel_candidate(number)) {
            printf("%ld\n", number);
        }
    }
}

int is_lychrel_candidate(long number)
{
    return 1;
}

#include <stdio.h>

/* Выводит все кандидаты в числа Лишрел из отрезка
   1, 2, ..., last_number */
void show_lychrel_candidates(long last_number);

/* Проверяет, является ли number кандидатом в числа Лишрел */
int is_lychrel_candidate(long number);

/* Основная функция */
int main()
{
    /* Получаем значение верхней границы последовательности */
    long last_number;
    printf("Введите верхнюю границу отрезка поиска чисел Лишрел: ");
    scanf("%ld", &last_number);

    /* Выводим все кандидаты в числа Лишрел до last_number */
    show_lychrel_candidates(last_number);

    return 0;
}

void show_lychrel_candidates(long last_number)
{
    long number;

    /* Проверим каждое число в заданном отрезке: */
    for (number = 1; number <= last_number; number++) {
        /* Если оно является кандидатом в числа Лишрел, напечатаем его */
        if (is_lychrel_candidate(number)) {
            printf("%ld\n", number);
        }
    }
}

int is_lychrel_candidate(long number)
{
    return 1;
}

Теперь будем решать задачу проверки числа. Напомним алгоритм:

  1. Перевернем десятичную запись числа, т. е. получим новое число записью цифр исходного в обратном порядке.
  2. Сложим полученное число с исходным.
  3. Если полученная сумма не является палиндромом, т. е. числом

одинаково читающимся с начала и с конца, то повторим п. 1 для суммы.

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

  1. Вычисляем обращение числа, записав его цифры в обратном порядке.
  2. Если сумма числа и его обращения переполняет разрядную сетку, то считаем число искомым кандидатом и завершаем проверку, иначе складываем полученное число с исходным.
  3. Если полученная сумма не является палиндромом, т. е. числом одинаково читающимся с начала и с конца, то повторим п. 1 для суммы, иначе считаем, что проверяемое число не является числом Лишрел и завершаем проверку.

Очевидно, что алгоритм проверки представляет собой цикл, более того, так как проверка необходимости новой итерации осуществляется в конце (п. 3), то цикл с постусловием.

Предполагая существование функции reverse(), вычисляющей обращение аргумента, реализуем функцию is_lychrel_candidate(): 

int is_lychrel_candidate(long number)
{
    long n = number;
    long r = reverse(n);

    /* Повторяем ... */
    do {
        /* Если сумма числа и его обращения переполняет разрядную сетку, */
        if (n > LONG_MAX - r) {
            /* то считаем число искомым кандидатом и завершаем проверку */
            return 1;
        }
        /* иначе вычисляем новое значение, складывая число с обращением */
        n = n + r;

        /* Вычисляем обращение суммы */
        r = reverse(n);

    /* ... пока число не совпадает с обращением */
    } while (n != r);

    /* Считаем, что проверяемое число - не число Лишрел и завершаем проверку */
    return 0;
}

Алгоритм обращения числа и его реализация в виде функции reverse() будут разобраны на практическом занятии. Для использование константы LONG_MAX должен быть включен заголовочный файл limits.h.

Итоговый код программы: 

#include <stdio.h>
#include <limits.h>

/* Выводит все кандидаты в числа Лишрел из отрезка
   1, 2, ..., last_number */
void show_lychrel_candidates(long last_number);

/* Проверяет, является ли number кандидатом в числа Лишрел */
int is_lychrel_candidate(long number);

/* Возвращает обращение числа n */
long reverse(long n);

/* Основная функция */
int main()
{
    /* Получаем значение верхней границы последовательности */
    long last_number;
    printf("Введите верхнюю границу отрезка поиска чисел Лишрел: ");
    scanf("%ld", &last_number);

    /* Выводим все кандидаты в числа Лишрел до last_number */
    show_lychrel_candidates(last_number);

    return 0;
}

void show_lychrel_candidates(long last_number)
{
    long number;

    /* Проверим каждое число в заданном отрезке: */
    for (number = 1; number <= last_number; number++) {
        /* Если оно является кандидатом в числа Лишрел, напечатаем его */
        if (is_lychrel_candidate(number)) {
            printf("%ld\n", number);
        }
    }
}

int is_lychrel_candidate(long number)
{
    long n = number;
    long r = reverse(n);

    /* Повторяем ... */
    do {
        /* Если сумма числа и его обращения переполняет разрядную сетку, */
        if (n > LONG_MAX - r) {
            /* то считаем число искомым кандидатом и завершаем проверку */
            return 1;
        }
        /* иначе вычисляем новое значение, складывая число с обращением */
        n = n + r;

        /* Вычисляем обращение суммы */
        r = reverse(n);

    /* ... пока число не совпадает с обращением */
    } while (n != r);

    /* Считаем, что проверяемое число - не число Лишрел и завершаем проверку */
    return 0;
}

long reverse(long n)
{
    long r = 0;

    do {
        r = r * 10 + n % 10;
        n /= 10;
    } while (n > 0);

    return r;
}

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

Приведенная программа не лишена недостатков. Один из недостатков вам предстоит исправить.

План работы

  1. Подготовьте каталог task3 в каталоге inf.
  2. В каталоге inf/task3 с помощью текстового редактора, создайте файл исходного кода lychrel.c с приведенным выше кодом (не забудьте добавить заголовочный комментарий).
  3. Подготовьте файл Makefile для программы.
  4. Внимательно изучите приведенный выше анализ задачи и код программы.
  5. Выполните сборку и запуск программы, для входного значения 1000 сравните вывод программы с списком значений последовательности Лишрел в энциклопедии числовых последовательностей. Запишите (или сохраните в текстовом файле) количество чисел последовательности Лишрел, не превышающих 1000.
  6. Изучите инструкцию по отладке программ. Для запуска отладчика в Emacs можно использовать команду M-x gdb.
  7. Открыв программу в отладчике, поставьте контрольную точку на строку вызова функции проверки числа if (is_lychrel_candidate(number)) {.
  8. Запустите программу, введите в качестве верхней границы 200. Остановившись в контрольной точке, подмените средствами отладчика значение переменной number сразу на 196. Войдите в функцию is_lychrel_candidate() (Step Into). Отслеживая значения переменных n и r, выполняйте функцию по шагам, не входя в вызываемые функции (Next) пока не убедитесь, что 196 действительно является кандидатом в числа Лишрел. Запишите (или сохраните в текстовом файле) последние значения переменных n и r перед тем, как в программе было обнаружено переполнение суммы. Подумайте, на какую строку можно было бы поставить контрольную точку, чтобы быстрее получить искомые значения переменных n и r.
  9. Запустите программу, введите в качестве верхней границы 2000000000000000000 (двойка и восемнадцать нулей). Остановившись в контрольной точке, подмените значение переменной number сразу на 144444444444444448 (единица, шестнадцать четверок и восьмерка). Войдите в функцию is_lychrel_candidate() (Step Into). Отслеживая значения переменных n и r, выполняйте функцию по шагам, не входя в вызываемые функции (Next) пока не убедитесь, что 144444444444444448 не является числом Лишрел. Запишите (или сохраните в текстовом файле) значение полученного палиндрома.
  10. Запустите программу, введите в качестве верхней границы 2000000000000000000 (двойка и восемнадцать нулей). Остановившись в контрольной точке, подмените значение переменной number на 1999999999999999999 (единица, восемнадцать девяток). Войдите в функцию is_lychrel_candidate() (Step Into). Отслеживая значения переменных n и r, выполняйте функцию по шагам, убедитесь, что обращение числа может вызвать переполнение. Запишите (или сохраните в текстовом файле) первое некорректное обращение r переменной n.
  11. Скорректируйте функцию обращения числа reverse() так, чтобы в случае переполнения, функция возвращала специальное значение -1. Скорректируйте функцию проверки is_lychrel_candidate() так, чтобы в случае невозможности проверки по причине переполнения при обращении, функция возвращала, что проверяемое число является кандидатом в числа Лишрел.
  12. Подготовьтесь ответить на вопросы инструктора и сдайте работу. Представляя результаты работы преподавателю вам необходимо продемонстрировать следующие навыки:
    • владения методом структурной декомпозиции в решения задач и проектировании программ,
    • использования подпрограмм: определения, вызова, передачи параметров, использования возвращаемого значения,
    • отладки программы средствами отладчика GDB.

4. Гипотеза Гольдбаха

4 балла до 30.10
1 | 2 | 3 | 4 | 5 | 6 | 7

В 1742 г. немецкий математик Христиан Гольдбах в письме к Эйлеру сформулировал гипотезу о том, что любое нечетное число не меньшее семи можно представить в виде суммы трех простых чисел. В ответ Эйлер предложил более сильный вариант: любое четное число не меньшее четырех можно представить в виде суммы двух простых чисел. Эта гипотеза на сегодняшний день не подтверждена (то есть является так называемой «проблемой»), но и не опровергнута. С использованием современных вычислительных машин удалось проверить ее истинность для огромного набора значений. Вам предлагается реализовать собственную программу для проверки гипотезы.

Для решения задачи, требуется получить набор простых чисел вплоть до некоторого граничного \(n\).

Для теста простоты достаточно попытаться разделить тестируемое число только на те потенциальные делители, которые сами являются простыми числами. Тогда для построения набора простых чисел достаточно в цикле перебрать все значения от 2 до \(n\), выполнив с каждым следующую процедуру: если текущее значение не делится ни на одно число в наборе, содержащем уже найденные простые числа, оно добавляется в этот набор. Изначально набор полагается пустым.

Другой возможный вариант построения набора простых чисел — решето Эратосфена. Рассмотрим все натуральные числа, начиная с 2. Вычеркнем (просеем через решето) все числа до граничного значения \(n\), являющиеся произведениями 2 на натуральные множители 2, 3,… Среди невычеркнутых чисел найдем наименьшее — этим числом окажется 3. Вычеркнем (просеем через решето) все числа до \(n\), являющиеся произведениями 3 на натуральные множители 2, 3,… Среди невычеркнутых чисел найдем наименьшее — этим числом окажется 5. И так далее. Повторяя процедуру, мы вычеркнем все составные числа из рассматриваемого отрезка.

Имея набор простых чисел, можно построить удобную для целей задачи структуру данных — массив индикаторов простых чисел, т. е. массив, каждый элемент которого представляет 0 или 1, в зависимости от того, является ли индекс элемента простым числом. Приведем в качестве примера несколько начальных значений элементов массива индикаторов:

Индекс 0 1 2 3 4 5 6 7 8 9 10 11
Значение 0 0 1 1 0 1 0 1 0 0 0 1

План работы

  1. Подготовьте каталог task4 в каталоге inf.
  2. В каталоге inf/task4 с помощью текстового редактора, создайте файлы primes.c и Makefile.

  3. Напишите программу для печати всех простых чисел из промежутка от 1 до \(n\), где \(n\) не превосходит 10 000 000, на экране по возрастанию. В вашей программе должна быть предусмотрена как минимум одна вспомогательная функция для построения таблицы индикаторов простых чисел, реализующая решето Эратосфена и имеющая следующий прототип: 

    /* Заполняет массив индикаторов простых чисел от 0 до n включительно,
   primes — массив размера не менее n + 1. */
void calculate_primes(int primes[], int n);

    Важно, что функция calculate_primes() выполняет только построение массива индикаторов простых чисел, заполняя переданный в качестве параметра неинициализированный массив необходимыми значениями. Код печати набора простых чисел на экране должен быть размещен в функции main().

  4. Проверьте работу программы с различными входными данными.
  5. Вынесите функцию calculate_primes() в отдельный файл исходного кода calculate_primes.c, подготовьте заголовочный файл calculate_primes.h и модифицируйте Makefile для раздельной компиляции и последующей сборки.

  6. Напишите программу goldbach.c для проверки гипотезы Гольдбаха с использованием функции calculate_primes() из соответствующего модуля.

    Программа считывает со стандартного ввода пару натуральных четных чисел \(n\) и \(m\), где \(4 \le n < m < 10 000 000\) (десять миллионов). Гарантируется, что входные заданы корректно, дополнительная проверка не требуется. В стандартный вывод для каждого \(k\) из диапазона \([n, m]\) в порядке возрастания \(k\) вывести само \(k\), общее количество разложений, и одну пару простых чисел \(x\) и \(y\) через пробел, таких что \(x + y = k\). В случае, если разложений числа несколько, следует вывести пару с наименьшим \(x\). Для каждого значения диапазона разложение должно быть напечатано на отдельной строке. Разложения, отличающиеся только порядком следования чисел, различными не считаются.

    Для входных данных: 

    4 10

    должно быть выведно: 

    4 1 2 2
6 1 3 3
8 1 3 5
10 2 3 7
  7. Модифицируйте Makefile, добавив новую цель и псевдоцель all для сборки обеих программ. Таким образом, пользователь должен иметь возможность с помощью программы make собрать программу primes (make primes), программу goldbach (make goldbach) или сразу обе программы (make all или просто make).
  8. Подготовьтесь ответить на вопросы инструктора и сдайте работу. Обратите внимание, представляя результаты работы преподавателю вам необходимо продемонстрировать понимание:
    • использования вложенных циклов,
    • обработки хранимых в памяти целочисленных массивов,
    • реализации генератора простых чисел на основе решета Эратосфена,
    • сборки программы из нескольких модулей.

5. Англо-русский словарь

8 баллов до 20.11
1 | 2 | 3 | 4 | 5 | 6 | 7

Для представления словарей используются специальные форматы, упрощающие машинную обработку словарных статей, в частности, обеспечивающие возможность быстрого поиска. Рассмотрим представление словарной статьи в упрощенном формате DICT без сжатия. Ниже приведен фрагмент словаря Мюллера из проекта Mueller English-Russian Dictionary в этом формате: 

lesser

  [ˈlesə] _a. _attr. (_comp. от little) меньший; the lesser of two evils
  меньшее из двух зол; the Lesser Bear _астр. Малая Медведица
lesson

  [ˈlesn]

    1. _n.

      1) урок; to give (to take) lessons in English давать (брать) уроки
      английского языка; let this be a lesson to you пусть это послужит
      вам уроком

      2) нотация; to give (или to read) smb. a lesson прочесть кому-л.
      нотацию; проучить кого-л.

    2. _v.

      1) давать урок(и); обучать

      2) читать нотацию, поучать

Как видно из примера, словарная статья начинается переводимым словом с новой строки без отступов. Через строку следует транскрипция в соответствии с правилами Международного фонетического алфавита (IPA) и перевод, записанные с отступом в 2 пробела. Для многозначных слов структура несколько сложнее. Однако, в любом случае словарная статья заканчивается там, где начинается новая, то есть новым переводимым словом.

Вам необходимо реализовать программу поиска словарных статей в соответствии с заданным словом. Файл словаря приложен к заданию.

Программа, реализующая (довольно бессмысленный) поиск словарной статьи по ее порядковому номеру, представлена ниже. 

/**
 * dict1.c -- программа чтения словаря и печати словарной статьи по номеру
 *
 * Copyright (c) 2022, Student Name <student@cs.petrsu.ru>
 *
 * This code is licensed under MIT license.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAXLINE 1023

int main(int argc, char *argv[])
{
    /* Файл словаря */
    FILE* dict = NULL;
    
    /* Текущая строка */
    char current_line[MAXLINE + 1] = "";    
    
    /* Номер искомой статьи */
    int requested_entry_number;
    
    /* Номер текущей словарной статьи */
    int current_entry_number = 0;  
    
    /* Получаем номер словарной статьи для поиска */
    scanf("%d", &requested_entry_number);
    
    /* Открываем файл словаря */
    dict = fopen(argv[1], "r");
    
    /* Флаг соответствия текущей статьи условию отбора */
    int matched_entry = 0;
    
    /* Просматриваем словарь, печатая строки запрошенной статьи */
    while (fgets(current_line, MAXLINE, dict) != NULL) {
         /* Если первый символ строки не является пробельным разделителем,
            найдено начало новой словарной статьи */
         if (!isspace(current_line[0])) {
             current_entry_number++;
             /* Определяем, выполнено ли условие отбора для данной статьи */
             if (current_entry_number == requested_entry_number)
                 matched_entry = 1;
             else
                 matched_entry = 0;
         }         
         /* Печатаем строку, если она относится к запрошенной статье */
        if (matched_entry) {
             printf("%s", current_line);
         }
    }

    /* Завершаем работу с файлом словаря */
    fclose(dict);

    return EXIT_SUCCESS;
}

На вход программа получает словарь, заданный первым аргументом командной строки. Программа запрашивает номер словарной статьи и копирует на стандартный вывод все строки этой статьи. 

user@host:~> ./dict1 mueller.dict
2145
aerostat

  [ˈɛərəustæt] _n. аэростат; воздушный шар
user@host:~>
  1. Подготовьте каталог task5 в каталоге inf. Загрузите и разместите в нем файл словаря mueller.dict.
  2. В каталоге inf/task5 с помощью текстового редактора создайте файл dict1.c с приведенным выше содержимым и подготовьте файл Makefile.
  3. Выполните сборку, запустите и протестируйте программу, передавая имя файла словаря аргументом командной строки как показано в примере выше.
  4. Откройте файл словаря в текстовом редакторе и просмотрите содержимое, затем, используя знания о представлении символов в кодировке UTF-8, сделайте вывод, достаточно ли заданного в программе размера буфера для хранения очередной строки текста. Для подсчета максимального количества отображаемых символов среди строк текстового файла можно также воспользоваться командой wc -L.

  5. Исследуйте поведение программы в случае, когда аргумент командной строки, задающий путь к файлу словаря, опущен.

    Скорректируйте код программы таким образом, чтобы при задании неправильного количества аргументов, программа выводила бы диагностическое сообщение с подсказкой о корректном использовании и завершалась с кодом возврата, сигнализирующем о неуспешном выполнении (EXIT_FAILURE). Диагностические сообщения следует выводить в стандартный поток ошибок stderr. Пример сообщения: 

    Неправильное число аргументов.
Использование: dict1 файл_словаря

  6. Исследуйте поведение программы в случае, когда заданный файл словаря 1) отсутствует, 2) не может быть прочитан (например, можно указать файл /etc/shadow, который не доступен для чтения).

    Скорректируйте код программы таким образом, чтобы при любых ошибках файлового ввода-вывода, программа выводила бы соответствующее диагностическое сообщение и завершалась с кодом возврата, сигнализирующем о неуспешном выполнении (EXIT_FAILURE) . Для вывода сообщений об ошибках, полученных в результате вызова стандартных функций, используйте функцию perror().

  7. Вместо поиска словарной статьи по номеру реализуйте поиск и вывод набора словарных статей по шаблону. Шаблон слова считывается со стандартного ввода и представляет собой подстроку искомого слова. Например, для введенного пользователем шаблона or, среди найденных словарных статей, могут встретиться переводы слов orbital, doctor, word.
  8. Модифицируйте код программы, предполагая, что шаблон может начинаться со специального символа ^, обозначающего начало строки и оканчиваться специальным символом $, обозначающим конец строки, например:
    • для введенного пользователем шаблона ^or, среди найденных словарных статей, может встретиться перевод слова orbital, но не могут встретиться переводы слов doctor, word;
    • для введенного пользователем шаблона or$, среди найденных словарных статей, может встретиться перевод слова doctor, но не могут встретиться переводы слов orbital, word;
    • для введенного пользователем шаблона ^or$ программа найдет единственную словарную статью для слова or.

  9. Вынесите цикл обработки строк словаря и вывода отобранных статей в отдельную функцию, которая может иметь следующий прототип: 

    void show_entries(const char *pattern, FILE *stream);

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

  10. В каталоге inf/task5 создайте файл dict2.c — копию программы dict1.c, модифицируйте файл Makefile, добавив новую цель и псевдоцель all для сборки обеих программ.
  11. Модифицируйте код программы в файле dict2.c следующим образом.

    1. Программа должна загрузить данные словаря в предварительно выделенную область динамической памяти полностью. Так как файл словаря фактически занимает немногим менее 10 Мбайт, можно выделить 10 Мбайт, однако в коде все равно должна быть предусмотрена обработка ситуации, когда при чтении данных из файла обнаруживается, что выделенного объема недостаточно, то можно просто считать, что загрузка словаря завершилась неудачей. В программе должен быть предусмотрен вспомогательный буфер такого же размера для размещения результата поиска. Для загрузки данных должна быть предусмотрена отдельная функция: 

      char* load_dictionary(char *dictionary, FILE *stream);

      Функция получает два параметра: адрес буфера для размещения словаря и указатель, связанный с файлом словаря. Функция возвращает адрес буфера словаря или значение NULL, если загрузить словарь не удалось. Для чтения данных из файла рекомендуется использовать функцию fread().

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

      char* filter_dictionary(const char *pattern, const char *dictionary, char *entries);

      Функция получает три параметра: шаблон поиска, адрес буфера словаря и адрес буфера для размещения отобранных статей. Функция возвращает адрес буфера отобранных статей или значение NULL если поиск завершился неудачей.

    3. Все действия, связанные с выделением-освобождением памяти, открытием-закрытием файла, контролем ошибочных ситуаций, а также цикл ввода шаблонов и печати наборов словарных статей должны располагаться в основной функции main().
  12. Подготовьтесь ответить на вопросы инструктора и сдайте работу. Обратите внимание, представляя результаты работы преподавателю вам необходимо продемонстрировать навыки:
    • обработки нуль-терминальных строк с доступом к отдельным символам (байтам) по индексу и по указателю, а также использования функций, объявленных в заголовочных файлах ctype.h и string.h стандартной библиотеки;
    • обработки текстовых файлов, включая открытие и закрытие потоков ввода-вывода, чтение и запись данных, обработку ошибочных ситуаций;
    • обработки аргументов командной строки.

6. Калькулятор рациональных дробей

8 баллов до 4.12
1 | 2 | 3 | 4 | 5 | 6 | 7

Предлагается реализовать калькулятор для вычисления выражений в рациональных дробях.

Пользователь вводит строки выражений, которые имеют вид число оператор число (через пробел), где

  • число задано в формате n или n/d, где n — десятичное целое, d — положительное десятичное целое;
  • вместо числа может быть введено слово last — в этом случае будет использован результат вычисления предыдущего выражения;
  • оператор задан одним из символов арифметических операций +-*/.

Программа должна вычислять значения вводимых выражений и выводить результат в виде строки = число. Работа программы заканчивается при достижении конца файла на стандартном потоке ввода.

Пример: 

5/6 - 3/4
= 1/12
last * -20
= -5/3
13/6 + last
= 1/2
last + last
= 1

План работы:

  1. Подготовьте каталог task6 в каталоге inf.
  2. Разработайте модуль для представления рациональных чисел.

    • Разместите заголовочный файл модуля rational.h: 

      #ifndef RATIONAL_H
#define RATIONAL_H

typedef struct {
    int num;
    unsigned int denom;
} rational_t;

/*
 * Возвращает рациональное число, получаемое как результат деления
 * n на d.
 */
rational_t rational(long n, long d);

/*
 * Возвращает числитель рационального числа r.
 */
long rat_num(rational_t r);

/*
 * Возвращает знаменатель рационального числа r.
 */
long rat_denom(rational_t r);

#endif

      Прототипы функций rational(), rat_num() и ran_denom() определяют абстрактный тип данных рационального числа.

    • Создайте файл rational.c с реализацией этих функций. Функция-конструктор rational() должна выполнять сокращение дроби и учитывать знак числа в числителе, а также приводить нулевое значение числа к каноническому виду \(0/1\).

      Для поиска наибольшего общего делителя при сокращении дроби рекомендуется использовать алгоритм Эвклида.

  3. Разработайте модуль rat_math для выполнения арифметических операций с рациональными числами. Модуль должен предоставлять функции rat_add(), rat_sub(), rat_mul() и rat_div() и использовать только операции АТД рационального числа, избегая непосредственного обращения к полям структуры.

    Пример реализации функции суммирования: 

    rational_t rat_sum(rational_t a, rational_t b) {
    return rational(rat_num(a) * rat_denom(b) + rat_num(b) * rat_denom(a),
                    rat_denom(a) * rat_denom(b));
}
  4. Разработайте модуль rat_io, предоставляющий функции для преобразования из строки и для вывода рациональных чисел. Функция вывода не должна печатать знаменатель, если он равен 1 (число является целым). Для разбора строки может быть удобно использовать функцию sscanf().

  5. Разработайте программу калькулятора calc, используя модули rat_io и rat_math.

    Таким образом, разработанная программа будет включать 3 уровня абстракции:

    1. Реализация АТД рационального числа.
    2. Функции для работы с рациональными числами.
    3. Текстовый пользовательский интерфейс калькулятора.

  6. Обеспечьте сборку модулей для работы с рациональными числами в виде статической или (по желанию) динамической разделяемой библиотеки и использование этой библиотеки в программе calc.

    Статическая библиотека включается в исполняемый файл на этапе компоновки. Динамическая библиотека подключается при загрузке программы.

    1. Создайте подкаталог rational и перенесите в него исходные файлы модулей rational, rat_math и rat_io.
    2. Создайте в каталоге rational файл Makefile для сборки модулей библиотеки, напишите правила для сборки объектных файлов всех модулей.

    3. Добавьте правило для сборки библиотеки librational.

      Для создания статической библиотеки librational.a можно использовать правило: 

      librational.a: rational.o rat_math.o rat_io.o
	ar -rcs librational.a rational.o rat_math.o rat_io.o

      Команда ar создает архив с указанными объектными файлами.

      Или для сборки динамической библиотеки можно использовать: 

      librational.so: rational.o rat_math.o rat_io.o
	gcc -shared -o librational.so rational.o rat_math.o rat_io.o

      Для динамической библиотеки также необходимо добавить ключ -fPIC к командам gcc, которые используются для сборки составляющих библиотеку объектных файлов.

    4. В Makefile в базовом каталоге задания определите правило для сборки объектного файла calc.o и исполняемого файла calc. При сборке исполняемого файла нужно подключить созданную библиотеку: 

      calc: rational calc.o
	gcc -g -o calc calc.o -L./rational -lrational

      Эта команда будет работать как для статической, так и для динамической библиотеки.

    5. В Makefile для программы calc добавьте цель rational с вызовом make для сборки библиотеки в подкаталоге. 

      .PHONY: rational
rational:
	cd rational && $(MAKE)

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

  7. Проверьте сборку и выполнение программы. Подготовьтесь ответить на вопросы инструктора и сдайте работу.

    Если используется динамическая библиотека, при запуске программы возникнет ошибка: 

    $ ./calc
./calc: error while loading shared libraries: librational.so: cannot open shared object file: No such file or directory

    Решение — указать путь поиска для библиотек: 

    $ LD_LIBRARY_PATH=./rational ./calc

7. Прототип компьютерной игры

Все пункты: 8 баллов до 18.12.
Можно сдать только пункты 1-5 на 4 балла.
1 | 2 | 3 | 4 | 5 | 6 | 7

Лабораторная работа посвящена разработке прототипа небольшой компьютерной игры с использованием сторонней библиотеки SDL версии 1.2 (при желании можно портировать программу на актуальную версию SDL2). Приведенный код программы обеспечивает отрисовку управляемого игроком объекта (спрайта). Вашей задачей является расширение прототипа.

Для выполнения лабораторной работы необходим доступ к графическому дисплею. Запустить программу можно в среде рабочего стола в ОС GNU/Linux в дисплейных классах, на домашних компьютерах с ОС GNU/Linux, в том числе в виртуальной среде (можно использовать готовый образ ОС) в Windows или MacOS. В текстовом терминале запустить программу не получится.

При выполнении работы используйте документацию к библиотеке SDL, SDL_ttf и к другим библиотекам семейства (при необходимости).

  1. Подготовьте каталог task7 в каталоге inf и распакуйте в него содержимое архива spacexpolore.zip.
  2. Соберите программу с помощью make и выполните несколько раз, исследуйте код функций программы.
  3. Реализуйте ограничение перемещения корабля влево, вправо и вниз — пределами экрана, вверх — одной третьей высоты экрана.
  4. Подберите подходящий фоновый рисунок, реализуйте отрисовку фона перед каждой отрисовкой корабля. Используйте функцию SDL_SetColorKey() для установки ключевого цвета (цвета прозрачных пикселей).
  5. Реализуйте таймер, отсчитывающий секунды и отображение значения таймера в левом верхнем углу. По истечении минуты игровой процесс должен автоматически завершаться с сообщением об успешном прохождении уровня.
  6. Расширьте функциональность игры, добавив специальные спрайты — астероиды. Астероиды генерируются в случайных точках за пределами экрана и перемещаются по случайно выбранной прямолинейной траектории. При столкновении корабля с астероидом игра завершается с сообщением о провале миссии.
  7. Расширьте функциональность игры, добавив специальные спрайты — ресурсы. Игроку необходимо собирать ресурсы, уворачиваясь от астероидов. Реализуйте отображение количества собранных ресурсов в правом верхнем углу экрана.
  8. Реализуйте фиксацию успешного прохождения уровня игры в текстовом файле. Для каждой записи об успешном прохождении в файл должны записываться дата и время попытки, количество собранных ресурсов. При успешном завершении игры на экран должны выводиться несколько последних записей.
  9. При желании (необязательно) реализуйте возможность производить выстрелы для уничтожения астероидов по нажатию определенной клавиши.
  10. Подготовьтесь ответить на вопросы инструктора и сдайте работу.

Использование Emacs

Некоторые комбинации клавиш и команды редактора.

Обозначения: C — Control, M — Meta (клавиша Alt), S — Shift, SPC — пробел, ESC — Escape. Дефис — одновременное нажатие, пробел — последовательное нажатие. Комбинации чувствительны к раскладке клавиатуры (нужно использовать английскую).

Команды, требующие дополнительных аргументов или подтверждений, будут запрашивать их в минибуфере внизу экрана. Для подтверждения действий, которые потенциально могут привести к потере информации, может потребоваться ввод ответа "yes" (слово целиком). Те же команды, но вызванные из меню мышкой, вместо запросов в минибуфере могут использовать графические диалоги.

  • Работа с файлами:
    • C-x C-f — открыть или создать файл,
    • C-x C-s — сохранить файл,
    • C-x s — сохранить все файлы (в минибуфере будут запрошены подтверждения).
  • Редактирование:
    • C-SPC — начать выделение текста,
    • M-w — копировать,
    • C-w — вырезать,
    • C-k — вырезать от курсора до конца строки (можно нажать несколько раз, чтобы вырезать несколько строк сразу),
    • C-y — вставить,
    • M-y — вставить из истории ранее скопированных фрагментов или заменить только что вставленный текст.
    • C-x u или C-/ — отменить предыдущее изменение,
    • M-; закомментировать выделенное или начать новый комментарий,
    • C-s поиск строк,
    • M-% или ESC % — поиск и замена ("%" нужно вводить с Shift, вариант с Escape нужен, если Alt+Shift используется для переключения раскладок),
    • TAB — выравнивание кода (отступы), автодополнение.
  • Окна и буферы:
    • C-x 2 — разделить окно горизонтально,
    • C-x 3 — разделить окно вертикально,
    • C-x 1 — убрать разделение окна,
    • C-x o — перейти к другому окну (части разделенного экрана),
    • C-x b — выбрать другой буфер (открытый файл), также можно использовать меню "Buffers",
    • C-x k — закрыть буфер.
  • Дополнительные команды:
    • M-x — найти и вызвать любую команду редактора по имени (например, если для команды не назначена отдельная комбинация клавиш),
    • M-x compile — вызов инструмента сборки программы (make),
    • M-x shell — открыть командный интерпретатор (shell),
      • C-c C-c — прервать выполнение текущей команды в шелл (например, остановить выполнение зациклившейся программы),
    • M-x gdb — запуск отладчика,
    • M-x man — просмотр страниц руководства man (информация по командам шелл, функциям Си, заголовочным файлам и др.),
    • M-x info — справка info (подробная структурированная документация, как сайт или книга).
  • Разное:
    • C-g — отмена текущего действия (например, убрать запрос в минибуфере),
    • C-x C-c — выход из Emacs, в минибуфере могут появиться запросы о сохранении файлов и завершении работающих встроенных процессов (шелл, отладчик).

Это только вершина айсберга. См. также:

Командная оболочка

Получить доступ к командной оболочке можно:

  • запустив приложение «Терминал» в системе GNU/Linux,
  • выполнив команду M-x shell в Emacs,
  • подключившись к терминальному серверу с помощью программы удаленного доступа (PuTTY).

Когда командная оболочка готова для ввода команд пользователя, отображается приглашение интерпретатора команд, которое выглядит примерно следующим образом (конкретный вид зависит от дистрибутива и настроек оболочки): 

student@kappa:~/inf/task1>

Здесь student — имя пользователя, kappa — имя компьютера, который будет выполнять команды, ~/inf/task1 — текущий каталог, относительно которого будут рассматриваться указанные в командах пути и имена файлов. Символ ~ (тильда) обозначает домашний каталог пользователя (ваши файлы хранятся в нем и в его подкаталогах), символ / разделяет элементы пути — последовательности вложенных каталогов.

Во многих системах по умолчанию используется интерпретатор команд bash, предоставляющий полноценный язык программирования с переменными, функциями и управляющими конструкциями, но простой вызов команды сводится к вводу строки вида команда аргумент1 аргумент2 ... аргументN. Аргументы (если они заданы) разделяются пробелом. Ввод команды завершается нажатием «Enter».

Обычно аргументы задают имена файлов, к которым будет применяться команда, или меняют режимы работы команды. Во втором случае аргументы называются ключами и обычно (так принято, но возможны исключения) начинаются с символа - (дефис или минус).

Например, в Makefile из задания 1 используется следующая команда для компиляции программы: 

gcc -g -O0 -с main.c

Здесь gcc — вызов компилятора, -g -O0 -c — ключи, определяющие параметры его работы, main.c — исходный файл, который будет обрабатываться.

Некоторые команды:

  • pwd — вывод полного пути к текущему каталогу;
  • ls — вывод списка файла в текущем каталоге:
    • ls -a — включая и скрытые файлы,
    • ls -l — с дополнительной информацией о каждом файле,
    • ls -a -l или ls -al — использовать оба предыдущих ключа,
    • ls каталог — вывод списка файлов в указанном каталоге,
    • ls -al каталог — и так можно;
  • mkdir каталог — создание каталога;
  • cd каталог — переход в указанный каталог (сделает его текущим);
  • cd или cd ~ — переход в домашний каталог;
  • mv файл1 файл2 — переименование файла из файл1 в файл2;
  • cp файл1 файл2 — копирование файла;
  • rm файл — удаление файла;
  • rmdir каталог — удаление пустого каталога;
  • rm -r каталог — удаление каталога вместе со всем его содержимым (без лишних вопросов и не в корзину — используйте осторожно!);
  • cat файл — вывод содержимого файла;
  • diff файл1 файл2 — вывод различий между двумя текстовыми файлами.

Чтобы не тратить время на ввод длинных путей и имен файлов, используйте автодополнение (клавиша TAB).

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

  • emacs main.c — запустить редактор Emacs для редактирования указанного файла (может работать в текстовом режиме);
    • emacs -nw main.c — то же, но принудительно в текстовом режиме (работать в терминале, не создавать окно, даже если это возможно);
  • firefox https://cs.petrsu.ru/ — открыть сайт в браузере;
  • libreoffice document.doc — открыть документ в текстовом процессоре…

Часто команда — это исполняемый файл программы, расположенный в одном из специальных каталогов. Аналогично можно запустить и вашу программу, созданную при выполнении очередной лабораторной работы, но поскольку соответствующий исполняемый файл расположен не в одном из таких каталогов, нужно явно указать к нему путь. Путь к текущему каталогу можно задать просто символом . (точка). Таким образом, команда для запуска программы из задания 1 — 

./task1

См. также: учебное пособие «Операционные среды, системы и оболочки».

Отладка программы

Отладкой называется процесс локализации и устранения ошибок в коде программы. Как правило отладке предшествует тестирование программы, в ходе которого выясняется, что программа содержит дефекты:

  • результаты выполнения программы на контрольных примерах (тестовых данных) отличаются от эталонных;
  • программа демонстрирует непредусмотренное поведение (например, аварийно завершается).

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

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

Отладчик GDB

GDB (GNU Debugger) — отладчик проекта GNU, поддерживающий множество языков программирования, включая язык Си, различные аппаратные платформы и форматы исполняемых файлов.

Отладчик GDB предоставляет командный интерфейс пользователя, но также используется и для внутреннего обеспечения процесса отладки многими интегрированными средами разработки и специализированными приложениями с графическим интерфейсом.

Для запуска GDB можно использовать:

  • команду gdb исполняемый_файл в терминале,
  • команду M-x gdb в редакторе Emacs (будет предложено уточнить команду отладчика, имя исполняемого файла обычно подставляется автоматически — нужно только подтвердить нажатием Enter). Emacs предоставляет одновременно графический интерфейс для отладки и возможность непосредственного ввода команд отладчика.

Не забудьте сохранить и откомпилировать программу перед запуском отладчика! Отлаживаемый исполняемый файл должен соответствовать текущей версии исходного кода, иначе код, который показывает отладчик, не будет соответствовать тому, что выполняется на самом деле.

Основные команды GDB:

  • break строка — поставить точку останова на указанную строку программы (номер или имя функции),
  • run — запуск программы и ее выполнение до первой точки останова.
  • next или n — выполнить следующую инструкцию программы (вызов функции выполняется как одна инструкция),
  • step или s — выполнить следующую инструкцию программы с заходом в вызываемую функцию,
  • continue или c — продолжить выполнение программы до следующей точки останова,
  • print выражение — показать значение выражения (обычно в качестве выражения используется имя переменной),
  • display выражение — показывать значение выражения на каждом шаге,
  • set var переменная=значение — изменить значение переменной,
  • list — вывести код программы,
  • help команда — показать справку по команде отладчика,
  • quit — завершить работу отладчика.

См. также: инструкция по использованию отладчика.

Вычислительная система и средства разработки

Справочная информация

Литература

  • Керниган, Б., Ритчи, Д. Язык программирования Си. — 2-е изд.: Пер. с англ. — М.: Вильямс, 2009.
  • Stallman, R., Rothwell, T. GNU C Language Introduction and Reference Manual. 2022.
    Копия книги

Использованы материалы курса «Основы информатики и программирования», который разрабатывался А. В. Бородиным до 2021 г.

Автор: М. А. Крышень

Created: 2023-01-09 Пн 13:00

Emacs 28.2 (Org mode 9.6)

Validate