Wednesday, December 19, 2012

Три задачи по программированию - решение

Полные условия задач, находятся тут.

1. Бесконечная ж/д с 2 паровозами с парашютами.
2. Запрограммировать лифт.
3. Отсортировать большой файл в бесконечной файловой системе.

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


Ниже есть продолжение.

Подсказки.

1. Бесконечная ж/д с 2 паровозами с парашютами.

2a. Попробуйте решить упрощённый вариант сначала без ограничения языка, чтобы получить некоторое начальное представление (спорная подсказка).

2b. Посмотрите на используемые ваши средства выражения языка. "Считать шаги" тоже нельзя.

2c. Код программы должен быть конечен (это относится к "считать шаги").

2d. Попробуйте другой подход. Помните, что код в обоих паровозах должен быть идентичен, однако у вас есть if(isOtherParachuteFound)...

2e. Попытайтесь сначала найти парашют другого паровоза...

2f. Как после этого, найти другой паровоз? Запомните, что вы делали после того, как нашли парашют.

3a. Каким образом, вы можете гарантировано найти парашют.

3b. Если вы будете идти в одну сторон, то один из паровозов обязательно наткнётся на другой парашют.

3c. Где при этом будет второй паровоз?

3d. Как ему можно "сообщить", о том, что вы только нашли его парашют?

4. Вместо того чтобы увеличить скорость паровоза в два раза, можно уменьшить первоначальную скорость паровоза.

2. Запрограммировать лифт.

1. Тут главное понять условие задачи, и что от вас требуется. Представьте обычный дом с одним лифтом. Вы подходите к лифту и хотите добраться до какого-то этажа. Как лифт себя ведёт. Почему? Сымитируйте его действия.

2. Представьте конкретные примеры. Ниже приведены несколько, читайте по одному и возвращайтесь к решению задачи, придумывайте свои примеры:

а) Вы стоите на входе. Лифт находится на 5 этаже. Вам надо на 2. Вы нажимаете "вверх". Лифт опускается до 0 этаже. Вы входите, нажимаете 2, лифт поднимается до 2.

б) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно выйти из здания.

в) Развёрнутый б) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно выйти из здания. Вы нажимаете "вниз". Лифт доезжает до 7 этажа, из него там выходит другой человек, затем он едет в вам на 4 этаж, вы нажимаете на кнопку 0, лифт едет вниз до входа из здания, вы выходите.

г) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно на 6 этаж.

д) Развёрнутый г) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно на 6 этаж. Вы нажимаете "вверх". Лифт доезжает до 4 этажа, останавливается, вы туда заходите, нажимаете на 6. Лифт продолжает ехать вверх, доезжает до 6 этажа, останавливается, вы выходите. Лифт продолжает ехать до 7 этажа, чтобы довести другого человека.

е) Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно на 8 этаж.

ж) Структура данных 2 связанных списка с указателями в начало и конец списка (Deque).

з) Зная ж) перечитайте д) и е). Всё должно стать очевидным.

3. Отсортировать большой файл в бесконечной файловой системе.

1. Фраза При этом a/b не является O(1) является в условии задачи является своего рода подсказкой.

2. Игнорируйте на данном этапе I\O. Вас ограничили в оперативной памяти, но у вас сколько угодно места на диске. Используйте диск.

3. Вы можете отсортировать 10Mb чисел.

4. Вы можете получить 2048 "стопок" (файлов!) по 10Мb чисел в каждом.

5. Вы можете отсортировать каждую "стопку чисел" по отдельности.

6. Две "стопки чисел"=две колоды карт, которые нужно слить в одну.

7а. Напишите два списка отсортированных чисел, подумайте как их можно объединить в один список.

7б. Это можно сделать за O(n+m), где n и m - длины списков. При этом если a/b не является точной степенью 2 n может в точности не равнятся m и может быть, что количество списков будет нечётным. Но это ничего не меняет. Подумайте почему.

7с. За сколько операция объедений списка можно слить все "стопки чисел" в одну "стопку"?

8. Вспомните про I\O. Подумайте как можно уменьшить перемещение головки записи диска по всему диску (количество r\w при этом практически не изменится).

9. Нужно выбрать "стопку" с наименьшим "верхним" числом (среди всех "верхних" чисел). Следующая "стопка" должна быть со "следующим" "верхним" числом. Как при этом не потерять связь между числом и "стопкой" из которой он был взят?

10. Вспомните, что k=a/b=2048 "большое число" (не константа), как в таком случае, можно сделать пункт 8 за O(k*log k)?


No comments:

Post a Comment