Jednoczesne znajdowanie największego i najmniejszego elementu w zbiorze (metoda naiwna i optymalna)
Znajdowanie elementu najmniejszego lub największego w zbiorze nieuporządkowanym odbywa się na tych samych zasadach. Różnica jest w teście porównania większe- mniejsze.
Wyszukiwanie największego elementu w zbiorze (metoda naiwna)
Wczytaj pierwszy element zbioru. Przyjmij, że jest to max (wartość maksymalna). Przeglądaj kolejne elementy, i porównuj czy są większe od bieżącego kandydata na wartość maksymalną. Jeżeli tak, to zrób nowego kandydata na max-a.
Zakończenie algorytmu zwraca odszukaną wartość maksymalną. Podobnie działa algorytm szukania wartości minimalnej (min).
Schemat algorytmu znajdowania wartości maksymalnej w zbiorze (metoda naiwna)
Kod funkcji realizującej powyższy schemat wyszukiwania wartości maksymalnej metodą naiwną
Wskazówka:
void naiwnyMax(Int32[] t)
{
//wyznacz Max metodą naiwną
//ustaw poczatkowego kandydata na maxa
Int32 poz=0,max = t[poz];//
for(Int32 i=1; i < t.Length; i++)
if (t[i] > max)
{
max = t[i];
poz = i+1;//bo zlicza od zerowego wiersza
}
MessageBox.Show(
"Wartość max = " + max.ToString()
+ ", jest na poz. " + poz.ToString(),
"Komunikat",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
}
Aby można było przetestować działanie tej funkcji należy wygenerować losowy zbiór danych. Poniżej kod funkcji, która losuje bez powtórzeń liczby całkowite z podanego zakresu i zapisuje je do tablicy. Ta tablica będzie zbiorem liczb do testowania.
Wskazówka:
void losujTabliceBezPowtorzen(Int32[] t,int zakres)
{
Random r = new Random();
int L, P,//lewa graniza, prawa granica zbioru
los;//wylosowana wartość
bool fWylosowano;//flaga sprawdzania czy juz nie wylosowano
int i = 0;
while (i <t.Length)
{
fWylosowano = false;
los = r.Next(zakres) + 1;
L = 0;//lewy zakres
P = i;//prawy zakres
while (L <= P)
{
if (t[L] == los) { fWylosowano = true;break; }
if (t[P] == los) { fWylosowano = true;break; }
L++;
P--;
}
if (!fWylosowano) {
t[i] = los;
i++;
}
}
}
Jednoczesne wyszukiwanie wartości maksymalnej i minimalnej (metoda optymalna)
Ta metoda polega na jednoczesnym wyszukiwaniu wartości maksymalnej i minimalnej przy wykorzystaniu strategii zwanej: dziel i zwyciężaj.
Do wyszukiwania bierze się jednorazowo dwa elementy. Przez porównanie ich ze sobą określa się bieżącego kandydata na max-a i min-a. Ten test porównawczy prowadzi do podziału zbioru na dwa podzbiory. Jeden podzbiór zawiera kandydatów na max-y, a drugi podzbiór zawiera kandydatów na min-y.
Działanie tego algorytmu wymaga aby zbiór danych zawierał parzystą liczbę elementów. Jeżeli nie jest zbirem o parzystej ilości elementów należy rozszerzyć zbiór o jeden element. Najwygodniej jest zdublować ostatni element zbioru wejściowego.
Schemat algorytmu jednoczesnego znajdowania wartości maksymalnej i minimalnej w zbiorze (metoda optymalna)
Kod funkcji realizującej powyższy schemat jednoczesnego wyszukiwania wartości maksymalnej i minimalnej metodą optymalną
Wskazówka:
void optymalnyMinMax(Int32[] t)
{
Int32 max, min;
//zdubluj ostatni element gdy tablica jest nieparzysta
if (t.Length % 2 == 1)
{
int staryRozmiar=t.GetLength(0);
//ustaw nowy rozmiar
Array.Resize(ref t, staryRozmiar + 1);
//skopiuj przedostatni na ostatni
t[staryRozmiar] = t[staryRozmiar - 1];
}
if (t[0] > t[1]) { max = t[0]; min = t[1]; }
else { max = t[1]; min = t[0]; }
for (int i = 2; i < t.Length - 2; i += 2)
{
if (t[i] > t[i + 1])
{
if (t[i] > max) max = t[i];
if (t[i + 1] < min) min = t[i + 1];
}
else
{
if (t[i] < min) min = t[i];
if (t[i + 1] > max) max = t[i + 1];
}
}
MessageBox.Show(
"Min = " + min.ToString() + ", Max = " + max.ToString(),
"Komunikat",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
}
Przykładowa aplikacja wykorzystująca oba rozwiązania przedstawione w/w algorytmach
Pełny kod klasy Form dla formatki utworzonej aplikacji jednoczesnego znajdowania wartości maksymalnej i minimalnej.
Wskazówka:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace _9AlgMinMax
{
public partial class Form1 : Form
{
Int32[] tab;
int rozmiar = 10;
void losujTabliceBezPowtorzen(Int32[] t,int zakres)
{
Random r = new Random();
int L, P,//lewa graniza, prawa granica zbioru
los;//wylosowana wartość
bool fWylosowano;//flaga sprawdzania czy juz nie wylosowano
int i = 0;
while (i <t.Length)
{
fWylosowano = false;
los = r.Next(zakres) + 1;
L = 0;//lewy zakres
P = i;//prawy zakres
while (L <= P)
{
if (t[L] == los) { fWylosowano = true;break; }
if (t[P] == los) { fWylosowano = true;break; }
L++;
P--;
}
if (!fWylosowano) {
t[i] = los;
i++;
}
}
}
void naiwnyMax(Int32[] t)
{
//wyznacz Max metodą naiwną
//ustaw poczatkowego kandydata na maxa
Int32 poz=0,max = t[poz];//
for(Int32 i=1; i < t.Length; i++)
if (t[i] > max)
{
max = t[i];
poz = i+1;//bo zlicza od zerowego wiersza
}
MessageBox.Show(
"Wartość max = " + max.ToString()
+ ", jest na poz. " + poz.ToString(),
"Komunikat",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
}
void optymalnyMinMax(Int32[] t)
{
Int32 max, min;
//zdubluj ostatni element gdy tablica jest nieparzysta
if (t.Length % 2 == 1)
{
int staryRozmiar=t.GetLength(0);
//ustaw nowy rozmiar
Array.Resize(ref t, staryRozmiar + 1);
//skopiuj przedostatni na ostatni
t[staryRozmiar] = t[staryRozmiar - 1];
}
if (t[0] > t[1]) { max = t[0]; min = t[1]; }
else { max = t[1]; min = t[0]; }
for (int i = 2; i < t.Length - 2; i += 2)
{
if (t[i] > t[i + 1])
{
if (t[i] > max) max = t[i];
if (t[i + 1] < min) min = t[i + 1];
}
else
{
if (t[i] < min) min = t[i];
if (t[i + 1] > max) max = t[i + 1];
}
}
MessageBox.Show(
"Min = " + min.ToString()
+ ", Max = " + max.ToString(),
"Komunikat",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
}
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
//Losowanie nowego zbioru danych
if (textBox2.Text.Length < 1) return;
//wyczysc stara tablicę
if (tab != null) Array.Clear(tab, 0, tab.Length);
//przypisz nowy rozmiar
rozmiar=int.Parse(textBox2.Text);
tab=new Int32[rozmiar];
losujTabliceBezPowtorzen(tab, rozmiar * 2);
//pokaz wylosowany zbior
textBox1.Clear();
for (int i = 0; i < tab.Length; i++)
textBox1.AppendText(tab[i].ToString()+Environment.NewLine);
}
private void button2_Click(object sender, EventArgs e)
{
if (tab==null) return;
naiwnyMax(tab);
}
private void button3_Click(object sender, EventArgs e)
{
optymalnyMinMax(tab);
}
}
}
