tablica-podium zwycięzców-czy jest lepszy algorytm?

Odpowiedz Nowy wątek
2015-02-17 14:41
0

Witam
do rozwiązania mam podane poniżej zadanie w języku C, rozwiązałem je jednak interesuje mnie to czy jest poprawnie rozwiązane i czy istnieje lepszy algorytm.

zad
dana jest tablica nieujemnych liczb całkowitych, należy napisać program który wypisze podium zwycięzców (ich numer)
przykład:

tab1[10]={0,6,2,6,4,9,6,7,8,3}
podium[3]={9,8,7}
czyli po prostu program wypisuje 3 największe elementy tablicy.

 #include <stdio.h>
#include <stdlib.h>

int a=20;
int b=3;

int* up()
{
int i;
int *tab,*tab2;
int pierwszy,drugi,trzeci;

tab=(int*)malloc(b*sizeof(int));
tab2=(int*)malloc(a*sizeof(int));

for(i=0;i<a;i++)
{
tab2[i]=i;
}

pierwszy=tab2[0];
drugi=tab2[0];
trzeci=tab2[0];

for(i=0;i<a;i++)
{
if(pierwszy<tab2[i])
{
    pierwszy=tab2[i];
}
}

for(i=0;i<a;i++)
{
   if(tab2[i]<pierwszy && tab2[i]>drugi)
    {
    drugi=tab2[i];
    }
}

for(i=0;i<a;i++)
{
if(tab2[i]<drugi && tab2[i]>trzeci)
{
    trzeci=tab2[i];
}
}

tab[0]=pierwszy;
tab[1]=drugi;
tab[2]=trzeci;

return tab;
}
int main()
{
int *tab, i;
tab = up();

for(i=0; i<b;i++)
{
printf("%d\n", tab[i]);
}

return 0;
}

Pozostało 580 znaków

2015-02-17 14:45
0

czy istnieje lepszy algorytm w sposobie rozwiązania jaki podałem?
oprócz sortowania tablicy?

Pozostało 580 znaków

2015-02-17 16:05
//C99
#include <stdio.h>
#include <stdlib.h>

int cmpfunc(const void *a, const void *b) {
   return *(int*)b - *(int*)a;
}

int main(void) {
    int size;
    scanf("%d ", &size);
    int results[size], it = size;
    while(it--) scanf("%d ", &results[it]);
    qsort(results, size, sizeof(int), cmpfunc);
    for(it = 0; it < 3; ++it)
        printf("top %d: %d\n", it+1, results[it]);
    return 0;
}

In:

5
88 56 100 2 25

Out:

top 1: 100
top 2: 88
top 3: 56

Link: http://ideone.com/iqRWow

edytowany 2x, ostatnio: spartanPAGE, 2015-02-17 16:13
zaproponowalem mu takie samo rozwiazanie, to mu sie nie podobalo... - fasadin 2015-02-18 10:33
Właśnie też się zdziwiłem, że zaakceptował rozwiązanie z sortowaniem, gdy sam pisał, że nie chce :D Może po prostu nie podałeś gotowca :P - twonek 2015-02-18 10:36
prawie nigdy nie daje gotowca ;) - fasadin 2015-02-18 10:37
ogólnie w Twoim rozwiązaniu podając ze będzie np 5 elementów wprowadzamy 6. zawsze o 1 więcej - pawlo1508 2015-02-18 10:49
zaakceptowałem bo mnie zainteresowało, jest w miarę krótkie - pawlo1508 2015-02-18 10:50

Pozostało 580 znaków

2015-02-17 19:11
0

dzięki za odpowiedź i mam prośbę czy mógł byś podać opisowo jak ten program działa?
np. też o co chodzi w tej części "return (int)b - (int)a;"
z góry dzięki.

ps.jestem początkującym wiec nie wszystko dobrze rozumiem.

edytowany 1x, ostatnio: pawlo1508, 2015-02-17 19:14
rzutowanie, wyłuskanie wartości i operacja odejmowania - spartanPAGE 2015-02-17 19:12

Pozostało 580 znaków

2015-02-17 19:15
0

Wczytanie wielkości tablicy, utworzenie tablicy o odpowiedniej wielkości (VLA), wczytanie do niej wartości, posortowanie i wybranie 3 pierwszych pozycji.

Pozostało 580 znaków

2015-02-17 21:10
0

To ja mam pytanie takie, qsort używa algorytmu merge sort który ma złożoność obliczeniową O(n log n), więc czy nie lepsze będzie sprawdzanie w jednej pętli i ewentualne segregowanie elementów w wektorze tym 3-elementowym.

#include <iostream>
using namespace std;

int main()
{
    int input[9] = {7 ,5 ,1 ,12 ,33, 2, 231, 2 ,56};
    int out[3] = { 0, 0 ,0};

    for (int i = 0; i < (sizeof(input)/sizeof(*input)); i++)
    {
        if (input[i] > out[2])
        {

            out[0] = out[1];
            out[1] = out[2];
            out[2] = input[i];

            continue;
        }

        if (input[i] > out[1])
        {
            out[0] = out[1];
            out[1] = input[i];
            continue;
        }

        if (input[i] > out[0])
        {
            out[0] = input[i];
            continue;
        }
    }

    std::cout<<out[2]<<" "<<out[1]<<" "<<out[0]<<std::endl;
} 
mikrooptymalizacjom mówimy stanowcze: a zrób tak w przypadku 100 razy większych ilości danych do zebrania - spartanPAGE 2015-02-17 21:23
Pomysł dobry, zaś realizacja beznadziejna. Dodawać do set'a oraz pilnować aby set nie przekroczył rozmiar 3. O(n log(k)) - gdzie k=3 w tym przypadku, dopiero przy drastycznym zwiększeniu k - sortowanie będzie lepsze. - _13th_Dragon 2015-02-17 21:34
:) odezwałeś się - spartanPAGE 2015-02-17 21:35
Wiem żę wygląda słabo :) Ale pytanie było o lepszy algorytm więc coś takiego wydało mi sę bardziej sensowne niż użycie qsorta. Choć fakt przy niewielkich tablicach jak tutaj nie ma to specjalnie znaczenia. - lemonov 2015-02-17 22:28

Pozostało 580 znaków

2015-02-18 10:29
0

ogólnie to miała być funkcja zwracająca tablice (podium) i wypisująca ją w main.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0