时间戳

首页 > 解决方案 > 插入成功后如何停止递归？

algorithm - 插入成功后如何停止递归？

问题描述

问题定义是

给定一个额外的数字0 ≤ x ≤ 9，编写一个函数，该函数返回将 x 插入 n 所得到的整数，使其数字也以从左到右的升序出现。例如，如果 n =24667并且x = 5，函数应该返回245667。

我的代码

// the divisions are integer division, no floating point
int x(int n, int insertValue)
{
    if (n == 0) return 0;
    int val = x(n/10, insertValue);
    if((n%10) > insertValue)
    {
        int q = insertValue * 10 + (n%10);
        return val * 100 + q;
    }
    return val*10 + (n%10);
}

例如，对于 的情况x(2245,3)，它输出223435。但是我在处理时已经完成了224。它不应该继续添加要插入的值，我的意思是 3 不应该在 5 之前出现。

我可以想出一个解决方案，我可以在每个递归步骤中放入一个布尔标志，该标志通过取模除以 10 并除以 10 来识别单个数字的情况。如果没有任何标识，则进入该 if 块，否则不。但这听起来太傻了。

标签： algorithmfunctionrecursionrecurrence

解决方案

当你递归除法时，你实际上是从右到左，而不是从左到右，所以你应该检查一个数字是否小于插入的数字而不是更大（除非你总是让递归达到n==0条件并进行比较你的出路，但那将是无效的）。

第二件事是，一旦插入数字（正如我现在在问题标题中看到的那样，您已经知道这一点），您就不会中断递归，因此它会在每个大于insertValue. 至于怎么做：你已经用if(n==0)条件停止递归，即如果n==0函数停止调用自身（它立即返回）。插入数字时，不同之处在于您需要使用原始值 ( n) 从函数返回，而不是进一步传递它。

在这一点上，它适用于您的示例，但如果您希望该功能发挥作用，还需要考虑一种极端情况。当你没有什么要除的 [ if(n==0)] 时，无论如何你都需要插入你的数字 ( return insertValue)，这样它就不会像在x(2245,1)通话中那样在左边缘丢失。

简洁的改进：

  • %*与and具有相同的优先级/，因此这里不需要括号。
  • 我删除了val变量，因为它现在只使用一次，而且它的计算并不总是必要的。

这是工作代码：

int x(int n, int insertValue){
    if(n == 0) return insertValue;
    
    //if insertion point was found, use original value (n)
    if(n%10 <= insertValue)
        return n*10 + insertValue;

    //if not there yet, keep calling x()
    return x(n/10, insertValue)*10 + n%10;
}

推荐阅读