[+] Wyznaczenie krotno

[drekkett]

Witam Szanownych Forumowiczów

Mam taki oto projekt:

Proszę napisać algorytm, który dla uporządkowanej niemalejąco tablicy jednowymiarowej, wyznacza krotność wystąpienia zadanej wartości. Uwaga: do tego celu należy między innymi użyć algorytmu wyszukiwania binarnego.

Poniżej przedstawiam swoje wypociny w tak zwanym pseudokodzie C. Proszę o ocenę.

Kod: Zaznacz cały

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

Kod: Zaznacz cały

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]

Kod: Zaznacz cały

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:

Kod: Zaznacz cały

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]

Bardzo dziękuję za odzew.
Oczywiście masz rację, w moim przykładzie do pętli while powinienem dodać

Kod: Zaznacz cały

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

Kod: Zaznacz cały

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]

Kod: Zaznacz cały

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]

[quote="piter"]

Kod: Zaznacz cały

Tab [n] = {1 2 2 2 3 3 4 5 6 6 9}, n = 11
x = 6
p = 0][/quote]
Dziękuję za odpowiedź.
Jeżeli zmienię drugą pętlę while:
[code]while (Tab[p] ==x && p<=n-1)

To będzie już chyba wszystko dobrze?
Nie ma chyba więcej błędów?
Pozdrawiam.

[piter]

Na podstawie Twojego algorytmu wyszło mi coś takiego w C++

Kod: Zaznacz cały

#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.

Kod: Zaznacz cały

Tab [4] = {2, 2, 2, 2}

lub

Kod: Zaznacz cały

Tab [0] = { }

oraz gdy szukana wartość nie występuje w tablicy.
Co ciekawe dla tablicy o zerowej ilości elementów

Kod: Zaznacz cały

Tab [0] = { } 

obie pętle zostaną pominięte i w rezultacie wartość zmiennej

Kod: Zaznacz cały

licznik

pozostaje nie zmieniona, czyli zero.

Nie ma chyba więcej błędów?

Ja nie widzę, chyba że ktoś inny znajdzie.

[drekkett]

Ja nie widzę, chyba że ktoś inny znajdzie.

Miejmy nadzieję, że więcej błędów nie ma.
Jeszcze raz dziękuję za pomoc Piter.