---
title: 'FAKE COIN'
disqus: hackmd
---

FAKE COIN
===
**給定一個數字序列，僅能使用天平去找出唯一不同的數字**

## 目錄

[TOC]

## 環境
**Windows系統**
**IDE** : Dev_C++
**語言標準**: GNU C++ 11

演算法設計想法
---
首先將前兩個硬幣分別放到天平的左邊與右邊，然後兩種情況:
1. **天平持平**:
代表本次輪兩個硬幣皆非FAKE COIN，繼續放兩個硬幣到天平左邊與右邊直到傾斜
3. **天平傾斜**:
代表FAKE COIN出現在輪中，留下本輪其中一枚硬幣(左右都行)，然後將天平清空，將這枚硬幣與前面測試TRUE COIN放上天平兩端，若造成傾斜，則代表這枚硬幣是FAKE COIN，若持平，則代表本輪的另一枚硬幣是FAKE COIN

**!!注意!! 若第一輪就傾斜，那代表之後的COIN就全部都是TRUE COIN，利用此結果做一次2就好了**

實作重點
---
先處理第一輪情況:

balance.left+=coin.left
balance.right+=coin.right
if balance.left==balance.right:
    #若持平，代表第一輪硬幣皆是True coin，繼續往下堆
    find_coin()
else:
    #天平傾斜，代表fake coin在本輪中
    #從後面的coin(必為true)隨便挑一個與本輪隨便挑一個做比較
    if coin[0]==coin[2] : fake_coin為coin[1]
    else fake_coin為coin[0]; 

若第一輪持平，進到find_coin函式

int find_coin(vector<int >coin){
    for(int i=2;i<coin.size()-1;i+=2){
        int j=i+1;
        balance.left+=coin[i]; 
        balance.right+=coin[j];
        if(balance.left!=balance.right){ //代表fake coin在本輪
            balance.left=0,balance.right=0; //把天平裡硬幣全部清空
            
            balance.left+=coin[i]; 
            #留下本輪其中一枚(我留左邊那枚)
            balance.right+=coin[0];
            #天平右端放上之前測量過後為True的硬幣
            if(balance.left==balance.right) return j; //coin[j]為fake
            else return i;  //coin[i]為fake 
        }	
    }
	return weight.size()-1; 
       #此為處理奇數硬幣個數且FAKE COIN是最後一個的情況
}

## 演算法分析
**時間複雜度:**

使用每次天平處理掉兩個coin，在測試直到傾斜後，需再多使用一次天平確定哪個是fake coin
Worst case: N/2+1
Best case: 1+1
程式實際時間複雜度:O(N)

**空間複雜度:**

由於是連續使用天平，只需要宣告兩個整數就行，每次把值累加上去
程式實際時間複雜度:O(1)