Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Сортировка >> Номер 20

[Назад]    [Содержание ]    [Вперед]

  


Номер 20


  Условие: Номер 20


Задача 20. Построить максимальное множество, состоящее из попарно не сравнимых векторов v. Векторы v определяются парами чисел, выбираемые из данной последовательности чисел а1, ...аn , n>=1. Два вектора v=(а,в) и v'=(а',в') называются сравнимыми, если а<=а' и в<=в' или а>=а' и в>= в', в противном случае не сравнимыми.

  Решение задачи: Номер 20


Решение задачи 20. Пусть числа a[1], ..., a[n] расположены в порядке неубывания (если это не так, то просто отсортируем массив). Будем выписывать искомые векторы v[1], ..., следующим образом: Пусть k - номер формируемого сейчас вектора. Положим сначала индекс i первого элемента формируемого сейчас вектора v[k] равным 1, а индекс второго элемента j=N. k:=0; пока (i<j) повторять {пока есть возможные элементы для пар} k:=k+1; v[k]:=(a[i],a[j]); полагаем i:=i+1; j:=j-1; {переходим к следующим элементам} если v[k]=(a[i],a[j]) то пусть количество оставшихся в массиве A элементов справа от а[i-1], равных a[i-1], есть u, т.е. a[i]=a[i+1]=...=a[i+u], а количество оставшихся в массиве A элементов слева от а[j+1], равных a[j+1], есть v, т.е. a[j]=a[j-1]=...=a[j-v]. если u>=v то, так как мы стремимся получить максимальное число пар, то мы отбросим все оставшиеся элементы со значением a[j] и положим j:=j-v-1 иначе по аналогичной причине отбросим все оставшиеся элементы со значением a[i], т.е. положим i:=i+u+1; конец_если конец_если конец_пока

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017