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
沒有留言:
張貼留言