Найти наибольшее число среди первых n членов последовательности.

@Kristiina · Регистрация: 03.12.2020

Студворк — интернет-сервис помощи студентам

Недавно на муниципальном этапе Всероссийской олимпиады школьников по информатике дали такую задачу. Имеется бесконечная числовая последовательность, построенная по правилу:
Первый член последовательности равен единице.
Если имеется построенная часть последовательности, то к ней справа приписывается она же сама, но со всеми членами, умноженными на два.
То есть сначала последовательность состоит только из одного числа: 1
Затем приписывают удвоенный элемент, получается: 1, 2
Потом удваивают каждый элемент, получается 2, 4 и приписывают: 1, 2, 2, 4
Затем удваивают и приписывают уже 2, 4, 4, 8, получается: 1, 2, 2, 4, 2, 4, 4, 8
И так далее. Подобный принцип построения последовательностей называется рекурсивным.
В задаче требовалось найти наибольшее число среди первых n членов этой последовательности, где n не превосходило 1018.
Вы — участник этой олимпиады. Решите задачу!
Например, первые 11 членов последовательности выглядят так:
1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4.
И наибольшее значение среди первых 11 элементов равно 8.
Исходные данные
В первой и единственной строке дано натуральное число n — длина рассматриваемой части последовательности (1 ≤ n ≤ 1018).
Результат
Необходимо вывести одно число: значение наибольшего из элементов среди первых n членов описанной выше последовательности.
Пример:
исходные данные результат
11 8

@Gdez · 03.12.2020, 09:43

Kristiina, максимальная степень двойки меньше введенного числа
1, 2, 4, 8, 16, 32...
В эту последовательность "вставляешь" введенное число. Число слева от него - ответ
Решается сдвигом влево

Добавлено через 10 минут
Kristiina,

Python
1
2
3
4
5
6
7
8
from math import log
n = int(input())
k = 1
while k * 2 <= n :
    k <<= 1
print(k)
# а, если можно пользоваться math, то одна строчка
print(2 ** int(log(n,2)))

@eaa · 03.12.2020, 09:47

мда...

Python
1
print(2**bin(int(input())).count('1'))

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@Kristiina 0 / 0 / 0 Регистрация: 03.12.2020 Сообщений: 2

	Найти наибольшее число среди первых n членов последовательности. 03.12.2020, 08:50. Показов 3353. Ответов 2 Метки нет (Все метки) Недавно на муниципальном этапе Всероссийской олимпиады школьников по информатике дали такую задачу. Имеется бесконечная числовая последовательность, построенная по правилу: Первый член последовательности равен единице. Если имеется построенная часть последовательности, то к ней справа приписывается она же сама, но со всеми членами, умноженными на два. То есть сначала последовательность состоит только из одного числа: 1 Затем приписывают удвоенный элемент, получается: 1, 2 Потом удваивают каждый элемент, получается 2, 4 и приписывают: 1, 2, 2, 4 Затем удваивают и приписывают уже 2, 4, 4, 8, получается: 1, 2, 2, 4, 2, 4, 4, 8 И так далее. Подобный принцип построения последовательностей называется рекурсивным. В задаче требовалось найти наибольшее число среди первых n членов этой последовательности, где n не превосходило 1018. Вы — участник этой олимпиады. Решите задачу! Например, первые 11 членов последовательности выглядят так: 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4. И наибольшее значение среди первых 11 элементов равно 8. Исходные данные В первой и единственной строке дано натуральное число n — длина рассматриваемой части последовательности (1 ≤ n ≤ 1018). Результат Необходимо вывести одно число: значение наибольшего из элементов среди первых n членов описанной выше последовательности. Пример: исходные данные результат 11 8 0