如何在没有递归的情况下使用+3或*5操作获取目标号码？

Question

这是我昨天遇到的一个面试问题,我可以想到一个递归的解决方案,但我想知道是否存在非递归解决方案.

给定数字N,从数字1开始,您只能将结果乘以5或将3加到结果中.如果无法通过此方法获得N,请返回"无法生成它".

例如:

Input: 23
Output: (1+3)*5+3
Input: 215
Output: ((1*5+3)*5+3)*5
Input: 12
Output: Can't generate it.

递归方法可以是明显和直观的,但是有任何非递归方法吗？

Answer 1

我认为最快,非递归的解决方案是(对于N> 2):

• 如果N mod 3 == 1,它可以生成为1 + 3*k.
• 如果N mod 3 == 2,它可以生成为1*5 + 3*k
• 如果N mod 3 == 0,它无法生成

最后一个陈述来自以1(= 1 mod 3)开头的事实,你只能达到等于1或2 mod 3的数字:

• 添加3时,不要更改值mod 3
• 数字等于1 mod 3乘以5得到一个数字等于2 mod 3
• 数字等于2 mod 3乘以5得到的数字等于1 mod 3

Answer 2

这里的关键是向后工作.从你想要达到的数字开始,如果它可以被5整除,则除以5,因为乘以5会得到比加3更短的解.唯一的例外是如果值等于10,因为除以5将产生2是无法解决的.如果数字不能被5整除或等于10,则减去3.这将产生最短的字符串

重复直到达到1

这是python代码:

def f(x):
    if x%3 == 0 or x==2:
        return "Can't generate it"
    l = []
    while x!=1:
        if x%5 != 0 or x==10:
            l.append(3)
            x -= 3
        else:
                l.append(5)
                x /=5
    l.reverse()
    s = '1'
    for v in l:
        if v == 3:
            s += ' + 3'
        else:
            s = '(' + s + ')*5'
    return s

相信以前的解决方案,以确定给定的数字是否可行