|
Задача 1.
Элементами массива a[1..n] являются неубывающие
массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of
integer; a[1][1] <= ... <= a[1][m], ..., a[n][1] <= ... <=
a[n][m]). Известно, что существует число, входящее во все массивы a[i] (существует такое х, что для всякого i из [1..n]
найдётся j из [1..m], для которого a[i][j]=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инадлежит точка.
б. Каким именно отрезкам принадлежит точка.
[Решение]
Задача 9.
На пpямой своими концами заданы N отpезков. Найти точку, принадлежащую максимальному числу отрезков
[Решение]
Задача 10.
Вводится последовательность из n натуральных чисел. Необходимо определить наименьшее натуральное число, отсутствующее в последовательности.
[Решение]
Задача 11.
На длинной перфоленте записаны N попарно различных положительных целых чисел. Ваша ЭВМ может перематывать ленту на начало и считывать числа одно за другим. Внутренняя память машины может хранить только несколько целых чисел. Требуется найти наименьшее положительное целое число, которого нет на ленте. Опишите алгоритм, который сделает это за небольшое количество перемоток ленты.
[Решение]
Задача 12.
На столе в двух столбиках лежат 64 золотых и 64 серебряных монеты соответственно. Как серебряные, так и золотые монеты упорядочены в порядке убывания масс. Массы всех монет разные. Какое наименьшее количество взвешиваний необходимо для определения 64-ой монеты в порядке убывания масс среди всех 128 монет? За один раз можно взвешивать две монеты и определить, которая из них тяжелее. Ответ обосновать.
[Решение]
Задача 13.
Задано N наборов монет из различных стран. Наборы упорядочены по невозpастанию массы монет. В i-ом наборе ai монет. Необходимо за минимальное число взвешиваний на чашечных весах определить к-тую по массе монету среди всех монет.
[Решение]
Задача 14.
Заданы массивы A[1..n] и B[1..n]. Необходимо найти такие индексы i0 и j0, , что
ai0 + bj0 = max (ai + bj ),
где 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
мажорирующего элемента нет.
Необходимо определить, есть ли в массиве мажорирующий элемент, и если есть, то какой.
[Решение]
|
