Zadanie szkolne - sprawdzenie poprawności zadania

pytanie zadane 3 grudnia 2019 w PHP przez progNewbie Obywatel (1,130 p.)
edycja 3 grudnia 2019 przez progNewbie

Hej,

Mam takie zadanie do zrobienia na studiach:

1. Opracować i zaimplementować algorytm wyszukiwania dwóch największych elementów w tablicy w kolejności wartości – bez sortowania tablicy!

2. Na podstawie algorytmu pierwszego opracować wyszukiwanie dwóch najmniejszych elementów w tablicy – również bez sortowania.

Chciałbym zapytać się czy moje rozwiązanie jest akceptowalne, ew. porady jak można byłoby je wykonać prościej.

<?php

$tab = array(20,6,7,5,1,8,25,12);

$max1 = $tab[0];
$max2 = $tab[1];

for($i=2; $i < count($tab); $i++){
    $pom = $tab[$i];
    
    $max1 > $max2 ? ($pom > $max2 ? $max2 = $pom : $max2 = $max2) : ($pom > $max1 ? $max1 = $pom : $max1 = $max1);
}

echo $max1 . "<br>" . $max2 . "<br><br>";

$min1 = $tab[0];
$min2 = $tab[1];

for($i=2; $i < count($tab); $i++){
    $pom = $tab[$i];
    
    $min1 > $min2 ? ($min1 > $pom ? $min1 = $pom : $min1 = $min1) : ($min2 > $pom ? $min2 = $pom : $min2 = $min2);
}

echo $min1 . "<br>" . $min2;

2 odpowiedzi

odpowiedź 3 grudnia 2019 przez dawid6512 Gaduła (4,550 p.)

ja bym to zrobil tak

 $max1 = 0;
        $max2 = 0;
        foreach($tab as $val){
            if($val > $max1){
                $max2 = $max1;
                $max1 = $val;
            }
        }

nie gwarantuje ze działa bo pisane na telefonie

komentarz 3 grudnia 2019 przez progNewbie Obywatel (1,130 p.)

Zadziałać, zadziała, ale to załatwi nam tylko tablice posortowane.

Nieposortowana np. {20,10,18} zwróci nam parę 20,0 co jest nieprawdą.

komentarz 3 grudnia 2019 przez dawid6512 Gaduła (4,550 p.)

racja, to moze tak

$max1 = 0;
        $max2 = 0;
        foreach($tab as $val){
            if($val > $max1){
                $max2 = $max1;
                $max1 = $val;
            }else if($val > $max2){
                $max2 = $val;
            }
        }

komentarz 4 grudnia 2019 przez progNewbie Obywatel (1,130 p.)
edycja 4 grudnia 2019 przez progNewbie

Też nie:

Rozpatrzmy przypadek tablicy np.: {20,6,15,7,25}

Wyniki:

[20,0][20,6][20,15][20,15][25,15] , co jest nie prawdą bo największa para to [25,20].

Kurczę nie czuję możliwości uproszczenia tego.

Trzeba sprawdzić, czy max1 czy max2 jest większy aby wiedzieć, które podmienić.

komentarz 4 grudnia 2019 przez progNewbie Obywatel (1,130 p.)

zainspirowany Twoim sposobem przerobiłem to na minimalnie krótsze.

$max1 = 0;
$max2 = 0;

for($i = 0; $i < count($tab); $i++){
    $max1 >= $max2 ? ($tab[$i] > $max2 ? $max2 = $tab[$i] : $max2 = $max2) : ($tab[$i] > $max1 ? $max1 = $tab[$i] : $max1 = $max1);
}

odpowiedź 5 grudnia 2019 przez damenox Obywatel (1,400 p.)

Proponuję w ten sposób

<?php

$tab = array(20,6,7,5,1,8,25,12);

$max1 = max($tab);
unset($tab[array_search($max1, $tab)]);
$max2 = max($tab);

echo "[{$max1}, {$max2}]";

A najmniejsze wykorzystując funkcję min.

Nie jest to najlepsze rozwiązanie ani najwydajniejsze, ale to jakie pierwsze mi przyszło do głowy

komentarz 5 grudnia 2019 przez progNewbie Obywatel (1,130 p.)

Hej, Profesor by mi tego nie przepuści. Nie możemy korzystać z gotowych funkcji. :P

komentarz 5 grudnia 2019 przez damenox Obywatel (1,400 p.)

Ehh, skądś to znam :P

komentarz 5 grudnia 2019 przez progNewbie Obywatel (1,130 p.)

a orientujesz się może nad złożonością obliczeniową algorytmów?

Czy tutaj będzie O(N) ?

komentarz 5 grudnia 2019 przez progNewbie Obywatel (1,130 p.)

Chyba nie O(N) bo tutaj są 3 operacje przypisania poza for'em.

Więc w takim razie chyba: O(N + 3) ?

komentarz 5 grudnia 2019 przez Tomek Sochacki Ekspert (227,510 p.)

Ehh dlaczego na polskich uczelniach pracują jako wykladowcy tacy idioci.... :( co jest zlego w uzywaniu gotowych funkcji? Potem przychodzą na staż ludzie ktorzy wszystko by robili petlami for a gotowyh metod nie znają... szczerze to nie pakietam juz kiedy uzywalem petli for i to zarowno w js jak i w backendzie... są lepsze metody dużo czytelniejsze j wygodniejsze... w takich chwilach ciesze sie, że nie studiowalem informatyki :)

komentarz 6 grudnia 2019 przez damenox Obywatel (1,400 p.)

@progNewbie,

Nie znam się dokładnie na liczeniu złożoności obliczeniowej więc nic nie pomogę bo nie chcę wprowadzić Cię w błąd.

Twoje rozwiązanie jest ok, ale lepiej by było gdyby zamiast dwóch forów użyć tylko jednego.

Spójrz na to rozwiązanie: https://stackoverflow.com/a/26448941

komentarz 6 grudnia 2019 przez progNewbie Obywatel (1,130 p.)

@Tomek Sochacki,

Najbardziej narzekam na pisanie bardzo ogólnikowych zadań, poleceń. Jako początkujący programista gdy czytam tego typu polecenia to rodzi mi się jeszcze więcej pytań i jeszcze bardziej nie wiem w jakiej formie mam oddać np. jakieś zadanie. Bo o swoich wymaganiach wprost nie mówi, a ma jakieś swoje upodobania, których od nas oczekuje.

@damenox,

Użyłem tutaj dwóch for'ów, ponieważ pierwszy wyszukuje parę maksymalnych, a drugi parę minimalnych. Wiem że można byłoby oba te wyszukania zamknąć w jednym forze, ale Profesor raczej oczekuje trzech "oddzielnych" funkcji. - przerobiłem już to na OOP.

Jakby nie było to bardzo dziękuję za podpowiedzi :P

komentarz 6 grudnia 2019 przez Tomek Sochacki Ekspert (227,510 p.)

Profesor

jestem ciekaw ile lat Ci "Profesorowie" przepracowali przy tworzeniu realnego, komercyjnego opgoramowania :) czy są ro osoby, które nawet chociaż tych 5 lat nie przepracowały gdzie indziej po za uczelnią...