UVA 一星題筆記10041 Vito’s Family

因為最近的CPE考試，讓我寫程式的信心有極大的打擊，所以決定要開始好好練習寫題目了。就從UVA的一星題開始練習吧！

一星題題目

第一題題目大致如下：

有一個黑幫老大他家族人數眾多，然後他想要在他眾多家族中，找一個地方是離其他親戚比較近的地方。

解題：一開始我也一直搞不懂題目到底想要要我幹嘛，但看完其他大大的解釋後就懂了。他很簡單的就是要我們先找中位數（老大家），然後再去找中位數與其他家人的距離而已。

那中位數要怎麼找呢？

用程式寫出個排列（Bubble Sort, insertion sort, qsort…）都不限制，我使用的是Bubble Sort，等等會介紹。然後排序後再用，總個數最中間的位子即為中位數，若為偶數狀況的話，則用中間兩的數字相加的和再除以2。

假設我們有一組數字：1 1 1 1 1000 1000

則其中此組數字的中位數為1 + 1 / 2 =1（中位數為1）因為裡面最中間兩個數字為1 1

再來用其他數字減去這個中位數即是題目要的答案。

再來是排序問題：介紹Bubble Sort

他是一個把先把最大的數字，先拿出來放著，等下一輪再找一個下一輪最大的數，以此類推，把數字給排序完成。

＊不算是很好的排序方式，當數字很大的話，會讓程式跑很久。請大家注意一下囉～

程式碼我用兩個函式去寫，分成交換、排序。

void BubbleSort(int *arr, int len)
{
   int temp;
   //計算總共會做幾次
   for(int i = 0; i < len - 1; ++i)
   {
      //兩個兩個數字交互比較，當前面大於後面的數時，則做交換的動作
      for(int j = 0; j < len-1-i; ++j)
      {
         if(arr[j] > arr[j+1])
         swap(&arr[j], &arr[j+1]);
      }
    }
}
void swap(int *num1, int *num2)
{
    int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

至於距離怎麼算就給大家參考看看吧（個人的拙見）

int distance(int *arr, int med, int num)
{
    int sum = 0;
    for(int i = 0; i < num; ++i)
    {
        sum = sum + abs(arr[i] - med);
    }
    return sum;
}

以上為這次的筆記，我們下次見！！