[C Programming] 等值數目-延伸

延伸問題：
1. 請修改程式，將相等元素的足碼(index)顯示出來。
2. 如果f[]和g[]中有相同的元素，但仍然是自小到大排好了，
    這個程式還能正常工作嗎？問題何在？請嘗試修改之。
    舉例來說，如果f[]是1,3,3,5,7而g[]是1,3,3,8,9，就會產生四對3是相同的。
    修改後的程式效率還能一樣好嗎？
3. 為什麼一邊的元素用完就可以停止工作呢？
4. 試證明這個程式的比較次數絕對不會超過2n次，n是f[]與g[]中的元素個數。

個人解法：
1. 只要加入在相等時輸出的函式或者以陣列記錄下來即可。
    或者也可以開二維陣列記錄下來，不過比較麻煩。

將原Code處加入printf：

else if(f[i] == g[j])
 {printf("\n(f[%d],g[%d]),"); i++;j++;cnt++; }

2. 如果f[]和g[]中有相同的元素的話，程式就無法正常計算了。
    因為在i++和j++的過程中會漏算組合。
    修改的方法是當發現相等時，嘗試去尋找兩邊平台長度，
    相乘後得到組合的數目。當兩邊長度為1時(單個)，
    組數自然也是1，合乎邏輯。


將原Code的else...if處更改如下：

else if(f[i] == g[j])
{
 len_f = 1; len_g = 1; tmp = f[i]; // 在進入函式時宣告之
 while(i+1<m)
  if(f[i+1] == tmp){i++;len_f++;}
  else break; // 搜尋到最後一個相等的f[i]為止
 while(j+1<n)
  if(g[j+1] == tmp){j++;len_g++;}
  else break;
 cnt += len_f * len_g;   
 i++;j++; // 讓index遞增移出平台範圍
}

注意如果還要達到1的要求的話就要在這中間跑迴圈完成，在此不再重複。

3. 因為在前題是同陣列中的各元素皆不相等的條件下，
    當發生一個陣列的元素被用完，
    要嘛是f[]的最後一個比g[j]小或相等，
    這樣後面的g[j+1]、g[j+2]...等更大，所以也都不用比了；
    不然就是g[]的最後一個比f[i]小或相等，
    這樣後面的f[i+1]、f[i+2]...更大，所以同樣也都不用比了。
4. 這程式會繼續跑的條件就是(i < n) && (j < n)。
    每一次判斷式中，i或j之中最少有一個數會遞增，
    最壞的狀況就是i跑到n-1，j也跑到n-1，如此，
    亦不會超過2*( (n-1)-0 +1) = 2n次。