Ocena użytkownikóww: ***** / 4
Nadesłany przez Tomasz Lubiński, 27 lipca 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
AlgorytmHoare.java:
/**
* algorytm Hoare'a
* www.algorytm.org
* Tomasz Lubiński (c)2005
*/
public class AlgorytmHoare {
public static int partition(int c[], int a, int b)
{
int e,tmp;
e=c[a]; //elemennt dzielacy
while (a<b)
{
while ((a<b) && (c[b]>=e)) b--;
while ((a<b) && (c[a]<e)) a++;
if (a<b)
{
tmp=c[a];
c[a]=c[b];
c[b]=tmp;
}
}
return a;
}
public static void main(String[] args) {
int n,i,j,k,w;
int c[] = new int[100];
System.out.println("Podaj liczbe elementow ciagu");
n = Console.readInt("?");
for (i=0; i<n; i++) {
System.out.println("Podaj "+ (i+1) +" element ciagu");
c[i] = Console.readInt("?");
}
System.out.println("Podaj ktory element obliczyc\n");
w = Console.readInt("?");
// algorytm Hoare'a
i=0;
j=n-1;
n=w;
while (i!=j)
{
k=partition(c,i,j);
k=k-i+1;
if (k>=w) j=i+k-1;
if (k<w)
{
w-=k;
i+=k;
}
}
System.out.println(n + " element ciagu to " + c[i]);
}
}