分治法求解查找假币问题。有n枚硬币递归方法

假币问题可以使用分治法来解决。假设有n枚硬币，其中一枚是假币，并且假币比真币轻。现在要用天平来称这些硬币，最少需要称多少次才能找出假币。

分治法的思想是将问题分解成若干个子问题，然后递归求解子问题。对于假币问题，可以将n个硬币分成三组：每组一样多的硬币。然后将这三组硬币分别放在天平的两端和中间，比较天平的平衡情况，可以确定假币在哪一组中。假设假币在第一组中，那么可以将第一组硬币继续进行分治，直到找到假币为止。

递归方法如下：

def find_fake_coin(coins):
    n = len(coins)
    # 没有硬币或只有一枚硬币，直接返回
    if n <= 1:
        return coins[0]
    # 将硬币分成三组
    group_size = n // 3
    group1 = coins[:group_size]
    group2 = coins[group_size:2*group_size]
    group3 = coins[2*group_size:3*group_size]
    # 比较天平的平衡情况
    if sum(group1) == sum(group2):
        # 假币在第三组中
        return find_fake_coin(group3)
    elif sum(group1) < sum(group2):
        # 假币在第一组中
        return find_fake_coin(group1)
    else:
        # 假币在第二组中
        return find_fake_coin(group2)

其中，coins为硬币的重量列表，函数返回值为假币的重量。对于每次递归，硬币数量都会减少三分之一，因此递归深度为log3(n)，时间复杂度为O(log3(n))。