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

Quicksort źle segreguje tablicę z losowych liczb C++

VPS Starter Arubacloud
0 głosów
538 wizyt
pytanie zadane 12 września 2019 w C i C++ przez artur247 Nowicjusz (120 p.)

Cześć,

Uczę się programowania i mam problem, którego nie mogę rozwiązać. Chciałem napisać program na zasadzie Totolotka. Program pobiera 6 liczb od użytkownika. Sam też generuje 6 liczb losowych. Wyniki są zapisane w dwóch oddzielnych tablicach, a następnie są sortowane i wyniki z obu tablic są porównywane. Program bez problemu generuje liczby losowe. Jednak gdy ma je posortować to się wykrzacza. Nie wiem czemu ale gdy robię to samo dla liczb podanych przez użytkownika to wszystko jest ok. Z góry dzięki za pomoc. 

#include <iostream>
#include <time.h>
#include <cstdlib>

using namespace std;

void quicksort(int *tablica, int lewy, int prawy)
{
	int v = tablica[(lewy + prawy) / 2];
	int i, j, x;
	i = lewy;
	j = prawy;
	do
	{
		while (tablica[i] < v) i++;
		while (tablica[j] > v) j--;
		if (i <= j)
		{
			x = tablica[i];
			tablica[i] = tablica[j];
			tablica[j] = x;
			i++;
			j--;
		}
	} while (i <= j);
	if (j > lewy) quicksort(tablica, lewy, j);
	if (i < prawy) quicksort(tablica, i, prawy);
}

int main()
{
	srand(time(NULL));
	int tablica[6];
	int tablica2[6];

	cout << "Witam wszystkich na losowaniu duzego lottka." << endl;
	cout << "Podaj prosze 6 liczb z zakresu od 1 do 49 i zobaczymy czy to tobie sprzyja dzis szczescie." << endl;
	cout << "Pierwsza liczba:";
	cin >> tablica2[0];
	cout << "Druga liczba:";
	cin >> tablica2[1];
	cout << "Trzecia liczb:";
	cin >> tablica2[2];
	cout << "Czwarta liczba:";
	cin >> tablica2[3];
	cout << "Piata liczba:";
	cin >> tablica2[4];
	cout << "Szosta liczba:";
	cin >> tablica2[5];
	for (int i = 0; i < 6; i++)
	{
		do
		tablica[i] = rand() % 49 + 1;
		while (tablica[0] == tablica[1] == tablica[2] == tablica[3] == tablica[4] == tablica[5]);
		quicksort(tablica, 0, 5);


		cout << tablica[i] << " ";
	}
	cin.get();
	return 0;
}

 

2 odpowiedzi

0 głosów
odpowiedź 12 września 2019 przez tkz Nałogowiec (42,000 p.)
#include <algorithm>
#include <iostream>
#include <time.h>
#include <cstdlib>
 
using namespace std;
 
void quicksort(int *tablica, int lewy, int prawy)
{
    int v = tablica[(lewy + prawy) / 2];
    int i = lewy;
    int j = prawy;
    do
    {
        while (tablica[i] < v) i++;
        while (tablica[j] > v) j--;
        if (i <= j)
        {
           swap( tablica[ i ], tablica[ j ]);
            i++;
            j--;
        }
    } while (i <= j);
    if (j > lewy) quicksort(tablica, lewy, j);
    if (i < prawy) quicksort(tablica, i, prawy);
}
 
int main()
{
    srand(time(NULL));
    int tablica[6];
    int tablica2[6];
 
    cout << "Witam wszystkich na losowaniu duzego lottka." << endl;
    cout << "Podaj prosze 6 liczb z zakresu od 1 do 49 i zobaczymy czy to tobie sprzyja dzis szczescie." << endl;
    cout << "Pierwsza liczba:";
    cin >> tablica2[0];
    cout << "Druga liczba:";
    cin >> tablica2[1];
    cout << "Trzecia liczb:";
    cin >> tablica2[2];
    cout << "Czwarta liczba:";
    cin >> tablica2[3];
    cout << "Piata liczba:";
    cin >> tablica2[4];
    cout << "Szosta liczba:";
    cin >> tablica2[5];
    for (int i = 0; i < 6; i++)
        tablica[i] = rand() % 49 + 1;
    quicksort(tablica2, 0, 5);
    for (int i = 0; i < 6; i++)
    {
        if(tablica[i]==tablica2[i])
            cout << tablica[i] << " ";
    }
    
    cin.get();
    return 0;
}

Sam w sobie działa. http://cpp.sh/ dałem tylko inne sprawdzanie tablic, bo nie wiem co chciałeś uzyskać tym whielm. 

