|
9 / 9 / 2
Регистрация: 03.04.2016
Сообщений: 89
|
|
Небоскреб и стеклянный шарик06.04.2016, 01:58. Показов 24513. Ответов 35
Метки нет (Все метки)
В небоскребе n этажей. Известно, что если уронить стеклянный шарик с этажа номер p, и шарик разобьется, то если уронить шарик с этажа номер p+1, то он тоже разобьется. Также известно, что при броске с последнего этажа шарик всегда разбивается. Вы хотите определить минимальный номер этажа, при падении с которого шарик разбивается. Для проведения экспериментов у вас есть два шарика. Вы можете разбить их все, но в результате вы должны абсолютно точно определить этот номер.
Определите, какого числа бросков достаточно, чтобы заведомо решить эту задачу. Формат входных данных Программа получает на вход количество этажей в небоскребе. Формат выходных данных Требуется вывести наименьшее число бросков, при котором можно всегда решить задачу. Примечание Комментарий к первому примеру. Нужно бросить шарик со 2-го этажа. Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется - то бросим шарик с 3-го этажа. Подсказки 1. Как следует действовать, если шарик был бы только один? 2. Пусть шариков два и мы бросили один шарик с этажа номер k. Как мы будем действовать в зависимости от того, разобьется ли шарик или нет? 3. Пусть f(n) - это минимальное число бросков, за которое можно определить искомый этаж, если бы в небоскребе было n этажей. Выразите f(n) через значения f(a) для меньших значений a. Sample Input 1: 4 Sample Output 1: 2 Sample Input 2: 5 Sample Output 2: 3 n/3 достаточно. Бросаем первый с этажа номер n/3. Если разбился, то бросаем второй по очереди с 1 этажа, потом со 2, ... до n/3 пока не разобьется. Так найдем этаж. Если первый шар не разбился. бросаем его с этажа 2n/3. Если тут разбился, то бросаем второй с этажа n/3+1, потом с n/3+2, ... пока не разобьется. Если 1 шар при падении с 2n/3 не разбился, то бросаем его с 2n/3+1, потом с 2n/3+2, ... пока не разобьется. Примерно так, надо закодить в с++
0
|
|
| 06.04.2016, 01:58 | |
|
Ответы с готовыми решениями:
35
Неподвижный шарик Два шарик |
|
116 / 106 / 51
Регистрация: 29.03.2016
Сообщений: 480
|
|
| 06.04.2016, 08:19 | |
|
может просто измерить силу при которой шарик трескается и приложить данное значение к известным постоянным (типа ускорение свободного падения). рассчитаем высоту. в итоге у нас будет один треснутый шарик и один целый.
и не надо ничего ломать!. Добавлено через 1 минуту AGPro, а вообще вы лишили кодеров удовольствия составить свой алгоритм (который будет очень похож на ваш). так что сами делайте
0
|
|
|
77 / 50 / 16
Регистрация: 17.05.2015
Сообщений: 262
|
|||||||||||
| 06.04.2016, 09:50 | |||||||||||
|
Дело было вечером, делать было нечего.
0
|
|||||||||||
|
116 / 106 / 51
Регистрация: 29.03.2016
Сообщений: 480
|
|
| 06.04.2016, 09:54 | |
|
AGPro,
ну, или не сами
0
|
|
|
77 / 50 / 16
Регистрация: 17.05.2015
Сообщений: 262
|
|||||||||||
| 06.04.2016, 10:06 | |||||||||||
|
Даже лучше так, а то в той работе ошибка
![]()
0
|
|||||||||||
|
2083 / 1575 / 169
Регистрация: 14.12.2014
Сообщений: 13,614
|
|
| 06.04.2016, 10:25 | |
|
используем метод дихотомии. Гарантированно имеем
Если шариков дефицит а времени на дурогонство с избытком, то кидаем шарик с первого этажа, потом со второго, и т.д. пока не разобъется. Имеем гарантированно 1 разбитый шарик. Если шариков 2 то можно совместить два метода. Т.е бросаем со среднего этажа. Если разбился идем со вторым снизу до разбития. Если нет, то делим верхние этажи пополам и пока не разобьется, или не дойдем до одного этажа в отрезке, если таки мы его расхренячили, то идем со вторым шариком снизу последнего отрезка, пока и его не расхренячим.
0
|
|
|
9 / 9 / 2
Регистрация: 03.04.2016
Сообщений: 89
|
|
| 06.04.2016, 14:08 [ТС] | |
|
Valeryn,
"Для проведения экспериментов у вас есть ДВА шарика!" Только два! Добавлено через 21 минуту Valeryn, Кстати в код что добавить надо, чтобы в консоли русскими буквами было видно?) Добавлено через 8 минут Valeryn, Да и в проге надо ввести только высоту небоскреба "n" и все. Добавлено через 25 минут Valeryn, прога ваша не правильно работает. Решение не верно.
0
|
|
|
116 / 106 / 51
Регистрация: 29.03.2016
Сообщений: 480
|
|
| 06.04.2016, 14:09 | |
|
AGPro, скажите пожалуйста, вам процесс программирования интересен?
0
|
|
|
9 / 9 / 2
Регистрация: 03.04.2016
Сообщений: 89
|
|||||||||||
| 06.04.2016, 14:35 [ТС] | |||||||||||
|
Что-то не в порядке с условием разрушения. Надо по другому задать.
int destroy = rand() % (n_house - 10) + 10
Со скобками напутал выше. Здесь ответы не правильные:
0
|
|||||||||||
|
Комп_Оратор)
|
||
| 06.04.2016, 15:08 | ||
|
AGPro, я мыслю так:
Пусть пороговый этаж это k-тый этаж. Имея два шарика и используя "наивный" алгоритм мы гарантировано получаем максимум k/3+1 бросков. Первый шарик бросаем с третьего этажа (шаг соответствует количеству шариков плюс 1), потом с 6-го, потом где-то на m-том броске, он обязательно разобьётся и придётся бросить этажом ниже. Если разбился то, ответ ещё ниже этажом, потому, что 2-мя этажами ниже мы уже бросали, причём успешно. Ну, а если на m-1 броске он не разбился, то ответ равен m-1 и один шарик остаётся как премия. За гениальность. ![]() Попытка применить дихотомию сократит половину ходов, но остальную половину придётся делать пошагово. Это значит, что дихотомия пролетает. Написать прогу не составит труда. Главное, правилен ли предложенный алгоритм. Пока ничего лучшего не выдумывается. ![]() зы через четыре надо кидать первый. А последний на 2 ниже. Тогда элемент дихотомии присутствует. А количество бросков не более k/4+1. Добавлено через 14 минут То есть кидаем первый: 4-й, 8-й, 12-й ... m-й (бэмц!) кидаем второй: m-2 если Бэмц! ответ m-3 Если целый то нужно ещё кинуть m-1 и тогда будет ясно m-2 или m-1.//вот этот бросок
0
|
||
|
1550 / 877 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
||||||
| 06.04.2016, 15:14 | ||||||
|
Что-то вы здесь перемудрили. Ответ из одной строчки.
По порядку. 1) Очевидно, что функция необходимого кол-ва бросков, от высоты дома - неубывающая. Т.е. Мы можем найти такие высоты, при которых просто посчитать кол-во бросков, и все, что между округляем в сторону большего. 2) Нам необходим минимизировать общее кол-во бросков. Т.е. кол-во бросков первого, пока он не разбился + кол-во бросков второго. Очевидно, что для минимизации бросков первый шарик бросается не равныи промежутками, Т.к. если мы бросили 1 шарик m раз то остается n-m бросков второго шарика, где n - минимально необходимое кол-во бросков. Итого Если высота дома вписывается в сумму арифметической прогрессии - ответ - n дальше см. пункт (1) Итого решая уравнение получаем
0
|
||||||
|
Комп_Оратор)
|
||
| 06.04.2016, 15:18 | ||
![]() Пусть этажей в доме n=100, а искомый - 49-й. Бросив первый шарик с 50-го этажа мы его разобьём. Дальше второй будем бросать с певого до 49-го пошагово. То есть максимум n/2 бросков?
0
|
||
|
1550 / 877 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
| 06.04.2016, 15:30 | |
|
IGPIGP, 100 плохое число (см п.1), пусть будет 105.
105=1+2+...+14. Тогда: Первый пока не разбился кидаем с 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102, 104. Второй шарик кидаем последовательно с предыдущего перед разбившимся. Итого: Максимум 14 бросков (В том случае если искомый этаж 13, 26, 38,... - это в худшем случае) Для 100 тоже максимум 14.
2
|
|
|
Комп_Оратор)
|
||
| 06.04.2016, 16:08 | ||
0
|
||
| 06.04.2016, 16:13 | |
|
Старая известная задача. Интервал между этажами с каждым броском уменьшается на 1.Тогда, если шарик разобьется не на самом последнем шаге, необходимое количество бросков (в худшем случае) одинаково и равно нижнему этажу цепочки.
В данной формулировке за 14 бросков определяется этаж для 106 этажного дома. За 15 - для 121 этажного.
0
|
|
|
9 / 9 / 2
Регистрация: 03.04.2016
Сообщений: 89
|
|
| 06.04.2016, 17:36 [ТС] | |
|
zer0mail, Если вы разбрались, как это все закодить?
0
|
|
|
Вездепух
12937 / 6804 / 1821
Регистрация: 18.10.2014
Сообщений: 17,218
|
|
| 06.04.2016, 17:48 | |
|
1
|
|
|
9 / 9 / 2
Регистрация: 03.04.2016
Сообщений: 89
|
|
| 06.04.2016, 17:56 [ТС] | |
|
avgoor, int n=ceil(sqrt(1.0+8*h)*0.5-0.5); Это не катит!
Эксперты! Код-то поправьте тогда.
0
|
|
|
77 / 50 / 16
Регистрация: 17.05.2015
Сообщений: 262
|
|||||||||||||
| 07.04.2016, 02:05 | |||||||||||||
|
Указываем сколько шариков (их может быть 1 а может быть 100). Кликните здесь для просмотра всего текста
0
|
|||||||||||||
| 07.04.2016, 02:05 | |
|
Помогаю со студенческими работами здесь
20
Стеклянный ИК обогреватель Стеклянный электрочайник: стоит ли покупать? Стеклянный фартук на кухне треснул Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Символьное дифференцирование
igorrr37 13.02.2026
/ *
Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2).
Унарный минус обозначается как !
*/
#include <iostream>
#include <stack>
#include <cctype>. . .
|
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
|
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу,
и светлой Луне.
В мире
покоя нет
и люди
не могут жить в тишине.
А жить им немного лет.
|
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила»
«Время-Деньги»
«Деньги -Пуля»
|
|
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога
Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога
Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
|
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
|