2013年1月29日 星期二

[C Programming] 兩陣列最短距離-延伸

1. 將程式改寫成函數來解下一題,雖然解法不會很好。(等值首尾和問題)
2. 其中有一個陣列沒排好時,還能正常運作嗎?兩個都沒排好的話呢?
    請克服之。
3. 請修改程式,報告出造成最短距離的那兩個元素的位置與它們的值。
4. 將兩個++的敘述都移到"minimum=..."之前的話,會有相同的結果嗎?

個人解法:
1. 留待下一題吧XD
2. 陣列沒排好的時候,可以進行sorting來回到適合本解法的狀態。
    如果不作排序的話,對單一陣列而言,比如x[]未排序而y[]已排序時,
    拿每一個x[i]去跟y[]中的值比較,找到y[j-1]<x[i]<y[j]的時候,
    就可以算出x[i]和y[]的最小距離,如此一來,
    每個x[]中的值都比過後就可以得到答案。
    但這個方法的worst case還是n^2(兩者長度皆為n的話),
    所以可以的話,先排序好來作比較有效率。
    沒排好的狀況只要有斷層就會令程式出錯,無法正確輸出。
3. 修改時就變成要記住是誰造成最短距離了。
Code如下:
int min_dist(int x[], int y[], int m, int n)
{
 int minimum = INT_MAX, _xi = 0, _yi = 0;
 int _xmin = 0, _ymin = 0;
 while( (_xi < m) && (_yi < n) )
  if(x[_xi] >= y[_yi]) 
  { 
   if(x[_xi]-y[_yi] <= minimum)
   {
    minimum = x[_xi] - y[_yi];
    _xmin = _xi; _ymin = _yi;
   }
   _yi++; 
  }
  else
  { 
   if(y[_yi]-x[_xi] <= minimum)
   {
    minimum = y[_yi]-x[_xi];
    _xmin = _xi; _ymin = _yi;
   }
   _xi++;  
  } 
 printf("\nFrom x[%d] and y[%d],",_xmin,_ymin);  
 return minimum;
}


4. 不會,因為移動後的index不一定比較符合,且第一次的值比較會被跳過。
    再者,index會移動到陣列範圍外,會有什麼值在那沒人知道的XD

沒有留言:

張貼留言