komentarz 12 września 2019 przez artur247 Nowicjusz (120 p.)
Whilem chciałem uzyskać to, żeby generowało kolejne liczby tak długo, aż nie będą się powtarzać. Poza tym dodałeś tylko drugą funkcję for ,żeby się wyświetliła tablica 1 gdy tablica 2 jest taka sama, a nigdy nie będą takie same, bo nie wiem czemu ale quicksort dla tabeli numer 1 czyli liczb generowanych pseudo losowo powoduje, że wyskakują liczby z poza zakresu typu "-858993460" i się w dodatku powtarzają.
komentarz 12 września 2019 przez tkz Nałogowiec (42,000 p.)

#include <algorithm>
#include <iostream>
#include <time.h>
#include <cstdlib>

using namespace std;

void quicksort(int *tablica, int lewy, int prawy)
{
    int v = tablica[(lewy + prawy) / 2];
    int i = lewy;
    int j = prawy;
    do
    {
        while (tablica[i] < v) i++;
        while (tablica[j] > v) j--;
        if (i <= j)
        {
           swap( tablica[ i ], tablica[ j ]);
            i++;
            j--;
        }
    } while (i <= j);
    if (j < lewy) quicksort(tablica, lewy, j);//tutaj na odrót miałeś
    if (i > prawy) quicksort(tablica, i, prawy);
}

int main()
{
    srand(time(NULL));
    int tablica[6];
    int tablica2[6];
    cout << "Witam wszystkich na losowaniu duzego lottka." << endl;
    cout << "Podaj prosze 6 liczb z zakresu od 1 do 49 i zobaczymy czy to tobie sprzyja dzis szczescie." << endl;
    cout << "Pierwsza liczba:";
    cin >> tablica2[0];
    cout << "Druga liczba:";
    cin >> tablica2[1];
    cout << "Trzecia liczb:";
    cin >> tablica2[2];
    cout << "Czwarta liczba:";
    cin >> tablica2[3];
    cout << "Piata liczba:";
    cin >> tablica2[4];
    cout << "Szosta liczba:";
    cin >> tablica2[5];
    quicksort(tablica2, 0, 5);
    for (int i = 0; i < 6; i++)
        if(int random = rand() % 49 + 1; tablica[i] !=random)
            tablica[i] = random;
        else
            i--;
    tablica[0] = 5;
    quicksort(tablica, 0, 5);
    for (int i = 0; i < 6; i++)
    {
        if(tablica[i]==tablica2[i])
            cout << tablica[i] << " ";
    }

    return 0;
}

 

komentarz 12 września 2019 przez j23 Mędrzec (194,920 p.)

@tkz, pewny jesteś tej pętli z linii 48?

Losowanie bez powtórzeń można zrobić tak:

    for (int i = 0; i < 6;) {
        int rnd = rand() % 49 + 1; 
        auto j = std::find(tablica, tablica + i, rnd);
        if(j == tablica + i) { *j = rnd; ++i; }
    }

Choć użycie std::shuffle byłoby jeszcze prostsze.

komentarz 12 września 2019 przez tkz Nałogowiec (42,000 p.)

Dobra, teraz widzę, że pomysł był średni. Ogólnie użył bym tego

    vector<int> lotto(49);
    iota(lotto.begin(), lotto.end(), 1);
    mt19937 random{random_device{}()};
    shuffle(lotto.begin(), lotto.end(), random);

 

komentarz 13 września 2019 przez artur247 Nowicjusz (120 p.)

@j23, Dzięki za pomoc teraz działa. Mam jeszcze tylko 1 pytanko. Jak mogę w miarę prosto i szybko porównać sobie te 2 tablice. Tak aby wyświetlało się ile liczb zgadł użytkownik. Chciałem to zrobić "ifem" ale nie wiem jak to zrobić w prostszy sposób niż wypisywanie wszystkich możliwości.

komentarz 13 września 2019 przez tkz Nałogowiec (42,000 p.)
for (int i = 0; i < 6; i++)
    {
        if(tablica[i]==tablica2[i])
            cout << tablica[i] << " ";
    }

 

komentarz 13 września 2019 przez j23 Mędrzec (194,920 p.)

@artur247: można tak:

    for (int i = 0; i < 6; ++i) {
        if(std::binary_search(tablica, tablica + 6, tablica2[i]))
            std::cout << tablica2[i] << ' ';
    }

Sortujesz liczby, więc możesz użyć std::binary_search, choć dla tak małych tablic można spokojnie zastosować std::find.
 

