Wyszukiwanie binarne

26.11.2009 - Marcin Oczeretko
Trudność

Pierwsza większa:


    Zmodyfikuj nieco algorytm wyszukiwania binarnego tak, by znajdować w posortowanym niemalejąco ciągu pierwszą liczbę większą niż podana wartość.
   
Wejście:

    Pierwszy wiersz zawiera dwie liczby naturalne $ n $ i $ k $ ($ 1\le n \le 10^6 $, $ 1 \le k \le 1000 $).

    W drugiej linijce pojawi się $ n $ liczb: $ a_1, a_2, \ldots, a_n $ ($ 1 \le a_i \le 2^{30} $).

    W trzeciej linijce będzie $ k $ liczb: $ b_1, \ldots, b_k $ ($ 1 \le b_i < a_n $)


Wyjście:


    Dla każdej liczby $ b_i $ z trzeciego wiersza należy wypisać w osobnym wierszu taką liczbę $ a_j $ spośród $ a_1, \ldots, a_n $, że zachodzi nierówność:

$ a_{j-1} \le b_i < a_j $
   

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Słownik:


    Przeszukiwać binarnie możemy nie tylko ciągi zawierające same liczby. Algorytm ten poradzi sobie z każdym posortowanym zbiorem! Aby się o tym przekonać, napisz program, który sprawdzi czy podany wyraz występuje na uporządkowanej alfabetycznie liście różnych słów. Jeśli tak będzie to wypisuj jego pozycję.
   
Wejście:

    W pierwszym wierszu podana zostanie liczba naturalna $ n $ ($  1 \le n \le 10^5 $).

    W $ n $ kolejnych wierszach dostaniesz $ n $ uporządkowanych alfabetycznie słów: $ v_1, \ldots, v_n $.

    Kolejny wiersz zawierać będzie liczbę naturalną $ k $ ($ 1\le k \le 10^4  $).

    W $ k $ kolejnych wierszach podanych zostanie $ k $ słów: $ t_1, \ldots, t_k $.

    Możesz założyć, że wszystkie słowa na wejściu będą miały taką samą długość, która nie przekroczy 10 znaków.


   
Wyjście:

    Powinno składać się z i wierszy. W i-tym wierszu należy:

  • jeśli $ t_i $ występuje wśród wyrazów $ v_1, \ldots, v_n $: wypisać pozycję, na której możemy to słowo odnaleźć,
  • w przeciwnym wypadku: wypisać "NIE".

   

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Miejsce zerowe


    Przećwiczmy jeszcze wyszukiwanie miejsc zerowych funkcji. Napisz program, który dla danego wielomianu piątego stopnia w(x) poda jego miejsce zerowe w zaokrągleniu do 10 cyfr po przecinku. Dane wejściowe będą tak dobrane, by istniała tylko jedna taka wartość $ x_0 $, że $ w(x_0) = 0 $. Prawdziwa też będzie nastepująca nierówność:

$  0 < x_0 < 1  $

Wejście:


    Wejście składa się z jednej linii, zawierającej 6 liczb rzeczywistych: $ a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5} $
   
Wyjście:

    Wypisz miejsce zerowe wielomianu $ w(x) = a_{5}x^{5} + a_{4}x^{4} + a_{3}x^{3} + a_{2}x^{2} + a_{1}x + a_{0} $ w zaokrągleniu do 10 cyfr po przecinku. Należy wypisać dokładnie 10 cyfr z rozwinięcia dziesiętnego liczby (np. jeśli w zmiennej wynik typu double mamy wyliczone poprawnie 11 pierwszych cyfr po przecinku, to w języku C wypisujemy prawidłową wartość za pomocą printf("%.10lf",wynik) ).
   

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.923075
Twoja ocena: Brak Ocena: 4.9 (13 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com