Задача 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 точек на каждой.
Их коо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инадлежит точка.
б. Каким именно отрезкам принадлежит точка.
Задача 11.
На длинной перфоленте записаны N попарно различных положительных целых чисел. Ваша ЭВМ может перематывать ленту на начало и считывать числа одно за другим. Внутренняя память машины может хранить только несколько целых чисел. Требуется найти наименьшее положительное целое число, которого нет на ленте. Опишите алгоритм, который сделает это за небольшое количество перемоток ленты.
Задача 12.
На столе в двух столбиках лежат 64 золотых и 64 серебряных монеты соответственно. Как серебряные, так и золотые монеты упорядочены в порядке убывания масс. Массы всех монет разные. Какое наименьшее количество взвешиваний необходимо для определения 64-ой монеты в порядке убывания масс среди всех 128 монет? За один раз можно взвешивать две монеты и определить, которая из них тяжелее. Ответ обосновать.
Задача 13.
Задано N наборов монет из различных стран. Наборы упорядочены по невозpастанию массы монет. В i-ом наборе ai монет. Необходимо за минимальное число взвешиваний на чашечных весах определить к-тую по массе монету среди всех монет.
Задача 15.
Мажорирующим элементом в массиве A[1..N] будем называть элемент, встречающийся в массиве более N/2 раз. Легко заметить, что в массиве может быть не более одного мажорирующего элемента. Например, массив
3, 3, 4, 2, 4, 4, 2, 4, 4
имеет мажорирующий элемент 4, тогда как в массиве
3, 3, 4, 2, 4, 4, 2, 4
мажорирующего элемента нет.
Необходимо определить, есть ли в массиве мажорирующий элемент, и если есть, то какой.
