Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Здраствуйте уважаемые эксперты. помогите пожалуста решить задачу.
Условие такое:
На обруч равномерно наклеили числа от одного до N по возрастанию по часовой стрелки так, что в верхней точке обруча было число 1. Затем с обручем проделали M действий. Нужно определить положение обруча в конце.
Возможные операции:
1. поворот влево или вправо на несколько позиций -с этим вроде бы все понятно.
2. поворот относительно какой-то точки.
Во время выполнения любой операции центр обруча остается на месте.

Входные данные:
Первая строка - числа M и N.
Последующие M строк имеют следующий формат:
+X-поворот вправо на X позиций
-X-поворот влево (против часовой стрелки) на X позиций
Y-поворот относительно позиции Y, отсчитываемой по часовой стрелке с самого верхнего числа, позиция которого равна 1.

Выходные данные:
Hoop.out должен содержать N целых чисел - числа на обруче в итоговом положении по часовой стрелки, начиная с самого верхнего.

Пример:
hoop.in:
[Code]
5 3
+2
-3
3
[/Code]
hoop.out:
[Code]
1 5 4 3 2
[/Code]
Комментарий к примеру:
Исходное положение обруча: 1 2 3 4 5
После 1-ой операции: 4 5 1 2 3
После 2-ой операции: 2 3 4 5 1
После 3-ой операции: 1 5 4 3 2

Вопрос задал: Александр-446 (статус: Посетитель) Вопрос отправлен: 14 января 2007, 16:50 Состояние вопроса: открыт, ответов: 1.

Ответ #1. Отвечает эксперт: Вадим К

Да, сложная задача, ничего не скажеш. Я так понимаю с чтением файла проблем нет?
Тогда начнём. Эту задачу лучше решать если знать математику остатков (поля Галуа). Но всё знать не обязательно. Надо только уметь додавать и вычитать. Итак, основная идея этой матиматики в отличии от обычной, то что количество чисел строго ограничено. Например от 0 до 9. А что же делать, если результат сложения, к примеру, выходит за этот интервал? Тогда берут по модулю. В нашем случае по модулю 10. Приведу примеры, станет ясней. Будем считать на нашем диапазоне.
2+2 = 4 - это работает
5+5 = 0. Упс, необычно, но на самом деле 10 mod 10 = 0, где mod - взятие остатка.
4+8 = 2.
теперь вычитание
3-2 = 1
2-3 = 9
Если присмотреться, то это очень похоже на вращения вашего обруча
где первое слагаемое - текущая позиция, второе - на сколько сдвинуть а модуль - максимальное число на обруче. Но так как у нас счёт начинается с 1, то просто необходимо чуточку "модифицировать" нашу арифметику.
Что бы Вы не мучились, я написал готовую функцию, которая складывает (и вычитает, если второй аргумент указать с минусом)
function Add(a,b,m:integer):integer;
begin
result:=(a+b) mod m;
if Result<0 then
result:=result+m;
end;
С вращением первого типа разобрались. Осталось разобраться с вторым типом.
Давайте обозначем текущую точку (та, что вверху) буквой T, точку вращения - V. Теперь обозначим на кругу точку X. Именно она окажеться вверху после переворота. Здесь будет слудующая зависимость
(T-V) mod N = (V-X) mod N; Но если переписать в нашей арифметике, то это будет просто
X=V-(T-V) - только функцию прийдётся вызывать дважды!
Ну а дальше уже всё просто. Можно ещё и оптимизировать.

Ответ отправил: Вадим К (статус: Академик) Время отправки: 14 января 2007, 21:26 Оценка за ответ: 5

Мини-форум вопроса

Knjazev (статус: 3-ий класс), 14 января 2007, 17:53 [#1]: Да вот вам делать нечего. Займитесь делом, напишите троян, что-ли.

Александр-446 (статус: Посетитель), 16 января 2007, 04:27 [#2]: Я не понял при подстановки значений в формулу нужно брать номер позиции или саму позицию? С поворотами влево и вправо вроде все получилось а вот с этим... Короче мне всегда приходит значение "7" после вставки значений в формулу X:=V-(T-V), где V - это позиция вокруг которой поворачивается обруч а T - это верхняя позиция ("1" что ли всегда будет?).

Александр-446 (статус: Посетитель), 16 января 2007, 04:34 [#3]: Вот код программы: ... function rotate(v,r:integer):integer; begin y:=v-(r-v); end; begin ... val(s,t,error); rotate(t,1); for a:=y downto 1 do begin if a1[a]<>0 then begin inc(k); a2[k]:=a1[a]; end; end; if k for a:=y to n do a2[k]:=a1[a]; for a:=1 to n do a1[a]:=a2[a]; Там массивы a1 - это массив в котором должен быть конечный результат. А a2 это временный массив.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.