Algorytm sortowanie ze zliczaniem

Encerrado Postado Nov 8, 2015 Pago na entrega
Encerrado 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

Programação C++

ID do Projeto: #8861453

Sobre o projeto

5 propostas Projeto remoto Ativo em Dec 15, 2015

5 freelancers estão ofertando em média zł76 nesse trabalho

McHay

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

zł65 PLN em 1 dia
(1 Comentário)
0.2
sobitps

Witam Proszę o kontakt poprzez wiadomość na portal Freelance - jest tutaj taka możliwość. Pozdrawiam

zł85 PLN in 3 dias
(0 Comentários)
0.0
ahhlcistzl

Nie złożono jeszcze oferty.

zł75 PLN in 3 dias
(0 Comentários)
0.0
kowal9517

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.

zł80 PLN in 3 dias
(0 Comentários)
0.0