|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
12.07.2022, 02:53 | #1 |
Пользователь
Регистрация: 25.04.2010
Сообщений: 21
|
Функции и рекурсия C++
В небоскребе 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 |
12.07.2022, 08:59 | #2 |
Форумчанин
Регистрация: 27.04.2022
Сообщений: 493
|
Что за поток сознания? Задание надо переписывать слово в слово без собственных умозаключений.
стимулятор https://yoomoney.ru/to/41001303250491
|
13.07.2022, 08:20 | #3 |
Пользователь
Регистрация: 25.04.2010
Сообщений: 21
|
Valick, Задание оригинальное
|
13.07.2022, 09:17 | #4 |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
n /2
двоичный поиск до разбивания первого шарика. (самый плохой случай это разобьется при первой попытке) последовательный поиск (вверх) для последнего(второго) шарика. ( с гарантией что разобьется на первом из "высоких" )
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 13.07.2022 в 09:20. |
13.07.2022, 11:59 | #5 |
Форумчанин
Регистрация: 27.04.2022
Сообщений: 493
|
Если разбился со второго и не разбился с первого, значит минимальный этаж второй, зачем бросать с третьего?
стимулятор https://yoomoney.ru/to/41001303250491
|
13.07.2022, 13:35 | #6 |
Участник клуба
Регистрация: 17.04.2022
Сообщений: 1,833
|
Так написано
Последний раз редактировалось macomics; 13.07.2022 в 13:38. |
13.07.2022, 13:49 | #7 |
Пользователь
Регистрация: 25.04.2010
Сообщений: 21
|
Комментарий к заданию:
Посмотрев видео про Фаберже и порывшись в Гугле, нашел формулу суммы n- первых членов арифметич прогрессии: Sn = ((a1 + an)*n)/2, и ф-лу n-го члена арифметич прогрессии : an = a1 + d(n - 1). Подставил вторую в первую и, учитывая, что у нас а1 и d равны единице, по-максимуму сократил. Получил: Sn = (n + n*n) / 2. В итоге, имея неравенство: (n + n*n) / 2 >= количества этажей минус один, написал рекурсивную функцию. Вначале n = 1, затем увеличиваем ее рекурсивно. Смысл такой: нам надо при любом раскладе иметь одинаковое число бросков. Сначала разбиваем всё здание на большие интервалы в которые бросаем первый мяч. Но эти интервалы должны быть разной длины: первый длиной n, далее если мяч разбился - второй мяч кидаем c 1 до n-1 этажа последовательно, пока не разобьётся (т.е. мах n-1 шагов для 2-го мяча). Тогда в сумме 1 + (n-1) = n бросков для обоих шаров. Теперь предположим, что 1-ый шар не разбился при первом броске, а разбился при 2-ом. Тогда было сделано 2 броска 1-ым шаром. Чтобы общее число бросков было равным всегда, нужно сделать максимально n-2 броска (от отметки n, где не разбился 1-ый шар, до отметки n + n-1 ) 2-м шаром (в сумме n). Т.е. поднимаясь вверх мы постепенно уменьшаем интервалы между бросками 1-го шара для того, чтобы общее число бросков было одинаковым: n, n-1, n-2, n-3, ... . Получается, что мы разбили высоту здания на интервалы разной длины, их сумма составляет количество этажей в здании: n + (n-1) + (n-2) + ... + 1 = N, где N - высота здания. Осталась только вызвать рекурсивную функцию, которая постепенно суммирует числа начиная с 1, пока сумма не превысит N. То значение n, при котором сумма станет >= высоте здания и будет нашей искомой длиной первого интервала, т.е. средним кол-вом бросков, при которых гарантируется результат. P.s. Чтобы было понятно, нарисуйте. P.s. При вызове рекурсивной ф-ии стоит задать начальные значения (1 - первое предполагаемое значение n, которое будет каждый раз наращиваться, 0 - первоначальное значение суммы, N-1 - этажность здания, число постоянное ). Этажи = минимально возможная последовательность = минимальное количество бросков (совпадает с выбранным этажом для первого броска) 2 = 1 = 1 3 = 2 - 1 = 2 4 = 2 - 1 = 2 5 = 3 - 1 - 2 = 3 6 = 3 - 5 - 4 = 3 7 = 3 - 5 - 6 = 3 8 = 4 - 1 - 2 - 3 = 4 9 = 4 - 7 - 5 - 6 = 4 10 = 4 - 7 - 9 - 8 = 4 11 = 4 - 7 - 9 - 10 = 4 12 = 5 - 1 - 2 - 3 - 4 = 5 13 = 5 - 9 - 6 - 7 - 8 = 5 14 = 5 - 9 - 12 - 10 - 11 = 5 15 - 5 - 9 - 12 - 14 - 13 = 5 16 - 5 - 9 - 12 - 14 - 15 = 5 17 = 6 - 1 - 2 - 3 - 4 - 5 = 6 18 = 6 - 11 - 7 - 8 - 9 - 10 = 6 19 = 6 - 11 - 15 - 12 - 13 - 14 = 6 20 = 6 - 11 - 15 - 18 - 16 - 17 = 6 21 = 6 - 11 - 15 - 18 - 20 - 19 = 6 22 = 6 - 11 - 15 - 18 - 20 - 21 = 6 23 = 7 - 1 - 2 - 3 - 4 - 5 - 6 = 7 24 = 7 - 13 - 8 - 9 - 10 - 11 - 12 = 7 25 = 7 - 13 - 18 - 14 - 15 - 16 - 17 = 7 26 = 7 - 13 - 18 - 22 - 19 - 20 - 21 = 7 27 = 7 - 13 - 18 - 22 - 25 - 23 - 24 = 7 28 = 7 - 13 - 18 - 22 - 25 - 27 - 26 = 7 29 = 7 - 13 - 18 - 22 - 25 - 27 - 28 = 7 Затем придумать рекурсию под эту красоту. Можно вывести рекурсивную функцию с 1 условием для выхода из рекурсии в одну строку. Я столкнулся с нуждой написать тесты и видеть, в каких случаях программа работает неправильно, когда начинал решать задачу - поэтому для удобства написал небольшую функцию для логирования упавших тестов. #include <iostream> using namespace std; void expect(int(*a)(int), int b, int c) { if (a(b) != c) cout << "Test failed: Returned " << a(b) << " with arg " << b << " not equal expected " << c << endl; } int x2(int a) { return a + a; } int main() { expect(x2, 1, 2); expect(x2, 2, 4); expect(x2, 2, 4); expect(x2, 3, 6); expect(x2, 4, 8); return 0; } |
13.07.2022, 14:02 | #8 |
Форумчанин
Регистрация: 27.04.2022
Сообщений: 493
|
macomics, спасибо.
стимулятор https://yoomoney.ru/to/41001303250491
|
13.07.2022, 14:10 | #9 |
Форумчанин
Регистрация: 27.04.2022
Сообщений: 493
|
nartov55, ну не знаю, я бы такое решал по методу "половинного деления" (бисекции) 9 этажей, бросаем с 4-го, смотрим разбился или нет и принимаем решение кидать со 2-го или с 6-го этажа и тд.
PS крайне не удобно писать на ыорум со смартфона
стимулятор https://yoomoney.ru/to/41001303250491
|
13.07.2022, 14:27 | #10 | |
Участник клуба
Регистрация: 17.04.2022
Сообщений: 1,833
|
Цитата:
Собственно это и описано в #7. Последний раз редактировалось macomics; 13.07.2022 в 14:36. |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
[Free Pascal] Рекурсия(функции и процедуры) | Jake_Alan | Фриланс | 20 | 06.03.2019 17:54 |
Процедуры и функции. Рекурсия. | Бугра | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 05.04.2016 22:07 |
Рекурсия Функции | trish145 | Visual C++ | 2 | 19.03.2013 18:50 |