作者lincy075 (Kasim)
看板ASIA_ISA
標題Re: [問卷] 有關使用維基百科於課業上之調查
時間Thu Jan 7 22:09:44 2010
話說今天一位大四同學問老師下面這個問題
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
1F：推 ag2360133:快回 不然會被說看不懂 01/07 22:11
2F：推 invite0403:英文的WIKI跟中文的WIKI內容豐富度差好多= = 01/08 01:47
3F：推 XXXmilk:快回不然會被說看不懂 其實我5歲的時候就常常拿這個來玩了 01/09 14:30
4F：→ ag2360133:樓上金豪洨 01/11 03:05