GoldenLine
Zaloguj się
Paweł Grzegorz Kwiatkowski

Paweł Grzegorz Kwiatkowski Architekt
oprogramowania,
Ericsson

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Przeglądając portal analogiczny do GL, natknąłem się na ciekawą (przynajmniej dla mnie) zagadkę, którą się dzielę.

===
Jak odwrócić string w jednym przebiegu? Żeby było ciekawiej:
* nie znamy długości stringa
* wywołanie strlen() uznajemy za jeden przebieg
===

Miłej zabawy :)

pozdrawiam,
Paweł

p.s. przepraszam, jeśli ta zagadka już tu wystąpiła i proszę o usunięcie posta.
Link do wypowiedziLink
Łukasz C.

Łukasz C. Senior Technical
Architect

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

hmm ujemny wskaznik?
tzn: mam wskaznik do pierwszego elementu stringa zapamietuje jego pozycje pozniej w jednym przebiegu wstawiam kolejne znaki przed poczatkowy wskaznik dekrementujac go az napotkam na null terminator '\0' i ten wynikowy dekrementowany wskanzik bedzie poczatkiem mojego odwroconego stringa :P

jedyny minus ze poczatkowy string musi miec sporo miejsca "przed soba" ;)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MEMSIZE 1000000

char *invert(char *str)
{
char *l = str;
char *r = str;
while (*r) {
*--l = *r++;
}
*str = '\0';
return l;
}

int main()
{
char *mem = (char *) malloc(MEMSIZE);
char *str = (mem + MEMSIZE / 2);
char *str2 = NULL;

strcpy(str, "to jest jakis string");
str2 = invert(str);
printf("%s\n", str2);

return 0;
}

troche czitowane ale trybi :DŁukasz Cepowski edytował(a) ten post dnia 17.05.10 o godzinie 12:47
Link do wypowiedziLink
Paweł Grzegorz Kwiatkowski

Paweł Grzegorz Kwiatkowski Architekt
oprogramowania,
Ericsson

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Na takie minusy nie ma co patrzeć, jako że jest to zabawa ;-)

Ogólnie 3 pomysły na rozwiązanie:
- rekursja
- "ujemne wskaźniki"
- zabawa ze stosem i ramkami w celu wyznaczenia długości stringa (minus taki, że: nieprzenośne, zależne od platformy, systemu, kompilatora...)
Link do wypowiedziLink
Karol Nowacki

Karol Nowacki Programista PHP,
Perl, C,
administrator
systemów *NIX

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

hmmm...
void strrev(char *str) {

  char *p = str;

  char t;

  while (*p && *(p+1)) p+=2; // czy można potraktować to jako pół przebiegu?

  

  // TAK WIEM! Wszelkie komentarze na temat, że przecież i tak sprawdzam

  // wszystkie elementy są zbędne. Nie mniej jednak pętla wykonuje się

  // strlen(str)/2 razy. :)

  

  if (*p == 0) p--;

  while(str < p) { // ... a to jako drugie pół

    t = *p; *p = *str; *str = t;

    p--;str++;

  }

}
Link do wypowiedziLink
Łukasz C.

Łukasz C. Senior Technical
Architect

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

ee nie ma tak! bo w warunku sprawdzasz dwa sasiednie bajty wiec wykonujesz caly przebieg ;)
Link do wypowiedziLink
Adam Woźniak

Adam Woźniak software architect
and developer

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Cześć Paweł ;]
Paweł Grzegorz Kwiatkowski:
Na takie minusy nie ma co patrzeć, jako że jest to zabawa ;-)

Ogólnie 3 pomysły na rozwiązanie:
- rekursja
- "ujemne wskaźniki"
- zabawa ze stosem i ramkami w celu wyznaczenia długości stringa (minus taki, że: nieprzenośne, zależne od platformy, systemu, kompilatora...)

Doprecyzuj trochę zagadkę, proszę ;]
No bo nie da się odwrócić stringa szybciej niż w czasie O(n).
Rozwiązanie dwuprzebiegowe jest trywialne. Kosztuje: O(n) czasu oraz O(1) dodatkowej pamięci.

Zatem co jest celem zagadki? Znalezienie jednoprzebiegowego algorytmu odwracającego string?
I czy można uzyć O(n) pamięci pomocniczej? ("ujemne wskaźniki" właśnie używają pamięci pomocniczej)

Peace, Adam Woźniak
Link do wypowiedziLink

konto usunięte

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Jeśli mamy O(1) pamięci i mamy to rozwiązać w jednym przebiegu ( notacja O(n) jakoś do mnie nie przemawia w tym wypadku, bo przecież O(n) = O(2n) ), to mam wrażenie, ze rozwiązania nie ma. Bo rekurencja (niejawny stos) będzie wymagać O(n) pamięci...
Link do wypowiedziLink
Maciej Hehl

