0 / 0 / 1
Регистрация: 08.12.2012
Сообщений: 32
|
|
1 | |
Одномерный массив. Циклический сдвиг вправо03.02.2013, 01:46. Показов 17636. Ответов 28
Метки нет (Все метки)
Дан массив A размера N и целое число K (1 ≤ K ≤ 4, K < N). Осущест-
вить циклический сдвиг элементов массива вправо на K позиций (при этом A перейдет в A , A — в A , …, A — в A ). Допускается использовать 1 K+1 2 K+2 N K вспомогательный массив из 4 элементов.
0
|
03.02.2013, 01:46 | |
Ответы с готовыми решениями:
28
Дано одномерный массив Х, размером 15 элементов. Провести циклический сдвиг элементов в массиве вправо на 2 позиции Одномерный массив. Циклический сдвиг влево Одномерный массив. Осуществить сдвиг вправо на k позиций Дан массив размера N. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k- индекс максимального элемента. |
0 / 0 / 1
Регистрация: 08.12.2012
Сообщений: 32
|
|
03.02.2013, 01:51 [ТС] | 3 |
0
|
Неэпический
|
||||||
03.02.2013, 02:04 | 4 | |||||
ShiftR - вправо
ShiftL - влево Shift - если shift меньше 0, то влево, иначе вправо
2
|
Модератор
8909 / 6678 / 918
Регистрация: 14.02.2011
Сообщений: 23,524
|
|
03.02.2013, 02:16 | 5 |
Сообщение было отмечено как решение
Решение
есть одно интересное решение приводить пока не буду
расскажу принцип для того чтобы циклически сдвинуть массив надо сначала перевернуть правую часть потом левую часть потом весь массив 12345678 надо сдвинуть на три элемента влево 1-32145678 2-32187654 3-45678123 надо сдвинуть на три элемента вправо 1 54321678 2 54321876 3 67812345 Добавлено через 56 секунд никакой дополнительной памяти все делается в этом же массиве
8
|
2 / 2 / 0
Регистрация: 26.12.2012
Сообщений: 17
|
||||||
10.02.2013, 16:13 | 6 | |||||
Написал реализацию циклического сдвига в обе стороны по способу ув. ValeryS. Буду благодарен за комментарии и исправления
1
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
04.03.2016, 20:49 | 7 |
Croessmah, ValeryS, Господа, прошу прощения за эксгумацию. ссылками занесло.Croessmah, как говаривала моей недоброй памяти учительница английского - "Шейман ю" Заводить массивы - это конечно же моветон. Когда вполне можно справиться и без них, воспользовавшись идеей взаимной простоты.
ValeryS, а вот твое решение меня весьма заинтриговало. Понять его смысл в данный момент мне не предоставляется возможным. Надеюсь, что утром тучки разойдутся, голова посвежеет, попробую разобраться
0
|
Байт
|
04.03.2016, 21:27
#9
|
0
|
Модератор
8909 / 6678 / 918
Регистрация: 14.02.2011
Сообщений: 23,524
|
|
04.03.2016, 21:33 | 10 |
честно говоря, это не мое решение, давным давно подсмотрел в какой-то книге
там еще пример был на пальцах, причем реально на пальцах, два кулака вместе, массив из 10 пальцев, сдвиг на 5 поворачиваешь левый кулак,потом правый, потом оба вместе, так чтобы кулаки поменялись местами посмотри вот эту тему, там несколько решений Функция циклического сдвига массива
0
|
Вездепух
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,078
|
|||||||||||
04.03.2016, 22:15 | 11 | ||||||||||
Эта задача всплывала здесь не раз (https://www.cyberforum.ru/post6813125.html) и, в частности, является одной из классических задач программирования (подробно разобрана у Бентли в "Жемчужинах программирования"). Разумеется, задача тривиальна если разрешается использовать дополнительный массив. Задача становится интереснее, если дополнительного массива использовать не разрешается.
У задачи три классических решения 1. Популярное и общеизвестное решение через три переворота (упоминается ValeryS выше в ответе #5) 2. Более хитрое решение через обмен неравных блоков (несложно видеть, что циклический сдвиг - это то же самое, что обмен местами двух блоков длины K и N-K) 3. Жонглирование - индивидуальная перестановка элементов сразу на правильные места со следованием циклов в перестановке Отдельно стоит заметить, что в С++ задача уже решена стандартным алгоритмом 'std::rotate', т.е. с этой точки зрения делать ничего не надо. В частности, в стандартной библиотеке MSVC++ 'std::rotate' для итераторов с произвольным доступом реализуется именно через три вызова 'std::reverse'. GCC, насколько я помню, делает это по-другому. А вот, например, возможная реализация по методу 2
2
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
05.03.2016, 00:17 | 12 |
Если эта задача является жемчужиной, то должен вас предупредить, жемчуг - фальшивый. Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.
Решение я знаю, сам придумал, ничего там особенного нет. Только надо взять НОД от N и step и устроить 2 простых вложенных цикла. Даже хотел это решение куда-то прикрепить, но с модераторами не удалось столковаться. А вот твое "кулачное" решение - я просто сейчас, по убожеству своей соображалки, не могу разобрать. Просплюсь - попробую.
0
|
Вездепух
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,078
|
|
05.03.2016, 00:30 | 13 |
Отнюдь!
Во-первых, авторитет классической книги мы тут оспаривать мы не будем. Задача действительно является жемчужиной. Во-вторых, в "Жемчужинах программирования" эта задача преподносится в большей степени для иллюстрации того, как формальная эффективность алгоритма (в данном случае - оцениваемая по количеству переносов единичных элементов массива в памяти) может существенно не согласовываться с фактической производительностью реализации этого алгоритма на современных кэшированных архитектурах. Формально оптимальным решением данной задачи является "жонглирующий" алгоритм, который берет элемент массива i и сразу же перемещает его в его финальную позицию (i + K) % N (я не буду расписывать все детали). Однако фактически такой алгоритм ведет себя очень плохо с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах (при достатчоном размере массива, разумеется). Вопрос поиска алгоримов и эффективных реализаций, которые хорошо себя ведут в таких ситуациях - вопрос весьма и весьма нетривиальный и, во многих случаях, неаналитический, т.е. решаемый только на чисто эмпирической основе. Кстати, ваше упоминание НОД свидетельствует именно о том, что вы изобрели какую-то вариацию того самого "жонглирующего" алгоритма
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
05.03.2016, 00:38 | 14 |
Чего это вдруг?
Вот уж Америка!
И впрямь, не стоит. Там деталей-то...
Простите, но в данном контексте это выглядит просто чушью.
0
|
Вездепух
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,078
|
|
05.03.2016, 00:43 | 15 |
Я так сказал.
Хм... Интересно, в каком таком "контексте" объективные факты могут вдруг "выглядеть просто чушью". Мне действительно интересно.
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
05.03.2016, 00:57 | 16 |
Убедили
Ну... Стоит только соетнести контекст решения простой задачи с вашими глубочайшими изысканиями... Понимаете, тема которую вы пытаетесь поднять, лежит совершенно в других плоскостях. Наверное, тема эта эта интересна. Но всему свое место, вы не находите?
Я неплохо знаю математику. И в программировании не совсем уж новичок. И книжечки читывал. Но в процитированной фразе понимаю 1 слово из трех. А уж связи между ними... Но тут же раздел - "для начинающих"
0
|
Вездепух
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,078
|
||||||
05.03.2016, 01:19 | 17 | |||||
Единственная тема, которую я тут "пытался поднять", это наличие как минимум трех несложных алгоритмов решения данной задачи in-place. А дальше, по какой-то мне не ясной причине, пошли какие-то странные посягательства на светлое имя этой задачи... Как истинный джентльмен, я должен был вступиться.
----- Кстати, если внимательно посмотреть на условие задачи, то можно заметить, что там четко оговорено ограничение на размер сдвига (не более 4) и при этом разрешается использовать дополнительный массив размером не более 4. Это говорит о том, что постановщик задачи не ищет жемчужин, а ожидает лобового тривиального решения
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
05.03.2016, 11:11 | 18 |
Да чего на нее смотреть! Школьная чушь! Если на это смотреть, так и вообще говорить не о чем.
Ваша правда
Добавлено через 9 часов 46 минут Как я понимаю, 3 - это величина сдвига, да? Но тогда это решение эквивалентно исходной задаче... Или я чего-то не допонял?
0
|
7 / 7 / 4
Регистрация: 08.01.2016
Сообщений: 50
|
|
20.07.2016, 13:12 | 20 |
Осталось код в голове смастерить=)
0
|
20.07.2016, 13:12 | |
20.07.2016, 13:12 | |
Помогаю со студенческими работами здесь
20
Дан массив размера N. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – индекс максимального элемента Циклический сдвиг вправо Циклический сдвиг массива вправо Реализовать циклический сдвиг вправо Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |