Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.144.193.129] |
|
Сообщ.
#1
,
|
|
|
Даны 20 чисел, образующие неубывающую последовательность. Несколько
чисел, идущие подряд, равны между собой. Найти количество таких чисел. Сколько различных чисел имеется в последовательности? |
Сообщ.
#2
,
|
|
|
Последовательность называется монотонной, если она является неубывающей, либо невозрастающей
1 2 2 2 4 7 8 8 8 8 10 10 10 11 13 15 17 19 21 21 Может быть на С есть какие нить навороты с последовательностями, но дельфе если совсем топорно, то алгоритм будет что-то типа: 0) wile I < 20 1) берем первое 2) wile... пока первое число равно следующему считать одинаковые S=S+1; I+1 3) если текущее число не равно следующему I+1. Если S>1 вывести количество одинаковых I+1 |
Сообщ.
#3
,
|
|
|
Цитата alex____666 @ Неоднозначность имеется в такой формулировке. Так (см. пример из соо. №2) могут быть варианты:Найти количество таких чисел. 1) 3 (двойки) + 4 (восьмёрки) + 3 + 2 = 12; 2) 3 - просто двойки (первое найденное); 3) 4 - количество повторяющихся последовательностей. |
Сообщ.
#4
,
|
|
|
Цитата Славян @ Цитата alex____666 @ Неоднозначность имеется в такой формулировке. Так (см. пример из соо. №2) могут быть варианты:Найти количество таких чисел. 1) 3 (двойки) + 4 (восьмёрки) + 3 + 2 = 12; 2) 3 - просто двойки (первое найденное); 3) 4 - количество повторяющихся последовательностей. Славян известная задача, найти максимальное, суть в том что надо стоить массив где кол--во елементов равно максимальному числа, если число три то пишем на третью позицию 1, если снова три то увеличиваем счетчик, alex____666 дальше понятно ? |
Сообщ.
#5
,
|
|
|
По мне так требование неубывания/монотонности лишнее. Можно просто искать серии подряд идущих одинаковых чисел и считать то, что требуется. Что требуется подсчитать, из формулировки не очень ясно.
Задача решается за один просмотр массива с использованием константной памяти (O(1)) за пропорциональное длине массива (O(N)) время. Быстрее просто невозможно. |
Сообщ.
#6
,
|
|
|
Для проверки различности же монотонность нужна (для линейности работы по времени).
|
Сообщ.
#7
,
|
|
|
Цитата Славян @ Зачем? Разве речь идёт об одинаковых числах по всему массиву? Тогда да, либо подсчёт, если диапазон сильно ограничен, либо сортировка с последующим подсчётом длин серий.Для проверки различности же монотонность нужна (для линейности работы по времени). А для определения собственно длин серий с остоянным значением монотонность уже не важна. Если число равно и тому, что слева от него, и тому что справа, значит оба соседа тоже равны между собой. Поэтому при поиске серий и их длин достаточно ограничиться сравнение только непосредственных соседей. При этом можно не обрабатывать числа стоящие по-одиночке. Они просто будут образовывать серию длины 1, которую можно обработать по отдельному правилу. Если в ряду одинаковых чисел где-нибудь по-середине стоит отличающееся от них число, то это уже три раздельные серии, обрабатываемые по-отдельности. В любом случае у ТС уже неубывающая последовательность (на всякий случай это тоже можно проверить за линейное время) и двух отдельных серий с одинаковым значением элементов быть не может. В общем проблема в том, что формулировка задачи не очень чёткая. В частности, не ясно, какого результата ТС ожидает, если окажется несколько таких серий-полок с разными значениями и длинами. Или все числа окажутся различными и получится N серий длины 1. |
Сообщ.
#8
,
|
|
|
Полагаю, пора курсовых закончилась еще в мае и автору вопроса его решение уже давно до лампочки.
|