Problem 10034 Freckles 雀斑

這題是標準的最小伸展樹(Minimum Spanning Tree)問題(或稱為最小生成樹)，可以使用 Prim 或 Kruskal 演算法來解決，不需要自己再發明什麼新的方法。

這裡使用 Prim 的演算法，參考蔡宗翰譯的「演算法--使用C++虛擬碼」書中(碁峯資訊，2004年)，第四章貪婪演算法的方式，很快就可以完成。
在讀取雀斑輸入值之座標點後，你必須自行製作 W 距離矩陣，W 是全域變數，提供 prim 函數使用。另一個全域變數 F ，用來存放解答中相連的點。
prim 函數如下：

void prim(int m)
{
    int i,j,k,vnear;
    int nearest[SIZE];
    float distance[SIZE], Dmin;
    for (i=1; i<m; i++)
    {
        nearest[i] = 0; /* Start from v0 */
        distance[i] = W[0][i];
    }
    for (k=1;k<m;k++)
    {
        Dmin = inf;
        for (i=1;i<m;i++)
            if (0<=distance[i] && distance[i]<Dmin)
            {
                Dmin = distance[i];
                vnear = i;
            }
        F[k][0] = vnear;
        F[k][1] = nearest[vnear];
        
        distance[vnear] = -1;
        for (i=1;i<m;i++)
            if (W[i][vnear] < distance[i])
            {
                distance[i] = W[i][vnear];
                nearest[i] = vnear;
            }
    }
}

當完成10034 Freckles，ACM 10147 Highways (高速公路)與 ACM 10397 Connect the Campus(連接校園) 這兩題就可以順便輕鬆的解題了。
p10034題目連結
回ACM題庫目錄
回首頁

Problem 119 Greedy Gift Givers 貪心的送禮者

這題目中，每次送禮者最多十人，每個人送出一個數字的金額，平均分配給指定的人。題目的要求在計算每個送禮者到底是收了多少錢，或付出多少錢。
題目說是貪心的送禮者，就是說你要斤斤計較，到底誰賺誰賠，所以多收了就賺到了，少收了就賠了，那斤斤計較的過程就顯得有點貪心，這樣說，對嗎？管它的，寫程式吧。

這個ACM 題目是練習C語言結構的好機會，程式的結構定義如下，name是名字，mget是淨收入。

typedef struct
{
    char name[20];
    int mget;
} person;

由於輸入格式中，並未告知有多少案例，題目所列的示範是兩個案例，因此程式可以用

while (scanf("%d", &n)!= EOF)

來判斷是否還有下一個案例。
每次執行前，別忘了將所有人的變數設定為初設值。
在讀取每個人的付出時，就可以先計算每個人的淨支出，別忘了不能整除時，要將餘數留著，C語言程式碼如下所示。

scanf("%s%d%d", givename, &give_amount, &m);
if (strcmp(givename, P[k].name)==0)
{
    if (m!=0)
        P[k].mget -= give_amount;
    if (m!=0)
        P[k].mget += give_amount%m;
}

然後，讀取付給哪些人，使用 strcmp 進行姓名字串的比較，比較輸出為 0 時，表示兩個字串相等，這時就可以將那個人的收入進行累加，程式如下。

if (strcmp(getname, P[k].name)==0)
    P[k].mget += give_amount / m;

其實，程式是很簡單的，但是要注意一種狀況，就是有付出金額，分配人員的數量是零的情形，也就是上述程式碼 m 為零的情形，因為題目也沒說會有設定分配人數是零的情形 (很詐)，如果沒考慮這點，上傳就會收到 wrong answer，這種情形最ㄐㄧㄢˋ，誰曉得是為什麼錯。
另外，要注意輸出的案例與案例之間要空一行。
p119題目連結
回ACM題庫目錄
回首頁

如何進行指標 (pointer) 的傳址呼叫(call by reference) (下)

這篇文章介紹函數的傳址呼叫，本文的內容是關於指標變數存放位址的改變。

