面试中遇到的有趣算法题(因式分解)


题目

文字版描述如下:

定义两个字符串变量:s和m,再定义两种操作如下
第一种:
m = s
s = s + s
第二种操作:
s = s + m
假设s,m初始化如下
s = “a”
m=s
求最小的操作步骤数,可以将s拼接为长度为n的字符串
输入为一个正整数n(0 < n < 10000)
输出为最小的操作次数

思路

首先我们看到第一种 m = s后,s = s + s = s + m,形式与第二种相同,所以本质上两种形式都是相同的,只是第一种修改了m的取值,既然对s的修改上形式统一了,那我们就可以更集中去求解了,另外s与m之间一定有倍数关系,如果有第一种操作的话可以明显得知,如果没有第一种操作,则m=1,也是有倍数关系。

归纳法证明

因为两种操作形式都是s=s+m,我们先找出一个对于所有数都存在的解法,即倒数第a步用第一种操作令s’=m=s/a,最后的a-1步都用第二种操作s=s’+m=s/a+s/a的形式获得,其中a为s的因子,且a>1:
f(s) = a-1(步) +f(s/a)

  1. 当s是质数的时候
    那么他的因子只有1和本身,所以a=s,相当于每一步都是s = s + s/a = s+1得到,此时 f(s) = s-1

  2. 当s只可以分解为2个质数因子相乘的时候
    设质数因子为a、b,a≥2,b≥2
    则f(s) = a-1 + f(s/a) = a - 1 + f(b)
    由1中得知f(b) = b-1
    故f(s) = a - 1 + b -1 = a + b - 2
    而此时s仍然可以分解为1和s两个因子,那么另一种解法就是
    f(s) = s - 1 + f(1) = s-1
    此时可以证明:(a-1)+(b-1)≤ (a-1)*(b-1) = ab - (a+b)+1 = s - (a+b)+1 ≤ s-1
    故此时最优解是f(s) = a-1 +f(s/a) = a-1 + f(b) = a - 1+b -1=f(a) +f(b) ,其中由于a,b为质数所以f(a) = a - 1,f(b) = b - 1

  3. 当s可以分解为3个质数因子相乘的时候
    设质数因子为a、b、c,a≥2,b≥2,c≥2
    f(s) = a-1 + f(b*c),这里用上第二步的结论可得:
    f(s) = a-1 + f(b*c) = a-1 + b-1 + c-1

    f(s) = b-1 +f(a*c) = b-1 + a-1 + c-1

    f(s) = c-1 +f(a*b) = c-1 + a-1 + b-1

    f(s) = s -1
    同时易证 a-1 + b-1 + c-1 ≤ s-1
    故此时最优解是f(s) = a-1 + b-1 + c-1 = f(a) + f(b) + f(c)

  4. 以此类推
    所有的非质数都可以分解为质数的积,那么f(s)就是其所有质数因子的f函数值求和,如
    f(12) = f(2) +f(2) + f(3) = 4

结论

那么根据以上的等式我们可以得到,f(n) = f(a1)+f(a2)+…+f(an),其中a1~an为将n进行因式分解后的所有质数因子
如f(12) = f(2) + f(2) + f(3)
所以我们从底向上不断刷表就可以求出结果

优化

由于上式要求出所有的质数因子,会比较麻烦,我们观察得出
f(4) = f(2) + f(2)
f(6) = f(2) + f(3)
f(12) = f(2) + f(2) + f(3) = f(2) + f(6) = f(4) + f(3)
注意到我们在从底向上刷表的时候,底下的数已经全部求出来了,此时就不需要求出所有质数因子了,只要找到第一个因子即可,新的式子如下
f(n) = f(n/a) + f(a) ,当n为质数时f(n) = n-1
所以每次计算一个数时我们从2开始往上找他的因子,找到sqrt(n)还没找到时,他就是一个质数,f(n) = n-1即可,若找到因子,直接回去查表就可以得到结果