Срок выполнения задания:
по 31.05.2026
Написать программную реализацию решения задачи про круговой поезд с лампочками и провести вычислительный эксперимент для определения временной сложности
Формулировка задачи про поезд:
Представьте себе замкнутую по окружности железную дорогу. По ней едет поезд, последний вагон которого скреплён с первым так, что внутри можно свободно перемещаться между вагонами. Вы оказались в одном случайном вагоне и ваша задача — подсчитать их общее количество. В каждом вагоне можно включать или выключать свет, но начальное положение переключателей случайное и заранее неизвестно. Все вагоны внутри выглядят строго одинаково, окна закрыты так, что невозможно посмотреть наружу, движение поезда равномерное. Помечать вагоны как-либо, кроме включения или выключения света, нельзя. Количество вагонов конечно.
В данной реализации используется класс Train, в котором содержится связанный список вагонов (Car)
class Train {
private:
struct Cage {
bool light; // состояние лампочки
Car *next;
Car *prev;
};
int countOp; // счетчик шагов (число переходов из вагона в вагон)
Car *first; // точка входа в поезд (первый вагон)
public:
Train();
void addCar(bool light); // добавить вагон с начальным состоянием лампочки
int getLength(); // вычислить длину поезда
int getOpCount(); // вернуть число переходов (из вагона в вагон)
};Поясним основные элементы класса Train. Поезд организуется как двусвязный циклический список из вагонов (структура Car). В каждом вагоне мы храним true, если свет включен и false, если выключен. Поезд может состоять минимум из 2-х вагонов.
При добавлении в поезд вагона мы передаем параметром состояние его лампочки (addCar). Метод getLength вычисляет длину поезда самым простым (и нерациональным способом!) Движения человека по поезду должны учитываться в переменной countOp, в которую заносятся все шаги из вагона в вагон.
Метод getOpCount возвращает общее число шагов.
Модифицировать код функции main.cpp для проведения вычислительного эксперимента. Необходимо построить график:
Зависимость числа операций от длины поезда n
- если все лампочки выключены
- если все лампочки включены
- если распределение включенных/выключенных лампочек случайное
Построить графики с линиями тренда и сохранить в файле plot.png
В проект должен входить заголовочный файл include/train.h. Файл src/train.cpp должен содержать реализацию методов класса. Файл src/main.cpp содержит пример использования класса Train. Файл result/plot.png содержит результаты вычислительного эксперимента.