Sprawdzanie c++ funkcja

Question

Witam, mam problem z funkcją która ma sprawdzać czy w tablicy są przynajmniej 2 takie same elementy, jeżeli są wypisuje "Sa 2 lub wiecej takich samych elementow" a jeżeli nie ma,  funkcja ma za zadanie wypisać na ekranie np. "Nie ma takich samych elementow"

Comments

W czym problem ? Nie zadałeś żadnego pytania.

Answer 1

Nie jest to trudne zadanie.

- Deklarujesz tablicę n-elementową

- W pętlach for każdy element tablicy, poczynając od pierwszego porównujesz kolejno z pozostałymi. Każdy pierwszy, pozytywny wynik porównania kończy wykonywanie pętli, wyświetlasz odpowiedni tekst. Jeśli nie będzie dwóch jednakowych elementów, pętle dobiegną końca, wtedy wyświetlasz drugi tekst.

Comments

Masz rację, o której było wiadomo. Na razie, jak widziałeś walczyliśmy z podstawowym uruchomieniem programu..

Nie mam gotowego pomysłu na optymalizację, ale pomyślę. Jeśli mnie się nie uda (nie jestem informatykiem), Ty opublikujesz optymalne rozwiązanie, żeby nasz kolega dostał szóstkę z zadania. Mnie samego też to interesuje.

P.S. Tę zewnętrzną pętlę można skrócić o jeden: int i mniejsze 9, gdyż ostatniego elementu nie ma już z czym porównywać.

---

Pierwszym pomysłem jaki przychodzi mi do głowy, to zastosować prosty algorytm sortowania elementów (i przy "okazji" wykrywać dwa jednakowe). Wtedy wystarczy jedna pętla, i Twój request będzie spełniony.

---

Z samej definicji, kontener danych "zbiór" czyli dla C++ std::set, ma przechowywać unikalne dane. W trakcie wykonywania na nim metody insert(...), zwraca parę wartości (std::pair... ). Jest to iterator wskazujący na wstawiany element i wartość true/false (czyli typ bool) wskazującą na to czy wstawienie się udało. Uda się jeśli danego elementu nie było w zbiorze. Wystarczy więc wstawiać po kolei elementy z tablicy do tegoż zbioru, sprawdzając czy przy jakimś wstawieniu nie będzie zwrócona 2 wartość false. Jeśli tak się stanie, mamy duplikat.

http://en.cppreference.com/w/cpp/container/set/insert

Dodatkowo, std::set posiada wbudowaną weń właściwość sortowania elementów wstawianych. To zajmuje czas i w tej implementacji jest zbędne. Stąd warto zastosować std::unordered_set który nie wykonuje tego sortowania. 

http://en.cppreference.com/w/cpp/container/unordered_set/insert

#include <iostream>
#include <unordered_set>

bool checkDuplicated(int * values, size_t size) {
    std::unordered_set<int> checkingSet;
    // Ostatni prawidłowy element tablicy
    --size;
    while(size--) {
        if(! checkingSet.insert(values[size]).second) {
            return true;
        }
    }
    return false;
}

int main() {
    int valuesDup[] = { 10, 22, 32, 55, 22, 21, 6, 23 };
    int valuesUniq[] = { 10, 22, 32, 55, 24, 21, 6, 23 };

    // Rozmiary tablic
    size_t valuesDup_size = sizeof(valuesDup) / sizeof(valuesDup[0]);
    size_t valuesUniq_size = sizeof(valuesUniq) / sizeof(valuesUniq[0]);

    // Naiwne sprawdzenie duplikatów
    std::cout << "W waluesDup "
        << (checkDuplicated(valuesDup, valuesDup_size) ? "": "nie ")
        << "występują duplikaty.\n";
    std::cout << "W waluesUniq "
        << (checkDuplicated(valuesUniq, valuesUniq_size) ? "": "nie ")
        << "występują duplikaty.\n";
}

Nieco gorszym rozwiązaniem, będzie wstawianie wszystkich elementów z tablicy bez sprawdzania czy udał się insert czy nie (czyli bez testu 2 wartości). Na koniec sprawdzenia wystarczy testować czy rozmiar zbioru (czyli *.size()), jest mniejszy nisz rozmiar tablicy. Jeśli nie, wszystkie elementy były unikalne. Jeśli mniejszy, to jakiś się powtórzył. To jest gorsze bo niepotrzebnie kontynuujesz wstawianie jeśli już można odkryć że było powtórzenie.

Jeszcze innym rozwiązaniem pozostającym w obrębie O(n), jest stosowanie mapy. Kluczem będzie wartość z tablicy a wartością licznik zwiększany po każdym wstawieniu. Wystarczy wtedy test licznika cz jest większy od 1.

Przy znanym zakresie danych w tabeli, można posłużyć się kontenerem std::bitset, ustawiając bit na danej pozycji i sprawdzając czy... nie jest już ustawiony...

To takie kilka pomysłów które szybko przychodzą do głowy... 

---

Hi Mokrowski

To rzeczywiście szybkie i bezpośrednie metody testowania zbiorów na unikatowość elementów, mieszczące się w zakresie O(n). Trzeba jednak mieć świadomość, że wewnętrznie wykonują podobny algorytm do naszego - dla każdego wstawianego/pobieranego elementu "skanują" cały zbiór. To również kosztuje czas.

Autor tematu ma teraz co najmniej 5 wariantów na wykonanie funkcji sprawdzającej.

Dziękuję za info. Chapeau bas!

---

Trzeba jednak mieć świadomość, że wewnętrznie wykonują podobny algorytm do naszego - dla każdego wstawianego/pobieranego elementu "skanują" cały zbiór. To również kosztuje czas.

Bzdura. Tam jest hash czyli funkcja skrótu. Tam nie ma skanowania całego zbioru. Znalezienie jest w O (1).

Answer 2

Najprostsze (i najmniej efektywne, ale działające) rozwiązanie to użycie dwóch pętli do przeglądnięcia zbioru.