解題區►解題區 - UVa

UVa 157 - Route Finding

Problem

Many cities provide a comprehensive public transport system, often integrating bus routes, suburban commuter train services and underground railways. Routes on such systems can be categorised according to the stations or stops along them. We conventionally think of them as forming lines (where the vehicle shuttles from one end of the route to the other and returns), loops (where the two ends of the branch are the same and vehicles circle the system in both directions) and connections, where each end of the route connects with another route. Obviously all of these can be thought of as very similar, and can connect with each other at various points along their routes. Note that vehicles can travel in both directions along all routes, and that it is only possible to change between routes at connecting stations.

To simplify matters, each route is given a designation letter from the set A to Z, and each station along a route will be designated by another letter from the set a to z. Connecting stations will have more than one designation. Thus an example could be:

A common problem in such systems is finding a route between two stations. Once this has been done we wish to find the best route, where best means shortest time.

Write a program that will read in details of such a system and then will find the fastest routes between given pairs of stations. You can assume that the trip between stations always takes 1 unit of time and that changing between routes at a connecting station takes 3 units of time.

Input

Input will consist of two parts. The first will consist of a description of a system, the second will consist of pairs of stations. The description will start with a number between 1 and 26 indicating how many routes there are in the system. This will be followed by that many lines, each describing a single route. Each line will start with the route identifier followed by a : followed by the stations along that route, in order. Connections will be indicated by an = sign followed by the complete alternative designation. All connections will be identified at least once, and if there are more than two lines meeting at a connection, some or of all the alternative designations may be identified together. That is, there may be sequences such as ...hc=Bg=Cc=Abd.... If the route forms a loop then the last station will be the same as the first. This is the only situation in which station letters will be repeated. The next portion of the input file will consist of a sequence of lines each containing two stations written contiguously. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines, one for each pair of stations in the input. Each line will consist of the time for the fastest route joining the two stations, right justified in a field of width 3, followed by a colon and a space and the sequence of stations representing the shortest journey. Follow the example shown below. Note that there will always be only one fastest route for any given pair of stations and that the route must start and finish at the named stations (not at any synonyms thereof), hence the time for the route must include the time for any inter-station transfers.

The example input below refers to the diagram given above.

Sample input

1
2
3
4
5
6
7
8
9
4
A:fgmpnxzabjd=Dbf
D:b=Adac=Ccf
B:acd=Azefg=Cbh
C:bac
AgAa
AbBh
BhDf
#

Sample output

1
2
3
 5: Agfdjba
 9: Abaz=Bdefgh
10: Bhg=Cbac=Dcf

Solution

題目描述：

這一個交通運輸工具，配置如上圖所述，以大寫字母 (A - Z) 表示哪一種線路，每一條線路上有一些站牌 (a - z)。求某線某站到某線某站的最少花費時間。

然而在同一個線路上，轉換一個站的成本為 1，如果在線路交集站換一條線路走成本為 3。

輸入上比較特別，會用 = 表示交集的站編號，當然有可能會遇到多個線路的站交集在一起。

Dhc=Bg=Cc=Abd 則表示 D 線路上的 Dh-Dc-Dd，其中 Dc, Bg, Cc, Ab 共站。

可以當作雙向連通，如果有環，則會頭尾相同，例如 Dhch。

題目解法：

題目最令人討厭的是，交集站沒有說清楚，也就是說單一線路上的轉運站沒有說清楚，但事實上會被表示在其他線路上，這裡要自己取聯集。

但是做聯集是件挺麻煩的事，因此在求最短路上做點手腳，把狀態表示成 (某線某站, 前一次是否轉運)，這麼做就方便多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int trans_node(int r, int a) {
	r -= 'A', a -= 'a';
	return r * 26 + a;
}
void reverse_node(int n, int &r, int &a) {
	r = n /26 + 'A', a = n %26 + 'a';
}
vector<int> g[1024], g2[1024];
void spfa(int st, int ed) {
	int used[1024][2] = {}, dist[1024][2] = {}, prex[1024][2][2];
	for(int i = 0; i < 1024; i++)
		dist[i][0] = dist[i][1] = 0x3f3f3f3f;
	queue<int> Q, S;
	Q.push(st), S.push(0);
	dist[st][0] = 0, prex[st][0][0] = -1;
	while(!Q.empty()) {
		int u = Q.front(), s = S.front();
		Q.pop(), S.pop();
		used[u][s] = 0;
		for(int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			if(dist[v][0] > dist[u][s] + 1) {
				dist[v][0] = dist[u][s] + 1;
				prex[v][0][0] = u, prex[v][0][1] = s;
				if(!used[v][0]) {
					used[v][0] = 1, Q.push(v), S.push(0);
				}
			}
		}
		int cost = (s == 1) ? 0 : 3;
		for(int i = 0; i < g2[u].size(); i++) {
			int v = g2[u][i];
			if(dist[v][1] > dist[u][s] + cost) {
				dist[v][1] = dist[u][s] + cost;
				
				if(cost == 0)
					prex[v][1][0] = prex[u][s][0], prex[v][1][1] = prex[u][s][1];
				else
					prex[v][1][0] = u, prex[v][1][1] = s;
				if(!used[v][1]) {
					used[v][1] = 1, Q.push(v), S.push(1);
				}
			}
		}
	}
	printf("%3d: ", min(dist[ed][0], dist[ed][1]));
	
	int r = -1, a = -1, s, mm = ed;
	if(dist[ed][0] <= dist[ed][1])
		s = 0;
	else
		s = 1;
	do {
		int nr, na;
		reverse_node(mm, nr, na);
		if(nr != r) {
			if(mm != ed)	printf("=");
			printf("%c%c", nr, na);
		} else {
			printf("%c", na);
		}
		int om = mm;
		mm = prex[om][s][0], s = prex[om][s][1];
		r = nr, a = na;
	} while(mm != -1);
	puts("");
}
int main() {
	char line[1024];
	for(int n; scanf("%d", &n) == 1;) {
		for(int i = 0; i < 1024; i++)
			g[i].clear(), g2[i].clear();
		while(n--) {
			scanf("%s", &line);
			int r = line[0], preX;
			preX = trans_node(r, line[2]);
			for(int i = 3; line[i]; i++) {
				if(line[i] != '=') {
					int x = trans_node(r, line[i]);
					int y = preX;
					g[x].push_back(y);
					g[y].push_back(x);
					preX = x;
				} else {
					int x = trans_node(line[i+1], line[i+2]);
					int y = preX;
					g2[x].push_back(y);
					g2[y].push_back(x);
					i += 2;
				}
			}
		}
		while(scanf("%s", line) == 1 && line[0] != '#') {
			int x = trans_node(line[0], line[1]);
			int y = trans_node(line[2], line[3]);
			spfa(y, x);
		}
	}
	return 0;
}
/*
4
A:fgmpnxzabjd=Dbf
D:b=Adac=Ccf
B:acd=Azefg=Cbh
C:bac
AgAa
AbBh
BhDf
#
5 
A:ab=Bbcdefghijk 
B:abc=Ajdef=Cb 
C:ab 
D:cd=Eg 
E:fg=Bf 
AaAk 
AcAk 
AbBb 
BaDd 
# 
*/
Read More +
解題區►解題區 - UVa

UVa 172 - Calculator Language

Problem

Calculator Language (CL) supports assignment, positive and negative integers and simple arithmetic. The allowable characters in a CL statement are thus:

All operators have the same precedence and are right associative, thus 15 - 8 - 3 = 15 - (8 - 3) = 10. As one would expect, brackets will force the expression within them to be evaluated first. Brackets may be nested arbitrarily deeply. An expression never has two operators next to each other (even if separated by a bracket), an assignment operator is always immediately preceded by a variable and the leftmost operator on a line is always an assignment. For readability, spaces may be freely inserted into an expression, except between a negative sign and a number. A negative sign will not appear before a variable. All variables are initialised to zero (0) and retain their values until changed explicitly.

Write a program that will accept and evaluate expressions written in this language. Each expression occupies one line and contains at least one assignment operator, and maybe more.

Input

