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

А. Какому количеству отpезков пpинадлежит точка.

Б. Каким именно отрезкам принадлежит точка.

 

Отсортируем концевые точки отрезков в порядке неубывания. Если несколько концевых точек отрезков имеют одинаковую координату, то сначала выпишем те из них, которые являются начальными точками отрезков, а за ними - конечные точки. Для такой сортировки необходимо для каждой точки сохранить информацию, является ли она правым или левым концом отрезка.

Рассмотрим одну из возможных реализаций:

Заведем массив A[1..2,1..2*N]; сначала в ячейки A[1,2i-1] и A[1,2i] заносим координаты начала и конца i-го отрезка, а в ячейки A[2,2i-1] и A[2,2i] - числа +i и -i -- признаки того, что соответствующие координаты являются началом и концом отрезка i. Сортируем столбцы массива A по неубыванию элементов первой строки, и если при этом несколько элементов первой строки равны (то есть соответствующие точки имеют одинаковые координаты), то сначала выписываем начальные точки отрезков (A[2,i]>0), а затем - конечные (A[2,2i-1]<0).

Заведем еще массив Pr[1..N], в котором будет храниться информация об отрезках, содержащих точку A[1,i]. После окончания работы алгоритма Pr[j]=1, если отрезок j содержит точку A[1,i], и Pr[j]=0 иначе. Сначала массив Pr нулевой.

Пусть в переменной C хранится количество отрезков, пересекающихся в точке A[1,i]. Сначала C=0.

Делаем проверку, размещается ли точка X левее A[1,1] или правее A[1,2*N]. Если да, то выводим сообщение о принадлежности точки бесконечному интервалу, если же нет, то будем росматривать массив A слева направо в порядке неубывания элементов. Пока выполняется следующее условие:

массив A не закончился и (или текущая точка A[1,i] < Xили текущая начальная точка отрезка A[1,i] = X) повторять Если A[1,i] - начальная точка отрезка, тоувеличить C на 1 (начался еще один отрезок с номером A[2,i]), и присвоить Pr[A[2,i]] значение 1. Если A[1,i] - конечная точка отрезка, тоуменьшить C на 1 (отрезок с номером -A[2,i] закончился), и присвоить Pr[-A[2,i]] значение 0.. конец_пока. Когда мы выйдем из цикла, то проверим: Если С=0, то X лежит на межотрезочном интервале (A[1,i-1], A[1,i]), иначе X пpинадлежит C отpезкам. Номера отрезков есть индексы единичных элементов массива Pr.Набросок этого фрагмента программы: i:=1; пока (i<=2*N) и ((A[1,i]<X) или (A[1,i]=X) и (A[2,i]>0)) повторять если A[2,i]>0 то C:=C+1; Pr[A[2,i]:=1 конец_то иначе C:=C-1; Pr[-A[2,i]:=0 конец_иначе i:=i+1; конец_пока если С=0,то X лежит на межотрезочном интервале (A[1,i-1],A[1,i]),иначе X пpинадлежит C отpезкам. Напечатаем номера этих отрезков: для i:=1 до N повторять если Pr[i]=1 то печатать i

Задача №11

Задана матрица натуральных чисел A(n,m). За каждый проход через клетку (i,j) взымается штраф A(i,j). Необходимо минимизировать штраф и

а) Пройти из какой-либо клетки 1-ой строки в n-ую строчку, при этом из текущей клетки можно перейти

1) в любую из 3-х соседних, стоящих в стpоке с номеpом на 1-цу большем;

2) в любую из 8 соседних клеток;

б) Реализовать пункт a) для перехода из клетки (1,1) в (n,m).

Для решения пункта 1 задачи достаточно воспользоваться

тем фактом, что для определения минимальной величины штрафа, взимаемого за проход в клетку i-той строки достаточно знать минимальные величины штрафа, взимаемого за проход в клетки (i-1)-той строки, которые являются соседними рассматриваемой клетке. Поэтому алгоритм решения пункта 1 следующий:

для i от 1 до nШтраф[i,1]:=A[i,1] для i от 2 до nдля j от 1 до mнцШтраф[i,j]:=Штраф[i-1,j]+A[i,j];если j>1 и Штраф[i,j] < Штраф[i-1,j-1]+A[i,j]; то Штраф[i,j]:=Штраф[i-1,j-1]+A[i,j];если j<m и Штраф[i,j] < Штраф[i-1,j+1]+A[i,j]; то Штраф[i,j]:=Штраф[i-1,j+1]+A[i,j];