PS. zamiast implementować własną funkcję sortującą, możesz/powinieneś użyć std::sort.

0 głosów
odpowiedź 13 września 2019 przez Piotr Batko Stary wyjadacz (13,190 p.)

Koledzy wyjaśnili Ci już jak napisać ten program szybko, elegancko i wydajnie. Uważam jednak, że pisanie swojej funkcji sortującej na początkowym etapie nauki jest bardzo dobrym ćwiczeniem i nie przesadzałbym ze stosowaniem do wszystkiego biblioteki standardowej. Postaram się zatem wyjaśnić dlaczego ta wersja programu, jaką zamieściłeś w pytaniu nie działała i podpowiedzieć w rozwiązaniu kolejnego problemu jaki opisałeś w komentarzach, a więc jak sprawdzić ile liczb trafił użytkownik.

Dlaczego nie działało?
W warunku pętli while napisałeś coś takiego, jakbyś chciał sprawdzić, czy wszystkie liczby mają taką samą wartość. Tak jakby losowanie 1, 1, 1, 1, 1, 2 Ci odpowiadało :) Oczywiście tak nie jest. To sprawdzenie jest niepoprawne jeszcze z paru powodów. Po pierwsze gdy wykonywać się ono będzie po wylosowaniu pierwszej liczby, to w tablicy mogą być dowolne wartości (np. 12325, -125, 9999999 itd.). Odpalamy program, jesteśmy po losowaniu pierwszej liczby, wypadło 3. Sprawdzamy czy w tablicy wszystkie liczby są różne (zawartość tablicy to teraz: 3, -125, 9999999 itd.). Powiedzmy, że są różne, więc losowanie się kończy, ale to nie jesteśmy usatysfakcjonowani wynikami, prawda? :D A ostatnim powodem, przez który program nie działał jest to, że w C++ porównanie: a == b == c. Działa trochę inaczej niż sobie wyobrażałeś. Taki zapis nie oznacza "czy a i b i c są równe?". To jest wykonywane tak, że najpierw jest sprawdzane, czy a == b. To nam zwraca jakiś wynik, np. true i wyrażanie teraz wygląda tak: true == c. Zupełnie nie o to chodziło Ci przy pisaniu Twojego warunku :) Ufff... no to wiemy co było źle. Teraz zajmiemy się tym...

Jak zrobić, żeby działało?
Możesz delikatnie przerobić swoją pętlę i napisać ją mniej więcej tak:

for (int i = 0; i < 6; i++)
{
	int wylosowanyNumer;
	do
	{
		wylosowanyNumer = rand() % 49 + 1;
	} while (tablicaZawieraLiczbe(wylosowaneNumery, i, wylosowanyNumer));

	wylosowaneNumery[i] = wylosowanyNumer;
}

quicksort(wylosowaneNumery, 0, 5);
wypiszZawartoscTablicy(wylosowaneNumery, 6);

Żeby powyższy kod zadziałał musisz napisać wcześniej funkcje:

bool tablicaZawieraLiczbe(int tablica[], int rozmiar, int liczba);
void wypiszZawartoscTablicy(int tablica[], int rozmiar);

ale to już pozostawię jako ćwiczenie :) Funkcja tablicaZawieraLIczbe zwraca true, gdy... tablica zawiera podaną liczbę :) Co robi wypiszZawartoscTablicy chyba nie muszę tłumaczyć? :)

Aha! No i zmieniłem nazwę zmiennej tablica w Twoim kodzie na wylosowaneNumery, żeby mi się go łatwiej czytało. Musisz zwrócić na to uwagę przy wklejeniu powyższej pętli do swojego kodu.

Jak napisać sprawdzenie ile liczb trafił użytkownik?
Wiesz już jak to zrobić z wykorzystaniem std::find, ale możesz spróbować zastosować w to miejsce już zaimplementowaną funkcję własnego autorstwa: tablicaZawieraLiczbe.

Powodzenia! :)

komentarz 13 września 2019 przez DragonCoder Nałogowiec (36,500 p.)
Dodam, ze istnieje biblioteka random, a rand jest już odradzany do uzywania

Podobne pytania

–1 głos
0 odpowiedzi 2,594 wizyt
pytanie zadane 13 lipca 2018 w C i C++ przez Jason_Nr_1 Bywalec (2,980 p.)
0 głosów
2 odpowiedzi 4,510 wizyt
pytanie zadane 22 marca 2018 w C i C++ przez darek_s91 Użytkownik (580 p.)
0 głosów
1 odpowiedź 511 wizyt

92,453 zapytań

141,262 odpowiedzi

319,086 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...