Задача Т-1 (C)

Светлана в категроии Информатика, вопрос открыт 22.04.2017 в 16:05

В массиве из N элементов разрешается между собой менять 1 и 3 элементы, 2 и 4, 3 и 5, 4 и 6 и т.д., а также первый и последний. Все остальные обмены элементов запрещены. При каких N с помощью таких операций массив всегда можно привести к отсортированному виду, а при каких N — не всегда.

Задача Т-2 (C)

В прямоугольной матрице NxM в каждой клетке записано некоторое число A[i,j]. Разрешается завести вспомогательную матрицу B[i,j] размера NxM и вычислить ее элементы с суммарной сложностью O(NM) так, чтобы затем, используя элементы этой матрицы, за константное (не зависящее от размеров матрицы и размеров прямоугольника) время давать ответ на вопрос о том, какова сумма элементов матрицы A в прямоугольнике с координатами противоположных угловых клеток (x1,y1), (x2,y2) (где x1,y1,x2,y2 — переменные, значения которых заранее не известны).
Вопрос: чему должны быть равны элементы матрицы B, как их вычислить, и как потом через них вычислять ответ на интересующий нас вопрос.


Задача Т-3 (C)

Рассмотрим следующую задачу. Есть глобальный массив a (используются его элементы с 1-го по N-ый), элементы идут в неубывающем порядке (это важно!). Требуется найти в этом массиве элемент, равный k.
Рассмотрим такую функцию, которая осуществляет поиск:

На языке Pascal:

function find(i, j, k: integer): integer;
var q: integer;
begin
q := ( i + j ) div 2;
if a[ q ] = k then find := q
else
if a[ q ] > k then find := find( i, q, k )
else find := find( q, j, k );
end;

На языке С/C++:

int find(int i, int j, int k)
{
int q;
q = ( i + j ) / 2;
if (a[q]==k) return q;
else {
if ( a[ q ] > k ) return find( i, q, k );
else return find(q, j, k );
}

Для поиска элемента, равного k ее нужно вызвать с параметрами find(1, N, k), где N — количество элементов в массиве.
Ответьте на следующие вопросы:
1) Всегда ли, если в массиве есть элемент, равный k, функция вернет его номер?
2) Что будет, если искомого элемента в массиве нет?
3) Приведите текст функции (по-возможности, модифицировав исходный текст как можно меньше) так, чтобы в случае отсутствия элемента функция возвращала бы 0, а в случае наличия элемента, всегда возвращала бы его номер.
4) Оцените сложность этой функции в зависимости от N.

Задача Т-4 (C, D)

Задача: из строки удалить все пробельные символы. Решение

procedure delspace( var s: string);
var i: integer;
begin
for i := 1 to length( s ) do
if s[ i ] = ' ' then delete( s, i, 1 );
end;

Постройте пример, на котором данная процедура будет удалять не все пробелы. Объясните, почему так происходит. Приведите правильное решение поставленной задачи.

Задача Т-5 (C,D)

Напишите фрагмент программы, который для двух переменных n и m (известно, что значения обеих переменных — натуральные числа, сами переменные — целого типа) выводит на экран 1, если N ≤ M, а если же N > M, то на экран выводится любое число, отличное от 1. При этом запрещено пользоваться условным оператором.

Задача Т-6 (C,D)

Василий живет в 15-этажном доме. Известно, что если кокос падает с 1-го этажа этого дома, то он не разбивается, а если с 15-го этажа, то разбивается. Василий хочет найти такое число X, что если кокос падает с этажа номер X, то он не разбивается, а если с этажа X+1 - то разбивается. Для этого он может ставить эксперименты - кидать кокос с разных этажей. При этом если кокос не разобьется, то его можно использовать для следующего эксперимента, а если разобьется, то использовать его дальше уже не получится. За какое наименьшее число экспериментов Василий может узнать число X, и какие эксперименты ему для этого нужно ставить, если для экспериментов ему выделено:
A. 1 кокос?
B. 2 кокоса?

Задача T-7 (D)

Сколько есть натуральных чисел, меньших 2013, квадрат которых делится на 13? Помимо ответа, опишите способ, каким вы этот ответ получили.