為什麼要改變指標存放的位址呢，這是個很好的問題，平時在主程式中使用 p = &i;就可以改變其位址值，但是我們要藉著函數呼叫來改變其內容，用途呢?例如你用函數傳入指標來取得新的變數的位址(例如：dequeue(v)呼叫)。但是，有一點要注意的是，指標的值，就像一般整數 int 的值，他們都是屬於傳值呼叫(call by value)的。沒錯，指標也是傳值呼叫。

在下列的C語言範例程式中，modify 收到一個指標 v，然後試著去改變其本身所存放的值，你可以從執行結果看到，ptr的值完全沒有改變，這是當然的，傳值呼叫嗎。要改變其值，必須使用傳址呼叫，所以在 modify2 函數中，注意到了嗎，傳進去的是 int **p ，因為傳進來的是指標變數本身所在的位址，而 **p 表示這個位址中的位址中的值是整數。還可以懂吧。

因此呼叫時，必須傳入指標變數本身的位址，如下所示：

modify2(&ptr);

從執行的結果可以看出，指標的值被函數改變了，好玩吧。

#include <stdio.h>
#include <stdlib.h>

int x=8;
void modify(int *v)
{
    v = &x;
}
void modify2(int **p)
{
    *p = &x;
}

int main(void)
{
    int i = 5, *ptr;
    ptr = &i;

    printf("Before: ptr=%p, *ptr=%d\n", ptr, *ptr);
    modify(ptr);
    printf("After: ptr=%p, *ptr=%d\n", ptr, *ptr);
    printf("Before: ptr=%p, *ptr=%d\n", ptr, *ptr);
    modify2(&ptr);
    printf("After: ptr=%p, *ptr=%d\n", ptr, *ptr);

    return 0;
}

程式的執行結果如下：

Before: ptr=0022FF74, *ptr=5
After: ptr=0022FF74, *ptr=5
Before: ptr=0022FF74, *ptr=5
After: ptr=00402000, *ptr=8

如何進行指標 (pointer) 的傳址呼叫(call by reference) (上)

這篇文章介紹函數的傳址呼叫，第一段是利用指標來改變其所指到位址的內容，
傳遞的是指標所存放的地址。第二段是改變指標變數所存放的位址，傳遞的是指標本身的所在的位址。

指標的所存放的內容是地址，通常是其他值的地址。
常見的宣告會告知其內容的地址中所存放值的型態，例如

int *ptr;

這表示ptr的內容地址所指到的地方存放著一個型態為 int 的值。
又例如

void *ptr;

這表示ptr的內容是一個地址，其地址中的值的型態尚未特別指出，暫時空著，
等到後來要用時，必須藉著 cast 的方式來表示其所指值的型態。

指標常用在函數的傳址呼叫(call by reference)，在下列的範例中，
函數 modify 傳入一個指標 p，而 *p=100;表示將100放入p所指的位址中。

所以當指標的地址是其他變數的位址時，自然就可以用相同的方式，
透過函數的傳址呼叫來改變其他變數的值。在第二段的modify 函數呼叫前，
我們使用 ptr = &i; 讓ptr 存放著 i 的位址，所以當呼叫modify(ptr);後，i 的值就被改變了。

#include <stdio.h>
#include <stdlib.h>

void modify(int *p)
{
  *p = 100;
}

int main(void)
{
  int i, *ptr;
  pp = &x;
  i = 5;

  printf("Before: i=%d\n", i);
  modify(&i);
  printf("After: i=%d\n", i);

  printf("Before: ptr=%p, *ptr=%d\n", ptr, *ptr);
  i = 20;
  ptr = &i;
  modify(ptr);
  printf("After: ptr=%p, *ptr=%d, &i=%p, i=%d\n", ptr, *ptr, &i, i);

  return 0;
}

程式的執行結果如下：

   Before: i=5
   After: i=100
   Before: ptr=0022FFA8, *ptr=0
   After: ptr=0022FF70, *ptr=100, &i=0022FF70, i=100

在第二段的內容中，將說明指標變數內容位址的改變方式。