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)

Schemat algorytmu znajdowania wartości maksymalnej w zbiorze (metoda naiwna). Visual studio C#

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)

Schemat algorytmu jednoczesnego znajdowania wartości maksymalnej i minimalnej w zbiorze (metoda optymalna). Visual studio C#

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

aplikacja wykorzystująca algorytmu jednoczesnego znajdowania wartości maksymalnej i minimalnej w zbiorze (metoda optymalna). Visual studio C#

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);
        }
    }
}
Układ okresowy- kod qr
Układ okresowy

Układ okresowy pierwiastków- darmowa aplikacja na Androida

Pobierz ze sklepu Google Play
Alkomat- wirtualny test kod qr
Alkomat- wirtualny test

Alkomat- darmowa aplikacja na Androida

Pobierz ze sklepu Google Play
Taklarz- olinowanie stałe kod qr
Olinowanie stałe- kalkulator średnic

Olinowanie stałe- darmowa aplikacja na Androida

Pobierz ze sklepu Google Play
przepis na gogfry

Przepis na gofry

zobacz
przepis na bitą śmietanę

Przepis na bitą śmietanę

zobacz