9.
Бинарный поиск_Практика-3
Задание можно решать по разному:
- Метод моделирования - реализовать последовательность и развернуть её требуемую глубину
(от такого способа нас предостеригают в пояснении к условию)
- Аналитически - определить формулу N-го члена и вычислить.
(это вполне рабочий метод, но как его реализовать)
- "Практический" - что-то среднее между 1 и 2. При реализации воспользуемся "восходящим" бинарным поиском по ответу.
Построение последовательности состоит из серий:
- добавили 1 нечетный
- добавили 2 четных
- добавили 3 четных
- и т.д.
Пусть k-я серия состоит из A
k1, ..., A
kk - тогда очевидно, что A
kk = A
k1 + 2*(k-1)
А если учесть, что A
k1 = A
k-1k-1 + 1. Таким образом A
kk = A
k-1k-1 + 2(k-1) + 1
Это дает следующие ответы:
- номер элемента Akk равен 1 + 2...+ л = л(л+1)/2
- значение элемент Akk равно (2*1 -1) +(2*2 - 1) + ... + (2*k -1) = k2
Теперь ясно, как находить N-й элемент
- Найти сколько "полных" серий до номера N и значение последнего элемента
- Определить номер элемента в серии и добавить необходимое значение
Для поиска числа полных серий можно (полезно в качестве тренировки)
- определить границы интервала "восходящим способом)
( while (f(R) <= N) { R*=2;} L = R/2; )
- бинарным поиском найти точное число серий,
Задача Чет-нечет
Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ...
Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее.
Выведите N-й элемент этой последовательности.
Программа должна работать быстрее, чем за линейный поиск
Входные данные
Одно целое число N (1 <= N <= 109).
Выходные данные
Выведите одно целое число - N-й элемент последовательности.
Пояснения к решению см. в теории
Напишите программу
Auto