中国电信数据分析笔试——三道编程题

1 找丑数

若一个数的因子只有2，3，5，那么这个数称为丑数，1是第一个丑数，2是丑数，7不是丑数 。
要求给定一个整数N, 返回第N个丑数
思路：递归，基线条件第一个丑数为1 ；递归条件：第N个丑数为N-1个丑数后面的那个丑数 。如何判定丑数？
a = 2^i 3^j 5^k ,则为a丑数

N =int(input())
def whoisNthugly(N):
    if N == 1: 
        return 1 
    if N>1:
        r = whoisNthugly(N-1)+1
        i,j,k= 0,0,0
        while 1:
            a=r
            while a!=1 :  # a==1 找到丑数
                if a%2==0: 
                    a = a/2 
                elif a%3==0: 
                    a = a/3
                elif a%5==0: 
                    a = a/5 
                else : 
                    r+=1
                    break
            return r
N=10
whoisNthugly(N) 
>12 
复制

2 找子列

给定一组整数，要求找到一组子列使其和最大，但原数组中相邻的数只能选一个。返回其和
思路：分而治之，不断转化为简单的情况。 基线条件：若列表长度为0， 和为0；若长度为1或2，和为较大的那个数 。
递归条件：若列表长度大于3， 找到最大的数a， 将a和与a相邻的数删除生成子列，该列表的和为a加子列的和

def findbiggset(li):
    if len(li)==0:return 0
    if len(li)==1 or  len(li)==2 :
        return max(li)
    else : 
        a = max(li)
        k=li.index(max(li))
        if k==len(li)-1:
            li = li[:-2]
        elif k==0:
            li=li[2:]
        else : 
            li = li[:k-1]+li[k+2:]
        #print(li)
    return a+findbiggset(li)
        
    
li=[2,4,2,5,6]
findbiggset(li)
>10 
复制

3 a,b,c,d 属于[0,9] ,使得abcd+bcda=8888的abcd有几种 ？

思路：没想到好的方法，总的可能也不多，遍历。

u=0
for a in range(10):
    for b in range(10):
        for c in range(10):
            for d in range(10):
                i = a*10**3+b*10**2+c*10+d
                j = b*10**3+c*10**2+d*10+a
                if i+j==8888:
                    #print(a,b,c,d,b,c,d,a)
                    u+=1
print(u)
>9
复制