Pseudo kod:
Kod:
Pseudo kod: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;
Kod:
import java.lang.reflect.Array;import java.util.Random;
public class Projekt {
private int n;
private int p=0;
private int k;
private int s;
private int licznik;
int[] Tab = new int[n];
int x;
int pom;
public Projekt()
{
Random r = new Random();
for(int i=0; i<Tab.length; i++)
Tab[i]=r.nextInt(100)+1;
// Wyświetlenie zawartości całej tablicy
for(int i=0; i<Tab.length; i++)
System.out.print(i+" element tablicy to: "+Tab[i]+"\n\r");
System.out.println("To jest wielkość tablicy: "+Tab.length);
int z;
for(z=Tab[0];z<Tab[20];z++)
{
while(p<=k && Tab[s] !=x) {
k=n-1;
s=(p+k)/2;
System.out.println("Wszedłem w pierwszy while");
if (Tab[s]>x){
System.out.println("to jest k: "+k);
}
else {
p=s+1;
System.out.println("To jest p: "+p);
}
pom=s+1;
System.out.println("To jest pom: "+pom);
while (Tab[s]==x) {
System.out.println("Wszedłem w drugi while");
licznik=licznik+1;
s=s-1;
}
while (Tab[pom]==x&&pom<=n-1) {
System.out.println("Wszedłem w trzeci while");
licznik=licznik+1;
pom++;
}
System.out.println("To jest licznik: "+licznik);
}
}
}
public static void main(String[] args) {
new Projekt();
}
}
Jakoś nie mam pomysłów. Pomożecie?
Tak mi się zapętla:
To jest licznik: 0Wszedłem w pierwszy while
to jest k: 499
To jest pom: 250
To jest licznik: 0
Wszedłem w pierwszy while
to jest k: 499
To jest pom: 250
To jest licznik: 0
Wszedłem w pierwszy while
to jest k: 499
To jest pom: 250
To jest licznik: 0
Wszedłem w pierwszy while
to jest k: 499
To jest pom: 250
To jest licznik: 0
Wszedłem w pierwszy while
Zakładki