Функции и рекурсия C++

[nartov55]

В небоскребе 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

[Valick]

Что за поток сознания? Задание надо переписывать слово в слово без собственных умозаключений.

[nartov55]

Valick, Задание оригинальное

[evg_m]

n /2
двоичный поиск до разбивания первого шарика. (самый плохой случай это разобьется при первой попытке)
последовательный поиск (вверх) для последнего(второго) шарика. ( с гарантией что разобьется на первом из "высоких" )

[Valick]

Сообщение от nartov55

Valick, Задание оригинальное

Сообщение от nartov55

Комментарий к первому примеру. Нужно бросить шарик со 2-го этажа. Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется - то бросим шарик с 3-го этажа.

Если разбился со второго и не разбился с первого, значит минимальный этаж второй, зачем бросать с третьего?

[macomics]

Так написано

Сообщение от nartov55

Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется (при броске 1-го шарика со 2-го этажа) - то бросим (1-ый шарик) шарик с 3-го этажа.

[nartov55]

Комментарий к заданию:

Посмотрев видео про Фаберже и порывшись в Гугле, нашел формулу суммы 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;
}

[Valick]

macomics, спасибо.

[Valick]

nartov55, ну не знаю, я бы такое решал по методу "половинного деления" (бисекции) 9 этажей, бросаем с 4-го, смотрим разбился или нет и принимаем решение кидать со 2-го или с 6-го этажа и тд.
PS крайне не удобно писать на ыорум со смартфона

[macomics]

Сообщение от Valick

nartov55, ну не знаю, я бы такое решал по методу "половинного деления" (бисекции) 9 этажей, бросаем с 4-го, смотрим разбился или нет и принимаем решение кидать со 2-го или с 6-го этажа и тд.
PS крайне не удобно писать на ыорум со смартфона

Тут нужно найти оптимальный делитель, чтобы количество этажей проверяемых вторым шариком было минимальным, а количество проверок первым шариком было максимальным.

Собственно это и описано в #7.