Dany jest ciąg rosnący a[0],..,a[n] oraz element x. Chcemy ustalić przedział (a[i],
a[i+1]>, w którym mieści się x ( lub czy x <=a[0] , czy x>a[n]). Opracuj rekurencyjny
algorytm rozwiązujący to zagadnienie. Przygotuj dane testowe.
Ma ktoś jakiś pomysł?
Matfizf napisał(a):
Ma ktoś jakiś pomysł?
Sprawdzaj wszystkie pary elementów (a[0], a[1]), (a[1], a[2]) itd.
Jeśli x <= a[0], albo x > a[n], to kończysz rekurencję i piszesz co ustaliłeś.
Jeśli x mieści się między elementami danej pary, to kończysz rekurencję i wypisujesz, że x mieści się w tym przedziale.
Trudność polega tylko na tym, że musisz rekurencyjnie iterować po tablicy i sprawdzać po dwa elementy.
to wygląda na zwykłe https://pl.wikipedia.org/wiki/Wyszukiwanie_binarne - z tym że nie szukamy konkretnej wartości tylko przedziału
Skoro masz ciąg rosnący czyli posortowaną tablicę to nie potrzebujesz przeszukiwać wszystkich par elementów, wystarczy że będziesz rekurencyjnie dzielił przedział na pół i znajdziesz maksymalną wartość mniejszą od x. wystarczy zmienić w algorytmie warunek końca na:
tablica[przeszukiwany_indeks] <= szukana && tablica[przeszukiwany_indeks + 1] > szukana
i poprawić resztę warunków i dodać obsługę wartości skrajnych.
W rzeczywistości nie musiałbyś w ogóle nic pisać. W .NET masz funkcję Array.BinarySearch która zachowuje się dokładnie tak jak chcesz - gdy jest znaleziona konkretna wartość to dostajesz indeks tej wartości - wtedy szukany przedział to a[i], a[i+1]
Jeśli nie jest znaleziona konkretna wartość to zwracana jest ujemna wartość która wskazuje na odwrócony bitowo indeks wartości gdzie wstawilibyśmy naszą wartość gdybyśmy ją mieli
var a = new[] { 1, 3, 4, 6, 9};
var x = 5;
var i= Array.BinarySearch(a, x);
if (i < -1) // musisz osobno obsłużyć wartości skrajne (pierwszy i ostatni indeks) żeby nie wykroczyć za tablicę
{
Console.WriteLine("Szukany przedzial to " + a[~i- 1] + " - " + a[~i]); // Szukany przedzial to 4 - 6
}