- Nie jesteś zalogowany.
- Polecamy: Biżuteria i zegarki
#1 2011-03-22 09:44:07
Zadanie u Ewy T.
mam pytanko
to zadanie u ewy co mamy jej przyniesc to ma byc skompilowany program czy na kartce jej tylko napisac?
bo juz sam nie wiem bo mnie na ćw nie bylo wtedy.
xDe
Offline
#2 2011-03-23 10:21:18
- jksomeone7
Użytkownik
- Zarejestrowany: 2010-10-20
- Posty: 18
- Punktów : 0
Re: Zadanie u Ewy T.
mamy to napisać na kompie i wydrukować, czyli nie program tylko tak jak to na zajęciach pisaliśmy
Offline
#5 2011-03-30 15:33:08
Re: Zadanie u Ewy T.
Zadanie:
Podaj algorytm (specyfikację i implementację) upraszczający ułamek n/m. Oszacuj
jego złożoność czasową.
Uwaga: aby uprościć ułamek, wystarczy licznik i mianownik podzielić przez ich największy
wspólny dzielnik.
u mnie na chomiku jest zrobione zadanie.
Ostatnio edytowany przez ShaguaR (2011-03-30 15:35:33)
xDe
Offline
#10 2011-04-12 23:59:10
Re: Zadanie u Ewy T.
coś takiego nieoptymalnego, ale zawsze coś....
Kod:
int Przeszukaj2(int a[], int n, int *x)
{
int min=a[0],max=a[0];
int lk=0; // przesunięcie względem najmniejszego indexu tablicy (czyli zera)
for (int i=0; i<n; i++)
{
min=a[i]<min ? a[i]:min; //wyznaczamy minimum
max=a[i]>max ? a[i]:max; //wyznaczamy maximum
}
if (min<0) lk=min*(-1); //jeśli minimum<0 lk=-min
lk++; // zwiększamy o 1 - czyli, żeby możliwe było b[max]
int *b=new int [max+lk];
for (int i=0; i<max+lk; i++) b[i]=0; //zerujemy elementy tablicy
for (int i=0; i<n; i++) b[a[i]+lk]+=1; //wartość z b[a[i] + przesunięcie lk] zwiększamy o 1
min=max; // dla ułatwienia
max=b[0]; // przykładowe maximum czyli 0
for (int i=1; i<min+lk; i++)
if (max<b[i]) {x=&i; max=b[i]; // szukamy w którym indexie jest maximum i przekazujemy do zmiennej x
return max; // ile jest najczęściej występujących elementów
}lub
Kod:
int Przeszukaj2(int a[], int n)
{
int min=a[0],max=a[0];
int lk=0; // przesunięcie względem najmniejszego indexu tablicy (czyli zera)
int x;
for (int i=0; i<n; i++)
{
min=a[i]<min ? a[i]:min; //wyznaczamy minimum
max=a[i]>max ? a[i]:max; //wyznaczamy maximum
}
if (min<0) lk=min*(-1); //jeśli minimum<0 lk=-min
lk++; // zwiększamy o 1 - czyli, żeby możliwe było b[max]
int *b=new int [max+lk];
for (int i=0; i<max+lk; i++) b[i]=0; //zerujemy elementy tablicy
for (int i=0; i<n; i++) b[a[i]+lk]+=1; //wartość z b[a[i] + przesunięcie lk] zwiększamy o 1
min=max; // dla ułatwienia
max=b[0]; // przykładowe maximum czyli 0
for (int i=1; i<min+lk; i++)
if (max<b[i]) {x=i; max=b[i]; // x jest indexem z największą wartością - czyli najczęściej występującą wartością w tablicy a[]
return x; // najczęściej występująca wartość w a[]
}do piątku chyba wymyślę coś lepszego... złożoność czasowa? nie wiem w którym miejscu (których miejscach?) ją liczyć w tej funkcji (lub jej 2 wersji).
funkcja ma nazwę Przeszukaj2, bo testowałem inny koncept, ale tamten miał zdecydowanie więcej porównań wynikających z pętli zagnieżdżonych
to rozwiązanie ma złożoność obliczeniową O(m+n) (o ile wierzyć opisowi rozwiązania nr 4 na http://edu.i-lo.tarnow.pl/inf/alg/001_s … 5.php#roz4), gdzie n - liczba elementów tablicy m - ilość wartości elementów tablicy. należałoby zmienić tylko algorytm tworzenia i indeksacji tablicy pomocniczej, bo dla bardzo dużych tablic może braknąć pamięci. rozwiązanie zamieszczę na chomiku jutro.
Ostatnio edytowany przez januszs (2011-04-13 14:27:32)
Nie pytajcie po co to robię
Offline
#11 2011-04-13 15:32:08
Re: Zadanie u Ewy T.
A co jeśli zbiór wejściowy ma 100 elementów od 1 do 1 000 000 000?
Tablica indeksująca będzie miała 999 000 000 elementów, z czego co najmniej 998 999 000 będzie miało wartość 0.
Mam wrażenie, że to nie do końca optymalne rozwiązanie.
Offline
#12 2011-04-14 22:21:14
Re: Zadanie u Ewy T.
wtedy można zastosować:
Kod:
int Przeszukaj3(int a[], int n)
{
int *b=new int [n];
for (int i=0; i<n; i++) b[i]=a[i];
int licznik,w, wmax=b[0], wlmax=0;
for (int i=0; i<n; i++)
{
w=b[i];
licznik=1;
for (int j=i+1; j<n; j++)
if (w==b[j])
{
b[j]=b[i+licznik];
b[i+licznik]=w;
licznik++;
}
if (licznik>wlmax)
{
wlmax=licznik;
wmax=w;
}
i+=licznik;
}
delete []b;
return wmax;
}no chyba, że tablica wypełnia prawie całą dostępną pamięć wtedy mamy jeszcze przerobioną wersję powyższej funkcji...
Kod:
int Przeszukaj4(int a[], int n)
{
int licznik,w, wmax=a[0], wlmax=0;
for (int i=0; i<n; i++)
{
w=a[i];
licznik=1;
for (int j=i+1; j<n; j++)
if (w==a[j])
{
licznik++;
}
if (licznik>wlmax)
{
wlmax=licznik;
wmax=w;
}
}
return wmax;
}złożoność czasowa powyższych funkcji wynosi.... w najgorszym wypadku (gdy nie ma powtarzających się wartości) (n*(1+n))/2. Im więcej powtarzających się elementów tym mniej razy zostanie wykonana główna pętla czyli w najlepszym wypadku będzie to 1 raz (w pierwszym wariancie funkcji - dla drugiego wariantu zawsze będzie to (n*(1+n))/2). Można zawsze drugi wariant przerobić tak, aby złożoność czasowa była taka jak w tym pierwszym, ale w rezultacie tablica którą przekazaliśmy funkcji zostanie zmieniona (uporządkowana w grupy powtarzających się elementów - zgodnie z przyjętym algorytmem)
Kod:
int Przeszukaj5(int *a[], int n)
{
int licznik,w, wmax=*a[0], wlmax=0;
for (int i=0; i<n; i++)
{
w=*a[i];
licznik=1;
for (int j=i+1; j<n; j++)
if (w==*a[j])
{
licznik++;
}
if (licznik>wlmax)
{
wlmax=licznik;
wmax=w;
}
i+=licznik;
}
return wmax;
}Ostatnio edytowany przez januszs (2011-04-14 22:24:51)
Nie pytajcie po co to robię
Offline
Stopka forum
Powered by PunBB
© Copyright 2002–2008 PunBB
Polityka cookies - Wersja Lo-Fi