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

@zzzt · Регистрация: 21.03.2010

Author24 — интернет-сервис помощи студентам

Добрый день) Сразу оговорюсь что честно пользовался поиском. Если у меня проблемы со зрением - прошу указать соответствующую тему. Спасибо.

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

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

C++

#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();
}

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

C++

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

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

@Ignat · 21.03.2010, 14:28

Алгоритм прост как 5 пять копеек, скорее всего кто-нибудь поможет.

@zzzt · 21.03.2010, 14:32 **[ТС]**

Я понимаю что он несложный. Но сам уже второй день голову ломаю ((( глупый я наверное)

@Ignat · 21.03.2010, 14:33

Попробуй эту функцию, делает что то похожее.

C++

template<class T>
long round_insert(T *const massive, const int size_m){
T tmp = massive[0];
for(int i=0;i<size_m-1;i++)massive[i]=massive[i+1];
massive[size_m-1]=tmp;
return 0;
}

или эту:

C++

long round_insert(int *const massive, const int size_m){
int tmp = massive[0];
for(int i=0;i<size_m-1;i++)massive[i]=massive[i+1];
massive[size_m-1]=tmp;
return 0;
}

@zzzt · 21.03.2010, 14:36 **[ТС]**

А просто алгоритма не существует, например, с циклом? Просто это слишком крутое решение. Мне ведь сдавать потом прогу)

@Ignat · 21.03.2010, 14:51

Вставь в коде куда тебе следует:

C++

int tmp = massive[0];
for(int i=0;i<size_m-1;i++)massive[i]=massive[i+1];
massive[size_m-1]=tmp;
return 0;

Добавлено через 28 секунд
return 0 убери

Добавлено через 4 минуты
у меня сдвиг влево сейчас сделаю вправо.

Добавлено через 6 минут

C++

1
2
3

int tmp = massive[size_m-1];
for(int i=size_m-1;i>0;i--)massive[i]=massive[i-1];
massive[0]= tmp;

@zzzt · 21.03.2010, 15:00 **[ТС]**

Простите, а можно разобрать что есть что из написанного? Я просто не могу понять что за массив с [0] что за size m и куда мне собственно девать количество сдвигов К, которое в моей программе задается пользователем

@Ignat · 21.03.2010, 15:09

Что то был не внимателен в прочтении задание, про k забыл.
Значит алгоритм меняется не намного.
K должно отвечать сколько надо потворить мой фрагмент, следовательно
надо внешний цикл ещё добавить.

Добавлено через 1 минуту
Допустим так:

C++

while(k){
int tmp = massive[size_m-1];
for(int i=size_m-1;i>0;i--)massive[i]=massive[i-1];
massive[0]= tmp;
k--;
}

@zzzt · 21.03.2010, 15:12 **[ТС]**

Вопрос мой прошлый остается так сказать "приоткрытым". У меня два массива. Массив А - заполнен элементами. Массив B пуст и в него надо в правильном порядке перенести значения из А. Учитывая k конечно.
Извините, но я просто хочу понять как работает код написанный вами и как его можно использовать в моей программе.

Я просто думал что у меня мышление по поводу алгоритма переноса верное, но надо добавить несколько условий if чтобы крайние элементы переносились в начало. Но я не как не могу придумать алгоритм

@Ignat · 21.03.2010, 15:14

Короче вожусь тут я чувствую зря...
Тем более на 100% процентов уверен, что на спасибо ни кто не нажмет.

@zzzt · 21.03.2010, 15:20 **[ТС]**

Раздел называется для начинающих ))) я не зря себя к ним отнес...
Я попросил только помочь в составлении алгоритма переноса только потому что сам уже сломал над ним голову. Вы написали какой-то код, который может быть и работает, но я не понимаю как (см. название раздела). Не понимаю также как использовать его в своей программе.
Просто меня не устраивает вариант тупо копипастить. Я пришел не за решением задачи, а за помощью.

В любом случае спасибо за потраченное время

@CyBOSSeR · 21.03.2010, 15:50

zzzt, вот самое красивое решение данной задачи из всех мне известных

C++

// Обмен значениями двух целочисленных переменных
void Swap(int& left, int& right)
{
  int tmp   = left;
      left  = right;
      right = tmp;
}
 
// Разворот массива
void Reverse(int* arr, int size)
{
  for (int i = 0; i < size / 2; ++i)
    Swap(arr[i], arr[size - i - 1]);
}
 
// Сдвиг вправо на k позиций
void ShiftRight(int* arr, int size, int k)
{
  k %= size;
  Reverse(arr, k);             // Разворот левой части массива
  Reverse(arr + k, size - k);  // Разворот правой части массива
  Reverse(arr, size);          // Разворот всего массива
}

Возьми листок бумаги, нарисуй массив и посмотри как это работает.

@Ignat · 21.03.2010, 15:59

zzzt Скажет это очень круто...

@zzzt · 21.03.2010, 18:01 **[ТС]**

