Мегаобучалка Главная | О нас | Обратная связь  


А. Какому количеству от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?

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

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

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

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

Шаг алгоритма: будем преобразовывать очередную цифру S1[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 матриц А1,...Аn, заданных своими размерами n(i)*m(i).

 

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

Замечание:

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

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

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




Читайте также:



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (592)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.008 сек.)