Input will consist of a series of lines, each line containing a correct CL expression. No line will be longer than 100 characters. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines, one for each line of the input. Each line will consist of a list of the final values of all variables whose value changes as a result of the evaluation of that expression. If more than one variable changes value, they should be listed in alphabetical order, separated by commas. If a variable changes value more than once in an expression, only the final value is output. A variable is said to change value if its value after the expression has been evaluated is different from its value before the expression was evaluated. If no variables change value, then print the message `No Change’. Follow the format shown below exactly.

Sample input

1
2
3
4
5
6
7
A = B = 4
C = (D = 2)*_2
C = D = 2 * _2
F = C - D
E = D * _10
Z = 10 / 3
#

Sample output

1
2
3
4
5
6
A = 4, B = 4
C = -4, D = 2
D = -4
No Change
E = 40
Z = 3

Solution

題目描述：

給一個六則運算，並且所有運算由右往左，也就是題目提及的 right associative，並且在每一個運算式之後輸出有改變值的變數結果。

題目解法：

要處理的問題相當多，按照一般的思路要做出 right associative 還不打緊，就像冪次的定義一樣，也就是把 stack 的嚴格遞增改成非嚴格遞增。

但是查閱討論區給定的數據後，如下所示

範例輸入

1
2
B=(A=1)+(A=2)
#

範例輸出

1
A = 1, B = 3

這表示著連括弧運算順序都是 right associative，這一點相當苦惱，於是最後建造 tree，然後先拜訪右子樹、再拜訪左子樹來解決這些問題。

中間誤把 No Change 寫成 No change，因此卡了不少 Wrong Answer。

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A = B = 4
B=B-6+B=100
C = (D = 2) * _2
C = D = 2 * _2
E = D * _10
F = 15 - 8 - 3
F = 15 - 8 + _3
F=1+F=F-1
A=((3))
Z=Y=X=A=B=C=1+D=E=F=G=2-H=K=J=I=L=M=O=N=P=Q=R=S=T=V=U=W=3
A=100/2
A=100/_2
B=(_1+A*2)/2
B=(1+A*_2)/2
A=(((1-2)*3)+4)
A=((1-(2*3))+4)
A=((1-2)*(3+4))
A=(1-(2*(3+4)))
A=1+2+1+1+1+1+1+1+1+1+1+1+1+1+1+11+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+3
#

AC Sample Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
A = 4, B = 4
B = -6
C = -4, D = 2
D = -4
E = 40
F = 10
No Change
No Change
A = 3
A = 0, B = 0, C = 0, D = -1, E = -1, F = -1, G = -1, H = 3, I = 3, J = 3, K = 3, L = 3, M = 3, N = 3, O = 3, P = 3, Q = 3, R = 3, S = 3, T = 3, U = 3, V = 3, W = 3
A = 50
A = -50
B = -50
B = 50
A = 1
A = -1
A = -7
A = -13
A = 62

一開始還在想為什麼當 B = 4 時，B=B-6+B=100 會產出 B = -6，由右往左運算。

  • B = 100
  • 6 + B = 106
  • B - (6 + B) = 100 - 106 = -6
  • B assign(=) -6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
// Accepted
#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
#include <ctype.h>
#include <iostream>
#include <sstream>
using namespace std;
int priority_op(char c) {
    switch(c) {
        case '(':return -1;
        case '=':return 3;
        case '+': case '-':return 1;
        case '*': case '/':return 2;
    }
    puts("ERROR");
    return -1;
}
void trans(char infix[], char buffer[]) {
    int len = strlen(infix);
    char *ptr = buffer;
    stack<char> op;
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
        if(infix[i] == '_' || isdigit(infix[i]) || isalpha(infix[i])) {
        	while(infix[i] == '_' || isdigit(infix[i]) || isalpha(infix[i])) {
        		if(infix[i] == '_')
        			sprintf(ptr, "-");
        		else
            		sprintf(ptr, "%c", infix[i]);	
            	while(*ptr)    ptr++;
            	i++;
        	}
            sprintf(ptr, " ");	
            while(*ptr)    ptr++;
        	i--;
        }else {
        	if(infix[i] == ' ')	continue;
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.pop();
            } else {
                if(infix[i] != '(') {
                	if(infix[i] == '=') {
                		while(!op.empty() && priority_op(op.top()) > priority_op(infix[i])) {
                    		sprintf(ptr, "%c ", op.top()), op.pop();
                    		while(*ptr) ptr++;
                		}
                	} else {
                		while(!op.empty() && priority_op(op.top()) > priority_op(infix[i]) && op.top() != '=') {
                    		sprintf(ptr, "%c ", op.top()), op.pop();
                    		while(*ptr) ptr++;
                		}
                	}
                }
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
}
int Variable[26] = {}, oldVal[26] = {};
string to_string(int number) {
   stringstream ss;//create a stringstream
   ss << number;//add number to the stream
   return ss.str();//return a string with the contents of the stream
}
struct TreeNode {
	string 	A, B, OP;
	int 	l, r;
	TreeNode(string a="", string b="", string op=""):
		A(a), B(b), OP(op) {}
};
TreeNode node[1024];
int runTree(int label) {
	string 	A = node[label].A;
	string	B = node[label].B;
	int 	a, b;
	if(node[label].OP == "LEAF") {
		if(isalpha(A[0]))
           	a = Variable[A[0] - 'A'];
        else
           	a = atoi(A.c_str());
		return a;	
	}
	b = runTree(node[label].r);
	a = runTree(node[label].l);
//	printf("%d %d\n", a, b);
	//cout << A << ", " << B << ", " << node[label].OP << endl;
	switch(node[label].OP[0]) {
    	case '+': a = a + b; break;
        case '-': a = a - b; break;
        case '*': a = a * b; break;
        case '/': a = a / b; break;
        case '=': 
        	a = b;
        	if(isalpha(A[0])) {
        		Variable[A[0] - 'A'] = a;
        		//cout << A << " -- " << a << endl;
        	}
        	break;
    }
    return a;
}
void buildTree(char postfix[]) {
	
	stringstream	sin(postfix);
	string 			token, A, B;
    stack<string>	stk;
    stack<int>		nodeLabel;
    int 			treeSize = 0;
    
    while(sin >> token) {
    	if(isalpha(token[0])) {
    		stk.push(token);
    		nodeLabel.push(treeSize);
    		node[treeSize++] = TreeNode(token, "", "LEAF");
    		
    	} else if(isdigit(token[token.length() - 1])) {
    		stk.push(token);
    		nodeLabel.push(treeSize);
    		node[treeSize++] = TreeNode(token, "", "LEAF");
    	} else {
			B = stk.top(), stk.pop();
            A = stk.top(), stk.pop();
            int a, b;
            b = nodeLabel.top(), nodeLabel.pop();
            a = nodeLabel.top(), nodeLabel.pop();
            nodeLabel.push(treeSize);
            node[treeSize] = TreeNode(A, B, token);
            node[treeSize].l = a, node[treeSize].r = b;
            treeSize++;
            stk.push("INNER");
    	}
    }
    runTree(nodeLabel.top());
}
char infix[262144], postfix[262144];
int main() {
    while(gets(infix) && infix[0] != '#') {
        trans(infix, postfix);
        
        for(int i = 0; i < 26; i++)
        	oldVal[i] = Variable[i];
        	
        buildTree(postfix);
        
        int f = 0;
        for(int i = 0; i < 26; i++) {
        	if(oldVal[i] != Variable[i]) {
        		if(f)	printf(", ");
        		f = 1;
        		printf("%c = %d", i + 'A', Variable[i]);
        	}
        }
        if(f == 0)
        	puts("No Change");
        else
        	puts("");
        //printf("%s\n", postfix);
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 177 - Paper Folding

Problem

If a large sheet of paper is folded in half, then in half again, etc, with all the folds parallel, then opened up flat, there are a series of parallel creases, some pointing up and some down, dividing the paper into fractions of the original length. If the paper is only opened half-way'' up, so every crease forms a 90 degree angle, then (viewed end-on) it forms adragon curve’’. For example, if four successive folds are made, then the following curve is seen (note that it does not cross itself, but two corners touch):

UVa 177

Write a program to draw the curve which appears after N folds. The exact specification of the curve is as follows:

  • The paper starts flat, with the ``start edge’’ on the left, looking at it from above.
  • The right half is folded over so it lies on top of the left half, then the right half of the new double sheet is folded on top of the left, to form a 4-thick sheet, and so on, for N folds.
  • Then every fold is opened from a 180 degree bend to a 90 degree bend.
  • Finally the bottom edge of the paper is viewed end-on to see the dragon curve.

From this view, the only unchanged part of the original paper is the piece containing the start edge, and this piece will be horizontal, with the start edge on the left. This uniquely defines the curve. In the above picture, the start edge is the left end of the rightmost bottom horizontal piece (marked s). Horizontal pieces are to be displayed with the underscore character _, and vertical pieces with the | character.

Input

Input will consist of a series of lines, each with a single number N (1 <= N <= 13). The end of the input will be marked by a line containing a zero.

Output

Output will consist of a series of dragon curves, one for each value of N in the input. Your picture must be shifted as far left, and as high as possible. Note that for large N, the picture will be greater than 80 characters wide, so it will look messy on the screen. The pattern for each different number of folds is terminated by a line containing a single `^’.

Sample input

1
2
3
4
2
4
1
0

Sample output

1
2
3
4
5
6
7
8
9
10
|_
 _|
^
   _   _
  |_|_| |_
   _|    _|
|_|
^
_|
^

Solution

題目描述：

將一個長條紙水平擺放，接著將右手邊的紙摺疊到左上邊的紙上面，接著又再重複做幾次，直到 N 次 ( 若將其攤平則會有 2N 個折疊區塊 )。摺疊完後，依序將其攤開，攤開的方式為：將前一次摺疊的 (想像與 s 重疊的那一片) 從 180 度旋轉到 90 度位置，依序攤開 N 次。

題目解法：

這一題就是題目理解麻煩點，但是不難發現肯定是有遞迴需要處理的。

假設我們定義展開的每一根，分別為往上下左右的射線，會發現其對應關係，新的尾會跟舊的頭對照，依序對照到中間部分。

