Strona 1 z 1
Przesunięcie cykliczne wierszy w tablicy
: 29 lis 2010, o 16:45
autor: edaro
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
: 30 lis 2010, o 11:47
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
Przesunięcie cykliczne wierszy w tablicy
: 30 lis 2010, o 12:14
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 */
Przesunięcie cykliczne wierszy w tablicy
: 30 lis 2010, o 13:14
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;
}