Ĺadny brzuch
Mam takie coś zrobić
Dana jest nieuporządkowana tablica jednowymiarowa (wektor) o długości n. Tablica ta zawiera tylko dwa rodzaje elementów. Posortuj tą tablicę w ten sposób, aby złożoność algorytmu była jak najmniejsza. Sortowanie wykonaj za pomocą przestawienia odpowiednich elementów i bez używania pomocniczej tablicy. Np., jeśli tablica jest typu całkowitego i zawiera tylko elementy o wartości 0 i 1, {0,1,1,0, ……0, 1, 0} to po uporządkowaniu jest postaci {0, 0, 0, ……,1, 1, 1}.
Już nawet zrobiłam ale nie zauważyłam że nie powinno być pomocniczej tablicy jak to zrobić może ktoś wie
Ps. najlepiej żeby to była rekurencja[COLOR=blue]
Użytkownik nuna edytował ten post 08 luty 2006, 20:09
prosze pomórzcie :(
Pomożemy, pewnie że pomożemy, czemu nie :) . Ale może dla ułatwienia powiesz, czy wiesz jaka ma być klasa tego algorytmu, żeby była najmniejsza złożoność? Czasem to wiadomo z góry. No i czy ta rekurencja musi być obowiązkowa? Przykładowo ja, to nie lubię rekurencji i staram się unikać :)
I jeszcze jedna rzecz: czy napoczątku algorytmu wiadomo jakie elementy są do posortowania, czy dana jest tylko relacja między nimi. Chodzi mi konkretnie o coś takiego, że jak mamy 0 i 1, to wiadomo, że 0 jest mniejsze i będzie na początku. Ale jeżeli pierwsze napotkamy 0, to mamy pewność, że następne nie będzie (-1) ? To może trochę zmieniać sytuację.
Mam coś takiego programik:
#include <stdlib.h>
#include <iostream.h>
const unsigned int rozmiar = 30;
void przez_scalanie( int pocz, int kon, int * tabl, int *tmp )
{
if( pocz==kon ) return;
int srodek;
srodek = (pocz + kon) / 2;
przez_scalanie( pocz , srodek, tabl, tmp);
przez_scalanie( srodek+1 , kon, tabl, tmp);
int i1 = pocz;
int i2 = srodek+1;
for (int i = pocz ; i <= kon ; i++)
{
if(i1 > srodek){
// nie ma nic w pierwszej tablicy
tmp[i] = tabl[i2++];
}else if(i2 > kon){
// nie ma nic w drugiej tablicy
tmp[i] = tabl[i1++];
}else if(tabl[i1] < tabl[i2]){ // wybieramy mniejszy
tmp[i] = tabl[i1++];
}else
tmp[i] = tabl[i2++];
}
for (int i = pocz ; i <= kon ; i++)
tabl[i] = tmp[i] ;
};
void main()
{
printf("+-------------------------+\n");
printf("| SORTOWANIE REKURENCYJNE |\n");
printf("+-------------------------+\n");
// tworzymy tablice 'rozmiar' elementowa i zapelniamy ja losowymi danymi
int tabl[rozmiar];
int *wsk_tabl = tabl;
int tmp[rozmiar];
int *wsk_tmp = tmp;
unsigned int i;
randomize();
printf("\nTworze tablice %d elementowa...\n\nWynik = [ ",rozmiar);
for (i = 0 ; i < rozmiar ; i++)
{
wsk_tabl[i] = random(2);
cout << wsk_tabl[i] << " ";
}
printf("]\n\n==============================\n");
// sortowanie
printf("\nSortuje...\n\nWynik = [ ");
przez_scalanie( 0, rozmiar-1, wsk_tabl, wsk_tmp);
for( i=0 ; i < rozmiar ; i++ )
cout << tabl[i] << " ";
cout << "]\n\n==============================\n\nWcisnij klawisz aby przeprowadzic test";
// testowanie, czy tablica zostala faktycznie posortowana
getchar();
printf("\nTest: ");
for (i = 1 ; i < rozmiar ; i++)
{
if(tabl[i] < tabl[i-1])
{
printf("Tablica nie jest posortowana!!!");
getchar();
return;
}
}
printf("Wszystko jest OK!");
getchar();
}
Nie wiem jaka ma być klasa to co wiem to nie ma to być sortowanie bąbelkowe a jak to będzie wyglądało to bez różnicy
A o złożoności to nie jestem w stanie nic powiedzieć bo jej nie kapuje nawet jak sie ją oblicza
Oki, mam taki pomysł, kod w C++ poniżej, nie jest rekurencyjny. Zakładam, że w tablicy jest 0 i 1 i że 0 jest mniejsze od 1, i że to wiadomo już na początku. NO i jeszcze pisane to jest na szybko, więc nie musi być idealne. Nie wiem jaka jest dokładnie złożoność tego algorytmu, ale mam wrażenie, że jest klasy n, bo przechodzi tablicę tylko raz (od początku i od końca, ale tylko do jakiegoś środka). Zakładmam też, że funkcja nie zwróci nigdy -1, ale nie sprawdzałem dla innych danych niż ta tablica. Czekam na inne pomysły, mam nadzieję, że da się to lepiej zrobić.
#include <iostream> using namespace std; int tab[]={0,0,1,1,0,1,1,0,1,1}; const int end=10;//rozmiar tablicy int next_b(int c){ for(int i=c+1;i<end;i++) if(tab[c]!=tab[i]) return i; } int next_e(int c){ for(int i=c-1;i>0;i--) if(tab[c]!=tab[i]) return i; } int first(){ for(int i=0; i<end; i++) if(tab[i]!=0) return i; return -1; } int last(){ for(int i=end-1; i>=0; i--) if(tab[i]!=1) return i; return -1; } bool zamien(int b, int e){ if(!(b<e)) return false; int t=tab[b]; tab[b]=tab[e]; tab[e]=t; return true; } int main(){ int b=first(); int e=last(); while(zamien(b, e)){ b=next_b(b); e=next_e(e); } for(int i=0; i<end; i++) cout<<tab[i]<<" "; cout<<endl; system("pause"); }
Więc wskakują mi błędy
a poza tym to chyba powinno być w funkcjach da rade coś takiego zrobić??
Wróżka mi mówi: napisz jakie błędy. To jest w funkcji, funkcja nazywa się main.
tylko to ma być w funkcji ale nie main
gdyż ja muszę zapisać algorytm w postaci funkcji ale nie mam podawać funkcji main wiec jak wszystko zrobię tylko w tej funkcji to nie będzie zbyt ciekawie
a wysypują mi się błędy takie:
namespace name expected
Function should return a value
call to undefined function 'system'
To, co napisałem to raczej zarys tego jak to można zrobić. Może ktoścoś tu dopisze. Zapewniam cię, że jest u parę osób, które znają się na algorytmice i mogą mieć lepsze pomysły. Napisałaś fragment kodu, więc pisać umiesz. MOżesz sobie to teraz przerobić tak jak chcesz. Podobno jest zasada, że tu nie pisze się gotowych programów, a tylko pomaga. To co ja napisałem właściwie spełnia warunki tego, co było w zapytaniu, nic nie wspomniałaś o funkcjach.
A teraz co do błędów: więc wykomentuj funkcję system, to zniknie problem. Zamiast cout napisz jakąś funkcję print i będzie działać. Ja to robiłem w Dev i całe się kompiluje.
ok dzieki
Hmm
chcesz najwydajniejsze sortowanie? Złożoność O(n):
(tablica do posortowania zwie się 'tablica', i ma ''ileElementow' elementów)
unsigned int ileZer = 0, ileJedynek = 0;
for(int i = 0 ; i < ileElementow ; ++i)
{
if(tablica[i] == 1)
{
++ileJedynek;
}
else if(tablica[i] == 0)
{
++ileZer;
}
}
for(int j = 0 ; j < ileZer ; ++j)
{
tablica[j] = 0;
}
for( ; j < ileElementow ; ++j)
{
tablica[j] = 1;
}
Działanie jest następujące - pierwszy obieg zlicza, ile jest zer a ile jedynek w tablicy. Skoro już to wiemy, to w drugim obiegu po prostu wpisujemy do tablicy na początku tyle zer ile miało być, a potem tyle jedynek ile trzeba. ;)
Pr0fesjonalnie nazywają to sortowaniem przez zliczanie.
Pozdrawiam.
Dzięki za szczere chęci
pozdrowionka
...
Tak się docepie tylko tego fragmentu kodu:
Hm... iterator j jest zadeklarowany w pędli więc dostaniesz błąd przy drugiej, że nie istnieje :)
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
Dana jest nieuporządkowana tablica jednowymiarowa (wektor) o długości n. Tablica ta zawiera tylko dwa rodzaje elementów. Posortuj tą tablicę w ten sposób, aby złożoność algorytmu była jak najmniejsza. Sortowanie wykonaj za pomocą przestawienia odpowiednich elementów i bez używania pomocniczej tablicy. Np., jeśli tablica jest typu całkowitego i zawiera tylko elementy o wartości 0 i 1, {0,1,1,0, ……0, 1, 0} to po uporządkowaniu jest postaci {0, 0, 0, ……,1, 1, 1}.
Już nawet zrobiłam ale nie zauważyłam że nie powinno być pomocniczej tablicy jak to zrobić może ktoś wie
Ps. najlepiej żeby to była rekurencja[COLOR=blue]
Użytkownik nuna edytował ten post 08 luty 2006, 20:09
prosze pomórzcie :(
Pomożemy, pewnie że pomożemy, czemu nie :) . Ale może dla ułatwienia powiesz, czy wiesz jaka ma być klasa tego algorytmu, żeby była najmniejsza złożoność? Czasem to wiadomo z góry. No i czy ta rekurencja musi być obowiązkowa? Przykładowo ja, to nie lubię rekurencji i staram się unikać :)
I jeszcze jedna rzecz: czy napoczątku algorytmu wiadomo jakie elementy są do posortowania, czy dana jest tylko relacja między nimi. Chodzi mi konkretnie o coś takiego, że jak mamy 0 i 1, to wiadomo, że 0 jest mniejsze i będzie na początku. Ale jeżeli pierwsze napotkamy 0, to mamy pewność, że następne nie będzie (-1) ? To może trochę zmieniać sytuację.
Mam coś takiego programik:
#include <stdlib.h>
#include <iostream.h>
const unsigned int rozmiar = 30;
void przez_scalanie( int pocz, int kon, int * tabl, int *tmp )
{
if( pocz==kon ) return;
int srodek;
srodek = (pocz + kon) / 2;
przez_scalanie( pocz , srodek, tabl, tmp);
przez_scalanie( srodek+1 , kon, tabl, tmp);
int i1 = pocz;
int i2 = srodek+1;
for (int i = pocz ; i <= kon ; i++)
{
if(i1 > srodek){
// nie ma nic w pierwszej tablicy
tmp[i] = tabl[i2++];
}else if(i2 > kon){
// nie ma nic w drugiej tablicy
tmp[i] = tabl[i1++];
}else if(tabl[i1] < tabl[i2]){ // wybieramy mniejszy
tmp[i] = tabl[i1++];
}else
tmp[i] = tabl[i2++];
}
for (int i = pocz ; i <= kon ; i++)
tabl[i] = tmp[i] ;
};
void main()
{
printf("+-------------------------+\n");
printf("| SORTOWANIE REKURENCYJNE |\n");
printf("+-------------------------+\n");
// tworzymy tablice 'rozmiar' elementowa i zapelniamy ja losowymi danymi
int tabl[rozmiar];
int *wsk_tabl = tabl;
int tmp[rozmiar];
int *wsk_tmp = tmp;
unsigned int i;
randomize();
printf("\nTworze tablice %d elementowa...\n\nWynik = [ ",rozmiar);
for (i = 0 ; i < rozmiar ; i++)
{
wsk_tabl[i] = random(2);
cout << wsk_tabl[i] << " ";
}
printf("]\n\n==============================\n");
// sortowanie
printf("\nSortuje...\n\nWynik = [ ");
przez_scalanie( 0, rozmiar-1, wsk_tabl, wsk_tmp);
for( i=0 ; i < rozmiar ; i++ )
cout << tabl[i] << " ";
cout << "]\n\n==============================\n\nWcisnij klawisz aby przeprowadzic test";
// testowanie, czy tablica zostala faktycznie posortowana
getchar();
printf("\nTest: ");
for (i = 1 ; i < rozmiar ; i++)
{
if(tabl[i] < tabl[i-1])
{
printf("Tablica nie jest posortowana!!!");
getchar();
return;
}
}
printf("Wszystko jest OK!");
getchar();
}
Nie wiem jaka ma być klasa to co wiem to nie ma to być sortowanie bąbelkowe a jak to będzie wyglądało to bez różnicy
A o złożoności to nie jestem w stanie nic powiedzieć bo jej nie kapuje nawet jak sie ją oblicza
Oki, mam taki pomysł, kod w C++ poniżej, nie jest rekurencyjny. Zakładam, że w tablicy jest 0 i 1 i że 0 jest mniejsze od 1, i że to wiadomo już na początku. NO i jeszcze pisane to jest na szybko, więc nie musi być idealne. Nie wiem jaka jest dokładnie złożoność tego algorytmu, ale mam wrażenie, że jest klasy n, bo przechodzi tablicę tylko raz (od początku i od końca, ale tylko do jakiegoś środka). Zakładmam też, że funkcja nie zwróci nigdy -1, ale nie sprawdzałem dla innych danych niż ta tablica. Czekam na inne pomysły, mam nadzieję, że da się to lepiej zrobić.
#include <iostream> using namespace std; int tab[]={0,0,1,1,0,1,1,0,1,1}; const int end=10;//rozmiar tablicy int next_b(int c){ for(int i=c+1;i<end;i++) if(tab[c]!=tab[i]) return i; } int next_e(int c){ for(int i=c-1;i>0;i--) if(tab[c]!=tab[i]) return i; } int first(){ for(int i=0; i<end; i++) if(tab[i]!=0) return i; return -1; } int last(){ for(int i=end-1; i>=0; i--) if(tab[i]!=1) return i; return -1; } bool zamien(int b, int e){ if(!(b<e)) return false; int t=tab[b]; tab[b]=tab[e]; tab[e]=t; return true; } int main(){ int b=first(); int e=last(); while(zamien(b, e)){ b=next_b(b); e=next_e(e); } for(int i=0; i<end; i++) cout<<tab[i]<<" "; cout<<endl; system("pause"); }
Więc wskakują mi błędy
a poza tym to chyba powinno być w funkcjach da rade coś takiego zrobić??
Wróżka mi mówi: napisz jakie błędy. To jest w funkcji, funkcja nazywa się main.
tylko to ma być w funkcji ale nie main
gdyż ja muszę zapisać algorytm w postaci funkcji ale nie mam podawać funkcji main wiec jak wszystko zrobię tylko w tej funkcji to nie będzie zbyt ciekawie
a wysypują mi się błędy takie:
namespace name expected
Function should return a value
call to undefined function 'system'
To, co napisałem to raczej zarys tego jak to można zrobić. Może ktoścoś tu dopisze. Zapewniam cię, że jest u parę osób, które znają się na algorytmice i mogą mieć lepsze pomysły. Napisałaś fragment kodu, więc pisać umiesz. MOżesz sobie to teraz przerobić tak jak chcesz. Podobno jest zasada, że tu nie pisze się gotowych programów, a tylko pomaga. To co ja napisałem właściwie spełnia warunki tego, co było w zapytaniu, nic nie wspomniałaś o funkcjach.
A teraz co do błędów: więc wykomentuj funkcję system, to zniknie problem. Zamiast cout napisz jakąś funkcję print i będzie działać. Ja to robiłem w Dev i całe się kompiluje.
ok dzieki
Hmm
chcesz najwydajniejsze sortowanie? Złożoność O(n):
(tablica do posortowania zwie się 'tablica', i ma ''ileElementow' elementów)
unsigned int ileZer = 0, ileJedynek = 0;
for(int i = 0 ; i < ileElementow ; ++i)
{
if(tablica[i] == 1)
{
++ileJedynek;
}
else if(tablica[i] == 0)
{
++ileZer;
}
}
for(int j = 0 ; j < ileZer ; ++j)
{
tablica[j] = 0;
}
for( ; j < ileElementow ; ++j)
{
tablica[j] = 1;
}
Działanie jest następujące - pierwszy obieg zlicza, ile jest zer a ile jedynek w tablicy. Skoro już to wiemy, to w drugim obiegu po prostu wpisujemy do tablicy na początku tyle zer ile miało być, a potem tyle jedynek ile trzeba. ;)
Pr0fesjonalnie nazywają to sortowaniem przez zliczanie.
Pozdrawiam.
Dzięki za szczere chęci
pozdrowionka
...
Tak się docepie tylko tego fragmentu kodu:
Hm... iterator j jest zadeklarowany w pędli więc dostaniesz błąd przy drugiej, że nie istnieje :)