Re: [問卷] 有關使用維基百科於課業上之調查

[lincy075 (Kasim)]

話說今天一位大四同學問老師下面這個問題

How many spanning trees does a five node complete graph have?
(A) 120 (B) 60 (C) 48 (D) 24


老師想了想覺得這問題不容易, 就用維基百科找答案
可見維基百科是可以用在課業上的, 老師也常把維基百科的資料放到投影片,
不過呀維基百科的答案不在上面選項

http://en.wikipedia.org/wiki/Cayley%27s_formula

5^3 = 125

老師只好寫了一個程式去算 (同學既然問了總是要想辦法回答),
果然是 125 (看來是出題的人出錯了)
有興趣的同學可看看老師的程式 (不過是為了解答同學問題而寫的, 寫法沒很好)

import java.util.ArrayList;

public class STCG {

        static ArrayList<Edge> elist;

        public static void main(String[] args) {
                int [] bit = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};

                elist = new ArrayList<Edge>();
                elist.clear();
                elist.add(new Edge(0, 1));
                elist.add(new Edge(0, 2));
                elist.add(new Edge(0, 3));
                elist.add(new Edge(0, 4));
                elist.add(new Edge(1, 2));
                elist.add(new Edge(1, 3));
                elist.add(new Edge(1, 4));
                elist.add(new Edge(2, 3));
                elist.add(new Edge(2, 4));
                elist.add(new Edge(3, 4));

                int ntrees = 0;
                for (int i = 0; i < 1024; i++) {
                        for (int j = 0; j < 10; j++) {
                                if ((i & bit[j]) == bit[j]) {
                                        elist.get(j).treeedge = true;
                                } else {
                                        elist.get(j).treeedge = false;
                                }
                        }

                        int edgecount = 0;
                        for (int j = 0; j < 10; j++) {
                                if (elist.get(j).treeedge == true) {
                                        edgecount++;
                                }
                        }
                        if (edgecount != 4) continue;

                        ArrayList<Vertex> vlist = new ArrayList<Vertex>();

                        vlist.clear();
                        for (int j = 0; j < 5; j++) {
                                vlist.add(new Vertex(j));
                        }

                        for (int j = 0; j < 10; j++) {
                                if (elist.get(j).treeedge == true) {
                                        int p1 = elist.get(j).p1;
                                        int p2 = elist.get(j).p2;
                                        vlist.get(p1).neighbor.add(p2);
                                        vlist.get(p2).neighbor.add(p1);
                                }
                        }

                        DFSKernel(vlist, 0);

                        boolean kickflag = false;
                        for (int j = 0; j < 5; j++) {
                                if (vlist.get(j).ccid != 0) {
                                        kickflag = true;
                                        break;
                                }
                        }

                        if (kickflag == false)
                                ntrees++;

                }
                System.out.println(ntrees);
        }

        static void DFSKernel(ArrayList<Vertex> vlist, int vid) {
                vlist.get(vid).flag = true;
                for (int i = 0; i < vlist.get(vid).neighbor.size(); i++) {
                        int nid = vlist.get(vid).neighbor.get(i);
                        vlist.get(nid).ccid = 0;
                        if (vlist.get(nid).flag == false) {
                                DFSKernel(vlist, nid);
                        }
                }
        }
}

class Vertex {
        public ArrayList<Integer> neighbor;
        public int ccid;
        public boolean flag;

        Vertex(int ccid) {
                neighbor = new ArrayList<Integer>();
                neighbor.clear();
                this.ccid = ccid;
                flag = false;
        }
}

class Edge {
        public int p1;
        public int p2;
        public boolean treeedge;
        Edge(int p1, int p2) {
                this.p1 = p1;
                this.p2 = p2;
        }
}


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 210.70.83.127
推 ag2360133:快回 不然會被說看不懂
推 invite0403:英文的WIKI跟中文的WIKI內容豐富度差好多= =
推 XXXmilk:快回不然會被說看不懂 其實我5歲的時候就常常拿這個來玩了
→ ag2360133:樓上金豪洨