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

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

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

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

03.04.2016, 10:18. Просмотров 395. Ответов 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.
Я правильно мыслю?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2016, 10:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Для каждого i от 1 до n найти медиану среди первых i элементов последовательности (C++):

Среди первых n элементов последовательности найти среднее арифметическое отрицательных элементов - C++
#include <iostream> #include <math.h> /* Пусть a=0.01; a=sin(k+a) , k=2,3,... Среди первых n элементов...

В заданном массиве из n элементов среди первых n/2 элементов найти минимальное значение - C++
1.В заданном массиве из n элементов среди первых n/2 элементов найти минимальное значение, а в оставшихся- максимальное значение( через...

Найти сумму первых n элементов последовательности - C++
Дана последовательность чисел, числа n и k. Найти 1) сумму первых n элементов последовательности 2) первый элемент...

Используя рекурсивную функцию, найти сумму первых n элементов последовательности - C++
Используя рекурсивную функцию, найти сумму первых n элементов последовательности xn = 3 * xn-1, x0 = 1. Помогите пожалуйста. Нужно...

Массив: Найти минимальный среди минимальных элементов каждого столбца. - C++
Дана матрица размера 5 x 10. Найти минимальный среди минимальных элементов каждой столбца.

Найти наименьшее число среди четных элементов последовательности - C++
Напишите пожалуйста программу по условию задачи :Вводится последовательность из N положительных целых чисел. Найти наименьшее число среди...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Cuellius
181 / 89 / 64
Регистрация: 23.06.2015
Сообщений: 237
Завершенные тесты: 3
03.04.2016, 10:40 #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
1
SergBelom
0 / 0 / 0
Регистрация: 25.11.2015
Сообщений: 3
03.04.2016, 19:54 #3
А на чем пишите?
Можно код посмотреть для задачи?
0
SergBelom
0 / 0 / 0
Регистрация: 25.11.2015
Сообщений: 3
05.04.2016, 21:33 #4
Maxfashko,
Цитата Сообщение от Maxfashko Посмотреть сообщение
сортирую последовательность по возрастанию
какой алгоритм сортировки используйте?
0
Lunix
0 / 0 / 0
Регистрация: 05.04.2016
Сообщений: 35
05.04.2016, 21:49 #5
не, походу мысль у вас вообще не та! нужно просто пробегать от и = 2 до эн и каждый раз искать медиану.т.е. будет (эн-2) медианы, а потом сумм(мед) а, еще тут будет столько же сортировок! один раз не пойдет, т.к с добавлением нового элемента медианы может поменяться!
0
SergBelom
0 / 0 / 0
Регистрация: 25.11.2015
Сообщений: 3
05.04.2016, 21:56 #6
Цитата Сообщение от Lunix Посмотреть сообщение
еще тут будет столько же сортировок!
это понятно, но по какому алгоритму
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.04.2016, 21:56
Привет! Вот еще темы с ответами:

Вычислить произведение элементов каждого столбца матрицы, и найти среди них наименьшее - C++
Дан двумерный массив А который состоит из m и строк n столбцов. Составить программу, которая вычисляет произведение элементов каждого...

Среди элементов массива найти повторяющиеся и оставить по одному вхождению каждого, заменив остальные нулями - C++
Доброго времени суток. Имеется такое задание:" Дан массив A. Среди его элементов найти повторяющиеся и оставить по одному вхождению...

Для каждого столбца матрицы найти минимальные элементы среди четных чисел - C++
в двумерном квадратном массиве целых чисел для каждого столбца найти минимальные элементы среди четных чисел. помогите пожалуйста...

Для каждого числа последовательности найти количество цифр 5 - C++
Вводится последовательность из N целых чисел. Для каждого числа последовательности найти количество цифр 5 (функцией оформить определение...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
05.04.2016, 21:56
Ответ Создать тему
Опции темы

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