Перебор 2^30> чисел для рекурсии, вызовы 1000 рекурсий

Question

Перебирать долго и возникают ошибки, поэтому есть ли панацея от этой болезни, но чтобы сохранить суть шаблонности выполнения этой задачи без поиска каких-то алгоритмов? Тот же перебор, но быстрее, без ошибок? Те же многочисленные рекурсии, но без ошибок?

"""Алгоритм вычисления значения функции 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 (~~2^30), для которых F(n)  =  2."""

def F(n):
    if n == 0:
        return 0
    else:
        return F(n-1) + 1 if n % 2 else F(n//2)

c = 0
for n in range(100000000):
    if F(n) == 2:
        print(n)
        c += 1
    print('count of n:', c)

Заранее спасибо за ответ и извиняюсь за глупые вопросы. Желательно без сторонних библиотек, которые нужно скачивать.

Answer 1

Ваша функция F(n) подсчитывает количество единиц в двоичном представлении числа. Соответственно вопрос о том, как быстро вычислить количество n таких, что F(n) == 2 эквивалентен вопросу о том, сколько существует пар чисел m,k m > k таких, что 2^m + 2^k < N

Количество цифр в двоичном представлении числа N равно floor(log2(N))+1

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

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

def fastF(n):
    m = math.floor(math.log2(n))
    # 2^m <= n
    # Количество чисел с двумя единицами в записи длиной m-1 бит
    count_m = m*(m-1)/2
    
    # Теперь зафиксируем единицу в 2^m и добавим все числа вида 2^m + 2^k < n
    reminder = (n-1) - (1<<m)
    if reminder > 0:
        k = math.floor(math.log2(reminder)) + 1
    else:
        k = 0
    
    return int(count_m + k)

Результат

Fast:  10 4
Fast:  100 21
Fast:  1000 45
Fast:  10000 89
Fast:  100000 136
Fast:  1000000000 435

Answer 2

Итак, как, наконец, устаканили — требуется найти количество чисел до 100 миллионов (именно это значение задано в коде), в бинарном представлении которых ровно две единицы.

Что такое 100000000 в бинарном представлении - 101111101011110000100000000

Итого, нас интересуют все возможные размещения двух единиц в 26 знакоместах + количество чисел, начинающихся с 10 и у которых после этого идет только одна 1 на 25 знакомест. Т.е. 26*25/2 + 25 = 350.

Если все же миллиард, то он в бинарном представлении имеет вид 111011100110101100101000000000, так что теперь нас интересуют любые размещения двух единиц в 30 знакоместах (благо, начинается миллиард с 11), и получаем 30*29/2 = 435 таких чисел.

Все просто, никакого программирования :)

Но если очень хочется попрограммировать и вывести все эти числа...

int main(int argc, char * argv[])
{
    unsigned int n = 1000'000'000;
    int count = 0;
    for(int m = 1; m < 32; ++m)
    {
        unsigned int x = 1 << m;
        if (x > n) break;
        for(int l = 0; l < m; ++l)
        {
            unsigned int y = x + (1 << l);
            if ( y > n) break;
            cout << bitset<32>(y) << " : " << setw(10) << y << endl;
            ++count;
        }
    }
    cout << "Total: " << count << endl;
}

И кстати! Откуда эти "1000 рекурсий" (я так понимаю, имеется в виду глубина)? До миллиарда максимальная глубина рекурсии — 59 для числа 805306367...

БЛОГ НА HUSL

Перебор 2^30> чисел для рекурсии, вызовы 1000 рекурсий

Ответы (2 шт):