3. Приведенный ниже код циклически сдвигает массив х[п] влево на rotdist.
for I = [0 . gcd(rotdist. n ))
/* сдвиг i-x элементов блоков */ t = x[i ]
J - i 1 oop
k = j + rotdist if k >= n k -= n if k == i break x[j] = x[k] j - k x[j]
Наибольший общий делитель rotdist и n равен количеству циклов перестановок (в терминах современной алгебры это число равно количеству классов смежности в группе перестановок, обусловленных циклическим сдвигом).
Следующая программа взята из раздела 18.1 книги Гриса «Наука программирования» (Gries, Science of Programming). В ней предполагается, что функция swap(a/ b, т) меняет местами элементы х[а..а+т-1] и х[Ь..Ь+т-1].
if rotdist == 0 | | rotdist == n return
i = p = rotdist j = n - p whi1e i 1= j /* инвариант
x[0 p-i ] двигать не нужно x[p-i p-1 ] = а (нужно поменять с b) x[p p+j-1] = b (нужно поменять с a) x[p+j n-1 ] двигать не нужно */ i f i > J
swap(p-i. p, j) i -= J e 1 se
swap(p-1 . p+j -1 . i )
J i swap(p-i . p. i)
Понятие инварианта цикла описано в главе 4.
Этот код изоморфен приведенному далее (медленному, но верному) алгоритму Евклида вычисления наибольшего общего делителя i и j. Предполагается, что эти числа отличны от нуля.
int gcd(1nt i. int j) whi1e i != j i f i > J i -e J el se j -= i return i
Грис и Миллс исследуют все три алгоритма циклического сдвига в статье «Обмен участков» (Gries, Mills, Swapping Sections, Cornell University Computer Science Technical Report 81-452).
Опубликовал vovan666
April 17 2013 00:06:24 ·
0 Комментариев ·
4402 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.