W pascalu

Uwaga do realizacji zadania: program który będzie wyszukiwał dłużej niż 10 minut jest od razu dyskwalifikowany


W pliku o nazwie: proba.dat (umieszczonym w katalogu bieżącym programu), znajduje się zapisana tablica liczb całkowitych (Integer). Liczby są ułożone w porządku losowym.

Napisz program który:
1. odczyta ww plik
2. we wczytanych danych wyszuka liczbę która występuje dokładnie 2 razy (jest tylko jedna taka liczba wszystkie pozostałe dane są unikalne).
3. wyświetli na ekranie wyszukaną liczbę
4. wyświetli na jakich pozycjach (indeksy) liczba ta wystąpiła
plik jest ponizej

http://chomikuj.pl/cristiano303

1

Odpowiedzi

2010-04-17T10:04:41+02:00
Algorytm wygląda nast.:

1. Wczytać do tablicy pary: (liczba; jej indeks)
2. Posortować pary po pierwszej współrzędnej (lub leksykograficznie, tj. najpierw po pierwszej, później po drugiej współrzędnej - ale nie jest to wymagane)
3. Liniowo przejrzeć posortowany ciąg pamiętając ostatnią widzianą liczbę i wypisując z indeksem jeżeli się powtórzyła.

Do sortowania użyć jakiegoś algorytmu nlgn (np Quicksort).
Czas całego algorytmu jest ograniczony przez sortowanie i wynosi O(nlgn)

Jeżeli wiemy coś o liczbach (np. to, z jakiego są przedziału to możemy sortować kubełkowo) - wtedy czas całego algorytmu będzie O(n)
1 3 1