кц

Задача №12

Даны две строки x и y. Строка x состоит из нулей и единиц, строка y из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 - либо в непустую последовательность букв A, либо в непустую последовательность букв B?

Пусть строка S₁ состоит из цифр 0 и 1 и имеет длину N, а строка S₂ (из символов A и B) - длину M.

Заведем матрицу А размера N на M, при этом строки матрицы помечаются i-ой цифрой строки S₁, а j-й столбец - j-м символом строки S₂.

Возьмем в качестве примера S₁='00110', S₂='AAAABBAA'.

Первая цифра строки S₁ (цифра 0) может быть преобразована в одну из последовательностей букв 'A','AA','AAA','AAAA', являющиеся префиксами строки S₂. Заносим символ 'x' в те столбцы первой строки, буквы-пометки которых соответствуют последним буквам возможных последовательностей. Таким образом, помечаются элементы A[1,1], A[1,2], A[1,3] и A[1,4].

Шаг алгоритма: будем преобразовывать очередную цифру S₁[i], которой соответствует строка i.

Находим 'x' в предыдущей строке при просмотре ее слева направо (этому столбцу соответствует последняя буква в какой-то из непустых последовательностей букв, порожденных на предыдущем шаге). Если текущую цифру можно преобразовать в последовательность букв, помечающих следующие за данным столбцы, то в этих столбцах в данной строке ставим 'x'.

Далее от места над последней помеченной ячейкой ищем в предыдущей строке 'x' и, когда находим, повторяем указанные выше операции.

Эти действия проводим далее для i=2,...,N.

Вид матрицы после N шагов:

Замечание: Можно обойтись и одномерным массивом. В самом деле, при заполнении следующей строки мы обращаемся только к элементам предыдущей строки, к каждому - по одному разу.

Алгоритм (без учета замечания) может быть следующим:

for i:=1 to N dofor j:=1 to M doA[i,j]:=' '; {инициализация}if S1[1]=0then element:='A' {0 преобразуется в A}else element:=S2[1]; {1 - в A или в B}i:=1;while (i<=M) and (S2[i]=element) do begin {первый шаг}A[1,i]:='x';i:=i+1end;for i:=2 to N do beginj:=2;while j<M do begin {просмотр строки i}if A[i-1,j-1]='x'then beginif S1[i]=0then element:='A'else element:=S2[j];if S2[j]=elementthenwhile (j<=M) and (S2[j]=element) do beginA[i,j]:='x';j:=j+1;end {end for while}else j:=j+1end {end for then}else j:=j+1end {end for while}end; {end for for}if A[N,M]='x'

then writeln('Можно преобразовать') else writeln('Нельзя преобразовать');</P></DIR>

Напишите программу, использующую одномерный массив.

Задача №13.

Пусть известно, что для перемножения матрицы размера n*m на матрицу размера m*k требуется n*m*k операций. Необходимо определить, какое минимальное число операций потребуется для перемножения n матриц А₁,...А_n, заданных своими размерами n(i)*m(i).

 

При этом можно перемножать любые две рядом стоящие матрицы, в результате чего получается матрица нужного размера.

Замечание:

n(i) - число строк в матрице A_i

m(i) - число столбцов в матрице A_i

n(i)=m(i)+1.

Определим через F[i,j] минимальное число операций, которое требуется для перемножения группы матриц с номерами от i до j включительно. Ясно, что F[i,i]=0. Перемножение матриц в такой группе может производиться различными способами, а именно, производить сначала перемножение наилучшим способом группы от i до k, затем от k+1 до j, наконец перемножить получившиеся матрицы. Понятно, что k может быть величиной от i до j-1. Учитывая требование получить наилучший результат, величина F[i,j] определяется как

F[i,j]=max(F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j]), где k может быть величиной от i до j-1, n[i], n[k+1], m[j] определяют размеры матриц, получившихся при перемножении в группах.

для i от 1 до N выполнятьF[i,i]:=0;дляl от 1 до N-1 выполнятьдля i от 1 до N-l выполнятьнцKol:=бесконечность;j:=i+l;для k от i до j-1 выполнятьесли Kol > F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j] то Kol:=F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j];всеF[i,j]:=Kol;кц

Задача №14

а) Из последовательности, состоящей из N чисел, вычеркнуть минимальное количество элементов так, чтобы оставшиеся образовали строго возрастающую последовательность.

б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, одной пары соседних элементов (одного "разрыва" возрастающей подпоследовательности).

Например: A=(1,2,3,2,4,3,4,6);