infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: FMI Razvan Birisan din Noiembrie 08, 2015, 22:12:56



Titlul: Numărul optim de comparații
Scris de: FMI Razvan Birisan din Noiembrie 08, 2015, 22:12:56
Scrieți un program care citește 5 numere întregi și calculează suma celor
mai mari 3 numere dintre ele pe baza unui algoritm ce realizează un număr
minim de comparații. Câte comparații realizează algoritmul vostru?

Cod:
# include <stdio.h>
# include <limits.h>

int main()
{
    int a,b,c,d,e,m1,m2;
    m1 = m2 = INT_MAX;

    scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
    if( a <= b )
    {
        if( a < m1 ) m1 = a;
        if( b < m2 ) m2 = b;
    }
    else
    {
        if( a < m2 ) m2 = a;
        if( b < m1 ) m1 = b;
    }

    if( c <= d )
    {
        if( c < m1 ) m1 = c;
        if( d < m2 ) m2 = d;
    }
    else
    {
        if( c < m2 ) m2 = c;
        if( d < m1 ) m1 = d;
    }

    if( e < m1 )
    {
        m2 = m1;
        m1 = e;
    }
    else if( e < m2 )
        m2 = e;

    printf("%d",a+b+c+d+e-m1-m2);

    return 0;
}

Algoritmul meu face 7 comparații. Se pot face mai puține comparații ?


Titlul: Răspuns: Numărul optim de comparații
Scris de: Trasca Andrei din Ianuarie 13, 2016, 00:52:39
Se poate face fara nicio comparatie folosind un algoritm Counting Sort(daca memoria nu este o problema)
Counting Sort e un algoritm de sortare ce ordoneaza un vector in O(n) fara nicio comparatie, folosind doar operatii matematice.
Gasesti o gramada de detalii despre el pe internet. Uite un link catre wikipedia: https://en.wikipedia.org/wiki/Counting_sort (https://en.wikipedia.org/wiki/Counting_sort)