最後得到關係

  • 上 變成 左
  • 下 變成 右
  • 左 變成 下
  • 右 變成 上

輸出處理方面，利用一個 map 結構去完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h> 
#include <map>
#include <set>
#include <algorithm>
using namespace std;
map<int, set< pair<int, int> > > P;
void build(int n) {
	int A[1<<15];
	// 0 up, 1 down, 2 left, 3 right
	int trans[] = {2, 3, 1, 0};
	int m = 1;
	A[0] = 3;
	for(int i = 1; i <= n; i++) {
		for(int j = m - 1, k = m; j >= 0; j--, k++)
			A[k] = trans[A[j]];
		m = m << 1;
	}
	int x = -1, y = 0, px = 0, py = 0;
	P.clear();
	for(int i = 0; i < m; i++) {
		if(A[i] == 0)		x = px<<1, y = py;
		else if(A[i] == 1)	x = px<<1, y = py - 1;
		else if(A[i] == 2)	x = (px<<1)-1, y = py;
		else				x = (px<<1)+1, y = py;
		//printf("%d %d %d - %d %d\n", px, py, A[i], x, y);
		if(A[i] == 0) {
			P[y].insert(make_pair(x, 0));
		} else if(A[i] == 1) {
			P[y].insert(make_pair(x, 1));
		} else if(A[i] == 2) {
			P[y].insert(make_pair(x, 2));
		} else {
			P[y].insert(make_pair(x, 3));
		}
		if(A[i] == 0)		py++;
		else if(A[i] == 1)	py--;
		else if(A[i] == 2)	px--;
		else				px++;
	}
}
int main() {
	for(int n; scanf("%d", &n) == 1 && n; ) {
		build(n);
		int mxy = -0x3f3f3f3f, mnx = 0x3f3f3f3f;
		for(map<int, set< pair<int, int> > >::iterator it = P.begin();
		it != P.end(); it++) {
			mxy = max(mxy, it->first);
			for(set< pair<int, int> >::iterator jt = it->second.begin();
				jt != it->second.end(); jt++) {
				mnx = min(mnx, jt->first);
			}
		}
		for(map<int, set< pair<int, int> > >::reverse_iterator it = P.rbegin();
		it != P.rend(); it++) {
			int i = mnx;
			for(set< pair<int, int> >::iterator jt = it->second.begin();
				jt != it->second.end(); jt++) {
				while(i < jt->first)	putchar(' '), i++;
				i++;
				if(jt->second == 0 || jt->second == 1)
					putchar('|');
				else
					putchar('_');
			}
			puts("");
		}
		//printf("%d %d\n", mxy, mnx);
		puts("^");
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 132 - Bumpy Objects

Problem

132img1

Consider objects such as these. They are polygons, specified by the coordinates of a centre of mass and their vertices. In the figure, centres of mass are shown as black squares. The vertices will be numbered consecutively anti-clockwise as shown.

An object can be rotated to stand stably if two vertices can be found that can be joined by a straight line that does not intersect the object, and, when this line is horizontal, the centre of mass lies above the line and strictly between its endpoints. There are typically many stable positions and each is defined by one of these lines known as its base line. A base line, and its associated stable position, is identified by the highest numbered vertex touched by that line.

Write a program that will determine the stable position that has the lowest numbered base line. Thus for the above objects, the desired base lines would be 6 for object 1, 6 for object 2 and 2 for the square. You may assume that the objects are possible, that is they will be represented as non self-intersecting polygons, although they may well be concave.

Input and Output

Successive lines of a data set will contain: a string of less than 20 characters identifying the object; the coordinates of the centre of mass; and the coordinates of successive points terminated by two zeroes (0 0), on one or more lines as necessary. There may be successive data sets (objects). The end of data will be defined by the string ‘#’.

Output will consist of the identification string followed by the number of the relevant base line.

Sample input

1
2
3
4
5
6
7
Object2
4 3
3 2  5 2  6 1  7 1  6 3  4 7  1 1  2 1  0 0
Square 
2 2
1 1  3 1  3 3  1 3  0 0
#

Sample output

1
2
Object2             6
Square              2

Solution

題目描述：

給定一個多邊形，將會給予這個多邊形的質心和頂點。在圖中，質心表示成黑色正方形的小點，而頂點將會使用連續編號逆時針給點。

多邊形可以藉由旋轉放置於水平，並且穩定立起。這時可以發現，會有兩個頂點拉起的水平線，並且質心會位於水平線上的兩個端點之間。

通常一個多邊形具有多個這種水平放置方法，對於一個水平放置方式，可以用在水平線上最大編號的頂點描述。

請輸出最小水平放置的編號。

題目解法：

對多邊形著手凸包計算，這裡使用單調鍊去完成凸包。接著利用內積找到質心是否在兩個水平線端點 (segment 的上方) 之間。

可以利用外積判斷是否在線 (line) 上。

好好利用數學運算，將可以在簡短的代碼完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
	Pt operator-(const Pt &a) const {
		Pt ret;
		ret.x = x - a.x;
		ret.y = y - a.y;
        return ret;
    }
};
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
	return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
	return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
	return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m - 1;
}
int main() {
	char testcase[105];
	Pt P[1024], CH[1024], IN[1024];
	while(scanf("%s", testcase) == 1) {
		if(!strcmp(testcase, "#"))
			break;
		double 	x, y;
		int 	n = 0, m;
		Pt mc;
		scanf("%lf %lf", &mc.x, &mc.y);
		while(scanf("%lf %lf", &x, &y) == 2) {
			if(x == 0 && y == 0)
				break;
			IN[n] = P[n] = Pt(x, y);
			n++;
		}
		m = monotone(n, P, CH);
		int ret = 0x3f3f3f3f;
		for(int i = 0, j = m - 1; i < m; j = i++) {
			if(between(CH[i], CH[j], mc)) {
				int mn = 0;
				for(int k = 0; k < n; k++)
					if(onSeg(CH[i], CH[j], IN[k]))
						mn = max(mn, k);
				ret = min(ret, mn);
			}
		}
		printf("%-20s%d\n", testcase, ret + 1);
	}
	return 0;
}
Read More +
學校課程►作業系統

作業系統 multiprocess & multithread 作業

A 班程式要求

請使用所熟悉的程式開發環境設計單一行程產生子行程 ( Child Process ) 與 多執行緒 ( Multi-Thread) 的程式，意即完成下列傳統 for loop 之列印工作，將其改寫成多行程與多執行緒，由不同的行程與執行緒列印不同 i 值。

1
2
for (int i = 0; i < 10; i++)
	printf("output i = %d\n", i);

注意事項

  • 嚴禁從網路抄襲作業 。每份程式作業將被程式比對軟體檢查，一旦發現抄襲，該份作業以零分計，並且這學期作業系統作業成績以零分計。
  • 後略

這種作業不抄來抄去也難。但是作業格式不清楚，所以也有不同理解方式就是了。

開始動手

對於將 for 迴圈改寫，我們必須認知到幾項

  • 是否要按照順序輸出？
  • 平台 M$, Linux, or Max OS？

此篇假設目標是一模一樣的輸出

multiprocess

child process 屬於 multiprocess 中的一種方式。為什麼這麼說呢？multiprocess 只是要求一個 CPU 中有多個工作同時在進行，藉由排程器去進行工作分配。

先不管這些，要實作 child process 看起來只有走向 fork() 一途。而之前 inker 大神則是走非 child process 使用類似 ./nachos -e ../test/test1 -e ../test/test1 的方式去運行。

為了實作按照順序輸出，我們需要 process 共同擁有的 shared memory，這個 shared memory 將要紀錄原本 for 裡面的 i 值和一個 sem_t，來保證 process 和 process 之間不會同時搶先動作，sem_t 也許是不需要的，這裡留給實驗者去測試。

為了使輸出一致，在 fork() 完之後，使用 wait() 來等待所有子程序結束。這樣會造成當 for loop 需要跑 n 次，就會總共 n 個 process，也就是一整條鏈下去。

  • 思考 wait() 和 sem_t 都不是這麼必要？// 這個要看寫法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <semaphore.h>
#ifndef  MAP_ANONYMOUS
#ifdef  MAP_ANON
#define MAP_ANONYMOUS MAP_ANON
#endif
#endif
static int *glob_var;
static int n = 32;
int main(void)
{
    glob_var = (int *)mmap(NULL, sizeof *glob_var, PROT_READ | PROT_WRITE,
                    MAP_SHARED | MAP_ANONYMOUS, -1, 0);
    
    sem_t *sema = (sem_t *)mmap(NULL, sizeof(sema),
                       PROT_READ |PROT_WRITE,MAP_SHARED|MAP_ANONYMOUS,
                       -1, 0);
    sem_init(sema, 1, 0);
    *glob_var = 0;
    while (*glob_var < n) {
        sem_wait(sema);
        int pid = fork();
        int output = (*glob_var)++;
        if (output < n)
            printf("%d, pid = %d\n", output, pid);
        sem_post(sema);
        int wpid, status = 0;
        while ((wpid = wait(&status)) > 0)
        {
            //printf("Exit status of %d was %d (%s)\n", (int)wpid, status, (status > 0) ? "accept" : "reject");
        }
    }
    munmap(glob_var, sizeof *glob_var);
    return 0;
}