Придумал вот такую штуку

C++

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 вправо K раз

Но независимо от заданного K сдвигает только на 1. Будто бы цикл по j не работает. Только внутренний действует.
Где я не прав?

@Emiliya · 21.03.2010, 18:01

Здравствуйте

Извините, что не совсем в тему. Помогите, пожалуйста, разобраться. У меня есть два кода: первый кодирует, второй- раскодирывает одни и те же данные. Почему не совпадают исходники?
Задание:
Елемент профиля пользователя в системе исчисления представляется в виде:
№ разряду 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
Значення G G G G G G G G S S S S P 0 0 0
де:
G..G - идентификатор группы, к которой приналежит пользователь
S..S - код системы, которая загружается для пользователя
P - признак привелегии пользователя

Это первый

C

1.
#include <stdio.h>
#include<conio.h>
int main(void){
 char g; 
 char s; 
 char p; 
 unsigned int UnitStateWord; 
  printf("Vvedit identufikator grupu (0/1) >");
  scanf("%d",&g);
  printf("Vvedit kod systemu (0-16) >");
  scanf("%d",&s);
  printf("Vvedit oznaku pruveleyovanosti (0 / 1) >");
  scanf("%d",&p);
  UnitStateWord=((unsigned int)g&1)<<9;
  UnitStateWord|=((unsigned int)s&0x1F)<<11;
  UnitStateWord|=((unsigned int)p&1)<<8;
  printf("\nElement profilya korustuvacha = %04x\n"
     UnitStateWord);
{
getche();
getche();
}
return 0;
}

а это второй

C

#include <stdio.h>
#include<conio.h>
int main(void){
 char g; 
 char s; 
 char p; 
 unsigned int UnitStateWord; 
  printf("Vvedit element profilya korustuvacha \n");
  printf("(16-ruchne vid 0 do 0xFFFF) >");
  scanf("%x",&UnitStateWord);
  g=(UnitStateWord>>9)&1;
  s=(UnitStateWord>>11)& 0x1F;
  p=(UnitStateWord>>8)&1;
  putchar('\n');
  printf("Identufikator grupu                  = %d\n",g);
  printf("Kod systemu             = %d\n",s);
  printf("Oznaca pruveleyovanosti          = %d\n",p);
{
getche();
getche();
}
 return 0;
}

Умные люди сказали, что нужно найти такую битовую операцию, которая бы ОДНОЗНАЧНО определяла последний бит p. Подскажите, пожалуйста, как

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	21.03.2010, 14:28	2
	Алгоритм прост как 5 пять копеек, скорее всего кто-нибудь поможет. 0

@zzzt 0 / 0 / 0 Регистрация: 21.03.2010 Сообщений: 8
	21.03.2010, 14:32 [ТС]	3
	Я понимаю что он несложный. Но сам уже второй день голову ломаю ((( глупый я наверное) 0

@zzzt 0 / 0 / 0 Регистрация: 21.03.2010 Сообщений: 8
	21.03.2010, 14:36 [ТС]	5
	А просто алгоритма не существует, например, с циклом? Просто это слишком крутое решение. Мне ведь сдавать потом прогу) 0

@zzzt 0 / 0 / 0 Регистрация: 21.03.2010 Сообщений: 8
	21.03.2010, 15:00 [ТС]	7
	Простите, а можно разобрать что есть что из написанного? Я просто не могу понять что за массив с [0] что за size m и куда мне собственно девать количество сдвигов К, которое в моей программе задается пользователем 0

@zzzt 0 / 0 / 0 Регистрация: 21.03.2010 Сообщений: 8
	21.03.2010, 15:12 [ТС]	9
	Вопрос мой прошлый остается так сказать "приоткрытым". У меня два массива. Массив А - заполнен элементами. Массив B пуст и в него надо в правильном порядке перенести значения из А. Учитывая k конечно. Извините, но я просто хочу понять как работает код написанный вами и как его можно использовать в моей программе. Я просто думал что у меня мышление по поводу алгоритма переноса верное, но надо добавить несколько условий if чтобы крайние элементы переносились в начало. Но я не как не могу придумать алгоритм 0

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	21.03.2010, 15:14	10
	Короче вожусь тут я чувствую зря... Тем более на 100% процентов уверен, что на спасибо ни кто не нажмет. 3

@zzzt 0 / 0 / 0 Регистрация: 21.03.2010 Сообщений: 8
	21.03.2010, 15:20 [ТС]	11
	Раздел называется для начинающих ))) я не зря себя к ним отнес... Я попросил только помочь в составлении алгоритма переноса только потому что сам уже сломал над ним голову. Вы написали какой-то код, который может быть и работает, но я не понимаю как (см. название раздела). Не понимаю также как использовать его в своей программе. Просто меня не устраивает вариант тупо копипастить. Я пришел не за решением задачи, а за помощью. В любом случае спасибо за потраченное время 0

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	21.03.2010, 15:59	13
	zzzt Скажет это очень круто... 0