Сто этажное здание и 2 мячика. Алгоритм нахождения этажа.
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [216.73.216.88] |
|
|
правила раздела Алгоритмы

| Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Сто этажное здание и 2 мячика. Алгоритм нахождения этажа.
|
Сообщ.
#16
,
|
|
|
|
MIF, что то я не понял твою формулу k*(k + 1)/2 >= n не мог бы ты разъяснить? Например у нас n=100 этажей и k=3 шаров как тогда найти мин количество этажей?
|
|
Сообщ.
#17
,
|
|
|
|
Формула Мифа это другая запись моей (11 сообщение) формулы. Следует из того, что:
1 + 2 + 3 + ... + k Можно представить как сумму крайних элементов: 1 + k; 2 + (k - 1); 3 + (k - 2) 1 + k; 1 + k... которая повторяется k/2 раз. С тремя шарами посложнее будет... |
|
Сообщ.
#18
,
|
|
|
|
Теперь понятно, а то я думал это как раз ответ на общий вариант n этажей и k шаров. Я вот думаю в общем случае для k шаров можно делать примерно так : сначала найти разбиение на этажи как для 2 шаров, а потом в каждом промежутке не проходить по одному этажу как это было при одном оставшемся шаре, а использовать метод золотого сечения, либо до того момента как найдется нужный этаж, либо до того момента как останется один шар, и им уже пройти по-одному оставшиеся этажи. Логично ли что это и будет нужным алгоритмом или можно лучше?
|
|
Сообщ.
#19
,
|
|
|
|
С тремя шарами вроде двойная формула:
y=(x-1)Sy=0 (k=ySk=0 k) + 1>= 100 . Вроде 1 там нужна (?). Хотя формулы так и не пишут Получается х = 9. (9) -> (8) + 1 -> 36 + 1 (8) -> (7) + 1 -> 28 + 1 Кидаем: 37, 66, 88, 104 (100). Если на 37 разбивается: 8, 15, 21, 26, 30, 33, 35, 36. Если на 66 разбивается: 44, 50, 55, 59, 62, 64, 65. Добавлено Цитата int0x25 @ использовать метод золотого сечения Забудь ты про золотое сечение! Тут это не катит. От количества шаров будет зависеть количество вложенных сумм, по принципу: k - шаров, (k - 1) сумм. Осложняется еще все этой вылезшей вдруг единицей. |
|
Сообщ.
#20
,
|
|
|
|
_lcf_ спасибо за формулу и за подробное описание того, как она работает!
|