• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Znajdź wartość, która występuje w nieparzystej liczby elementów C++

Fiszki IT
Fiszki IT
0 głosów
224 wizyt
pytanie zadane 9 czerwca 2016 w C i C++ przez Macek Kolo Mądrala (5,480 p.)
edycja 9 czerwca 2016 przez Macek Kolo

Kod:

#include <iostream>
#include <vector>

using namespace std;

int solution(vector<int> &A)
{
    int result = 0;
    for(int i : A)
    {
        result ^= i;
    }
    return result;
}

int main()
{
    vector<int> vec {9,3,9,3,9,6,9};
    cout << solution(vec) << endl;
    return 0;
}

Może mi ktoś powiedzieć z jakich ot własności liczb binarnych korzysta ta funkcja, że zwraca dobry wynik? Bo ja bym nie wpadł, że wystarczy xorować... Dlaczego to działa? 

Najpierw result ma 0, potem 9, nastepnie 10. Jak się to ma do tych liczb w vektorze? 

 

Strona z zadaniem https://codility.com/programmers/task/odd_occurrences_in_array/

komentarz 9 czerwca 2016 przez Patrycjerz Mędrzec (192,040 p.)
Przepraszam, ale po tytule w ogóle nie mogę się domyśleć, co ta funkcja robi.
komentarz 9 czerwca 2016 przez Macek Kolo Mądrala (5,480 p.)
no właśnie dokładnie to co jest napisane w tytule :)
komentarz 10 czerwca 2016 przez Patrycjerz Mędrzec (192,040 p.)

Jeśli wziąłeś tytuł zadania z translatora, to czego się dziwisz, że go nie zrozumiałem.

Po drugie, jest on nieadekwatny do tego, co ma robić funkcja solution, gdyż nic nie mówi o szukaniu liczby nie pasującej do wzorca.

komentarz 10 czerwca 2016 przez MetRiko Nałogowiec (37,130 p.)
Tu chyba nie chodziło o liczbę nie pasującą do wzorca, a bardziej ogólnie o element występujący nieparzystą ilość razy.. przynajmniej to wywnioskowałem wypisując sobie kolejne kroki.
1
komentarz 10 czerwca 2016 przez Patrycjerz Mędrzec (192,040 p.)

Racja, bo słowo unpaired mnie zmyliło, co nie zmienia to faktu, że tytuł jest mocno niejasny.

1 odpowiedź

+2 głosów
odpowiedź 9 czerwca 2016 przez MetRiko Nałogowiec (37,130 p.)
wybrane 10 czerwca 2016 przez Macek Kolo
 
Najlepsza
Xor jest przemienny (jak dodawanie), tak więc a^b jest równe b^a ponadto, a^a jest równe 0.
Skoro w wektorze znajduje się tylko 1 liczba bez pary to wynikiem będzie właśnie ona, ponieważ reszta się zniweluje.
Tu masz dokładnie rozpisane kroki:
r:
0(-) - 0000
1(9) - 0000 xor 1001 = 1001 = 9
2(3) - 1001 xor 0011 = 1010 = 10
3(9) - 1010 xor 1001 = 0011 = 3
4(3) - 0011 xor 0011 = 0000 = 0
5(9) - 0000 xor 1001 = 1001 = 9
6(6) - 1001 xor 0101 = 1101 = 13
7(9) - 1101 xor 1001 = 0101 = 6
Mam nadzieję, że o to ci chodziło :D
komentarz 10 czerwca 2016 przez Macek Kolo Mądrala (5,480 p.)
Dzięki, to teraz pytanie. Jak wpadać na takie rzeczy przy pisaniu kodu? Czy jedynym wyjściem jest robić tak dużo przykładów, że w końcu zaczną się powtarzać, czy jak?

To zadanie jest z codiliy, robiłem też inne i mimo, że przy większości u mnie wszystko działało to na stronie wywalało błąd np. czasu. Z programowaniem nie mam problemu, właśnie moje algorytmy ssą :(
1
komentarz 10 czerwca 2016 przez MetRiko Nałogowiec (37,130 p.)
Co do wpadania na takie rzeczy.. myślę, że tu jest potrzebna nie tylko praktyka (rozwiązywanie tego typu problemów), ale i również znajomość różnych twierdzeń matematycznych oraz umiejętność poprawnego ich wykorzystania w praktyce.. np. jeżeli chcesz znaleźć dwie ostatnie cyfry wartości n! nawet dla n=1000.. to wystarczy pomyśleć, że dla n>=10 silnia jest mnożona przez 2, 5 i 10.

Podobne pytania

0 głosów
1 odpowiedź 154 wizyt
pytanie zadane 20 czerwca 2018 w C i C++ przez Hiskiel Pasjonat (22,850 p.)
+1 głos
3 odpowiedzi 5,080 wizyt
pytanie zadane 12 maja 2015 w C i C++ przez Kabiszon Użytkownik (890 p.)
+2 głosów
2 odpowiedzi 64 wizyt
pytanie zadane 16 kwietnia w SPOJ przez manjaro Nałogowiec (34,560 p.)
Porady nie od parady
Możesz ukryć, zamknąć lub zmodyfikować swoje pytanie, za pomocą przycisków znajdujących się pod nim. Nie krępuj się poprawić pochopnie opublikowanego pytania czy zamknąć go po uzyskaniu satysfakcjonującej odpowiedzi. Umożliwi to zachowanie porządku na forum.Przyciski pytania

84,736 zapytań

133,542 odpowiedzi

295,952 komentarzy

56,001 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...