Re: сдвиг массива

From

Sergey Andrianov (2:5020/1507.400)

To

Stanislav Tihohod

Date

2002-05-03T13:49:04Z

Area

RU.ALGORITHMS

Здравствуй, Stanislav!

Однажды 26-Apr-02  в 19:40   Stanislav Tihohod (2:5030/448.3)
написал       All    по поводу
-=-   сдвиг массива  -=-

ST> Я, наверное, тормоз, но не могу понять, как можно сдвинуть массив из N 
ST> элементов на M позиций за количество пересылок O(n)? Kоличество 
ST> дополнительной памяти ограничено несколькми ячейками. Можно пойти по N с 
ST> шагом M, но тогда если N и M - не взаимно простые, получаем цикл. Понятно, 
ST> что можно сделать несколько заходов, пока число передвинутых элементов не 
ST> будет N, но я не могу понять, как связано число заходов и сдвиг начала 
ST> очередного с N и M. 

   Начнем с того, что N элементов на M позиций можно сдвинуть только в массве, длина которого не меньше N+M-1. Дальше, думаю, элементарно.
   Если же имеется в виду циклический сдвиг, то делаешь именно так, как сам и предложил, только сдвиги придется начинать НОK раз по N/НОK элементов.

                  До свидания,  в  13:41 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)