Форум программистов, компьютерный форум CyberForum.ru

Для каждого i от 1 до n найти медиану среди первых i элементов последовательности - C++

Восстановить пароль Регистрация
 
Maxfashko
 Аватар для Maxfashko
5 / 5 / 1
Регистрация: 28.11.2012
Сообщений: 135
03.04.2016, 10:18     Для каждого i от 1 до n найти медиану среди первых i элементов последовательности #1
Здравствуйте, не могу сообразить с задачей:
Дана последовательность X.
для каждого i от 1 до n нужно найти медиану среди первых i элементов последовательности X. В качестве результата вывести сумму найденных значений.

Медианой последовательности в случае нечетной длины L называется элемент, который будет равноудален от концов последовательности, если ее отсортировать по возрастанию или убыванию (нетрудно сообразить, что этот элемент имеет номер (L+1)/2 в отсортированной последовательности, если номера считать с единицы). В случае четной длины L медианой будем считать элемент, который окажется на месте L/2, если последовательность отсортировать по возрастанию.

Пример1:

Число : 5
Последовательность : 5 3 1 2 4
Ответ: 16.

Пример2:

Число: 10
Последовательность: 5 10 8 1 7 3 9 6 2 4
Ответ: 59

Я делаю так:

Ищу медиану для исходной последовательности, затем для последовательностей больше медианы и меньше. Уменьшая таким образом последовательности.

1) сортирую последовательность по возрастанию
2) ищу медиану последовательности от 1...5 (это число 3)
3) ищу теперь медиану среди последовательности 1,2,3 (это число 2)
4) Складываем предыдущую медиану с новой найденной.
5) снова сокращаем последовательность и ищем медиану. складывая ее с предыдущими ответами.

У меня не выходит 16. Мой ответ 15.
Я правильно мыслю?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2016, 10:18     Для каждого i от 1 до n найти медиану среди первых i элементов последовательности
Посмотрите здесь:

Массив: Найти минимальный среди минимальных элементов каждого столбца. C++
Функции: Для каждого числа последовательности найти количество цифр 5 C++
C++ Найти сумму первых n элементов последовательности
C++ Найти наименьшее число среди четных элементов последовательности
Для каждого числа последовательности найти количество цифр 5 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Cuellius
176 / 84 / 62
Регистрация: 23.06.2015
Сообщений: 218
Завершенные тесты: 2
03.04.2016, 10:40     Для каждого i от 1 до n найти медиану среди первых i элементов последовательности #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Maxfashko Посмотреть сообщение
1) сортирую последовательность по возрастанию
2) ищу медиану последовательности от 1...5 (это число 3)
3) ищу теперь медиану среди последовательности 1,2,3 (это число 2)
4) Складываем предыдущую медиану с новой найденной.
5) снова сокращаем последовательность и ищем медиану. складывая ее с предыдущими ответами.
У меня не выходит 16. Мой ответ 15.
Я правильно мыслю?
Нет
Для каждого i от 1 до n находим медиану последовательности [1; i]. Полученные результаты складываем
На первом примере:

i = 1) последовательность 5, медиана 5
i = 2) последовательность 5 3, медиана 3
i = 3) последовательность 5 3 1, медиана 3
i = 4) последовательность 5 3 1 2, медиана 2
i = 5) последовательность 5 3 1 2 4, медиана 3

Тогда ответ: 5 + 3 + 3 + 2 + 3 = 16
SergBelom
0 / 0 / 0
Регистрация: 25.11.2015
Сообщений: 3
03.04.2016, 19:54     Для каждого i от 1 до n найти медиану среди первых i элементов последовательности #3
А на чем пишите?
Можно код посмотреть для задачи?
SergBelom
0 / 0 / 0
Регистрация: 25.11.2015
Сообщений: 3
05.04.2016, 21:33     Для каждого i от 1 до n найти медиану среди первых i элементов последовательности #4
Maxfashko,
Цитата Сообщение от Maxfashko Посмотреть сообщение
сортирую последовательность по возрастанию
какой алгоритм сортировки используйте?
Lunix
0 / 0 / 0
Регистрация: 05.04.2016
Сообщений: 24
05.04.2016, 21:49     Для каждого i от 1 до n найти медиану среди первых i элементов последовательности #5
не, походу мысль у вас вообще не та! нужно просто пробегать от и = 2 до эн и каждый раз искать медиану.т.е. будет (эн-2) медианы, а потом сумм(мед) а, еще тут будет столько же сортировок! один раз не пойдет, т.к с добавлением нового элемента медианы может поменяться!
SergBelom
0 / 0 / 0
Регистрация: 25.11.2015
Сообщений: 3
05.04.2016, 21:56     Для каждого i от 1 до n найти медиану среди первых i элементов последовательности #6
Цитата Сообщение от Lunix Посмотреть сообщение
еще тут будет столько же сортировок!
это понятно, но по какому алгоритму
Yandex
Объявления
05.04.2016, 21:56     Для каждого i от 1 до n найти медиану среди первых i элементов последовательности
Ответ Создать тему
Опции темы

Текущее время: 15:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru