假币问题的算法三种代码

假币问题是计算机科学中经典的排序问题之一，通常涉及识别一组硬币中哪些可能是假币，已知真币有固定的重量，而假币比真币轻或重。这里有几种常见的解决策略：

1. **称量法**（二分查找法）：

   def counterfeit_coins(weighs, target):
       total_weight = sum(weighs)
       if total_weight == target:  # 如果所有硬币加起来就是目标重量，没有假币
           return []
       
       half_value = total_weight // 2
       left, right = [], []
       for coin in weighs:
           if coin <= half_value:
               left.append(coin)
           else:
               right.append(coin)
       
       left_weighs, right_weighs = counterfeit_coins(left, half_value), counterfeit_coins(right, target - half_value)
       if not left_weighs and not right_weighs:  # 没有轻于半目标值的假币，所以剩下的都是假的
           return right
       elif not left_weighs:  # 右边的全部是假币
           return right + [coin for coin in left if coin < half_value]
       elif not right_weighs:  # 左边的全部是假币
           return left + [coin for coin in right if coin > half_value]
       else:  # 找到一个轻于半目标值的假币
           return [left_weighs[0]] + [coin for coin in right if coin > half_value]

2. **哈希表**（计数法）：

   def find_counterfeit_coins(weights):
       target_weight = sum(weights)
       real_weights = {weight: weights.count(weight) for weight in set(weights)}
       fake_counts = {weight: target_weight - count * weight for weight, count in real_weights.items()}
       return [weight for weight, count in fake_counts.items() if count % 2 != 0]

   # 使用示例
   coins = [1, 2, 3, 4, 5, 6]  # 假设我们只有这些面额
   result = find_counterfeit_coins(coins)

这两种方法都有其适用场景，称量法则更适用于重量范围较大且可以精确分割的情况，而哈希表则适合面额种类不多且假币数量较少的情况。