С++: сдвиг в динамическом массиве

[zzzt]

Итак. Мне нужно получить от пользователя массив на любое количество элементов (N), а потом сделать сдвиг вправо (K). K естественно задается пользователем, но по условию K строго меньше N.
Особенность: сдвиг "циклический" - элементы с правого края при нехватки "места" переносятся в начало массива.

Нет, не думайте, я не прошу написать программу за меня. Я спокойно написал программу по получению от пользователя массива любого размера. Также я подумал, что будет удобно сдвигать числа при помощи второго, пустого массива идентичного размера. Вот:

#include <stdio.h>
#include <fstream.h>
#include <alloc.h>
#include <conio.h>

void main ()
{
clrscr();
int *A,N,K,i,*B;
printf("  Введите количество элементов массива: ");
scanf("%d",&N);
A=(int*)malloc(N*sizeof(int));
B=(int*)malloc(N*sizeof(int));
for(i=0;i<N;i++)
{
printf("  Введите A[%d]= ",i); scanf("%d",&A[i]);
}
printf("\n\n  МАССИВ:\n");
for(i=0;i<N;i++)
{
printf("  %d",A[i]);
}
printf("\n\n Введите число сдвигов [=>]: "); scanf("%d",&K);
if(K>=N||K==0) printf("  !!! Сдвиг невозможен");
for(i=0;i<N;i++)
{
if(i==0) B[i]=A[N-1];
else B[i]=A[i-K];
}

printf("\n\n  МАССИВ:\n");
for(i=0;i<N;i++)
{
printf("  %d",B[i]);
}

free(B);
free(A);
getch();
}

В данном случае вот этот кусок:

 for(i=0;i<N;i++)
{
if(i==0) B[i]=A[N-1];
else B[i]=A[i-K];
}

Есть попытка организовать сдвиг, но она не работает. Это всего лишь один из десятков вариантов. Я уже голову сломал)
Прошу помочь составить алгоритм сдвига.
Большое спасибо заранее

Попросил помощи на профессианальном форуме программистов. Привели слишком сложные примеры. Мне нужен только алгоритм. Я так понимаю это как и у меня должен быть цикл с несколькими условиями типа if

 

[Кот]

Итак. Мне нужно получить от пользователя массив на любое количество элементов (N), а потом сделать сдвиг вправо (K). K естественно задается пользователем, но по условию K строго меньше N.
Особенность: сдвиг "циклический" - элементы с правого края при нехватки "места" переносятся в начало массива.

может быть стоит сдвигать по 1.
т е примерно задать величину пусть j, которая бы проверяла бы K(и цикл с ней)
потом N1 ставить в Nn (или Nn+1,тут я сомневаюсь, потому что как бы мы пихаем его в конец в числом элементов n)
потом все смещаем, т е пpисваем N1 N2 b и т.д. (через цикл до n+1)
кстати, возможно и нужно прописывать Nn+1
и соотвественно обнулять в первом цикле с J

и так он вроде работает)
если надо могу выложить фотку блоксхемы)

кстати у меня тоже была первая мысл как-то провернуть через ..-k, но там как-то все вычеркивалосью.

 

[zzzt]

Это уже похоже на дельный совет - спасибо)
То есть ты предлагаешь цикл в цикле. Один счетчик следит за K, внутри этого цикла еще один, который сдвигает каждый раз на 1. Верно я понял твою мысль?)

 

[zzzt]

Давай схему)) чего то я не могу сообразить из твоего поста формулу в код))

 

[Touareg]

Давай схему)) чего то я не могу сообразить из твоего поста формулу в код))

Я бы сделал так:
1. Создать временный массив temp0 на N элементов.
2. Сгрузить в temp0 от 0 до K-1 данные из A от N-K до N (то есть то, что при сдвиге вправо вылазит за пределы исходного массива)
3. Сгрузить в temp0 от K до N данные из A от 0 до N-K-1
4. Скопировать temp0 в A.
5. Освободить память из-под temp0.

Вроде как то так, с единичками на границах мог напутать надо в отладчике смотреть.

 

[zzzt]

Над вариантом Toureq'a пока не думал ) однако заранее спасибо.
Давайте попробуем вариант Кот'a довести до ума)

Ввел еще счетчик j и написал следующее:

for(j=0;j<K;j++)
{
for(i=0;i<N;i++)
{
if(i==0) B[0]=A[N-1];
else B[i]=A[i-1];
}
}

На 1 двигается идеально, но если ввести 2, то все равно на 1 двигается. Будто бы К не на что не влияет

Исходник прилагаю для вашего удобства. Переименовать в .cpp

 

[Touareg]

Над вариантом Toureq'a пока не думал ) однако заранее спасибо.

