Вопросы к зачету

по курсу «Основы программирования»

2 семестр

2011/2012 учебный год.

Теоретические вопросы.

1. Понятие массива. Описание, инициализация массивов.

2. Алгоритмы обработки массивов, сортировка массивов. Сортировка массива “пузырьком”. Сортировка массива выбором. Сортировка массива включением.

3. Работа с элементами одномерных и двумерных массивов. Алгоритмы поиска в массивах (минимальный, максимальный элементы, индексы максимального и минимального элемента в одномерном и двумерном массивах).

4. Адреса переменных. Понятие указателя.

5. Адресная арифметика.

6. Безтиповый, нулевой указатели.

7. Указатели в параметрах функций.

8. Массивы и указатели.

9. Объявление строк.

10. Сравнение и сортировка текстовых данных.

11. Строки и указатели.

12. Обработка фрагментов строк.

13. Массивы динамической памяти.

14. Массивы указателей и моделирование многомерных массивов.

15. Организация памяти в процессорах 80х86 и указатели языка С.

16. Потоковый ввод-вывод. Открытие и закрытие потока.

17. Ввод-вывод символов и строк.

18. Двоичный (бинарный) режим работы с файлами на диске.

19. Строковый обмен с файлами на диске.

20. Режим форматированного обмена с файлами.

21. Позиционирование в потоке.

22. Ввод-вывод структур при работе с файлами на диске.

23. Директивы препроцессора. Замены в тексте. Препроцессорные операции в строке замещения.

24. Директивы препроцессора. Включение текстов из файлов.

25. Макроподстановки средствами препроцессора.

Практические задания.

Опишите математическую и информационную модели, алгоритм и блок-схему для решения задачи:

Задача 1.

ПРОСТАЯ ИГРА.

Дед Мазай и заяц играют в очень простую игру. Перед ними огромная куча одинаковых морковок. Каждый из них во время своего хода может взять из этой кучи любое количество морковок, равное неотрицательной степени числа 2, т.е. 1, 2, 4, 8, … Начинает игру либо Дед Мазай, либо заяц. Затем игроки ходят по очереди. Тот, кто возьмет последнюю морковку, тот и выигрывает.

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

Технические требования:

Имя входного файла: INPUT.TXT

Имя выходного файла: OUTPUT.TXT

Ограничение по времени тестирования: 2 секунды на один тест.

Формат входных данных:

Входной файл INPUT.TXT содержит единственное целое число N (N10²⁵⁰), задающее число морковок в начале игры.

Формат выходных данных:

Выходной файл OUTPUT.TXT должен содержать в первой строке цифру «1», если выиграет тот, кто ходит первым, или цифру «2» - в противном случае. Если игру выиграл тот, кто ходил первым, то во второй строке этого файла должно содержаться минимальное число морковок, которое должен взять игрок, выполнявший ход первым, чтобы гарантировать свою победу.

Пример файлов входных и выходных данных:

INPUT.TXT	OUTPUT.TXT
8	1 2

Указания к решению.

В этой игре 2 игрока делают ходы по очереди, и выигрывает тот, кто достигает некоторой намеченной в начале игры позиции. В данной игре позиция

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

Спраг и Грюнди предложили (соответственно в 1936 и 1939 годах) связывать с каждой игровой позицией неотрицательное число следующим образом:

1. выигрывающей позиции сопоставляем 0;

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

Образуем числа Спрага-Грюнди (SG) для этой игры:

• позиции 0 сопоставляем число 0, т.е. SG(0)=0;

• исходя из 1, можно получить 0 (поскольку мы имеем право взять одну морковку). Следовательно, SG(1) – наименьшее неотрицательное целое число, отличное от нуля, т.е. SG(1)=1;

• исходя из 2, можно получить 0 и 1. Значит SG(2) – наименьшее неотрицательное целое число, отличное от 0 и 1, т.е. SG(2)=2;

• пусть у нас имеется 3 морковки. Можно взять 1 или 2, в результате чего останутся 2 или 1 морковка, но не 0. Число SG(3) – наименьшее неотрицательное целое число, отличное от 1 и 2, т.е. SG(3) =0;

• из 4 можно получить позиции 0, 2 или 3 (если взять соответственно 4, 2 или 1 морковку). Следовательно SG(4) – это не 0 и не 2, значит SG(4)=1;

• из 5 получаем позиции 1, 3 или 4. Значит SG(5)=2.

Установим общий закон: SG(p) есть остаток от деления p на 3.

Кто же выигрывает в простой игре?

Если p, т.е. исходное количество морковок кратно трем, то выигрывает тот, кто ходит вторым, независимо от хода первого игрока. Если же первоначальное количество морковок не делится на 3, то выигрывает тот, кто делает ход первым, взяв за этот ход столько морковок, каков остаток от деления p на 3.

Поэтому алгоритм достаточно прост:

1. считать n – начальное количество морковок;

2. найти t – остаток от деления n на 3;

3. если t=0, то в результирующий файл записать число «2», иначе в результирующий файл записать «1» и t.

Однако, если мы посмотрим на формат файла входных данных, то увидим, что ограничение, накладываемое на число морковок в начале игры (N10²⁵⁰), выводит N за рамки числового типа. Выход из сложившейся ситуации может быть в следующем: считаем начальное количество морковок как строку (длина  256 символов) и переведем ее в число, равное сумме цифр. Для решения задачи используем признак делимости на 3 и тот факт, что остатки от деления на 3 исходного числа и его суммы цифр совпадают.

Задача 2.

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

Задача 3.

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

Задача 4.

Вычислить сумму n первых совершенных чисел (натуральное число называется совершенным, если равно сумме всех своих делителей, исключая само себя, например, 6=1+2+3). Организовать вывод результатов работы программы в файл.

Задача 5.

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

Задача 6.

КИНОТЕАТР.

X мальчиков и Y девочек пошли в кинотеатр и купили билеты на подряд идущие места в одном ряду.

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

Технические требования:

Имя входного файла: INPUT.TXT

Имя выходного файла: OUTPUT.TXT

Ограничение по времени тестирования: 1 секунда на один тест.

Формат входных данных:

Входной файл INPUT.TXT содержит два натуральных числа X и Y (X,Y100), задающие число мальчиков и девочек.

Формат выходных данных:

Выходной файл OUTPUT.TXT должен содержать какую-нибудь строку, в которой будет ровно X символов «М» (обозначающих мальчиков) и Y символов «Д» (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно.

Если рассадить мальчиков и девочек согласно условию задачи невозможно, в выходной файл должна быть записана строка «НЕТ РЕШЕНИЙ».

Примеры файлов входных и выходных данных:

INPUT.TXT	OUTPUT.TXT
5 5	МДМДМДМДМД
5 3	МДМДММДМ
100 1	НЕТ РЕШЕНИЙ