multithread

Thread 就相當簡單，因為它們是共用同一個記憶體區段，因此沒有 share memory 的問題。
雖然使用 sem_wait(&sem) 和 sem_post(&sem) 來保證區域內的代碼不會同時有多個 thread 在運行，但仍遇到 i = 0 同時在多個 Thread 噴出的情況，這一點百思不得其解，為了解決這一切問題，使用課本提到的 Producer–consumer problem 寫法。

希望能從代碼中看懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <semaphore.h>
#include <pthread.h>
int i = 0, n = 16;
int count = 0;
sem_t sem;
const int MAX_THREAD = 4;
void *Producer(void *arg) {
	for(int i = 0; i < n;) {
		sem_wait(&sem);
		if(count == 1) {
			sem_post(&sem);
			continue;
		}
		count++;
		// printf("\nProducer is :%d\n", count);
		sem_post(&sem);
		i++;
	}
	pthread_exit(NULL);
}
void *runPrint(void *arg) {
    int id = *((int *) arg);
    for (; i < n ;) {
        sem_wait(&sem);
        if (count == 0) {
            sem_post(&sem);
            continue;
        }
        count--;
        i++;
        printf("loop i = %d, thread id %d\n", i, id);
        sem_post(&sem);
    }
    pthread_exit(NULL);
}
int main() {
	pthread_t *threads;
    sem_init(&sem, 0, 0);
	threads = (pthread_t *) malloc(MAX_THREAD * sizeof(pthread_t));
    for (int i = 0; i < MAX_THREAD; i++) {
        int *p = (int *) malloc(sizeof(int));
        *p = i;
        pthread_create(&threads[i], NULL, runPrint, (void *)(p));
    }
    pthread_t producer;
    int *p = (int *) malloc(sizeof(int));
    *p = -1;
    pthread_create(&producer, NULL, Producer, (void *)(p));
    for (i = 0; i < MAX_THREAD; i++) {
        pthread_join(threads[i], NULL);
    }
    sem_destroy(&sem);
	return 0;
}

後記

代碼沒有寫得很完整，也就是能達到輸出相同且用符合需求，這一點是有很多漏洞的，前人也是鑽漏洞交作業的。相較之下，我們 B 班的作業略顯兇殘，但是網路上資料還真是少呢，雖然還是找地方抄和理解。

測試的時候，為了保證輸出是穩定的，記得得多測試幾次，並且把數字範圍作變調，當然能不能讓一個 create thread 跑完整個迴圈呢？畢竟加上 main thread 就算是 multithread？haha

執行

編譯

  • Mac OSX

      $ clang -pthread x.cpp -o x

  • Linux

      $ gcc -lpthread x.cpp -o x

    運行

  • Linux & Max OSX

      $ ./x

Mac 運行問題

1
2
3
4
5
#ifndef  MAP_ANONYMOUS
#ifdef  MAP_ANON
#define MAP_ANONYMOUS MAP_ANON
#endif
#endif

不知道為什麼 clang 中沒有定義 MAP_ANONYMOUS，增加上述代碼後正確運行。

其他作業

B 班程式作業 1
B 班程式作業 2

Read More +
學校課程►通識課程

當代消費文化與社會 (2)

母親節篇

  1. 請簡述母親節與消費文化的關聯性 ?
    母親節與消費文化原本是扯不上邊的，後來商人們藉由這些推銷的活動，給予不知道母親節要怎麼犒勞養育辛勞的兒女們一項消費選擇，因此提供了相關的優惠活動方便消費者，母親節就逐漸跟情人節送禮一樣的氣氛。
  2. 舉例說明母親節有哪些消費現象 ?
    相關女性用品優惠，對於餐飲業而言就是雙人、多人套餐，而觀光景點就是帶著母親出遊享優惠 … 等等。
  3. 您決定購買什麼禮物送媽媽及其理由 ?
    身為一個程序猿，買禮物卻沒有思路，寫卡片卻沒有語言，在這樣的情況下，按照自己最常做的事情下手設計，但最近還有其他程序要趕，大概是趕不上這個母親節專案了。

血色月灣


Youtube

在這場被隱藏的殺戮中，繼上次壽司造成的魚類問題，沒想到日本又在海洋造成了更大的傷害，不管是不是海豚，也許有人會因為海豚可愛而在這一次的血色海灣而保護它，在我們不喜歡的動物上，說不定也有類似的問題。

最令人訝異的是，即使在國際會議中，也有隱瞞事實的大人物在，果然要執行某些事情，不是會議或者是組織所為，而是來自個人的發起。這句話有額外的啟發，為了背後國民的飯碗或支持，這些代表人物不得不說謊的情境，假使一開始錯了，他們便會一直錯下去，這樣的情況令人相當惋惜。

海豚的確很有靈性，在他們受到如此的遭遇，難免會感受到如新世界中，那些因為外表被看成不同種的情況，而受到摧殘的可能，對於靈性的動物，在受到傷害，我們給予同情，在其他情況下則沒有這麼強烈的反應。

消費型科技商品

現在出門一定有 GPS 衛星導航的裝置，才能穿梭於大街小巷，這些裝置給我們相當大的便利，不用攜帶大量的地圖資訊出門，不會迷路、不用煩惱就可以輕鬆出門。

科技所帶來的便利，使得停下來思考的機會少了，也不會看看四周的景色，追求更快速地抵達目的地，目的地以外的機緣就越來越少了。比起問人，問機器更來得有信任感，這也表示著相信別人給的知識也不是那麼重要。根據新聞的研究報導，也許我們正在改變記憶方式，開始不擅長記繁瑣的事物，而開始擅長去哪裡找資料、如何使用資料。

因此，也常發生因衛星導航所造成的交通事故，被引導到錯誤地方或者是進入不合適的地點。這也反應使用者即使發現了不合理之處，最後仍相信訊息給的答案。假使衛星給了錯誤訊息，或者被惡意修改成錯誤訊息，很容易造就嚴重事故，我們已經被訓練得無法自己處理這些資訊。

也許老師會問我「那你認為到底要不要買衛星導航？」這一點還真的是要看需求，身為宅的人們不喜歡出門呢。

Read More +
學校課程►作業系統

向 NachOS 4.0 作業進發 (1)

關於 NachOS 4.0

作為教學用作業系統，需要實現簡單並且儘量縮小與實際作業系統之間的差距，所以我們採用 Nachos 作為作業系統課程的教學實踐平臺。Nachos 是美國加州大學伯克萊分校在作業系統課程中已多次使用的作業系統課程設計平臺，在美國很多大學中得到了應用，它在作業系統教學方面具有一下幾個突出的優點：

  • 採用通用虛擬機器
  • 簡單而易於擴展
  • 物件導向性
  • … 略

簡單地來說，就是一個模擬作業系統的軟體

安裝

課程頁面：http://networklab.csie.ncu.edu.tw/2014_os/osweb.html#download

  • Platform: Linux or Linux over VMware 
      RedHat Linux 9.0
    在 Ubuntu 上面運行無法
  • Install steps
    • Get NachOS-4.0
        wget ../nachos-4.0.tar.gz
    • Get Cross Compiler
        wget ../mips-decstation.linux-xgcc.tgz
    • Move Cross Compiler to /
        mv ./mips-decstation.linux-xgcc.tgz /
    • Untar Cross Compiler
         tar zxvf ./mips-decstation.linux-xgcc.tgz
    • Untar NachOS-4.0
        tar zxvf ./nachos-4.0.tar.gz
    • Make NachOS-4.0
        cd ./nachos-4.0/code
  make
    • Test if installation is succeeded
        cd ./userprog
  ./nachos -e ../test/test1
  ./nachos -e ../test/test2

預期運行結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Total threads number is 1
Thread ../test/test1 is executing.
Print integer:9
Print integer:8
Print integer:7
Print integer:6
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
                                                                                
Ticks: total 200, idle 66, system 40, user 94
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
Total threads number is 1
Thread ../test/test2 is executing.
Print integer:20
Print integer:21
Print integer:22
Print integer:23
Print integer:24
Print integer:25
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
Ticks: total 200, idle 32, system 40, user 128
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

作業階段

Multiprogramming

執行下述指令

1
./nachos –e ../test/test1 –e ../test/test2
test1.c
1
2
3
4
5
6
#include "syscall.h"
main() {
	int n;
	for (n=9;n>5;n--)
		PrintInt(n);
}
test2.c
1
2
3
4
5
6
7
#include "syscall.h"
main() {
    int n;
    for (n=20;n<=25;n++)
        PrintInt(n);
}

在開始動工前，發現在 Multithread 操作會有錯誤，test1 程序會遞減輸出，而 test2 程序會遞增輸出，但是根據運行結果，兩個程式都會遞增輸出。

目標運行結果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Total threads number is 2
Thread ../test/test1 is executing.
Thread ../test/test2 is executing.
Print integer:9
Print integer:8
Print integer:7
Print integer:20
Print integer:21
Print integer:22
Print integer:23
Print integer:24
Print integer:6
return value:0
Print integer:25
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
 
