[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: Сергеев_ЕВ  
Форум учителей » Форумы для учителей предметников » Форум учителей информатики » ЕГЭ 16 (Задача из СтатГрад)
ЕГЭ 16
Дата: Понедельник, 14.02.2022, 13:17 | Сообщение #1

v0val

Профиль пользователя v0val
Начинающий
Группа: Пользователи
Сообщений: 1
Статус: Отсутствует
Видимо планируют в этом году запустить:
Алгоритм вычисления значения функции F(n), где n – целое неотрицательное
число, задан следующими соотношениями:
F(0) = 0;
F(n) = F(n – 1) + 1, если n нечётно;
F(n) = F(n/2), если n > 0 и при этом n чётно.
Укажите количество таких значений n < 1 000 000 000, для которых F(n) = 3.

Решал так:
def F(n):
    if n == 0: return 0
    if n % 2 == 1: return F(n - 1) + 1
    if n > 0 and n % 2 == 0: return F(n/2)
n = 1
k = 0
while n < 10 000 000:
    if F(n) == 2:
            k +=1
            #print(n, F(n))
    n +=1
print(k)
Примерно через час выдало 274. Но нужен 1 000 000 000 (миллиард ё-моё!!!) Формирование количества, в разных диапазонах не поддаётся логике
Дата: Понедельник, 14.02.2022, 23:35 | Сообщение #2

iyugov

фотография отсутствует
Владыка слова
Группа: Друзья
Сообщений: 1433
Статус: Отсутствует
v0val, во-первых, можно кэшировать результаты вызовов - хоть в массиве, хоть в словаре, хоть декоратором из functools:
Код
from functools import lru_cache
@lru_cache
def F(n):
...

Ответ для 10_000_000 (в Python можно прямо писать числа с подчёркиваниями) хоть для 2, хоть для 3 будет получен менее чем за минуту.

Во-вторых, с миллиардом что Python, что C++ будут возиться не меньше нескольких минут. Решение "в лоб" с циклом неоптимально даже без вызовов рекурсивной функции, а для кэширования не хватит памяти. Надо придумывать что-то принципиально другое.
Посмотрите на двоичную запись нужных чисел:
Код
if F(n) == 3:
            k +=1
            print(n, F(n), bin(n))

Заметили?

С учётом особенностей числа 1_000_000_000 задачу можно решить так:
Код
import math
p = 1_000_000_000
print(bin(p))
n = len(bin(p)) - 2
s = 0
for i in range(n):
    s += math.comb(i, 2)
print(s)

Однострочник для ценителей:
Код
import math; print(sum([math.comb(i, 2) for i in range(len(bin(1_000_000_000)) - 2)]))


Сообщение отредактировал iyugov - Понедельник, 14.02.2022, 23:52
Дата: Пятница, 25.02.2022, 14:28 | Сообщение #3

Сергеев_ЕВ

Профиль пользователя Сергеев_ЕВ
Модератор форума
Группа: Модераторы
Сообщений: 3177
Статус: Отсутствует
Иван Олегович, как всегда, не перестаёт нас восхищать!



Окажу помощь в создании и администрировании учительских сайтов в системе uCoz
Форум учителей » Форумы для учителей предметников » Форум учителей информатики » ЕГЭ 16 (Задача из СтатГрад)
  • Страница 1 из 1
  • 1
Поиск:
Если Вы хотите оставить сообщение на форуме, то рекомендуем Вам зарегистрироваться на нашем сайте или войти на портал как зарегистрированный пользователь
Маркер СМИ

© 2007 - 2024 Сообщество учителей-предметников "Учительский портал"
Свидетельство о регистрации СМИ: Эл № ФС77-64383 выдано 31.12.2015 г. Роскомнадзором.
Территория распространения: Российская Федерация, зарубежные страны.
Учредитель / главный редактор: Никитенко Е.И.


Сайт является информационным посредником и предоставляет возможность пользователям размещать свои материалы на его страницах.
Публикуя материалы на сайте, пользователи берут на себя всю ответственность за содержание этих материалов и разрешение любых спорных вопросов с третьими лицами.
При этом администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта.
Если вы обнаружили, что на сайте незаконно используются материалы, сообщите администратору через форму обратной связи — материалы будут удалены.

Все материалы, размещенные на сайте, созданы пользователями сайта и представлены исключительно в ознакомительных целях. Использование материалов сайта возможно только с разрешения администрации портала.


Фотографии предоставлены