[+] Wyznaczenie krotności wystąpienia zadanej wartości

drekkett - 01-12-2009 14:27
Witam Szanownych Forumowiczów:)

Mam taki oto projekt:
Poniżej przedstawiam swoje wypociny w tak zwanym pseudokodzie C. Proszę o ocenę. Dane: Tab[n] tablica, n - rozmiar tablicy
x- szukana
Wynik: licznik - krotność wystąpień szukanej liczby

Zmienne pomocnicze:

p - index początkowy
k - index końcowy
s - index środkowy
pom - zmienna pomocnicza

p=0;
k=n-1;
s=(p+k)/2;
licznik=0

//Najpierw szukam binarnie:

while(p<=k && Tab[s] !=x) {
if (Tab[s]>x){
k=s-1;
}
else {
p=s+1;
}
//po znalezieniu liczby zapisuję index komórki do pom

pom=s+1;

//przeszukuję i zliczam wystąpienia

while (Tab[s]==x && s>=0) {
licznik=licznik+1;
s=s-1;
}
while (Tab[pom]=x && pom<=n-1) {
licznik=licznik+1;
pom=pom+1;
}
pokaż licznik; Jeżeli jest dobrze napisane, to chciałbym to trochę udoskonalić dodając do omawianego kodu to aby przy wyszukiwaniu binarnym było tak, że może nie być elementu wyszukiwanego. To pewnie z instrukcją warunkową if i if else, ale jeszcze do tego nie dojrzałem:)
Trzeba dodać na początek
if (Tab[s]==x)
{nie mam pojęcia co napisać
}
else{
i tutaj wpisać całą pętlę while poszukiwania binarnego?? A dopiero potem zliczanie, czy jak?
W miarę pisania pytania się mnożą.
Proszę o pomoc, ewentualnie o podpowiedź, gdzie jest błąd (choć kod wydaje mi się dobry).
Pozdrawiam.

piter - 01-12-2009 22:23
while(p<=k && Tab[s] !=x) {
if (Tab[s]>x){
k=s-1;
}
else {
p=s+1;
} Rozumiem, że chcesz znaleźć wartość zmiennej s, dla której zajdzie równanie:
Tab[s] == x Wtedy pętla While zakończy działanie. Tylko, że modyfikujesz zmienne k lub p (w zależności od wyniku warunku if), a zmienna s pozostaje bez zmian.
Poza tym brakuje mi jednej końcowej klamry }.

drekkett - 01-12-2009 23:31
Bardzo dziękuję za odzew.
Oczywiście masz rację, w moim przykładzie do pętli while powinienem dodać
s=(p+k)/2; Zdaje mi się, że znalazłem bardziej eleganckie rozwiązanie mojego problemu.
Za pomocą wyszukiwania binarnego szukam pierwszego wystąpienia elementu
Dane: Tab[n] tablica, n - rozmiar tablicy
x- szukana
Wynik: licznik - krotność wystąpień szukanej liczby

Zmienne pomocnicze:

p - index początkowy
k - index końcowy
s - index środkowy

p=0;
k=n-1;
licznik=0;

while(p<k){

s=(p+k)/2;

if (Tab[s]>=x){
k=s;
}
else {
p=s+1;//pierwsze wystąpienie elementu zostaje zapisane w zmiennej p
}
}

//tworzę kolejną pętlę licząc wystąpienia liczby
while (Tab[p] ==x && p>=n-1) {
licznik=licznik+1;
p=p+1;
}
pokaż licznik; Co o tym myślisz?
Teraz powinno być chyba dobrze, nie?
Proszę o odpowiedź.
Pozdrawiam

piter - 02-12-2009 20:54
Tab [n] = {1 2 2 2 3 3 4 5 6 6 9}, n = 11
x = 6
p = 0; k = 10; licznik = 0;

while (0 < 10) {s = 5; 3 < 6 więc p = 6}
while (6 < 10) {s = 8; 6 = 6 więc k = 8}
while (6 < 8) {s = 7; 5 < 6 więc p = 8}
while (8 < 8) {nie wykona się}

// p = 8; k = 8 ; s = 7; licznik =0; n = 11
//druga pętla while
while (6 == 6 and 8 >= 10) {nie wykona się}

pokaż licznik = 0

drekkett - 02-12-2009 21:32

Tab [n] = {1 2 2 2 3 3 4 5 6 6 9}, n = 11
x = 6
p = 0; k = 10; licznik = 0;

while (0 < 10) {s = 5; 3 < 6 więc p = 6}
while (6 < 10) {s = 8; 6 = 6 więc k = 8}
while (6 < 8) {s = 7; 5 < 6 więc p = 8}
while (8 < 8) {nie wykona się}

// p = 8; k = 8 ; s = 7; licznik =0; n = 11
//druga pętla while
while (6 == 6 and 8 >= 10) {nie wykona się}

pokaż licznik = 0 Dziękuję za odpowiedź.
Jeżeli zmienię drugą pętlę while:
while (Tab[p] ==x && p<=n-1) To będzie już chyba wszystko dobrze?
Nie ma chyba więcej błędów?
Pozdrawiam.

piter - 03-12-2009 21:04
Na podstawie Twojego algorytmu wyszło mi coś takiego w C++
#include <iostream>

using namespace std;

int main ()
{
const int n = 11;
int Tab[n] = {2, 2, 3, 4, 4, 4, 5, 7, 7, 7, 9};
int x = 7;

int p = 0;
int k = n - 1;
int s;
unsigned licznik = 0;

while (p < k)
{
s = (p + k) / 2;
if (Tab[s] >= x) k = s;
else p = s + 1;
}

for (;Tab[p] == x && p < n; ++p) ++licznik; //zaproponowa przez Ciebie pętla while też działa

//Wyświetlenie wyników
cout << "Tab[" << n << "] = { ";
for (int i = 0; i < n; ++i) cout << Tab[i] << " ";
cout << "}" << endl << endl;
cout << "Wartość x = " << x << " występuje " << licznik << " raz(y)." << endl;

return 0;
} Sprawdzałem dla różnych tablic np.
Tab [4] = {2, 2, 2, 2} lub
Tab [0] = { } oraz gdy szukana wartość nie występuje w tablicy.
Co ciekawe dla tablicy o zerowej ilości elementów Tab [0] = { } obie pętle zostaną pominięte i w rezultacie wartość zmiennej licznik pozostaje nie zmieniona, czyli zero.
Ja nie widzę, chyba że ktoś inny znajdzie.

drekkett - 03-12-2009 22:29
Miejmy nadzieję, że więcej błędów nie ma.
Jeszcze raz dziękuję za pomoc Piter.