Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Numărul optim de comparații  (Citit de 5082 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
TheNechiz
De-al casei
***

Karma: 30
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« : 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 ?
« Ultima modificare: Noiembrie 09, 2015, 19:52:13 de către Razvan Birisan » Memorat
TrascaAndrei
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 18



Vezi Profilul
« Răspunde #1 : 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
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines