乐鑫 7.12笔试

第一题：x^(-1)+x = k, 求x^(-m)+x^m
题解：假设F(a)=x^(-a)+x^a
F(a)*F(1)=F(a+1)+F(a-1)
F(0)=2, F(1)=k，可以直接动规

F = [0]*(m+1)
F[0]=2
F[1]=k
for i in range(2, m+1):
    F[i] = F[i-1]*F[1]-F[i-2]
print(F[m])

第二题：给一个长度为n的乱序数组，每次只能将数组中的一个元素移到队首（置顶），求将该乱序数组变成升序数组的置顶次数
题解：如果一个数在乱序数组中，前面有数字比该数大，则这个数是乱序数。找出最大的乱序数，该乱序数在升序数组中的位置，该位置就是置顶次数（因为比该数小的数都需要在这个数之前置顶）

n = 6
nums = [1,6,5,3,4,2]
if n<2:
    print(n)
else:
    cur = nums[0]
    curMax = 0
    for item in nums:
        if item>cur:
            cur = item
        if item<cur and item>curMax:
            curMax = item
    nums.sort()
    for i in range(n):
        if nums[i]==curMax:
            print(i+1)