
                        ДИХОТОМИЯ И ПОИСК.

                            Задача 1.
     Дано целое х и массив целых  чисел  А[1],  ...,  А[n],  которые
отсортированы  в порядке неубывания и уже находятся в памяти.  Найти
такое i,  что A[i]=x,  или возвратить i=0, если элемента x в массиве
нет.

                           Задача 2.
     Задан массив чисел А[1:N,1:M],упорядоченный по возрастанию по
строкам и столбцам, т.е.:
             А[I,1]<А[I,2]<...<А[I,M]   (при всех I),
             А[1,J]<A[2,J]<...<А[N,J]   (при всех J).
     Найти элемент массива, равный заданному числу Х и отпечатать
его индексы (I,J).  Напечатать слово "НЕТ", если такого элемента
не  окажется.  Х  можно  сравнить  не более, чем с M+N элементами
массива.
                            Задача 3.
     Написать подпрограмму,  которая  в  двумерном массиве А(N,M)
целых чисел,  таком, что для всех I от 1 до N , J от 1 до М-1 вы-
полняется  А(I,J)>A(I,J+1)  и  для всех I от 1 до N-1 выполняется
A(I,M)>A(I+1,M),  находит все элементы A(I,J),  равные  J+I,  или
устанавливает, что таких элементов нет.

                           Задача 4.
     Написать подпрограмму,  которая в двумерном  массиве  А(N,M)
целых чисел,  таком, что для всех I от 1 до N , J от 1 до М-1 вы-
полняется А(I,J)<A(I,J+1) и для всех I от 1  до  N-1  выполняется
A(I,M)<A(I+1,M),  находит все элементы A(I,J),  равные J+I ,  или
устанавливает, что таких элементов нет.


                            Задача 5.
     Задана прямоугольная  таблица  А[1:N,1:N],  элементы  которой
равны 0 или 1 причем А[i,i]=0 для любого i.
     Необходимо найти,  если  они есть,  такие строку i0 и столбец
j0, чтобы в столбце j0 были все 0,  а в строке i0 - все  1  (кроме
элемента A[i0,i0], равного 0).

                            Задача 6.
     На плоскости  задается  выпуклый  N-угольник   целочисленными
кооpдинатами  своих  веpшин в порядке обхода по контуpу.  Вводятся
кооpдинаты точки (X,Y). Опpеделить:
         a) является ли она веpшиной N-угольника;
         б) пpинадлежит ли она N-угольнику.

                            Задача 7.
     На двух паpаллельных пpямых слева напpаво заданы по  N  точек
на каждой.

     ├────┬──────┬─────┬───┬───────┬──── A
     │    │     /     / x,y \      │
     │    │    /     /   .   \     │
     ├────┴───┴─────┴─────────┴────┴──── B
     0

     Их кооpдинаты задаются в массивах A[1..N] и B[1..N]. Расстоя-
ние между пpямыми единичное.  Вводится  точка  (X,Y),  где  0<Y<1.
Опpеделить,  в  какой из получившихся N-1 конечных и 2 бесконечных
тpапециях лежит точка.

                            Задача 8.
     На пpямой своими концами заданы N отpезков и точка X. Опpеде-
лить,  пpинадлежит ли точка межотpезочному интеpвалу.  Если да, то
указать концевые точки этого интервала. Если нет, то найти,
     а. Какому количеству отpезков пpинадлежит точка.
     б. Каким именно отрезкам принадлежит точка.

                            Задача 9.
     На пpямой своими концами заданы N отpезков. Найти точку, при-
надлежащую максимальному числу отрезков

                           Задача 10.
     Вводится последовательность из n натуральных чисел.Необходимо
определить наименьшее натуральное число,  отсутствующее в последо-
вательности.

                            Задача 11.
     На длинной  перфоленте  записаны  N попарно различных положи-
тельных целых чисел. Ваша ЭВМ может перематывать ленту на начало и
считывать  числа  одно  за другим.  Внутренняя память машины может
хранить только несколько целых чисел.  Требуется найти  наименьшее
положительное  целое  число,которого  нет на ленте.  Опишите алго-
ритм,который сделает это за небольшое количество перемоток ленты.

                            Задача 12.
     На столе в двух столбиках лежат 64 золотых  и  64  серебряных
монеты соответственно. Как серебряные, так и золотые монеты упоря-
дочены в порядке убывания масс. Массы всех монет разные. Какое на-
именьшее количество взвешиваний необходимо для  определения  64-ой
монеты  в порядке убывания масс среди всех 128 монет?  За один раз
можно взвешивать две монеты и определить,  которая из них тяжелее.
Ответ обосновать.

                            Задача 13.
     Задано N наборов монет из различных стран. Наборы упорядочены
по невозpастанию массы монет.  В i-ом наборе a_i монет. Необходимо
за  минимальное  число  взвешиваний  на  чашечных весах определить
к-тую по массе монету среди всех монет.

                            Задача 14.
     Заданы массивы A[1..n] и B[1..n].  Необходимо найти такие ин-
дексы i_0 и j_0, , что

                   a    + b    = max (a + b ),
                    i_0    j_0         i   j

где 1<=i<=n, 1<=j<=m , i<j.

                             Задача 15.
   Мажорирующим элементом в массиве A[1..N] будем  называть  эле-
мент,  встречающийся в массиве более N/2 раз. Легко заметить, что
в массиве может быть не более одного мажорирующего элемента. Нап-
ример, массив
   3, 3, 4, 2, 4, 4, 2, 4, 4
имеет мажорирующий элемент 4, тогда как в массиве
   3, 3, 4, 2, 4, 4, 2, 4
мажорирующего элемента нет.
   Необходимо определить, есть ли в массиве мажорирующий элемент,
и если есть, то какой.

