|
Заблокирован
|
||||||
Функция циклического сдвига массива26.06.2013, 21:13. Показов 51249. Ответов 50
Метки нет (Все метки)
Доброго времени суток,
есть задача - нужно написать функцию, которая сдвигает массив array[] размером size на shift элементов. соответственно, чтобы двигать вправо shift больше нуля, а влево наоборот. под буфер в цикле нельзя выделять целый массив, можно только одну переменную, тоесть нужно максимально оптимизировать использование памяти. сложность алгоритма не должна превышать O(N). не пишите пожалуйста код, помогите с логикой задачи. Раньше я делал вот так -
ткните носом в ошибки меня говнокодера. спасибо (-:
0
|
||||||
| 26.06.2013, 21:13 | |
|
Ответы с готовыми решениями:
50
Функция Циклического сдвига Функция циклического сдвига строк и колонок в матрице Ошибка в коде сдвига элементов массива |
|
Супер-модератор
|
|||
| 26.06.2013, 21:28 | |||
|
Вообще подобные задачи умиляют... Сдвинуть массив. Массив имеет фиксированные размеры. Куда девать элементы, которые "выходят за пределы"? И чем заполнять освобожающееся место?
0
|
|||
|
Заблокирован
|
|
| 26.06.2013, 21:31 [ТС] | |
|
я наверное криво описал по неопытности.
в функцию передаются array[] - массив int size - расмер массива int shift - размер сдвига сдвиг массива циклический -> int size = 6 array[size] = {1,2,3,4,5,6} int shift = 2 сдвиг на 2 вправо -> на выходе должно быть array[size] = {5,6,1,2,3,4}
0
|
|
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
|
|
| 26.06.2013, 21:40 | |
Сообщение было отмечено как решение
Решение
я уже описывал как то алгоритм циклического сдвига массива
код поищи на форуме а словами он выглядит так 1 переворачиваем одну часть массива 2 переворачиваем другую часть массива 3 переворачиваем весь массив например массив 123456789 нужно сдвинуть на три элемента влево 0) 123456789 1) 321456789 2) 321987654 3) 456789123 на три вправо 0) 123456789 1) 123456987 2) 654321987 3) 789123456
6
|
|
|
Заблокирован
|
|
| 26.06.2013, 21:41 [ТС] | |
|
так я не думал.
спасибо, буду пробовать так.
0
|
|
|
409 / 228 / 43
Регистрация: 10.02.2013
Сообщений: 780
|
|
| 26.06.2013, 21:51 | |
|
я б делал так:
1. нулевой элемент в временную переменную 2. и в циклу двигать элементы на место 0, 1,2 ну и тд. 3. в последний принудительно запишем с временной переменной число. поместив в цикл можно сдвинуть на сколько угодно позиций для сдвига в другую сторону делаем действия относительно последнего элемента
0
|
|
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
|
||||||||||||||
| 26.06.2013, 22:07 | ||||||||||||||
|
вот примерный код
учти не проверял пишу на коленке
здесь нет сдвига вправо и нет проверки если смещение больше чем размер но это не сложно добавить Добавлено через 2 минуты тогда уж так первые пять элементов во временный массив остатки сдвигаешь в начало из временного записываешь в конец Добавлено через 4 минуты
1
|
||||||||||||||
|
409 / 228 / 43
Регистрация: 10.02.2013
Сообщений: 780
|
|
| 26.06.2013, 22:08 | |
|
0
|
|
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
|
||
| 26.06.2013, 22:10 | ||
![]() посмотри на мою реализацию столько же сколько у тебя размер массива плюс одна переменная а во второй реализации вообще размер массива
0
|
||
|
409 / 228 / 43
Регистрация: 10.02.2013
Сообщений: 780
|
|
| 26.06.2013, 22:12 | |
|
ну вторую реализацию ты позже добавил, а я не видел
0
|
|
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
|
|||||||
| 26.06.2013, 22:18 | |||||||
![]() думал уже все знают как поменять две переменных не используя третью так же можно через + -
это всегда антогонизм или скорость или память если и то и другое нужно иши другие пути
0
|
|||||||
|
Модератор
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,973
|
||||||
| 27.06.2013, 04:44 | ||||||
|
Не по теме: Искренне надеюсь, что преподы, запрещающие использовать стандартную библиотеку, после смерти попадают в ад, в котором целую вечность переписывают реализацию этой самой libc, раз от раза всё быстрее и экономичнее... ;)
0
|
||||||
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
|
|
| 27.06.2013, 09:21 | |
|
@easybudda,
а как поведет себя прога если steps>count??? неправомерный доступ получим да и еще рекурсия ![]() какая нагрузка на машину( стек то он все таки не резиновый) и memmove внутри себя содержит тот же цикл оптимизированный правда, но для int эта оптимизация теряется Добавлено через 3 минуты пардон ![]() первое возражение снимается, чей то я ступил все будет в пределах массива
0
|
|
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
|
||
| 27.06.2013, 10:31 | ||
|
прочитал где то, давным давно в алгоритмах,в какой то книге там еще пример наглядный приводился на пальцах для удобства взят массив на 10 и сдвиг на 5 разворачиваешь левый кулак потом правый кулак и потом меняешь кулаки местами
0
|
||
|
Модератор
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,973
|
|||||||
| 27.06.2013, 11:35 | |||||||
0
|
|||||||
|
95 / 95 / 58
Регистрация: 04.10.2012
Сообщений: 189
|
||||||
| 27.06.2013, 17:51 | ||||||
|
@shurikspk, у вас идея заключается в том чтобы k раз применить функцию сдвига на 1.
Это плохая идея. У вас получается k*O(n) вместо O(n). И небольшое замечание для тех, кто будет читать тему: Такая перестановка переменных годится только для целого типа.
0
|
||||||
|
6 / 6 / 0
Регистрация: 28.06.2013
Сообщений: 15
|
|
| 28.06.2013, 11:57 | |
|
Я расцениваю это как задачу на логику, т.е. задача не максимальная производительность
, а использование одной ячейки памяти. Поэтому, думаю подойдёт следующий алгоритм(на примере 1,2,3,4,5,6 со сдвигом вправо на 2): общее количество Count=6; сдвиг Shift=2 массив значений data[6] количество которое нужно сдвинуть Count-Shift int nTemp; единственно доступная ячейка памяти for(int i=Count-Shift-1; i>=0; i--) { nTemp=data[i+Shift]; data[i+Shift]=data[i]; data[i]=nTemp; } виртуальный массив (без выделения памяти) первые Count-Shift элементов. Меняя с последнего элемента до первого (в виртуальном массиве) на элемент со смещением Shift из реального получим циклическое смещение начало 1,2,3,4,5,6 1,2,3,6,5,4 1,2,5,6,3,4 1,6,5,2,3,4 5,6,1,2,5,6 итого 4 перестановки. Аналогично смещение в другую сторону. Думаю идея ясна.
0
|
|
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
|
||
| 28.06.2013, 12:53 | ||
|
и размер массива этак 100 сколько будет перестановок
0
|
||
| 28.06.2013, 12:53 | |
|
Помогаю со студенческими работами здесь
20
Функция циклического сдвига элементов массива на заданное количество позиций Функция циклического сдвига побитово вправо Программа циклического сдвига элементов массива Описать процедуру циклического сдвига массива Ошиба циклического сдвига Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Символьное дифференцирование
igorrr37 13.02.2026
/ *
Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2).
Унарный минус обозначается как !
*/
#include <iostream>
#include <stack>
#include <cctype>. . .
|
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
|
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу,
и светлой Луне.
В мире
покоя нет
и люди
не могут жить в тишине.
А жить им немного лет.
|
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила»
«Время-Деньги»
«Деньги -Пуля»
|
|
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога
Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога
Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
|
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
|