Algorytm sortowanie ze zliczaniem
zł30-90 PLN
Pago na entrega
W pewnym doświadczeniu zebrano dane pewnych pomiarów całkowitoliczbowych dodatnich. Dodatkowym parametrem w tym doświadczeniu była krotność wystąpień odpowiedniej wartości.
Zadanie programisty polega na wczytaniu danych, będących parami (pomiar, krotność), posortowanie ich w porządku rosnących pomiarów, a następnie wykorzystanie posortowanej tablicy danych do odszukiwania określonych krotności pomiarów.
Bardziej szczegółowo:
program otrzymuje na wejściu pewną liczbę tablic do posortowania
pierwszym zadaniem programu jest posortowanie każdej z nich w porządku rosnących pomiarów i wyświetlenie na standarowe wyjście
następnym zadaniem programu jest "połączenie" wszystkich posortowanych tablic w jedną dużą tablicę (posortowaną w tym samym porządku) i zwrócenie jej na standardowe wyjście
ostatnim zadaniem jest wyszukanie zadanych pomiarów w posortowanej tablicy par (pomiar, krotność), gdzie każdorazowo program dostanie do odszukania pomiar, a wyświetlić powinien jego krotność lub 0, jeśli liczba nie występuje w posortowanej tablicy
Proces sortowania jest specyficzny, ponieważ nie dopuszcza się powtórzeń pomiarów w tablicy wynikowej. Jeśli zostaną znalezione dwa elementy w tablicy o tym samym pomiarze, należy "złączyć" je w jedną komórkę o krotności będącej sumą krotności poszczególnych elementów. Np:
dla wejściowego ciągu danych (dla czytelności krotność w nawiasach)
12(3) 5(2) 10(1) 5(4)
Ciąg posortowany powinien wyglądać tak:
5(6) 10(1) 12(3)
Dane wejściowe
w pierwszym wierszu liczba tablic do posortowania
następnie dla każdej tablicy
liczba pomiarów (rozmiar tablicy),
pary elementow (pomiar, krotność), rozdzielone znakami białymi
następnie liczba pomiarów do wyszukania
sekwencja tych pomiarów rozdzielona znakami białymi
Wszystkie wielkości są liczbami całkowitymi, większymi od 0, mieszczącymi się w typie całkowitym 4-bajtowym bez znaku. Poszczególne krotności są na tyle małe, że ich suma (dla tego samego pomiaru) również mieści się w typie 4-bajtowym bez znaku.
Wyjście
Wymagany format wyjścia (wyświetlenia) każdej z tablic jest identyczny jak format wejścia. Liczba znaków białych rozdzielających poszczególne elementy wyjścia nie ma znaczenia.
Dodatkowe wymagania
sortowanie pojedynczej tablicy powinno mieścić się w czasie O(n2) (jako bazę algorytmu można wykorzystać dowolny znany algorytm)
w przypadku otrzymania na wejściu tablicy posortowanej, algorytm sortowania powinien mieścić się w czasie O(n)
algorytm mergingu dwóch posortowanych tablic powinien mieć złożoność liniową (przy długościach tablic odpowiednio n i m mieścić się w czasie O(n+m))
wyszukiwanie w posortowanej tablicy powinno mieścić się w czasie logarytmicznym O(ln n)
Przykład
Dane wejściowe, składające się z 4 tablic oraz 5 liczb do odszukania:
4
4 199 3 213 2 312 4 324 2
6 79 2 32 1 312 5 24 2 75 10 24 3
4 119 4 413 2 112 4 54 2
6 19 1 32 2 312 4 34 7 13 2 19 3
5
10 19 3 75 77
Oczekiwany wynik (najpierw każda z 4 posortowanych tablic, następnie jedna "złączona" tablica ze wszystkimi danymi, na koniec wyszukane krotności pomiarów z ostatniej linii wejścia):
4 199 3 213 2 312 4 324 2
5 24 5 32 1 75 10 79 2 312 5
4 54 2 112 4 119 4 413 2
5 13 2 19 4 32 2 34 7 312 4
15 13 2 19 4 24 5 32 3 34 7 54 2 75 10 79 2 112 4 119 4 199 3 213 2 312 13 324 2 413 2
0 4 0 10 0
nie można korzystać z gotowych funkcji sortujących trzeba je zaimplementować samemu
ID do Projeto: #8861453
Sobre o projeto
5 freelancers estão ofertando em média zł76 nesse trabalho
Hej, robiłem kiedyś podobny projekt na studiach. Wystarczy, że go odrobinę zmodyfikuję i będzie działał, dlatego mogę go bardzo szybko dostarczyć. Daj znać jeśli jesteś zainteresowany! Pozdrawiam, Dominik
Witam Proszę o kontakt poprzez wiadomość na portal Freelance - jest tutaj taka możliwość. Pozdrawiam
Witam, Jestem zainteresowany realizacją zlecenia. Projekt wygląda na prosty i nie powinienem mieć z nim problemów. Bardzo dobrze czuję się w c++, więc cała praca nie zajęłaby mi więcej niż 3 dni.