Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Natatem00
0 / 0 / 0
Регистрация: 05.10.2018
Сообщений: 21
1

Как найти верхнюю границу?

15.02.2019, 20:14. Просмотров 202. Ответов 4
Метки нет (Все метки)

Имеется упорядоченная по весу группа из 10 камней, и другая упорядоченная по весу группа из 15 камней. Их «сливают» в одну упорядоченную группу так: сравнивают самые лёгкие камни в группах, и тот, который легче, откладывают. (Инвариант: отложенные идут в порядке возрастания и легче всех оставшихся в группах.) Какое максимальное число сравнений может понадобиться при этом?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.02.2019, 20:14
Ответы с готовыми решениями:

Найти число или его верхнюю границу
Задача возникла отсюда http://www.cyberforum.ru/c-beginners/thread2352174.html#post13065572...

Установить верхнюю границу цикла
как сделать, что бы число только могло доходить до 10?

Определить верхнюю границу полосы пропускания cхемы с ОЭ
1. Определить верхнюю границу полосы пропускания f усилительного каскада на транзисторе в схеме с...

Для чего верхнюю границу цикла уменьшать на единицу?
Всем привет! Довольно часто в различных примерах кода вижу такое(пример навскидку): For i = 0 To...

Определить верхнюю границу цикла, т.е. максимальный номер IP-адреса заданной сети, если компьютер, с которого
Определить верхнюю границу цикла, т.е. максимальный номер IP-адреса заданной сети, если компьютер,...

4
vantfiles
153 / 78 / 31
Регистрация: 07.05.2013
Сообщений: 279
16.02.2019, 10:53 2
Самый худший случай:
10: 1 3 5 7 9 11 13 15 17 19
15: 2 4 6 8 10 12 14 16 18 20 20 20 20 20 20

итого 19 сравнений

Добавлено через 3 минуты
нет, неправильно, больше...

Добавлено через 2 минуты
кстати задача не до конца поставлена - что делать если вес сравниваемых камней одинаков...

Добавлено через 5 минут
видимо, 24
1
Natatem00
0 / 0 / 0
Регистрация: 05.10.2018
Сообщений: 21
16.02.2019, 13:27  [ТС] 3
Цитата Сообщение от vantfiles Посмотреть сообщение
Самый худший случай:
10: 1 3 5 7 9 11 13 15 17 19
15: 2 4 6 8 10 12 14 16 18 20 20 20 20 20 20
Цитата Сообщение от vantfiles Посмотреть сообщение
видимо, 24
Спасибо. Действительно ответ - 24. Но, если Вам не трудно, можете рассказать способ решения? Ведь вряд-ли это банальный подбор. Просто мне интересен не сам ответ, а именно способ нахождения ответа
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
16.02.2019, 15:14 4
После каждого сравнения мы увеличиваем индекс как минимум одного из массивов (если веса камней одинаковы, то увеличиваем сразу оба индекса, но нас интересует худший случай). И так до тех пор, пока не закончится один из массивов. В худшем случае в этот момент в другом массиве останется всего один камень. 10 + 15 - 1 = 24.
0
Natatem00
0 / 0 / 0
Регистрация: 05.10.2018
Сообщений: 21
17.02.2019, 23:31  [ТС] 5
Цитата Сообщение от Shamil1 Посмотреть сообщение
После каждого сравнения мы увеличиваем индекс как минимум одного из массивов (если веса камней одинаковы, то увеличиваем сразу оба индекса, но нас интересует худший случай). И так до тех пор, пока не закончится один из массивов. В худшем случае в этот момент в другом массиве останется всего один камень. 10 + 15 - 1 = 24.
Спасибо
0
17.02.2019, 23:31
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.02.2019, 23:31

Как встроить верхнюю часть окна, на которой расположены кнопки управления в верхнюю панель системы, как в Ubuntu 16?
Всем привет. Использую Ubuntu 18.04, есть у нее некоторые преимущества перед предыдущей...

Найти границу последовательности
Проверьте, пожалуйста, задание Найти границу последовательности `lim_{n->oo}...

Найти нижнюю границу
Дан числовой конечный ряд 1 + 1/2 + 1/3 + ... + 1/n Найти нижнюю границу. Решение Проинтегрируем...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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