主页 / 问题 / 770303
Accepted
yoloy
Asked:2020-01-13 23:28:12 +0000 UTC2020-01-13 23:28:12 +0000 UTC

根据给定算法计算数字“x”的最小可能替换次数：x=m*n；x=m+n-2，其中 m 和 n 是一些自然数

  • 772

解释：有一个自然数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))

PS我的算法出错了，但还是算了一些数字

python

3 个回答

  1. Best Answer

    我不知道python...但是在C++中，这个问题的解决方案是：

    #include <iostream>
#include <iomanip>
#include <cmath>

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 秒内解决了 10 亿:)

    关键点：
    1.用裁剪搜索
    2.从靠近根的值开始
    3.记忆化

    顺便说一句，最多一百万，最长的链是 11，所以显然你不应该期望深度递归。

    • 12

  2. 您的算法是基于 if a < b, then的假设f(a) <= f(b)，但情况并非总是如此，例如f(7) = 4和f(8) = 3。

    首先，我认为值得从一个完整的枚举开始，如果你想不出更好的东西，那就添加 memoization。

    以下是 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<int, int> memory = new Dictionary<int, int>();
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];
}

    内存消耗小，但执行速度显着提高。

    • 6 
  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])

    这立即与缓存;-) 所以 Python 已经长大了))) 顺便说一下，f(1024) 给出 7。没有 @functools.lru_cache()，它需要 20 分钟，而使用 @functools.lru_cache() - 2 -3秒！！

    • 1

相关问题