Kzzav Temat założony przez niniejszego użytkownika |
Program wyszukujący ze zbioru liczb dwie, o najmniejszej różnicy » 2010-11-09 23:36:56 Witam.
Mam zadanie - napisać program, który ze zbioru dowolnej ( duużej ) ilości liczb, wyszuka dwie, których różnica jest jak najmniejsza, i wypisze tą różnicę. Np.
Dla liczb: 1 4 6 15 10
Program powinien wypisać: 2
Udało mi się zrobić taki program, problemem jest jednak czas wykonania przy większej ilości.
Otóż program musi znaleźć tą różnicę w czasie krótszym niż 4 sekundy...
Prosiłbym o jak najkrótszą metodę wyszukiwania tej różnicy. |
|
malan |
» 2010-11-10 00:15:01 2? Moim zdaniem to będzie -14. |
|
ison |
» 2010-11-10 10:20:00 Kzzav nie sprecyzowałeś treści zadania... po pierwsze: limity no dobra, program ma działać mniej niż 4 sekundy, ale dla ilu liczb? po drugie: czy wynikiem musi być dodatnia liczba? tak jak już to malan zauważył np {4,6,6} -> 4-6=-2 po trzecie: czy muszą być to 2 różniące się od siebie liczby? np {4,6,6} -> 6-6=0 po czwarte: czy może być to różnica tej samej liczby z samą sobą? np {5} -> 5-5=0 jeśli nie to co program ma zrobić jeśli dostanie tylko 1 liczbę? program, liczący najmniejszą różnicę dwóch dowolnych liczb, która w wyniku musi dać liczbę większą od 0 w złożoności O(n*logn) #include <cstdio>
#include <algorithm>
#define MAX_VALUE 2147483647
#define MAX_N 100000
int main()
{
int n, najm = MAX_VALUE;
int tab[ MAX_N ];
scanf( "%d", & n );
for( int i = 0; i < n; ++i ) {
scanf( "%d", & tab[ i ] );
}
std::sort( tab, tab + n );
for( int i = 1; i < n; ++i ) {
if( tab[ i ] - tab[ i - 1 ] < najm ) najm = tab[ i ] - tab[ i - 1 ];
}
printf( "%d\n", najm );
}
nie podałeś limitów więc ustawiłem wartości maxymalne tak jak wyżej, jeśli będzie to konieczne (tzn ten algorytm to część jakiegoś większego projektu) to użyj tablic dynamicznych W moim rozwiązaniu najpierw sortuję podane liczby, więc mam pewność że dla każdego i>0 tab[i]>=tab[i-1] -> mogę wtedy przeszukać tablicę od lewej strony i sprawdzić różnicę między kolejnymi elementami W programie na początku podajesz ilość liczb. Nie powiedziałeś co ma się stać gdy na wejściu program dostanie tylko 1 liczbę więc tego nie uwzględniłem |
|
malan |
» 2010-11-10 13:14:52 @ison: Trochę tego nie przemyślałeś... Twój algorytm zadziała w jakiś 10% może.
Poczekajmy, aż Kzzav poda więcej informacji, bo pisać programy tylko po to, żeby coś napisać to nie ma sensu. |
|
ison |
» 2010-11-10 13:20:28 @malan możliwe, pisałem to na szybko, przepraszam jeśli mój program wypisuje bzdury :D
mógłbyś podać przykład gdzie mój algo nie zadziała? bo jakoś nie mogę sobie tego wyobrazić |
|
malan |
» 2010-11-10 13:26:49 Może to ja piszę bzdury? ;p
Dla różnicy większej niż zero (0) działa :). Trochę się pospieszyłem, sory. |
|
ison |
» 2010-11-10 13:51:45 2? Moim zdaniem to będzie -14
|
w zadaniu nie chodzi o najmniejszą różnicę 2 dowolnych liczb np dla {5,6} 5-6=-1 tylko o najmniejszą odległość 2 liczb na osi liczbowej tzn dla {-5,-7} wynikiem powinno być 2 a nie -2 mój algorytm działa dobrze ;p, wszystkie pytania które zadałem do autora w moim 1 poście wycofuję, gdyż treść zadania można interpretować na 2 sposoby - jako najmniejszą różnicę lub najmniejszą odległość na osi liczbowej |
|
Elaine |
» 2010-11-10 14:05:39 Co oznacza to 2147483647 i dlaczego jest to właśnie tyle? |
|
| « 1 » 2 |