"Przekręcanie tablicy" C++

[Papkin]

Jaki jest najszybszy i najmniej zjadający pamieć algorytm, ktory mógłby "przekręcic" tablicę n-elementową o k elementów. np. Jeżeli nie jest zbyt jasne to co napisałem, to podaje przykład. Dla 1 2 3 4 5 oraz 2 zrobic 3 4 5 1 2. Bardzo proszę o szybką odpowiedź i z góry dziękuję.

[Szemek]

osobiście szukałbym czegoś w bibliotece
np. rotate

najlepiej sprawdź sam
większość algorytmów lepiej zastować na vector niż na zwykłą tablicę

[Papkin]

Jestem dość początkujący. Mógłbyś mi napisać skladnię do tej funkcji na vector?

[Szemek]

na tablicach

Kod: Zaznacz cały

#include<algorithm>
#include<iostream>
using namespace std;

int main()
{
	int tablica[]={0,1,2,3,4,5,6,7,8,9};
	rotate(tablica,tablica+4,tablica+10);
	for(int i=0;i<10;i++)
		cout<<tablica[i];

cout<<endl;

	int tab[]={1,2,3,4,5};
	rotate(tab,tab+2,tab+5);
	for(int i=0;i<5;i++)
		cout<<tab[i];
}

[Xitami]

Szemek pokazał rozwiązanie takie dość pragmatyczne (w jest wszystko? jeżeli tak, to programowanie jest strasznie nudną dziedziną), ale czy ktoś zaproponuje coś sensownego* robionego na piechotę?

* - pamięciowo: < k, super gdy jeden, czasowo: O(N) bo O(K*(N+1)) jest raczej mało pomysłowe.

[kadiii]

Myślę, że rodzaju złożoności raczej nie zmniejszymy - O(N) wydaje się optymalna. Co do ulepszeń rozwiązania na piechotę to na myśl przychodzą mi dwa: Liczenie przesunięcia modulo długość zadanego ciągu, co spowoduje pominięcie pełnych przebiegów cykli nie zmieniających wyniku końcowego oraz jeżeli długośc ciągu minus wartość przesunięcia jest mniejsza od wartości przesunięcia to zmieniamy kierunek przesuwania i przesuwamy o długość ciągu minus wartość przesunięcia. Dzięki temu wykonamy co najwyżej ceil(l /2) jednostkowych operacji przesunięcia, gdzie l to długość zadanego ciągu. Nie zmienia to faktu, że sama operacja przesunięcia jest chyba trudna do usprawnienia?

[Papkin]

Moim zadanie jest takie.
Mam 2 ciagi znakow i mam sprawdzic, czy jeden jest identyczny z drugim lub jest jego 'przekreceniem' jezeli wiecie o co chodzi. obracanie tablicy nie za wiele dalo, gdyz obliczenia dla dlugich ciagow byly bardzo dlugie. Sprobowalem wiec po prostu odwolywac sie do nastepnych elementow uzywajac modulo... Niestety program zawsze wypisuje mi, ze nie. Jezeli bylby ktos sklonny spojrzec w to i zobaczyc, co moze byc zle, bede bardzo wdzieczny.

#include
#include
#include
using namespace std;
int main(void)
{
char ciag1[50000];
char ciag2[50000];
bool log=0;
int t;
cin >> t;
for(int i=0;i> ciag1;
cin >> ciag2;
for(int ii=0;ii

Dane ciagi maja oczywiscie taka sama ilosc elementow.

[smiechowiec]

Jeśli tylko o to chodzi to wystarczy dzielić przez liczbę równą mniej więcej długości łańcucha zamiast 60 tys, wtedy wynik wydaje mi się nieco bardziej przewidywalny.

Kod: Zaznacz cały

#include <iostream>
#include <string>

using namespace std;

int main(void) {
  char ciag1[60000];
  char ciag2[60000];
  bool log = 0;
  unsigned int t;
  cout << "Podaj ilosc sprawdzen ";
  cin >> t;
  for(unsigned int i = 0; i < t; i++) {
    cout << "Podaj ciag1 ";
    cin >> ciag1;
    cout << "Podaj ciag2 ";
    cin >> ciag2;
    unsigned dlugosc = strlen(ciag1);
    for(unsigned int ii = 0; ii < dlugosc; ii++) {
      log = 0;
      for(unsigned int iii = 0; iii < dlugosc; iii++) {
        if (ciag1[iii] != ciag2[(iii + ii) % dlugosc]) {
          log = 1;
          break;
        }
      }
      if (log == 0) 
        break;
    }
    if(log==0)
      cout << "tak" << endl;
    else
      cout << "nie" << endl;
  }
  return 0;
}

[Papkin]

Dziękuję za pomoc w znalezieniu błędu i wszystkie informacje. Temat można już usunąć.

[Undre]

Tematów się tu nie usuwa, nie po to jest forum. Jeśli zależy ci na szybkości, to podejrzewam, że wszystkie powyższe kody można przebić dobrą wstawką asemblerową, ale to już nie bardzo C++ więc

[smiechowiec]

Jeśli chodzi o przyspieszenie porównania dla duzych tablic, to jest sporo możliwości.
Zaproponowany algorytm to prawie brute force.
Dla dużych tablic znaczne przyspieszenie da wyliczenie dla tablicy pewnych wskaźników, które powinny być równe dla ciągów z przesunięciem i porównanie ich, jeżeli będą się różnić od razu będzie wiadomo, że ciągi nie róznią się tylko przesunięciem.
Przykładowe wskaźniki to
- suma liczb w ciągu
- minimalna i maksymalna wartość elementu
- liczba skoków dodatnich ( i ujemych), czyli ile razy element n + 1 jest większy od n.