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

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

Логин:
Пароль:
Регистрация | Забыли пароль?

Delphi.int.ru Expert

Другие разделы портала

Переход к вопросу:

#   

Статистика за сегодня:  


Лучшие эксперты

Подробнее »



Вопрос # 265

/ вопрос открыт /

Здраствуйте уважаемые эксперты. помогите пожалуста решить задачу.
Условие такое:
На обруч равномерно наклеили числа от одного до 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 Вопрос ожидает решения (принимаются ответы, доступен мини-форум)

Вопрос задал: Александр-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


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

Всего сообщений: 3; последнее сообщение — 16 января 2007, 04:34; участников в обсуждении: 2.
Knjazev

Knjazev (статус: 3-ий класс), 14 января 2007, 17:53 [#1]:

Да вот вам делать нечего. Займитесь делом, напишите троян, что-ли.
Александр-446

Александр-446 (статус: Посетитель), 16 января 2007, 04:27 [#2]:

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

Александр-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 это временный массив.

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

Версия движка: 2.6+ (26.01.2011)
Текущее время: 26 сентября 2020, 05:07
Выполнено за 0.02 сек.
Рейтинг@Mail.ru