Squashu Temat założony przez niniejszego użytkownika |
[C++] Sortowanie bąbelkowe » 2017-01-06 22:20:01 Witam, mam dosc specyficzny problem z moim algorytem sortowania. Przy wpisaniu do tablicy liczby 1004, program wyrzuca mi z powrotem 582 - nie mogę zrozumieć gdzie popełniam błąd. Treść zadania W miasteczku Macondo co tydzień odbywa się loteria z cennymi nagrodami. Sprzedawane losy mają przypisane numery od 1 do 100 000 000. Losowany jest tylko jeden zwycięski kupon. Niektórzy mieszkańcy podejrzewają, że maszyna losująca nie jest do końca uczciwa i pewne numery mają większe szanse na wygraną. Sprawdź, czy wyniki dotychczasowych losowań wskazują na taką możliwość. Wejście Pierwsza linia wejścia zawiera liczbę n (1 <= n <= 100 000) dotychczasowych losowań. W kolejnych n liniach podane są numery kuponów, które wygrały w poszczególnych losowaniach (liczby całkowite z zakresu od 1 do 100 000 000). Wyjście Wypisz posortowane rosnąco numery, które zostały wylosowane więcej niż jeden raz. Przykład Wejście: 7 1 3 8 3 1 3 1004 Wyjście: 1 3 #include <iostream>
void zmiana( int & a, int & b ) {
int temp = a;
a = b;
b = temp;
}
void sort_b( int Tab[], int a ) {
for( int i = 0; i < a; i++ ) {
for( int j = a; j > i; j-- ) {
if( Tab[ j ] < Tab[ j - 1 ] ) {
zmiana( Tab[ j ], Tab[ j - 1 ] );
}
}
}
}
int main() {
int ilosc;
std::cin >> ilosc;
int Tab[ ilosc ];
for( int j = 0; j < ilosc; j++ ) {
std::cin >> Tab[ j ];
}
sort_b( Tab, ilosc );
for( int j = 0; j < ilosc; j++ ) {
std::cout << Tab[ j ] << " ";
}
std::cout << std::endl;
for( int j = 1; j < ilosc; j++ ) {
if(( Tab[ j ] == Tab[ j - 1 ] ) &&( Tab[ j ] != Tab[ j + 1 ] ) ) {
std::cout << Tab[ j ] << std::endl;
}
}
return 0;
}
|
|
Gibas11 |
» 2017-01-06 22:49:04 Masz nałożone jakieś ograniczenia co do wykorzystania biblioteki standardowej? Jeśli nie to raczej źle do tego podszedłeś, całość można zmieścić w ~18 linijkach właściwego kodu bez przejmowania się zbędną pracą, wszystkie zadania typu sortowanie czy usuwanie duplikatów możesz oddelegować do do gotowców w STL. //edit: 1. int Tab[ ilosc ]; To jest niezgodne ze standardem C++, zastąp tą tablicę std::vector albo dynamicznie alokuj pamięć operatorem new . 2. for( int j = 1; j < ilosc; j++ ) {
if(( Tab[ j ] == Tab[ j - 1 ] ) &&( Tab[ j ] != Tab[ j + 1 ] ) ) {
std::cout << Tab[ j ] << std::endl;
}
} …? |
|
michal11 |
» 2017-01-06 23:54:54 To jest chyba spoj (albo cos podobnego) wiec raczej nie masz ograniczeń na stosowanie biblioteki standardowej, dlatego podam alternatywne, prostsze rozwiązanie które możesz zastosować. Dane wczytuj do std::set żeby wykluczać od razu duplikaty, przekopiuj dane do std::vector, użyj std::sort i wypisz vector na wyjście, korzystając z std::copy można to zrobić praktycznie w 4 liniach kodu (bez deklaracji zmiennych, bibliotek itd.) |
|
Gibas11 |
» 2017-01-07 00:00:27 @up Sam chciałem to tak napisać, ale przy wczytaniu od razu do std::set nie ma jak usunąć tego, co występuje tylko raz. Ja zrobiłem to tak: - Wczytanie zmiennych do std::vector . - Usunięcie liczb, które występują tylko raz ( std::remove_if i std::count_if ). - Skopiowanie całości do std::set , on automatycznie usunął duplikaty i posortował dane. - Wypisanie przez std::copy i std::ostream_iterator . |
|
Squashu Temat założony przez niniejszego użytkownika |
» 2017-01-07 00:39:11 1. Struktury danych dowolne - nie możemy stosować tylko "gotowcow" 2. Poprawiłem 3. Problem znikł, tablica jest już dobrze sortowana - niby wszystko działa ale sprawdzarka ciągle odrzuca. 4. Dziękuje za dotychczasową pomoc :) #include <iostream>
#include <vector>
void zmiana( int & a, int & b ) {
int temp = a;
a = b;
b = temp;
}
void sort_b( std::vector < int >& Tab ) {
for( int i = 0; i < Tab.size(); i++ ) {
for( int j = Tab.size(); j > i; j-- ) {
if( Tab[ j ] < Tab[ j - 1 ] ) {
zmiana( Tab[ j ], Tab[ j - 1 ] );
}
}
}
}
int main() {
int ilosc, temp;
std::cin >> ilosc;
std::vector < int > Tab;
for( int j = 0; j < ilosc; j++ ) {
std::cin >> temp;
Tab.push_back( temp );
}
sort_b( Tab );
for( int j = 0; j < ilosc; j++ ) {
if(( Tab[ j ] == Tab[ j - 1 ] ) &&(( j + 1 == ilosc ) ||( Tab[ j ] != Tab[ j + 1 ] ) ) ) {
std::cout << Tab[ j ] << std::endl;
}
}
return 0;
}
|
|
mokrowski |
» 2017-01-07 01:36:43 Nie wiem czy spełnia "warunki sprawdzarki" bo nie podałeś linku do zadania a nie ukrywam że nie chce mi się szukać :-/ Dość że tu masz (jakieś) rozwiązane na algorytmach do postudiowania.... #include <vector>
#include <algorithm>
using namespace std;
void read_and_show_repeated( size_t count ) {
vector < unsigned long > vec;
copy_n( istream_iterator < unsigned long >( cin ), count, vec.begin() );
sort( vec.begin(), vec.end() );
auto iter = vec.begin();
while( iter != vec.end() ) {
auto repeated_value_iter = adjacent_find( iter, vec.begin() );
if( repeated_value_iter != vec.end() ) {
cout << * repeated_value_iter << '\n';
} else {
break;
}
while(( ++iter != vec.end() ) and( * iter == * repeated_value_iter ) );
}
}
int main() {
size_t count;
cin >> count;
read_and_show_repeated( count );
}
PS. Właśnie poszukałem.. Do tego zadania bubble sort nie spełnia warunków dobrego rozwiązania. Zaimplementuj quick sort (o ile znalazłem To zadanie). |
|
czaffik |
» 2017-01-07 02:16:07 Nie będę podawał jak rozwiązać to zadanie, masz dużo dobrych rad. Twój warunek może i działa ale jest jeden mały błąd, w pierwszym obiegu pętli wektor wyjdzie poza zakres: j = 0:
if(( Tab[ 0 ] == Tab[ - 1 ] ) &&(( 1 == ilosc ) ||( Tab[ 0 ] != Tab[ 1 ] ) )
a co się kryje pod Tab[-1] możesz sprawdzić: std::cout << "element -1: " << Tab[ - 1 ];
|
|
Squashu Temat założony przez niniejszego użytkownika |
» 2017-01-07 12:43:25 @up
poprawiłem błąd w pętli, faktycznie nie zauważyłem, że zaczynam od 0. Dziękuje
@mokrowski
Dziękuje Ci bardzo, faktycznie po zmianie algorytmu na qsort sprawdzarka przyjęła wszystko
Temat zamykam, dziękuje za pomoc. |
|
| « 1 » |