Подсчет минимального возможного количества замен у числа “x” по заданному алгоритму: x=m*n; x=m+n-2, где m и n - какие-то натуральные числа

#python #алгоритм

Пояснение:
Есть натуральное число x, его можно представить как произведение двух натуральных
чисел m и n (x=m*n). Далее x нужно заменить на m+n-2 (x=m+n-2). И это все необходимо
выполнять, пока x не станет равно 1

x может быть в пределах миллиарда 

Пример:
В программу поступило число 6.

6=3*2   3+2-2=3
6=6*1   6+1-2=5

3=3*1   3+1-2=2
5=5*1   5+1-2=4

2=2*1   2+1-2=1 - x=1, останавливаемся (до единицы мы дошли за 3 замены)
4=2*2   2+2-2=2


Мои попытки

from math import sqrt

def isint(n):
    return not(n%1)

def f(n):
   count = 0
   while(True):
      x=sqrt(n)
      if(n<=1):
         return count
      if(isint(x)):
         n=x+x-2
      else:
         x=int(x)
         while(isint(n/x)==False):
            x=x-1
         if(x<=0):
             return count
         n=int((n/x)+x-2)
      count+=1
print('Минимальное кол-во попыток для числа 6 = ',f(6))


P.S. Мой алгоритм делает ошибки, но некоторые числа он все же считает 
    

Ответы

Ответ 1

Я питон не знаю... Но на С++ решение этой задачи - вот:

#include 
#include 
#include 

using namespace std;

const int MAXSIZE = 1000000000;

unsigned char m[MAXSIZE+1];

int count(int x, int level = 0, int curmin = MAXSIZE)
{
    if (level > curmin) return -1; // Отсечение - нет смысла лезть вглубь
                                   // при наличии более короткого решения
    if (x == 1) return 0;
    if (m[x])
    {
        return m[x];               // Сохраненное значение
    }
    int res = MAXSIZE;
    for(int i = sqrt(x)+0.1; i >= 1; --i)
    {
        if (x%i) continue;
        int k = count(i+x/i-2, level+1, res);
        if (k < 0) continue;
        if (k < res) { res = k; }
    }
    return m[x] = res+1;
};

int main(int argc, const char * argv[])
{
    int n = (argc > 1) ? atoi(argv[1]) : MAXSIZE;
    if (n > MAXSIZE) n = MAXSIZE;
    cout << n << ":  " << count(n) << endl;

    int cur = m[n];
    while (n > 1)
    {
        for(int i = 1; i*i <= n; ++i)
        {
            if (n%i) continue;
            if (m[i+n/i-2] == cur-1)
            {
                n = i+n/i-2;
                --cur;
                cout << i << " ";
                break;
            }
        }
    }
    cout << endl;
}


Как видите, на ideone решило миллиард за 0.04с :)

Ключевые моменты:
1. Перебор с отсечением
2. Начинаем со значений, близких к корню
3. Мемоизация

Кстати, до миллиона включительно самая длинная цепочка - 11, так что глубокой рекурсии
явно не стоит ожидать.


Ответ 2

Ваш алгоритм основан на предположении, что если a < b, то f(a) <= f(b), но это не
всегда так, например f(7) = 4, а f(8) = 3.

Для начала, думаю, стоит начать с полного перебора, если ничего лучше не придумаете,
то добавьте мемоизацию.

Вот простой пример полного рекурсивного перебора на C#:

static int GetStepsCount(int x)
{
    // Граничное условие выхода
    if (x <= 1) return 0;
    // Делаем один шаг и прибавляем к нему
    return 1 +
        Enumerable
            // Для всех m от 1 до корня из x
            .Range(1, (int)Math.Sqrt(x))
            // Где m является делителем x
            .Where(m => x % m == 0)
            // Вычислить GetStepsCount
            .Select(m => GetStepsCount(m + x / m - 2))
            // И взять среди них минимум
            .Min();
}


Если алгоритм требуется выполнять для входных чисел бОльших, чем пару сотен, то мемоизация
неизбежна, т.к. полный перебор работает очень долго. Вот пример, с использованием словаря:

static Dictionary memory = new Dictionary();
static int GetStepsCount(int x)
{
    if (x <= 1) return 0;
    if (!memory.ContainsKey(x))
        memory[x] = 1 +
            Enumerable
                .Range(1, (int)Math.Sqrt(x))
                .Where(m => x % m == 0)
                .Select(m => GetStepsCount(m + x / m - 2))
                .Min();
    return memory[x];
}


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


Ответ 3

import functools 
from math import sqrt

@functools.lru_cache()
def f(x):
    if x <=1: return 0
    return 1 + min([ f(m + x // m - 2)  for m in range(1,int(sqrt(x))+1) if x%m ==0])


Это сразу с кэшированием ;-)
Так что єто Пайтон подрос получается )))
кстати, f(1024) дает 7.
Без @functools.lru_cache() считается минут 20, а с @functools.lru_cache() - 2-3 секунды !!