python-最大比例

解题思路:

我们知道等比数列的递推公式为a_n=a₁*q^n-1。a_i/a_j=q^i-j。

此处我们就假设最大公比为q，采访的金额数组为A，假设A中有三个不相同的金额，经排序后A中相邻两个数的比值放入数组B中。

①一开始我想的是先将A去重，然后将A中的元素从大到小排序，最后输出最小的那一个。结果不正确。这个时候好像是只有22分。

分析原因：

通过刚刚的思路，在B中我们可以得到两个元素[qⁱ,q^j]，此时i和j为>=1的正整数。如果此时B中最小的数为qⁱ，如果i>1，那么我们将其输出后结果就是错误的。

②接着对算法进行改进，我们将B中的元素从大到小排序，然后将B中的相邻两个元素的比值添加到B中，最后输出B中最小的那个数。结果也是错误的，此时有78分。

分析原因：

经过改进的算法后我们知道，此时的B中有三个元素[qⁱ,q^j,q^i-j]，此时在①的基础上我们在B中又刷新出了一波较小值，那就是q^i-j，最后为什么只得了78分呢，原因和之前是一样的，假设此时的最小值为q^i-j，(i-j>=1)，如果此时的i-j大于1那么我们输出的结果还是错误的。

③在②的基础上我们再次对算法进行改进，我们求②的刷新后的数组B中的最大公因数。此时AC了。

分析原因：

如果题目中没有说一定有解的话，其实最大公因数也不一定就是q。但是题目中说了一定有解，所以给出的数据就一定能得到q。

那么这里我们可能会有疑问，能不能在①的基础上我们直接求B中的最大公因数。这个我尝试过了，答案是错误的。

为什么在①的基础上求最大公因数不行，但是在②的基础上求就可以了呢，我认为可能是在①中的基础上B中的数据较少，不足以每次都能准确的得到q。

以上就是我对本题的一些想法，希望能够帮到大家。

注意事项:

参考代码:

from math import gcd  
  
def f():  
    A = {int(i) for i in input().strip().split()}  
    A = list(A)  
    A.sort(reverse=True)  
  
    B = set()  
    for i in range(len(A)-1):             #A经过排序后相邻两个数之间的比值  
        x = gcd(A[i],A[i+1])  
        B.add((A[i]//x,A[i+1]//x))  
  
    B = list(B)  
    B.sort(key= lambda x:x[0]/x[1],reverse=True)  
    n = len(B)  
    for i in range(n-1):                  #将B经过排序后相邻两个数的比值添加到B中  
        y = B[i][0]*B[i+1][1]  
        x = B[i][1]*B[i+1][0]  
        temp = gcd(x,y)  
        B.append((y//temp,x//temp))  
  
      
    ymax = B[0][0]  
    xmax = B[0][1]  
    for i in range(1,len(B)):             #求出B中的最大公因数  
        ymax = gcd(ymax,B[i][0])  
        xmax = gcd(xmax,B[i][1])  
    print('{}/{}'.format(ymax,xmax))  
      
  
if __name__ == '__main__':  
    num = int(input().strip())  
    f()