Ticks: total 300, idle 8, system 70, user 222
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
  • 為什麼兩個程式都會遞增輸出？
    明顯地是兩個程式匯入時，操作到相同區域的 code segment。如果發現各別遞增和遞減，但是輸出 n 的結果錯誤，則可以想到是 context-switch 上發生問題。

解決

需要為 physical address 做標記，這個 physical address 就是在 main memory 裡面的位置。而每一個 process 都會有一個 AddrSpace，然後紀錄 logical address 所對應在 physical address，也就是 pageTable 對應到 pageTable[i].physicalPage。

也就是說，當要執行 process 某一頁的程序，則將會去找 pageTable 所對應的 physicalPage，然後去運行。在作業一開始給的代碼中，會發現所有程序的 physicalPage 都共用，如此一來當然會執行到同一份 code。

首先，我們需要一個全局的標記，來記錄 main memory page 的情況。

usrprog/addrspace.h
1
2
3
4
5
6
7
class AddrSpace {
  public:
	...
    static bool usedPhyPage[NumPhysPages];
  private:
	...
};

接著，在 addrspace.cc 宣告實體，並且初始化是 0，表示全部都還沒有用過。

usrprog/addrspace.cc
1
2
3
4
5
6
7
8
#include "copyright.h"
#include "main.h"
#include "addrspace.h"
#include "machine.h"
#include "noff.h"
	...
bool AddrSpace::usedPhyPage[NumPhysPages] = {0};
	...

當 process 執行成功後，將會釋放資源。此時將要把標記使用的 page 設回未使用。

usrprog/addrspace.cc
1
2
3
4
5
6
AddrSpace::~AddrSpace()
{
	for(int i = 0; i < numPages; i++)
		AddrSpace::usedPhyPage[pageTable[i].physicalPage] = false;
   delete pageTable;
}

最後，就是稍微麻煩的地方，當將程序載入記憶體時，要去填入 pageTable[] 對應的 physicalPage，這裡使用線性時間去搜索第一個未使用的 page 進行填入。

載入確定後，便要開始執行，執行的時候要去算程序進入點，進入點的位置即是 main memory address。

mainMemory[pageTable[noffH.code.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]

首先算出第幾頁，然後乘上 PageSize 就是 page base，而 page offset 則是 code.address mod PageSize。

最後，page base + page offset 就是我們所需要的程序進入點。

usrprog/addrspace.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
bool AddrSpace::Load(char *fileName) {
    OpenFile *executable = kernel->fileSystem->Open(fileName);
    NoffHeader noffH;
    unsigned int size;
    if (executable == NULL) {
	cerr << "Unable to open file " << fileName << "\n";
	return FALSE;
    }
    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) && 
		(WordToHost(noffH.noffMagic) == NOFFMAGIC))
    	SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);
// how big is address space?
    size = noffH.code.size + noffH.initData.size + noffH.uninitData.size 
			+ UserStackSize;	// we need to increase the size
						// to leave room for the stack
    numPages = divRoundUp(size, PageSize);
//	cout << "number of pages of " << fileName<< " is "<< numPages << endl;
// morris add
	pageTable = new TranslationEntry[numPages];
	for(unsigned int i = 0, j = 0; i < numPages; i++) {
		pageTable[i].virtualPage = i;
		while(j < NumPhysPages && AddrSpace::usedPhyPage[j] == true)
			j++;
		AddrSpace::usedPhyPage[j] = true;
		pageTable[i].physicalPage = j;
		pageTable[i].valid = true;
		pageTable[i].use = false;
		pageTable[i].dirty = false;
		pageTable[i].readOnly = false;
	}
// end morris add
    size = numPages * PageSize;
    ASSERT(numPages <= NumPhysPages);		// check we're not trying
						// to run anything too big --
						// at least until we have
						// virtual memory
    DEBUG(dbgAddr, "Initializing address space: " << numPages << ", " << size);