Ну так подумай.

И кстати раз у тебя сдвиг циклический, то ограничение K надуманное и некорректное, если K больше N, то K=K-N до тех пор пока K не станет меньше N.

 

[zzzt]

Фраза K меньше N написана в задании. Так что пусть уж ограничение остается.
Мне просто твой вариант сложнее кажется ) вариант Кота "почти" работает ))

 

[Touareg]

1. Создать временный массив temp0 на K элементов.
2. Сгрузить в temp0 от 0 до K-1 данные из A от N-K до N (то есть то, что при сдвиге вправо вылазит за пределы исходного массива)
3. Сдвинуть данные в A от N-K-1 до 0, A[N-K-1] -> A[N], A[N-K-2] -> A[N-1] и т.д.
4. Скопировать temp0 от 0 до K-1 в начало A.
5. Освободить память из-под temp0.

Такой вариант жрет меньше памяти, да и побыстрее думаю))

 

[zzzt]

Наши исходники пока не оценивают на рациональность. Так что это некритично.
Есть идеи почему те два цикла работают неверно?

Я так понимаю что согласно моему коду программа должна. Сдвигать каждый элемент на 1 вправо K раз
Почему последнее не работает?)

 

[Touareg]

Почему последнее не работает?)

Тебя в отладчике забанили чтоли? Именно это она и делает - сдвигает каждый элемент на 1 вправо K раз. Сдвигает К раз, на единицу, начиная с нуля, все как ты заказывал.

А чтобы заработало как ты хочешь надо после каждого сдвига на единицу полностью перезаписывать заново массив А из массива В, поэтому рассмотри лучше мой алгоритм, потому что при достаточно больших N и К алгоритм Кота безобразно расточителен к ресурсам и я бы на месте твоего препода впелил бы тебе пару за этот работающий говнокод.

 

[zzzt]

Да не забанили) просто не мог понять) спасибо) дошло до самого, потом обновил страницу смотрю ты тоже самое написал)
Спасибо всем! )))

 

[sami]

я бы на месте препода рассматривал бы только решения в классе без дополнительной памяти и с минимальным числом шагов. Иначе эта задача не представляет интерес.

 

[Touareg]

я бы на месте препода рассматривал бы только решения в классе без дополнительной памяти и с минимальным числом шагов. Иначе эта задача не представляет интерес.

Память нынче дешевая.
А вот копирование всегда дорогое.

 

[sami]

Память нынче дешевая.
А вот копирование всегда дорогое.

Это не значит что методы обучения должны быть тоже дешевые.

Согласен, самое теоретически-эффективное решение не будет эффективным практически. Сдвигать многогигабайтные массивы дешевле будет копированием. Но копирование не интересно академически. Оно не учит решать задачи с ограничением на ресурсы.

 

[Touareg]

Это не значит что методы обучения должны быть тоже дешевые.

Согласен, самое теоретически-эффективное решение не будет эффективным практически. Сдвигать многогигабайтные массивы дешевле будет копированием. Но копирование не интересно академически. Оно не учит решать задачи с ограничением на ресурсы.

Ты прав. Предложи свой вариант решения, академически правильный.

 

[sami]

Ты прав. Предложи свой вариант решения, академически правильный.

Я займусь им в ближайшее время

 

[SCTRWD]

Итак. Мне нужно получить от пользователя массив на любое количество элементов (N), а потом сделать сдвиг вправо (K). K естественно задается пользователем, но по условию K строго меньше N.
Особенность: сдвиг "циклический" - элементы с правого края при нехватки "места" переносятся в начало массива.

Не знаю, правильно ли, но, помоему, должно работать:

// Берём начало
int *tmp1 = (int*)malloc(((N-K)*sizeof(int));
memcpy(tmp1, А, (N-K)* sizeof(int));

// Берём остаток
int *tmp2 = (int*)malloc((K*sizeof(int));
memcpy(tmp2, A + N - K, K*sizeof(int));

// Сводим результат
memmove(A, tmp2, K*sizeof(int));
memmove(A + K, tmp1, (N-K)*sizeof(int));

free(tmp1);
free(tmp2);

 

[fusion]

сделать указатель A на массив размером 2N из двух одинаковых половин.
сделать указатель B = A + K*sizeof(int). Это и будет ответ.
далее освободить указатель А. вопрос в том освободится ли А не затерев содержимое массива. Если не освободится, то придется копировать.

 

[Touareg]

сделать указатель A на массив размером 2N из двух одинаковых половин.
сделать указатель B = A + K*sizeof(int). Это и будет ответ.
далее освободить указатель А. вопрос в том освободится ли А не затерев содержимое массива. Если не освободится, то придется копировать.

Круто, зачот за правильный ход мысли).