Mógłby mi ktoś podać algorytm jak przesunąć wiersze w tabeli o k pozycji?
Z góry dziękuję.
Przesunięcie cykliczne wierszy w tablicy
-
- 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
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;
}
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
- argv
- 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
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:
- 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 */
- kadiii
- 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
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;
}