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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Maxfashko
 Аватар для Maxfashko
5 / 5 / 1
Регистрация: 28.11.2012
Сообщений: 157
#1

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

03.04.2016, 10:18. Просмотров 359. Ответов 5
Метки нет (Все метки)

Здравствуйте, не могу сообразить с задачей:
Дана последовательность 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++ Для каждого столбца матрицы найти минимальные элементы среди четных чисел
Массив: Найти минимальный среди минимальных элементов каждого столбца. C++
Функции: Для каждого числа последовательности найти количество цифр 5 C++
C++ Найти сумму первых n элементов последовательности
C++ Найти наименьшее число среди четных элементов последовательности
Для каждого числа последовательности найти количество цифр 5 C++
Вывести на экран 12 первых элементов последовательности C++
C++ В заданном массиве из n элементов среди первых n/2 элементов найти минимальное значение
C++ Для каждого числа заданной последовательности найти количество цифр 5
Используя рекурсивную функцию, найти сумму первых n элементов последовательности C++
Среди первых n элементов последовательности найти среднее арифметическое отрицательных элементов C++
C++ Найти минимальное значение среди элементов, стоящих над главной диагональю, и максимальное среди элементов

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Cuellius
176 / 84 / 62
Регистрация: 23.06.2015
Сообщений: 219
Завершенные тесты: 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
Сообщений: 33
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 элементов последовательности
Ответ Создать тему
Опции темы

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