Maciej Hehl w teorii Automatyk i
Robotyk (po wydziale
mechanicznym), ...

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

A gdybym zaproponował ordynarne rozwiązanie o złożoności O(n^2), w którym dla indeksu i podciąg [0, i) jest już odwrócony i następuje jego przesunięcie w prawo, do pozycji [1, i] a znak o indeksie i (jeśli nie jest końcem ciągu) jest przestawiany pod index 0, to ile przebiegów zostało by naliczone?
Link do wypowiedziLink

konto usunięte

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Rozwiązanie prawie-jak Karola (jedyne optymalne jakie znam) ma złożoność O(n/2 - n mod 2) = O(n) przy założeniu, że znana jest długość. I nie potrzebuje dodatkowej pamięci.

Reszta to jak dla mnie sztuka dla sztuki, przy czym stos i rekursja to ostatnie co bym tu zaproponował...
Link do wypowiedziLink
Paweł Grzegorz Kwiatkowski

Paweł Grzegorz Kwiatkowski Architekt
oprogramowania,
Ericsson

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Adam Woźniak:
Doprecyzuj trochę zagadkę, proszę ;]
No bo nie da się odwrócić stringa szybciej niż w czasie O(n).
Rozwiązanie dwuprzebiegowe jest trywialne. Kosztuje: O(n) czasu oraz O(1) dodatkowej pamięci.

Zatem co jest celem zagadki? Znalezienie jednoprzebiegowego algorytmu odwracającego string?
I czy można uzyć O(n) pamięci pomocniczej? ("ujemne wskaźniki" właśnie używają pamięci pomocniczej)

Adam,

cele zagadki:
- rozrywka intelektualna
- nauczenie się czegoś nowego

Można używać O(n) pamięci pomocniczej. Najlepiej jednak byłoby używać ciekawych konstruktów w C (np. unia i traktowanie stringa jako tablica char, a z drugiej strony jako tablica int, tego jak string jest reprezentowany w pamięci itd.) niż tworzyć algorytm, który jest ogólny i do zaimplementowania w innym języku. Słowem jakaś perełka programistyczna mile widziana i pokazująca siłę C :)

Nie chodzi o wydajne rozwiązanie, ot zabawę.

pozdr,
Paweł
Link do wypowiedziLink
Maciej Hehl

Maciej Hehl w teorii Automatyk i
Robotyk (po wydziale
mechanicznym), ...

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Tia...

Pewnie chodzi o jedną z tych perełek, które siłę C pokazują w ten sposób, że na architekturze innej niż x86 powodują core dump.

Bardzo chętnie zobaczę rozwiązanie rekurencyjne. Może rzuci to trochę światła na definicję pojęcia "przebieg"
Link do wypowiedziLink
Paweł Grzegorz Kwiatkowski

Paweł Grzegorz Kwiatkowski Architekt
oprogramowania,
Ericsson

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Maciej Hehl:
Tia...

Pewnie chodzi o jedną z tych perełek, które siłę C pokazują w ten sposób, że na architekturze innej niż x86 powodują core dump.

Owszem, może być coś takiego. Stąd sugerowana zabawa ze stosem i frame pointerami.

Bardzo chętnie zobaczę rozwiązanie rekurencyjne. Może rzuci to trochę światła na definicję pojęcia "przebieg"

Zdaję sobie sprawę, że pojęcie "przebieg" nie jest precyzyjne. Chodzi o przebiegnięcie raz przez wejściowy ciąg znaków.

A rekurencyjnie np. coś z grubsza takiego (zakładając O(n) pamięci na składowanie wyniku)



void reverse(char buf[]) {

  if (buf == NULL)  return;

  

  if (*buf) {

    reverse(buf+1);

  }

  printf("%c",*buf);

}
Link do wypowiedziLink
Maciej Hehl

Maciej Hehl w teorii Automatyk i
Robotyk (po wydziale
mechanicznym), ...

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu




void reverse(char buf[]) {

  if (buf == NULL)  return;

  

  if (*buf) {

    reverse(buf+1);

  }

  printf("%c",*buf);

}

Rozumiem, że liczba przebiegów powyżej to 1.

Niech zgadnę. W przypadku jak poniżej już nie



void unwid_the_stack_in_a_magical_way(std::stack<char*> & theStack)

{

    while(!theStack.empty())

    {

        printf("%c",*(theStack.top()));

        theStack.pop();

    }

}



void reverse(char buf[])

{

    if(buf == NULL) return;



    std::stack<char*> pointerStack;

    while(*buf)

    {

        pointerStack.push(buf++);

        if(buf == NULL)

        {

            printf("%c", *(buf - 1));

            return;

        }

    }

    printf("%c", *buf);

    unwid_the_stack_in_a_magical_way(pointerStack);

}


Wiem, że pierwszym "wypisywanym" znakiem jest '\0', ale starałem się naśladować pierwowzór na górze.Maciej Hehl edytował(a) ten post dnia 20.05.10 o godzinie 17:34
Link do wypowiedziLink

konto usunięte

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Jak dla mnie tutaj jest jeden przebieg i jest użyte O(n) dodatkowej pamięci, czyli to co chciał autor zagadki. Czyli jest OK.

Rozwiązanie z jednym przebiegiem i O(1) dodatkowej pamięci nie istnieje.
Link do wypowiedziLink
Szymon Kubisiak

Szymon Kubisiak Developer aplikacji
mobilnych Android

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Co rozumiecie jako "ujemny wskaźnik"? (przypominam że void* jest unsigned)

Gdzie ten string trafia? Mamy go odwrócić w miejscu, czy też gdzieś odkładamy? A może to "gdzieś" samo jest dwukierunkowe?
Możemy każdy ze znaków odkładać do dwukierunkowej link-listy. To bedzie jeden przebieg i niech się odbiorca martwi o wyciąganie. :P
Najlepiej jednak byłoby używać ciekawych konstruktów w C (np. unia i traktowanie stringa jako tablica char, a z drugiej strony jako tablica int, tego jak string jest reprezentowany w pamięci itd.)

Hmm. To podpowiedź do rozwiązania jakie masz, czy też znane i lubiane polecenie "konkurencja używa techniki X więc i my jej użyjmy, choć wcale nie pasuje do struktury naszego projektu".

Jesli chcesz coś systemowo zależnego, mogę Ci od ręki powiedzieć jak to zrobić na Symbianie: tam stringi (TDes) mają counter z przodu...

Stawiam tezę że nie da się zrobić tego w "jednym przebiegu" nie mając do dyspozycji nieskończonej ilości pamięci (w sensie bufora gwarantowanego że jest większy od wejściowego stringa).
Link do wypowiedziLink

konto usunięte

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

przecież rekurencja to stos, a stos trzeba przelecieć 2x (polozyc n wartosci a pozniej zdjac n wartosci)

rozwiazanie to tablica char[] o rozmiarze 2N + 3, gdzie N to przewidywalny maksymalny rozmiar stringu

na srodku tablicy ustawiamy '\0' i wczytujemy string od pozycji srodkowej s + 1

po wczytaniu stringu kopiujemy z tab[s + i] do tab[s - 1 - i] (wlaczajac '\0' na koncu stringu)

na koniec wyswietlamy string poczawszy od pozycji tab[s - l - 1], gdzie l to ostatnia wartosc i

informatycy..Piotr Wójtowicz edytował(a) ten post dnia 16.08.10 o godzinie 17:37
Link do wypowiedziLink
Piotr P.

Piotr P. Software Developer

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Piotr Wójtowicz:
przecież rekurencja to stos, a stos trzeba przelecieć 2x (polozyc n wartosci a pozniej zdjac n wartosci)

rozwiazanie to tablica char[] o rozmiarze 2N + 3, gdzie N to przewidywalny maksymalny rozmiar stringu

A świstak se siedzi i zawija ten string w nieprzewidywalną ilość sreberka ;)
Przewidywalne działanie takiej implementacji jest oparte na twierdzeniu iż otrzymany string nie jest przewidywalny. Chyba, że implementujesz to w środowisku w którym string nie może byc dłuższy niż N z takiego a nie innego powodu. Wówczas można przyjąć tezę, że da się to zrobić w jednym przebiegu w każdym środowiku pod warunkiem że wywołujący ten przebieg poda również długość stringa. Co oczywiście jest "bez sęsu" :)
Link do wypowiedziLink

konto usunięte

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Jak już było wspomniane trzeba by chyba wnikać w architekturę.
Np. jeśli string jest na stosie to położenie czegoś ( np. char='c' na potrzeby tego posta ) zaraz za nim umożliwia porównanie adresów początku stringa i tego czegoś na tej podstawie określenie rozmiaru ( zapewne alignment jakiś będzie więc adres 'c' można zmniejszać o 1 bajt aż trafimy na '\0' - znaczy się być może trafiliśmy na koniec stringa a równie dobrze mogą być śmieci a wsród nich '\0' przypadkiem ). W każdym razie oszacowanie wielkości będzie dokładne lub z niwielkim nadmiarem. Powyższe należy odpowiednio skorygować w zależności czy stos rośnie w górę czy w dół.
Link do wypowiedziLink
Rafał Toboła

Rafał Toboła Razor s.c. -
współwłaściciel

Temat: [Zagadka] - odwracanie C-stringa w jednym przebiegu

Skoro z rekurencją, to może tak:


void reverse(char *str) {

	if ((*str)!='\0')

		reverse(str+1);

	printf("%c", str[0]);

}

Taki żart oczywiście :-).
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy


Następna dyskusja:

Kolejna zagadka algorytmicz...




Wyślij zaproszenie do
Anuluj