Przesunięcie cykliczne wierszy w tablicy

edaro
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 18 gru 2006, o 20:01
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 56 razy
Pomógł: 16 razy

Przesunięcie cykliczne wierszy w tablicy

Post autor: edaro »

Mógłby mi ktoś podać algorytm jak przesunąć wiersze w tabeli o k pozycji?
Z góry dziękuję.
matshadow
Użytkownik
Użytkownik
Posty: 941
Rejestracja: 17 gru 2007, o 21:48
Płeć: Mężczyzna
Lokalizacja: Kingdom Hearts
Podziękował: 6 razy
Pomógł: 222 razy

Przesunięcie cykliczne wierszy w tablicy

Post autor: matshadow »

Kod: Zaznacz cały

#include <iostream>
using namespace std;
const int n=9;
int main()
{
    int k=11, i, j;
    int tab[]={1,2,3,4,5,6,7,8,9}, zap[n-k];
    k%=n;
    for(i=n-k, j=0; i<n; i++, j++) zap[j]=tab[i];
    for(i=n-1; i>=k; i--) tab[i]=tab[i-k];
    for(i=0; i<k; i++) tab[i]=zap[i];
    for(i=0; i<n; i++) printf("%d ", tab[i]);
    system("pause");
	return 0;
}
Najpierw k przyrównujemy do k%n, bo mając tablicę np 10 elementową i chcąc ją przesunąć o 15 elementów, przesuwamy ją de facto o 5 elementów.
Zauważ, że jak przesuwamy o k miejsc, to k ostatnich liczb z tablicy pójdzie na początek, a n-k zostanie po prostu przesuniętych. Musimy utworzyć dodatkową tablicę, która zapamięta te k liczb z końca, a następnie w początkowej tablicy od końca przesuwamy - tzn ostatni element dostaje wartość elementu o k miejsc wcześniej itd. Potem przepisujemy od początku te zapamiętane wcześniej wartości
Awatar użytkownika
argv
Użytkownik
Użytkownik
Posty: 569
Rejestracja: 27 maja 2009, o 01:27
Płeć: Mężczyzna
Podziękował: 51 razy
Pomógł: 66 razy

Przesunięcie cykliczne wierszy w tablicy

Post autor: argv »

Niezależnie od tego o co chodziło autorowi (?), jeśli chodzi faktycznie o cykliczne przesunięcie elementów w tablicy o \(\displaystyle{ k}\) pozycji to robimy to tak:
- odwracamy całą tablicę
- odwracamy pierwsze k elementów
- odwracamy pozostałe elementy

Kod z przykładem:

Kod: Zaznacz cały

void przesun_cyklicznie(int *tab, int n, int k){    /* odwracamy najpierw cala tablice */    odwrocpom(tab, 0, n-1);    /* odwracamy pojedyncze "polowki" */    odwrocpom(tab, 0, k-1);    odwrocpom(tab, k, n-1);    }void odwrocpom(int *tab, int pocz, int kon){    int tmp;        while(pocz < kon) {        tmp = tab[pocz];        tab[pocz] = tab[kon];        tab[kon] = tmp;        pocz++;        kon--;    }}/* np: 5 3 7 2 1 8 4 6 i przesuniecie o 3 * Odwracamy: | 6 4 8 | 1 2 7 3 5 * Odwracamy obie polowki: * 8 4 6 | 5 3 7 1 2 */ 
Awatar użytkownika
kadiii
Użytkownik
Użytkownik
Posty: 642
Rejestracja: 20 gru 2005, o 21:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 130 razy

Przesunięcie cykliczne wierszy w tablicy

Post autor: kadiii »

O ile sposób argv jest naprawdę bardzo ładny i polecam go użyć to użycie dodatkowej tablicy lepiej wyglądałoby tak.

Kod: Zaznacz cały

void przesun_cyklicznie(int *tab,int n,int k)
{
 int *pom=new int[n], i;
 for(i=0;i<n;i++)
    pom[i]=tab[i];
 for(i=0;i<n;i++)
    tab[(i+k)%n]=pom[i];
 delete [] pom;
}
ODPOWIEDZ