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

Пояснение: Есть натуральное число 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. Мой алгоритм делает ошибки, но некоторые числа он все же считает

Ответ

Я питон не знаю... Но на С++ решение этой задачи - вот:
#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, так что глубокой рекурсии явно не стоит ожидать.