Как из циклического сдвига вправо сделать циклический сдвиг влево?

Question

[kapysta13]

Что нужно изменить для циклического сдвига вправо, чтобы сделать сдвиг влево?

Answer 1

[Wataru]

Вариант тупой, при котором мозг не задет - развернуть массив, сдвинуть вправо, развернуть опять.

Вариант чуть получше - вместо разворота, представить, что массив развернут. Тогда при любом обращении к элементу номер x надо обращаться к элементу n-1-x. Т.е. тупо в программе, где сдвиг делается(после ввода), каждый arr[x] заменить на arr[n-1-x] (примеры x у вас там - n-1, i+1, i, 0).

Вариант еще лучше - включить голову и просто подумать. Сдвиг влево - это в сторону уменьшения индекса. arr[0] становится arr[1], arr[1] - arr[2], и так далее. arr[n-1] становится arr[0]. Т.е. надо в буфер запомнить arr[0], пройтись циклом по возрастанию i и присвоить каждому элементу следующее за ним (+1 к индексу) значение. Потом arr[n-1] заполнить из буфера. На самом деле получится то же, что и в предыдущем варианте, но без лишних вычислений индексов.

Вариант совсем хороший - не городить shift сдвигов на одну позицию, а сдвигать сразу на shift позиций. Для этого в буфер надо засунуть первые shift элементов, потом пройтись циклом и записывать в i-ый значение из i+shift-ого. Потом последние shift позиций заполнить из буфера.

Вариант со звездочкой - можно делать без буфера на shift элементов, и сдвигать на shift позиций прямо в массиве, но тут надо знать про перестановки и GCD.

Comments

[kapysta13]

такто ти предложил вариант вправо, а я просил влево,извини

[Wataru]

kapysta13, Что?

Лево от право отличить не можешь? Cено-солома: Циферка 3 в твоем нике с правого конца, а буква k - с левого. Соответсвтено, сдвиг влево - apysta13k: на место первого символа встает второй, на место второго - третий и так далее.

В вопросе у тебя сдвиг вправо, я написал, как сделать из него сдвиг влево (например тупой заменой "arr[x]" => "arr[n-1-x]" в цикле.

[kapysta13]

Илья Николаевский, аа понял,у меня просто ошиблись в задании

[kapysta13]

Илья Николаевский, почему то не получається

[kapysta13]

Илья Николаевский, int buffer = arr[0];
for (int m=0; m < n; m++) {
arr[m] = arr[n - m - 1];
}
arr[n - 1] = buffer;
вот код

[Wataru]

kapysta13, как, почему, откуда? Ты можешь взять свой код из вопроса, и тупо сделать замену arr[x] => arr[n-1-x] (кроме ввода и вывода). Можно даже не включать мозг, просто машинально. Видишь arr[ - вписываешь "n-1-(" после "[" и ")" перед "]".

У тебя сейчас намешан сдвиг на 1 (который надо в цикле, как у тебя в вопросе, повторить нужное количество раз), и то ли попытка развернуть массив, то ли попытка сдвинуть сразу на несколько позиций.

Answer 2

[Армянское Радио]

Завести второй массив (нигде в требованиях это не запрещено), а потом b[i] = a[ (i+shift) % size ];

Comments

[kapysta13]

а ето влево?

[Армянское Радио]

kapysta13, ну знак у шифта поменяйте

[kapysta13]

Фокс Йовович, спереди цифри виходят непонятние

[kapysta13]

Фокс Йовович, ну з + как би вроде влево или я ошибаюсь?

[Армянское Радио]

b[i] = a[ (i-shift) % size ];

[kapysta13]

Фокс Йовович, говорю что виходит -8583853831 вместо 10

[Армянское Радио]

kapysta13, код покажите

[kapysta13]

const int n = 10;
int arr[n] = { 1,2,3,4,5,6,7,8,9,10 };
int k;
cin >> k;
k = k % n;
int new_arr[100];
cout << "1 спосіб: " << endl;
for (int i = 0; i < n; i++) {
new_arr[i] = arr[(i - k) % n];
}@gbg,

[Армянское Радио]

kapysta13, это не весь код

[kapysta13]

Фокс Йовович, #include
#include
using namespace std;

int main() {
system("chcp 1251>nul");
const int n = 10;
int arr[n] = { 1,2,3,4,5,6,7,8,9,10 };
int k;
cin >> k;
k = k % n;
int new_arr[100];
cout << "1 спосіб: " << endl;
for (int i = 0; i < n; i++) {
new_arr[i] = arr[(i - k) % n];
}
cout << "array=" << endl;
for (int j = 0; j < n; j++) {
cout << new_arr[j] << " ";
}

system("pause>nul");
return 0;
}

[Wataru]

kapysta13, Проблема в том, что (i-k)%n может быть отрицательным. Если взять (-3) % 10 - то будет -3, а не 7, как надо в математике. Лечится это прибавлением лишнего n под модулем: (i+n-k)%n

[kapysta13]

Илья Николаевский, ну ето вийдет сдвиг вправо,так што всьо норм

[Армянское Радио]

Илья Николаевский, чертов C, у него остаток не как в математике!

[Wataru]

Фокс Йовович, Это проблема не C, а легаси-хак в x86 команде idiv:

Non-integral results are truncated (chopped) towards 0

Когда как по уму надо округлять вниз, а не в сторону 0. Но так быстрее и проще считать было, да и кому в голову тогда могло прийти что люди будут делить отрицательные числа... Вот и получилось, что приведенный вами код b[i] = a[ (i-shift) % size ]; - undefined behavior.