// then, copy in the code and data segments into memory
	if (noffH.code.size > 0) {
        DEBUG(dbgAddr, "Initializing code segment.");
	DEBUG(dbgAddr, noffH.code.virtualAddr << ", " << noffH.code.size);
// morris add
        	executable->ReadAt(
		&(kernel->machine->mainMemory[pageTable[noffH.code.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]), 
			noffH.code.size, noffH.code.inFileAddr);
// end morris add
    }
	if (noffH.initData.size > 0) {
        DEBUG(dbgAddr, "Initializing data segment.");
	DEBUG(dbgAddr, noffH.initData.virtualAddr << ", " << noffH.initData.size);
// morris add
        executable->ReadAt(
		&(kernel->machine->mainMemory[pageTable[noffH.initData.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]),
			noffH.initData.size, noffH.initData.inFileAddr);
// end morris add
    }
    delete executable;			// close file
    return TRUE;			// success
}

Sleep() System call

撰寫自己的 Sleep function，將該 Thread 進入休眠。

測試檔案

與一開始的 test1.c 很像，這裡先做個簡單測試。

/code/test/sleep.c
1
2
3
4
5
6
7
8
9
#include "syscall.h"
main() {
	int i;
	for(i = 0; i < 5; i++) {
		Sleep(10000000);
		PrintInt(50);
	}
	return 0;
}

因為整個測試檔案是要能在 nachOS 上面跑，所以不能使用一般的編譯方式？所以把這些訊息寫入 Makefile 中，之後下 $ make 產出 sleep 即可。
/code/test/Makefile
1
2
3
4
5
6
7
...
all: halt shell matmult sort test1 test2 sleep
...
sleep: sleep.o start.o
	$(LD) $(LDFLAGS) start.o sleep.o -o sleep.coff
	../bin/coff2noff sleep.coff sleep
...

> 如果無法在 /code/test 下 $ make 順利產出，則請參照 其他指令 ，將原本下載的 mips-decstation.linux-xgcc.gz 解壓縮產生的 /usr 移動到正確位置。

### 解決 ###

首先，要模仿 PrintInt()，找到切入的宣告位置。努力地尾隨前人。

/code/userprog/syscall.h
1
2
3
4
5
6
7
...
#define SC_PrintInt	11
#define SC_Sleep	12
...
void PrintInt(int number);	//my System Call
void Sleep(int number);         // morris add
...

接著，找一下 ASM。
以下部分就不得而知了，為什麼會出現在 /code/test 目錄下。

/code/test/start.s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
	...
PrintInt:
	addiu   $2,$0,SC_PrintInt
	syscall
	j       $31
	.end    PrintInt
	.globl  Sleep
	.ent	Sleep
Sleep:
	addiu   $2,$0,SC_Sleep
	syscall
	j	$31
	.end	Sleep
	...

最後，確定 nachOS 會處理我們的例外操作。

/code/userprog/exception.cc
1
2
3
4
5
6
7
8
9
10
11
	...
case SC_PrintInt:
	val=kernel->machine->ReadRegister(4);
	cout << "Print integer:" << val << endl;
	return;
case SC_Sleep:
	val=kernel->machine->ReadRegister(4);
	cout << "Sleep Time " << val << "(ms) " << endl;
	kernel->alarm->WaitUntil(val);
	return;
	...

到這裡需要喘口氣，剛找了一陣子的代碼。接著才是重頭戲，因為你看到了 kernel->alarm->WaitUntil(val); 出現了。沒錯！我們需要撰寫那邊的代碼。

既然 kernel 存有 alarm，也就是說每隔固定一段間，就會呼叫 Alarm::CallBack()，因此，對於這個鬧鐘來個累加器 Bedroom::_current_interrupt，全局去記數，當作毫秒 (ms) 看待就可以，每加一次就相當於過了 1 毫秒 (ms)。

假設現在某一個 time = _current_interrupt 呼叫 Sleep(x) 後，將 (Thread address, _current_interrupt + x) 丟入 List，則期望在 _current_interrupt + x 的時候甦醒。因此，每當 _current_interrupt++ 就去檢查 List 中，誰的預期時間小於 _current_interrupt，就將其從 List 中清除。

這裡先不考慮 _current_interrupt Overflow 的問題，根據電腦效率，可能在 5 ~ 10 秒內就發生一次，此時會造成所有 Thread 沉眠很久。若察覺 Sleep 太久，則是發生 Overflow。

  • 當有程序呼叫 Sleep() 時，會呼叫 WaitUntil()，然後將其丟入 Bedroom 安眠。
  • 然後在 CallBlack() 被呼叫時，來去 Bedroom 檢查誰該醒來了。
/code/threads/alarm.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include "copyright.h"
#include "utility.h"
#include "callback.h"
#include "timer.h"
#include <list>
#include "thread.h"
class Bedroom {
    public:
        Bedroom():_current_interrupt(0) {};
        void PutToBed(Thread *t, int x);
	bool MorningCall();
	bool IsEmpty();
    private:
        class Bed {
            public:
                Bed(Thread* t, int x):
                    sleeper(t), when(x) {};
                Thread* sleeper;
                int when;
        };
	
	int _current_interrupt;
	std::list<Bed> _beds;
};
// The following class defines a software alarm clock. 
class Alarm : public CallBackObj {
  public:
    Alarm(bool doRandomYield);	// Initialize the timer, and callback 
				// to "toCall" every time slice.
    ~Alarm() { delete timer; }
    
    void WaitUntil(int x);	// suspend execution until time > now + x
  private:
    Timer *timer;		// the hardware timer device
    Bedroom _bedroom;
    void CallBack();		// called when the hardware
				// timer generates an interrupt
};

確定有哪些 method 就可以開始實作了。

/code/threads/alarm.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void Alarm::CallBack() {
    Interrupt *interrupt = kernel->interrupt;
    MachineStatus status = interrupt->getStatus();
    bool woken = _bedroom.MorningCall();
    
    if (status == IdleMode && !woken && _bedroom.IsEmpty()) {// is it time to quit?
        if (!interrupt->AnyFutureInterrupts()) {
	    timer->Disable();	// turn off the timer
	}
    } else {			// there's someone to preempt
	interrupt->YieldOnReturn();
    }
}
void Alarm::WaitUntil(int x) {
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    Thread* t = kernel->currentThread;
    cout << "Alarm::WaitUntil go sleep" << endl;
    _bedroom.PutToBed(t, x);
    kernel->interrupt->SetLevel(oldLevel);
}
bool Bedroom::IsEmpty() {
    return _beds.size() == 0;
}
void Bedroom::PutToBed(Thread*t, int x) {
    ASSERT(kernel->interrupt->getLevel() == IntOff);
    _beds.push_back(Bed(t, _current_interrupt + x));
    t->Sleep(false);
}
bool Bedroom::MorningCall() {
    bool woken = false;
    _current_interrupt ++;
    for(std::list<Bed>::iterator it = _beds.begin(); 
        it != _beds.end(); ) {
        if(_current_interrupt >= it->when) {
            woken = true;
            cout << "Bedroom::MorningCall Thread woken" << endl;
            kernel->scheduler->ReadyToRun(it->sleeper);
            it = _beds.erase(it);
        } else {
            it++;
        }
    }
    return woken;
}

到這裡我們就完成 Sleep() 製作。

在下一階段，將要加入排程的製作。

Scheduling

目標完成 SJF, RR, FIFO。
請參閱 “向 NachOS 4.0 作業進發 (2)”

其他指令

  • 打包轉移 // 交作業前，將檔案包出傳送，此指令不是壓縮用途
1
$ tar cvf FileName.tar DirName
  • 複製資料夾 // 將 nachos gcc library 搬移至 /usr/local/nachos ...
1
$ cp -a DirName TARGET_PATH
  • 轉移至 root 權限 // 如果指令權限不夠，需要下達此指令。
1
$ su

備忘

  • 網路上有幾個 Java 版本的 NachOS，架構稍微不同，如果發現文章說明有點怪怪的，請看一下他是用 JAVA 版本還是 C++ 版本。
  • 至於怎麼將檔案從 Red Hat，這有點惱人，可以想辦法安裝其他瀏覽器，然後開 e-mail 送出，或者使用 terminal 上的 wget 安裝 … 一堆辦法。最後我自己用 nodejs 寫一個簡單的 upload server 傳出來。

代碼下載

Github

Read More +
解題區►解題區 - UVa

UVa 134 - Loglan-A Logical Language

Problem

Loglan is a synthetic speakable language designed to test some of the fundamental problems of linguistics, such as the Sapir Whorf hypothesis. It is syntactically unambiguous, culturally neutral and metaphysically parsimonious. What follows is a gross over-simplification of an already very small grammar of some 200 rules.

Loglan sentences consist of a series of words and names, separated by spaces, and are terminated by a period (.). Loglan words all end with a vowel; names, which are derived extra-linguistically, end with a consonant. Loglan words are divided into two classes—little words which specify the structure of a sentence, and predicates which have the form CCVCV or CVCCV where C represents a consonant and V represents a vowel (see examples later).

The subset of Loglan that we are considering uses the following grammar:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
A             →  a | e | i | o | u
MOD           →  ga | ge | gi | go | gu
BA            →  ba | be | bi | bo | bu
DA            →  da | de | di | do | du
LA            →  la | le | li | lo | lu
NAM           →  {all names}
PREDA         →  {all predicates}
<sentence>    →  <statement> | <predclaim>
<predclaim>   →  <predname> BA <preds> | DA <preds>
<preds>       →  <predstring> | <preds> A <predstring>
<predname>    →  LA <predstring> | NAM
<predstring>  →  PREDA | <predstring> PREDA
<statement>   →  <predname> <verbpred> <predname> | <predname> <verbpred>
<verbpred>    →  MOD <predstring>

Write a program that will read a succession of strings and determine whether or not they are correctly formed Loglan sentences.

Input and Output

Each Loglan sentence will start on a new line and will be terminated by a period (.). The sentence may occupy more than one line and words may be separated by more than one whitespace character. The input will be terminated by a line containing a single `#’. You can assume that all words will be correctly formed.

Output will consist of one line for each sentence containing either Good' orBad!’.

Sample input

1
2
3
4
la mutce bunbo mrenu bi ditca.
la fumna bi le mrenu.
djan ga vedma le negro ketpi.
#

Sample output

1
2
3
Good
Bad!
Good

Solution

其實這一題有比較好的解法，但是在正在學編譯器，因此把 LL(1) parser 運用在此題
，所以代碼會稍微長一點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<sentence>    ->  <common_pre>
<sentence>    ->  DA <preds>
<common_pre>  ->  <predname> <suffix>
<suffix>      ->  <predclaim>
<suffix>      ->  <statement>
<predclaim>   ->  BA <preds>
<preds>       ->  <preds_head> <preds_tail>
<preds_head>  ->  <predstring>
<preds_tail>  ->  A <predstring> <preds_tail>
<preds_tail>  ->  l
<predname>    ->  LA <predstring>
<predname>    ->  NAM
<predstring>  ->  PREDA <predstr_tail>
<predstr_tail> -> PREDA <predstr_tail>
<predstr_tail> -> l
<statement>   ->  <verbpred> <statement_s>
<statement_s> ->  <predname>
<statement_s> ->  l
<verbpred>    ->  MOD <predstring>

為了要符合 LL(1) 的形式，要想辦法將 Grammar 符合規格，也就是每一條 production rule 的 predict set 不會有模稜兩個的情況，也就是說當我看到某個 non-terminal 在 stack 上，在去看下一個 token，然後可以對於 (non-terminal, token) 只找到一條規則去匹配。

predict set 是根據每一條 production rule 所產生的，也就是說這個推論可以產生的第一個 token 是什麼，假使有相同的前綴時，則必須拉出做調整。// 因為這將會造成模稜兩可的情況。

遇到

1
2
A -> BCx
A -> BCy

應調整成

1
2
3
A -> BCW
W -> x
W -> y

在 parsing 問題上，應避免替換的無限迴圈。
遇到

1
2
3
A -> AC
A -> X
A -> Y

應調整成

1
2
3
4
5
A -> WD
D -> CD
D -> lambda
W -> X
W -> Y

發現對照課本的 parsing function 撰寫起來才發現有些不完善的地方，對於 lldriver() 會沒有辦法應對輸入結束，要吐出 lambda 的問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
#include <stdio.h> 
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <ctype.h>
#include <assert.h>
using namespace std;
class Production {
	public:
		string 			LHS;
		vector<string> 	RHS;
		int 			label;
		
		Production(string L = "", vector<string> R = vector<string>()) {
			LHS = L;
			RHS = R;
		}
		
		void print() {
			printf("%s -> ", LHS.c_str());
			for(size_t i = 0; i < RHS.size(); i++)
				printf("%s", RHS[i].c_str());
		}
};
class Grammar {
	public:
		static const string 		lambda;
		string 						start_symbol;
		vector<Production> 			rules;
		map<string, set<string> > 	first_set;
		map<string, set<string> > 	follow_set;
		map<string, bool> 			derives_lambda;
		map<string, map<string, Production> >	lltable;
		
		map<string, bool> mark_lambda();
		void fill_first_set();
		void fill_follow_set();
		bool isNonterminal(string token);
		set<string> compute_first(vector<string> rhs);
		set<string> get_predict_set(Production p);
		void fill_lltable();
		void lldriver(queue<string> tokens);
};
const string Grammar::lambda("l");
set<string> Grammar::compute_first(vector<string> rhs) {
	set<string> result;
	size_t i;
	
	if(rhs.size() == 0 || rhs[0] == Grammar::lambda) {
		result.insert(Grammar::lambda);
	} else {
		result = first_set[rhs[0]];
		for(i = 1; i < rhs.size() && 
			first_set[rhs[i-1]].find(Grammar::lambda) != first_set[rhs[i-1]].end(); i++) {
			set<string> f = first_set[rhs[i]];
			f.erase(Grammar::lambda);
			result.insert(f.begin(), f.end());	
		}
		if(i == rhs.size() 
			&& first_set[rhs[i-1]].find(Grammar::lambda) != first_set[rhs[i-1]].end()) {
			result.insert(Grammar::lambda);
		} else {
			result.erase(Grammar::lambda);
		}
	}
	
	return result;
} 
/*
 * please call get_predict_set() after fill_follow_set() and fill_first_set()
 */
set<string> Grammar::get_predict_set(Production p) {
	set<string> result;
	set<string> rfirst;
	
	rfirst = compute_first(p.RHS);
	if(rfirst.find(Grammar::lambda) != rfirst.end()) {
		rfirst.erase(Grammar::lambda);
		result.insert(rfirst.begin(), rfirst.end());
		rfirst = follow_set[p.LHS];
		result.insert(rfirst.begin(), rfirst.end());
	} else {
		result.insert(rfirst.begin(), rfirst.end());
	}
	
	return result;
}
/*
 * 
 */
void Grammar::fill_lltable() {
	string		A; // nonterminal
	Production 	p;
	
	for(size_t i = 0; i < rules.size(); i++) {
		p = rules[i];
		A = p.LHS;
		set<string> predict_set = get_predict_set(p);
		
		for(set<string>::iterator it = predict_set.begin();
			it != predict_set.end(); it++) {
			assert(lltable[A].find(*it) == lltable[A].end());
			lltable[A][*it] = p;
		}
	}
	
}
bool Grammar::isNonterminal(string token) {
	
	if(token[0] == '<' && token[token.length() - 1] == '>')
		return true;
	return false;
}
map<string, bool> Grammar::mark_lambda() {
	bool 				rhs_derives_lambda;
	bool 				changes;
	Production 			p;
	
	derives_lambda.clear();
	
	/* initially, nothing is marked. */
	for(size_t i = 0; i < rules.size(); i++) {
		derives_lambda[rules[i].LHS] = false;
	}
	do {
		changes = false;
		for(size_t i = 0; i < rules.size(); i++) {
			p = rules[i];
			if(!derives_lambda[p.LHS]) {
				if(p.RHS.size() == 0 || p.RHS[0] == Grammar::lambda) {
					changes = derives_lambda[p.LHS] = true;
					continue;
				}
				/* does each part of RHS derive lambda ? */
				rhs_derives_lambda = derives_lambda[string(p.RHS[0])];
				for(size_t j = 1; j < p.RHS.size(); j++) {
					rhs_derives_lambda &= derives_lambda[p.RHS[j]];
				}
				if(rhs_derives_lambda) {
					changes = true;
					derives_lambda[p.LHS] = true;
				}
			}
		}
	} while(changes);
	return derives_lambda;
}
void Grammar::fill_first_set() {
	
	string 		A; // nonterminal
	string 		a; // terminal
	Production 	p;
	bool 		changes;
		
	mark_lambda();
	first_set.clear();
	
	for(size_t i = 0; i < rules.size(); i++) {
		A = rules[i].LHS;
		if(derives_lambda[A])
			first_set[A].insert(Grammar::lambda);
	}
	
	for(size_t i = 0; i < rules.size(); i++) {
		for(size_t j = 0; j < rules[i].RHS.size(); j++) {
			a = rules[i].RHS[j];
			if(!isNonterminal(a)) {
				if(a != Grammar::lambda)
					first_set[a].insert(a);
				if(j == 0) { // A -> aXX
					first_set[rules[i].LHS].insert(a);
				}
			}
		}
	}
	
	do {
		changes = false;
		for(size_t i = 0; i < rules.size(); i++) {
			p = rules[i];
			set<string> rfirst = compute_first(p.RHS);
			size_t oldsize = first_set[p.LHS].size();
			first_set[p.LHS].insert(rfirst.begin(), rfirst.end());
			size_t newsize = first_set[p.LHS].size();
			if(oldsize != newsize)
				changes = true;
		}
	} while(changes);
} 
void Grammar::fill_follow_set() {
	string 	A, B; // nonterminal
	Production 	p;
	bool 	changes;
	
	for(size_t i = 0; i < rules.size(); i++) {
		A = rules[i].LHS;
		follow_set[A].clear();
	}
	
	follow_set[start_symbol].insert(Grammar::lambda);
		
	do {
		changes = false;
		for(size_t i = 0; i < rules.size(); i++) {
			/* A -> a B b
			 * I.e. for each production and each occurrence
			 * of a nonterminal in its right-hand side. 
			 */
			p = rules[i];
			A = p.LHS;
			for(size_t j = 0; j < p.RHS.size(); j++) {
				B = p.RHS[j];
				if(isNonterminal(B)) {
					vector<string> beta(p.RHS.begin() + j + 1, p.RHS.end());
					set<string> rfirst = compute_first(beta);
					size_t oldsize = follow_set[B].size();
					
					if(rfirst.find(Grammar::lambda) == rfirst.end()) {
						follow_set[B].insert(rfirst.begin(), rfirst.end());	
					} else {
						rfirst.erase(Grammar::lambda);
						follow_set[B].insert(rfirst.begin(), rfirst.end());	
						rfirst = follow_set[A];
						follow_set[B].insert(rfirst.begin(), rfirst.end());
					}
					size_t newsize = follow_set[B].size();			
					if(oldsize != newsize)
						changes = true;
				}
			}
		}
	} while(changes);
}
void Grammar::lldriver(queue<string> tokens) {
	stack<string> 	stk;
	string 			X;
	string			a;
	Production		p;
	/* Push the Start Symbol onto an empty stack */
	stk.push(start_symbol);
	
	while(!stk.empty() && !tokens.empty()) {
		X = stk.top();
		a = tokens.front();
		// cout << X << " " << a << endl;
		if(isNonterminal(X) && lltable[X].find(a) != lltable[X].end()) {
			p = lltable[X][a];
			stk.pop();
			for(int i = p.RHS.size() - 1; i >= 0; i--) {
				if(p.RHS[i] == Grammar::lambda)
					continue;
				stk.push(p.RHS[i]);
			}
		} else if(X == a) {
			stk.pop();
			tokens.pop();
		} else if(lltable[X].find(Grammar::lambda) != lltable[X].end()) {
			stk.pop();
		} else {
			/* Process syntax error. */
			puts("Bad!");
			return;
		}
	}
	while(!stk.empty()) {
		X = stk.top();
		if(lltable[X].find(Grammar::lambda) != lltable[X].end())
			stk.pop();
		else
			break;
	}
	if(tokens.size() == 0 && stk.size() == 0)
		puts("Good");
	else
		puts("Bad!");
	return;
}
int aVowel(char c) {
	switch(c) {
		case 'a':case 'e':case 'i':case 'o':case 'u':
			return 1;
	}
	return 0;
}
string token2symbol(const string &str) {
    int n = str.length();
    if (!islower(str[n - 1]) || !aVowel(str[n - 1])) {
        return "NAM";
    }
    switch (n) {
    	case 1: return "A";
    	case 5:
        n = aVowel(str[4]);
        n |= ((aVowel(str[0]) << 4) | (aVowel(str[1]) << 3));
        n |= ((aVowel(str[2]) << 2) | (aVowel(str[3]) << 1));
        return (n == 5 || n == 9) ? "PREDA" : "UN";
    	case 2:
        	switch (str[0]) {
        		case 'g': return "MOD";
        		case 'b': return "BA";
        		case 'd': return "DA";
        		case 'l': return "LA";
        	}
    }
    return "UN";
}
void parsingProduction(string r, Grammar &g) {
	static int 		production_label = 0;
	stringstream 	sin(r);
	string 			lhs, foo;
	vector<string> 	tokens;
	sin >> lhs >> foo;
	while(sin >> foo)
		tokens.push_back(foo);
	Production p(lhs, tokens);
	p.label = ++production_label;
	g.rules.push_back(p);
} 
int main() {
	Grammar g;
	parsingProduction("<sentence>    ->  <common_pre>", g);
	parsingProduction("<sentence>    ->  DA <preds>", g);
	parsingProduction("<common_pre>  ->  <predname> <suffix>", g);
	parsingProduction("<suffix>      ->  <predclaim>", g);
	parsingProduction("<suffix>	  	 ->  <statement>", g);
	parsingProduction("<predclaim>   ->  BA <preds>", g);
	parsingProduction("<predclaim>   ->  DA <preds>", g);
	parsingProduction("<preds>       ->  <preds_head> <preds_tail>", g);
	parsingProduction("<preds_head>  ->  <predstring>", g);
	parsingProduction("<preds_tail>  ->  A <predstring> <preds_tail>", g);
	parsingProduction("<preds_tail>  ->  l", g);
	parsingProduction("<predname>    ->  LA <predstring>", g);
	parsingProduction("<predname>    ->  NAM", g);
	parsingProduction("<predstring>  ->  PREDA <predstr_tail>", g);
	parsingProduction("<predstr_tail> -> PREDA <predstr_tail>", g);
	parsingProduction("<predstr_tail> -> l", g);
	parsingProduction("<statement>   ->  <verbpred> <statement_s>", g);
	parsingProduction("<statement_s> ->  <predname>", g);
	parsingProduction("<statement_s> ->  l", g);
	parsingProduction("<verbpred>    ->  MOD <predstring>", g);
	
	g.start_symbol = "<sentence>";
		
	g.fill_first_set();
	g.fill_follow_set();
	g.fill_lltable();
	
	queue<string> SYMBOL;
	for(string token; cin >> token && token != "#";) {
		size_t pos = token.find('.');
		if(pos == string::npos) {
			SYMBOL.push(token2symbol(token));
			//cout << token2symbol(token) << " ";
			continue;
		}
		token.erase(token.length() - 1);
		//cout << token2symbol(token) << endl;
		if(token.length() > 0)
			SYMBOL.push(token2symbol(token));
		g.lldriver(SYMBOL);
		
		while(!SYMBOL.empty())
			SYMBOL.pop();
	}
	return 0;
}
Read More +
雜言筆記

大神面試紀錄 Hardware Interview

序

本篇文章記錄身邊大神去面試時所遇到的神祕問題，對於現在大三的我只能旁觀，雖然在計算機組織這一類的硬體課程修完不久，但是看到這些問題，還真的不知所措。

面試的時候，可以帶上會協助您的小夥伴們一起面試，這一點相當地奇特，面試不再是單打獨鬥。當然，小夥伴有事也沒有關係，將可以使用線上 call out。

也是這些原因，才有機會參與這些問題的討論。

面試題目

以下附錄僅為討論，不代表正確答案。

面試採用漸進式，由高階至低階開始追問，同時也會問到 Hardware Algorithm。

  • 用 C/C++ 寫一個九九乘法表

    這邊就不多加以描述，通常採用兩層迴圈的寫法和一個 printf

    1
    2
    3
    for(int i = 1; i <= 9; i++)
    	for(int j = 1; j <= 9; j++)
    		printf("%d x %d = %d\n", i, j, i * j);

  • printf(format, arg) 怎麼實作的？

    請準備 stdio.h 開始查閱，不過當下要想出來還真的挺難的，不過在 linux 下，stdin, stderr, stdout 都是一個檔案形式，這是在呼叫 printf後會去導入的目標所在。但如何解決 arg，要查閱一下 va_start 怎麼運作的，若上網搜尋得到。

    printflink
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #include <libioP.h>
    #include <stdarg.h>
    #include <stdio.h>
    #undef printf
    /* Write formatted output to stdout from the format string FORMAT.  */
    /* VARARGS1 */
    int
    __printf (const char *format, ...)
    {
      va_list arg;
      int done;
      va_start (arg, format);
      done = vfprintf (stdout, format, arg);
      va_end (arg);
      return done;
    }
    #undef _IO_printf
    ldbl_strong_alias (__printf, printf);
    /* This is for libg++.  */
    ldbl_strong_alias (__printf, _IO_printf);

    多變數到底是如何在這裡實作的，這一點要去考量 va_start，他會將參數位置丟入 va_list arg 中，但是如果參數個數或者是型態不符合 format，則運行的時候指針會指到錯誤的地方而噴出 RE，嘗試所及就到這裡了。

  • CPU 怎麼實作這些？

    CPU 的 pipeline 的五個階段和實作，IF, ID, EX, MEM, WB
    擷取指令、指定解析、執行運算、寫入記憶體、寫回暫存器。
    然後如何 pipeline，如果有類型的不同的時候，pipeline 會猜測到底要不要 branch，如果真的要 branch，要將 branch 之後的指令清掉 … 計組忘得一乾二淨。

  • 實作一個 n bits 加法器 adder，在平行的情況下，最多能多快。

    一般而言，要在 n 個 clock 後才能得到，這麼做就太慢了，之前上課有提到 carry lookahead adder, carry saved adder, … 等，這些雖然能在比一般時間更快得到是否要進位，但問題是要怎麼知道加完之後的結果！

    所以通常是切塊，然後賭前一塊到底會不會進位過來，把兩個答案都先算出，最後再利用 selector 去選擇正確的那個結果。

    如果單純是要得到是否會 overflow，最快可以在 O(log n) 時間內得到，採用分治的方式去考慮進位問題。

    分治算法看起來很接近線段樹的做法，藉由上一步，把兩種可能的答案都先算出，我們已經在 O(log n) 時間內把線段樹建出，接著對每一個元素做前綴的區間查詢，全部并行可以在 O(log n) 時間內完成，然後調用 selector 決定我們的答案。

    太多平行，平行處理的效能分析和處理資料的優先順序，很少在 ACM 使用，只好在此刻 yy 了。

  • 給很多區間 [l, r]，接著詢問某個點 x 被多少區間覆蓋。

    線段樹處理，搭配區間的懶操作，直接對區間 [l, r] 所有元素 + 1 即可，在 O(n log n) 時間內建表，然後單點查詢 A[x] 的值為何，這種做法可以動態支持。

  • 給一般圖進行匹配，假設不使用標準的帶花樹算法，使用自己的算法，請問誤差為多少。

    貪婪策略：
    每次對一個鄰居最少的點，找到其鄰居 (他的鄰居也最少) 進行匹配，然後把這些點都拿掉，繼續遞迴匹配。

    至於誤差－只能想辦法找到一個反例，來確定誤差一定大於某個值，要詳細證明什麼的，大概可以順便報一篇論文了。

    天祥反例

    一群人在思考反例，想了很久都沒有結果，最後由天祥大神找到一個誤差有 20% 的反例，詳細如上圖所述，如果一開始拿到 AD 或者是 HI，則會把匹配數最多拿到 4 個，事實上為 5 個。

結論

相當可怕，學得都忘得一乾二淨，無法精準回答。

Read More +
解題區►解題區 - UVa

ICPC 4020 - Hard Rode

Problem

The road to Shu is hard, even harder than climbing to the blue sky. A poem by Li Po from Tang Dynasty 1,200 years ago described the difficulty in travelling into Sichuan.

\epsfbox{p4020.eps}

However the above old saying is no longer true as a convenient communication network of railway, highway, waterway and air transport has come into being. Railways cover a total mileage of 2,693 km, consisting of five trunk lines including the BaojiChengdu and Chengdu-Chongqing railways, eight feeder lines and four local railways. The total mileage of highways stretches to nearly 80,000 km, ranking at the forefront in China. Now a highway network with the provincial capital of Chengdu as the center radiating to all cities in the province has been formed. A total of 500 km of expressways have been built. It is very easy to transfer passengers and freights between Sichuan and other provinces. After a nationwide railway speed acceleration launched in last year, trains can be allowed to run at a speed above 120 km per hour. However, the average speed of a train depends on its make-up. There is only single railway track between stations from Baoji to Chengdu, A primary task for dispatchers is to arrange for trains to meet and pass each other. You are requested to write a program to make the arrangement for a series of trains of different speeds from one station to its next station in the least amount of time.

What you should pay attention to while writing this program is that since there is a single railway track from Baoji to Chengdu, two trains are not allowed to pass the same spot at the same time, or they would be collision, and that because of the limited staff, there should be a fixed interval time between two trains out of the station, what’s more, the trains could pull into the station at the same time, but never get out at the same time.

Input

The input consists of several test cases. Each test case begins with a line containing 3 integers L (1 <= L <= 100000) , N (1 <= N <= 8) and T (1 < T < 10000) which indicate the distance between two stations (unit is meter), the number of trains, as well as the interval time of adjacent trains when trains leave the start (unit is second).

The next N lines contain average speeds of N trains (unit is m/s).

A single line with L = 0 indicates the end of input file and should not be processed by your program.

Output

For each test case, your output should be in one line with the minimum time(round to integer) needed by the trains pulling into the terminal as indicated in the sample output.

Sample Input

1
2
3
4
5
6
7
8
100000 6 300 
3 
4 
5 
6 
2 
1 
0

Sample Output

1
Case 1: 101500

Solution

題目描述：

從 陝西省寶雞市 到 四川省成都市 有一條鐵軌，而這一條鐵軌一次有好幾台火車在運行，但是不會發生追撞事件，然而每台火車的速度不一樣，而且站務人員會每隔固定時間發一班車，在不發生碰撞的情況下，最後一台火車到達成都市的最少時間為何？

題目解法：

在這樣的情況，有可能慢車先出發，然在在 T 秒之後，快車恰好追到慢車，這樣的情況會更好。但是實際數據應該長成什麼樣子沒有仔細考慮。

如果使用慢車最後出發，這樣能確保一定不會產生碰撞，但不確定是否是最佳解。

所以使用 O(n!) 的窮舉來計算答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h> 
#include <algorithm>
#include <math.h>
using namespace std;
int main() {
	int L, N, T, cases = 0;
	long long speed[10];
	while(scanf("%d %d %d", &L, &N, &T) == 3 && L) {
		int p[10] = {};
		for(int i = 0; i < N; i++) {
			scanf("%lld", &speed[i]);
			p[i] = i;
		}
		sort(speed, speed + N);
		long long ret = 0x3f3f3f3f;
		do {
			double start = T, lastTime = L / speed[p[0]];
			for(int i = 1; i < N; i++) {
				double time = L / speed[p[i]] + start;
				if(time >= lastTime) {
					start += T;
					lastTime = time;
				} else {
					lastTime = 0x3f3f3f3f;
					break;
					// start += T + (lastTime - time);
				}
			}
			ret = min(ret, (long long) ceil(lastTime));
		} while (next_permutation(p, p + N));
		printf("Case %d: %lld\n", ++cases, ret);
	}
	return 0;
}
Read More +