解題區►解題區 - UVa

UVa 10320 - Cow Trouble! Help Please

Problem

There are many classic problem with cows/goats and grass field in the world of mathematics. One of such problems is shown in the picture (left one) below. A goat is tied at point C which is on the edge of a round field with a rope of length R. One has to determine the length R when the cow can eat 50% grass of the round field. But in this problem we will consider a slightly different scenario which is shown in the second figure. In a field of infinite area there is a house ABDC. A cow is tied with pillar B of the house with a rope of length R. The length and width of the house is l and w. If the house was not there the cow could eat all the grass in the round green field (The round green field is a circle of radius R). But the presence of the house will certainly reduce his ability as the cow cannot enter the house nor can any part of the rope. You will have to determine the area the cow can now roam around and eat grass.

Fig 1: A classic Problem with a Goat

Fig 2: The Current Classic Problem with Cow

Input

The input file contains several lines of input. Each line contains three floating point numbers l, w and R as described in the problem statement. All numbers are less than 10000. Input is terminated by end of file.

Output

For each line of input produce one line of output. This output denotes the area that the cow can cover by not entering the house. This value should contain ten digits after the decimal point. Output will be checked with special judge. So you should not worry about very small precision errors.

Sample Input

1
2
10 5 5
10 4 8

Sample Output

1
2
58.9048622548
163.3628179867

Solution

題目描述：
有一頭牛被一根長度 R 的繩子拴在一棟建築物 ABCD 的 B 點上，草地的範圍為無限大，求牛可以吃到的草的範圍。Input 會給l, w 和 R 表示建築物長寬和繩長；l, w, R < 10000。Output 要輸到小數點第 10 位。

題目解法：

就是根據 R 的四種情況去討論，其中最麻煩的是對於 R > l + w，這種情況會需要討論重疊的區域，算出三角形夾角然後分別算兩個扇形面積，再弄回重疊區域三角形中的哪一塊有草。

其實這一題的題解網路上是有的，但是 PO 出來是因為自己卡在 WA，原因是這樣子的，假使 A = 0.5 * B 和 A = B / 2，這兩者寫法並無不同，但是後者的精準度比較好，很多次的 WA 都掛在這一點。

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
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int main() {
	double w, l, r;
	const double pi = acos(-1);
	while(scanf("%lf %lf %lf", &l, &w, &r) == 3) {
		if(w > l)
			swap(w, l);
		double area;
		if(r <= w)
			area = r * r * pi * 3 / 4.0;
		else if(r <= l)
			area = r * r * pi * 3 / 4.0 + (r - w) * (r - w) * pi / 4.0;
		else if(r <= l + w)
			area = r * r * pi * 3 / 4.0 + (r - w) * (r - w) * pi / 4.0 
					+ (r - l) * (r - l) * pi / 4.0;
		else {
			double a = atan2(l, w), b, c;
			double la, lb, lc;
			
			la = hypot(w, l);
			lb = r - w;
			lc = r - l;
			b = acos((la*la + lb*lb - lc*lc)/(2*la*lb)) + a;
			c = acos((la*la + lc*lc - lb*lb)/(2*la*lc)) + (pi /2) - a;
						
			area = r * r * pi * 3 / 4.0;
			area += (r - w) * (r - w) * (pi - b) / 2;
			area += (r - l) * (r - l) * (pi - c) / 2;
			area += lb * la * sin(b - a) / 2;
			area -= w * l / 2;
		}
		printf("%0.10lf\n", area);			
	}
	return 0;
}
Read More +
學校課程►計算型智慧

計算型智慧 程式作業

Computational Intelligence 計算型智慧

本課程將會有三階段程式，將三個算法依序加入程式中，為了要實作這些算法，必須先作出模擬器。

Lv. 0 模擬器

在一個 2D 平面中，以一個圓形當作車子，道路為線段的方式進行描述。為了在隨後的擴充，將地圖內容物分成可行區域多邊形和障礙物多邊形。

  • 要支持車子下一秒的擺角，並且按下推動鍵會根據方程式進行移動。
  • 可以將車子兩側的感測器進行角度調整，並且可以根據感測器角度進行距離計算。
  • 並且在呈現 2D 平面時，附加顯示座標軸的比例。

完成圖

由於私心，有一些額外產物。

  • 完成可以自動置中的設定
  • 提供地圖縮放和讀取操作
  • 製作地圖產生器 (other project)
  • 模擬器的彈木遊戲番外篇 (other project)
  • 提供運行欄位的縮起

Lv. 1 模糊系統

車子運行公式

運行公式

其中 Φ(t) 是模型車與水平軸的角度，b 是模型車的長度，x 與 y 是模型車的座標位置， Θ(t) 是模型車方向盤所打的角度，我們對模擬的輸入輸出變數限制如下：

-40 deg <= Θ(t) <= 40 deg

寫一個程式使用模糊系統、理論模擬車子行徑，並且想辦法最佳化。

  • 考慮擴充性，以後車子的運行公式可能會替換，因此建造一個 Engine class。
  • 模糊系統的幾個特性拆分成數個 method，並且使用不同的數學計算採用繼承關係。
  • 最困難得地方在於計算函數交集，採用離散取點是最後的手段

函數實驗

  1. 經過實驗，三個感測器分別坐落於前方 (90度)、左右各偏轉 50 度左右的夾角比左右 90 度更好。用以應付多變的轉角彎度，防止模稜兩可的擺動。
  2. 不管哪裡種去模糊化系統，由於題目限制擺角於 [-40, 40] 度之間，因此很容易在加權平均、質心、離散化而導致邊界擺角的機率甚低，當越多函數則稀釋程度越高。因此函數定義可以超過限制擺角，只需要在去模糊化時，約束至條件內即可。
  3. 設計函數時，要討論向其中一個方向偏轉，也就是不能設計過於對稱的圖形，否則將會在死胡同裡打轉。

函數設計

d1 為前方感測器，d2 為右方感測器，d3 為左方感測器。

  1. d1 歸屬函數為
    d1 歸屬函數
    d2, d3 歸屬函數為
    d2, d3 歸屬函數
  2. 函數式加權平均
      If d3 large, θ = 55
  If d2 large, θ = -55
  If d2 medium, θ = -40
  If d3 medium, θ = 40
  If d1 large and d2 small, θ = -30
  If d1 large and d3 small, θ = 30
  If d1 small, θ = -60
    規則如上述七條，以最簡單的常數關係。測試結果還算不錯。
    if condition, then statement，statement 中的變數不存在於 condition 去做調整，後來發現由於太複雜去討論而一直失敗。

  3. 重心法、最大平均法、修正型最大平均法、中心平均法
    為了方便計算連續函數，採用離散取點，間隔 0.1 抓取 [-60, 60] 之間的點座標。對於以下四種方法討論於簡單彎道的過程記錄：
    If d3 large
    If d3 large
    If d2 large
    If d2 large
    If d2 medium
    If d2 medium
    If d3 medium
    If d3 medium
    If d1 large and d2 small
    If d1 large and d2 small
    If d1 large and d3 small
    If d1 large and d3 small
    If d1 small, θ = -60
    If d1 small

    • 重心法
      當中表現最為穩健，而且路徑平滑。
    • 最大平均法
      由於定義的函數較為簡單，而且大多都是以梯形的方式存在，雖然能在機率高的情況下走完全程，路徑中會呈現左右擺盪情況。並且大多都已極值的方式出現。
    • 修正型最大平均法
      情況會稍微好一些，但是對於並沒有向重心法一樣的圓滑曲線，仍是因為原先的函數設計所惹的問題。

    對於某一種方法而去定義相關的函數進行測較好，而在最大平均法的部分，必須使用較具有變化性的曲線，否則很容易在極值狀況下擺動。

Lv 2. GA

RBF

「放射狀基底函數網路 RBF」，基本上，其網路架構如圖1所示，為兩層的網路；假設輸入維度是p ，以及隱藏層類神經元的數目是J ，那麼網路的輸入可以表示成：

其中選用高斯型基底函數：

其中 x = (x1,x2,…,xp) 、mj = (mj1,mj2,…,mjp) 、|| || 代表向量絕對值
適應函數為：

請用實數型基因演算法，找出wj , mj , σj，在不同的數字J下，最好的基因向量 (例如J為9、輸入x為3維向量，則表示基因向量是1+9+3x9+9=46維度的向量，請注意這裡不是指族群數；又例如J為7、輸入x為3維向量，則表示基因向量是1+7+3x7+7=36維度的向量)下，評估函數E(式1)為越小越好。其中基因向量維度公式為 1+J + pJ+J = (p+2)J+1維向量( ,w1 , w2 ,.., wJ , m11, m12,.., m1p, m21, m22,.., m2p,.., mJ1, mJ2,…, mJp, σ1, σ2, …, σJ)。

參數說明 :

  • N 作業1產生的N筆成功到達目的訓練資料(換不同起始點)
  • yn 表示訓練資料的方向盤期望輸出值 P.s.如果配合wj值的範圍為0~1之間，在此則必須把yn由-40~+40度正規化到 0~1之間；如果不想正規化 就必須把 wj的值範圍調整到 -40~40之間 範圍為0~1之間
  • Wj 範圍為 0~1 (或是-40~40)之間 P.s.此需配合訓練集的yn跟F(n)值範圍，所以皆需正規化到0~1之間；若不正規化，wj的值範圍為 -40~40之間
  • mj 範圍跟X範圍一樣，如以提供的範例檔則為 0~30
  • σj 範圍為0~10之間；也可以設定更大的範圍做探討。

實作概要 ：
把參數編碼成 DNA，使用 GA 算法改變 DNA，然後用之前的模糊系統的結果，讓 RBF 接近之前定義的模糊系統。需要拿模糊系統的一些測資當作訓練資料，收集之後餵給 GA 做訓練。

實驗方法

  1. 核心代碼，對於每次迭代，著手適應、選擇、交配、突變。
  2. 細部 “交配” 代碼，採用實數型的分離和聚集兩種情況。
  3. 細部 “突變” 代碼，採用微量雜訊，唯一不同的地方在於，這個微量雜訊會根據當前數值的比例有關，為了避免大數字對於微量雜訊的干擾不夠強烈。

實驗結果

  1. 運行結果 J = 3, p = 3
    ( ,w1 , w2 ,.., wJ , m11, m12,.., m1p, m21, m22,.., m2p,.., mJ1, mJ2,…, mJp, σ1, σ2, …, σJ) = (0.163568 0.851471 1.594151 1.379580 13.092824 0.000505 12.611789 30.000000 0.000368 18.715240 0.000850 2.708967 30.000000 6.307677 7.584529 10.000000)
  2. 訓練數據為 “map2” 走一圈的訓練資訊，約為 500 筆。因為 “map0” (即本次作業給的地圖) 的複雜度不夠以至於無法充分表達原本設計的模糊系統。也就是根據當初模糊系統設計，收集的數據的多樣性和連續性不足。

實驗分析

根據 RBF 的神經元，這裡可以越少越好，在程式中，神經元個數(J) 設置 3 個。運行時採用輪盤式選擇，讓適應能力好的，具有較高的機會繁殖，採用一個隨機變數去挑選。而在基因方面使用實數型基因的形式。

  1. 運行時，突變機率和突變比例相當重要，由於相同適應能力好的物種量很多，只保留其中一部分即可，因此可以將突變機率0.5 左右，太低則會造成進化速度太慢，太高則容易失去原本適應好的物種，導致整體適應度的震盪。
  2. 另外設置突變的比例，也就是該段實數值上下調整的比例。
    g.getDNA()[i] = g.getDNA()[i] + ratio * Math.random() * g.getDNA()[i];
    藉由上述的式子，將 ratio 設置成一個調變比例，來製造爆炸效應的規模。而在運行時，突變效果還能接受。
  3. 原本運行時，只將 DNA 片段的值任意放置，並且約束在不會超出函數的定義域，在收斂速度上有明顯加速。但為了符合作業需求，將每個參數約束在指定範圍內，在收斂速度慢了一截，在預期結果並沒有很好。
  4. 在不同地圖收集的預期資訊，會針對不同車子感測器的角度有所差異，因此不能拿不同型的感測數據，訓練出來的 RBF 不能給另外一台車子來使用，除非使用的感測器角度相當接近。
  5. 對於死路的轉彎，在神經元個數(J) 等於 2 的時候，運行結果較為不佳，但是在本次作業中，並不會有這種數據的出現，也不用考慮這種情況。但是當神經元個數少時，GA 算法的運行速度是相當快的。

Lv. 3 PSO

請利用Particle swarm optimization替換掉 GA 部分。

  • AgentNum(粒子數)
  • IterationNum(疊代數),
  • MaxV(最大速度),
  • MaxX(最大值範圍),
  • Weights(兩個權重),
  • Convergent_Error(停止條件)
  • 並畫出 fitness function 曲線變化 (每一次疊代的最佳fitness值)，最後訓練完成的F(x)當作規則 請跑出車子軌跡。

實驗分析

一開始參數為

1
2
3
4
5
6
public int sandSize = 512;
public double maxVelocity = 0.5;
public double maxXposition = 0.5;
public double weightOfCognition = 0.5;
public double weightOfSocial = 0.5;
public double nearRatio = 0.5;

PSO 1

PSO 2

  • 基本上 maxXposition 沒有用到，調整其他比例可以發現端倪。

  • 從圖 PSO 2 中可以發現到，PSO 與 GA 最大的不同在於，如果 GA 調用部分突變的情況下，很高的機率會發現適應曲線是嚴格遞減的，但是在 PSO 由於會飛來飛去，有可能會來回震盪。

  • 當所有粒子逼近最佳解時，仍會以原本的速度繼續飛行，而原本屬於最佳位置的點也會開始模仿其他粒子飛行，如此一來就會造成震盪。

PSO 3

  • 其震盪的高低決定於鄰近模仿的權重，如果鄰近的粒子效果不好，模仿的權重高的時候，會導致整個最佳解有嚴重的偏離。由 PSO 3 中可以驗證這個震盪問題。

  • 如果對於全局模仿權重調高，很容易造成處於群聚粒子不容易分離，也就是很難在早到其他的區域最佳解，會在很快的時間內進入某一個區域最佳解，從這一點中可以發現 PSO 真的具有快速收斂的性質。

  • 設定 maxVelocity 是將整個向量長度 (歐幾里得距離) 壓縮，這將可以控制查找的精密度，如果設定太小會導致收斂速度明顯下降。將 maxVelocity = 10 時，適應函數看起來會有比較高的進展，由於會將每個參數約束，只要速度不是太小影響就不大。

  • 當速度上限增加時，粒子碰到牆的機會也會上升，由於搜索範圍的可能性涵蓋邊界的情況增加，如果最佳解在邊界，在這樣的情況就會更好。

  • 在代碼中，鄰近的定義為最近粒子中排名前 20% 的最佳解。如果採用對於常數長度，這種情況上不容易觀察，也就是說不能直接找到鄰近模仿的規模該定義在何處。

  • 運行結果 J = 3, p = 3
    ( ,w1 , w2 ,.., wJ , m11, m12,.., m1p, m21, m22,.., m2p,.., mJ1, mJ2,…, mJp, σ1, σ2, …, σJ) = (0.117271 1.270048 0.000000 0.805823 15.845525 0.000000 21.613452 13.509075 0.000000 0.000000 30.000000 0.000000 10.505934 10.000000 10.000000 5.238101)

Github Download

Download

Blog

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

UVa 12717 - Fiasco

Problem

Natasha always mixes up things in her algorithm classes. Last week Prof. Chhaya Murthy gave the class a classical problem -finding shortest path to all nodes from a special node of a weighted graph. Before that in another class, the professor taught them Prim’s and Dijkstra’s algorithms which are similar looking but does very different things. Always confused, poor Natasha submitted something
very similar to the Prim’s algorithm (actually we should call it Natasha’s lgorithm), she didn’t test it properly. Pseudocode of her algorithm looks as follows

uva 12717

After submission, she showed the code to a friend who is good at algorithms. That friend immediately found the aw. Natasha was really terrifed and started to cry. Then there came the guys, the guys who liked her. They jumped at the opportunity and got hold of the dataset to be used to test the solutions. Your friend Rehan is one of those guys. He really wanted to impress Natasha. He asked you to change the dataset in such a way that Natasha’s algorithm gives the right result. After the change, Rehan will somehow be able to put the modified data with the old timestamp. Rehan told you that:

  1. The dataset has T test cases.
  2. Each case contains a connected weighted undirected graph with n nodes and
    m edges.
  3. Each case will contain a source node source.
  4. Edge weights are positive and distinct.

To avoid suspicion, Rehan asked you not to change which vertices the edges connect, or the overall set of edge weights. You may only reorder which weights are assigned to which edges

Input

The first line of the input denotes the number of datasets T (1 < T <= 15). T sets of case will follow. Each case will start with a triplet of numbers n (2 <= n <= 2500), m (1 <= m <= 25000) and source (1 <= source <= n) | the number of nodes, the number of edges and the starting node respectively.

Each of the next m lines will contain a triplet of numbers (u, v, w) meaning that there is an edge between node u and node v with weight w (1 <= w <= m). Nodes are numbered from 1 to n.

It is guaranteed that there is no duplicate or self-edges in the input and the graph is connected. In each given graph, all edge weights will be distinct.

Output

For each set of input, print one set of output. First line of a set should be of the format, Case X: where X is the case number. Then print each edge triplet | one triplet (u, v, w) in each line separated by a single space. The edges should be printed in the order given in the input. If there is more than one solution to a dataset, any one of them will do.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
1
7 9 5
2 4 2
1 4 8
7 2 6
3 4 7
5 7 5
7 3 9
6 1 1
6 3 4
5 6 3

Sample Output

1
2
3
4
5
6
7
8
9
10
Case 1:
2 4 7
1 4 9
7 2 3
3 4 8
5 7 1
7 3 4
6 1 5
6 3 6
5 6 2

Solution

題目描述：
// 給一個錯誤代碼，修改測資，使錯誤代碼輸出正確。
在一門演算法課程中，上到了最短路徑算法，教授指出了 Prim 和 Dijkstra 算法之間的不同，課堂上有個妹子很不小心搞混了這兩個算法，甚至弄出了更奇怪的程序，這代碼其中有缺陷，她和朋友分享代碼後，沒想到朋友瞬間戳出輸出錯誤的測資，妹子一時之間哭了出來。

現在為了擄獲芳心，請修改測資，使得錯誤代碼有一樣的正確輸出。

題目解法：
這個妹子錯的地方在於，更新的時候，沒有將為探訪點的情況加以考慮，直接以 BFS 的方式丟入，那麼在隨後更新的路徑長就不會被丟入 Priority Queue，這樣在 Dijkstra 的更新順序上就會出錯。也就是說，只要 Graph 的權重依據 BFS 順序 符合由小到大，不會出現隨後更新的問題即可。

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
#include <stdio.h> 
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
vector<int> g[2505];
int used[25005];
int in_x[25005], in_y[25005], in_w[25005];
map< pair<int, int>, int> shortest_tree;
void bfs(int source) {
	queue<int> 	Q;
	int 		u, v, e = 0;
	Q.push(source), used[source] = 1;
	while(!Q.empty()) {
		u = Q.front(), Q.pop();
		for(int i = 0; i < g[u].size(); i++) {
			v = g[u][i];
			if(used[v])	continue;
			used[v] = 1;
			shortest_tree[make_pair(u, v)] = in_w[e], e++;
			Q.push(v);
		}
	}
}
int main() {
	int testcase, cases = 0;
	int n, m, source;
	int x, y, w;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %d %d", &n, &m, &source);
		
		for(int i = 1; i <= n; i++) {
			g[i].clear();
			used[i] = 0;
		}
		shortest_tree.clear();
		
		for(int i = 0; i < m; i++) {
			scanf("%d %d %d", &x, &y, &w);
			g[x].push_back(y);
			g[y].push_back(x);
			in_x[i] = x, in_y[i] = y, in_w[i] = w;
		}
		
		for(int i = 1; i <= n; i++)
			sort(g[i].begin(), g[i].end());
		sort(in_w, in_w + m);
		bfs(source);
		
		printf("Case %d:\n", ++cases);
		map< pair<int, int>, int>::iterator it, jt, kt;
		int e = m - 1;
		kt = shortest_tree.end();
		for(int i = 0; i < m; i++) {
			it = shortest_tree.find(make_pair(in_x[i], in_y[i]));
			jt = shortest_tree.find(make_pair(in_y[i], in_x[i]));
			if(it != kt)
				w = it->second;
			else if(jt != kt)
				w = jt->second;
			else
				w = in_w[e], e--;
			printf("%d %d %d\n", in_x[i], in_y[i], w);
		}
	}
	return 0;
}
/*
1
7 9 5
2 4 2
1 4 8
7 2 6
3 4 7
5 7 5
7 3 9
6 1 1
6 3 4
5 6 3
*/
Read More +
解題區►解題區 - UVa

UVa 12716 - GCD XOR

Problem

Given an integer N, Find how many pairs (A, B) are there such that gcd(A, B) = A xor B where 1 < B < A <= N. Here gcd(A, B) means the greatest common divisor of the numbers A and B. And A xor B is the value of the bitwise xor operation on the binary representation of A and B.

Input

The First line of the input contains an integer T (T < 10000) denoting the number of test cases. The following T lines contain an integer N (1 <= N <= 30000000).

Output

For each test case, print the case number first in the format, Case X: (here, X is the serial of the input) followed by a space and then the answer for that case.
There is no new-line between cases.

Explanation
Sample 1:
For N = 7, there are four valid pairs: (3, 2), (5, 4), (6, 4) and (7, 6).

Sample Input

1
2
3
2
7
20000000

Sample Output

1
2
Case 1: 4
Case 2: 34866117

Solution

首先，嘗試把 N <= 1000 的情況列下來，列出 gcd(A, B) = C = A xor B

其中滿足 B < A and A mod C = 0，然後我們又觀察到 A&C == C，也就是說看 bitmask 的話，C 是 A 的 subset。

經由這一點，我們可以先寫出一個不會過 (TLE) 的做法，對 A 找到所有因子 C，查看是否符合 A&C == C，但是這樣的做法很容易知道時間效率不夠好。

下面是一個最簡單的版本。

TLE version
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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define maxL (30000000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
int P[5500], Pt = 0;
int F[30000005] = {};
void sieve() {
    register int i, j, k, l;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(j = i + i; j <= n; j += i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
vector< pair<int, int> > factor(int n) {
	int on = n;
	vector< pair<int, int> > R;
	
	for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
		if(n%P[i] == 0) {		
			for(j = 0; n%P[i] == 0; n /= P[i], j++);
			R.push_back(make_pair(P[i], j));
		}
	}
	if(n != 1)	R.push_back(make_pair(n, 1));
	return R;
}
void make(int idx, int n, int m, vector< pair<int, int> > &v) {
	if(idx == v.size()) {
		if((n&m) == m)
			F[n]++;
		return;
	}
	int a = m, b = v[idx].first;
	for(int i = v[idx].second; i >= 0; i--)
		make(idx + 1, n, a, v), a *= b;
}
int main() {
	sieve();
	vector< pair<int, int> > ff;
	for(int i = 1; i <= 30000000; i++) {
		ff = factor(i);
		make(0, i, 1, ff);
	}
	int testcase, cases = 0, n;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d", &n);
		int ret = 0;
		for(int i = 1; i <= n; i++)
			ret += F[i];
		printf("%d\n", ret - n);
	}
	return 0;
}

接著，使用其他的考慮方式，既然 (n, n + 1) 是已知解，其倍數解 (kn, k(n + 1))也是考量的一部分。

總歸一句，觀察 orz。

accepted
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
using namespace std;
int F[30000005] = {};
int main() {
	for(int i = 1; i <= 30000000; i++) {
		for(int j = i << 1; i + j <= 30000000; j += i) {
			if(((i + j)&(j)) == j)
				F[i + j]++;
		}
	}
	for(int i = 1; i <= 30000000; i++)
		F[i] += F[i-1];
	int testcase, cases = 0, n;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d", &n);
		printf("Case %d: %d\n", ++cases, F[n]);
	}
	return 0;
}
Read More +
學校課程►作業系統

作業系統 Thread 程式作業

C++ Thread 練習

作業要求

作業一:應用 Thread 撰寫任意程式(語言不限)，繳交方式 FTP:140.115.155.192(選擇自己學號的資料夾上傳) 帳:os2014 密碼不知道者請再問助教，檔案名稱: “作業一學號姓名第幾版” ex:”作業一_10252200x林大乖_v1” 繳交內容:壓縮檔(報告word 以及 程式碼,執行檔)，截止日期:2014/05/25(日)23:59

程式功能

兩個 n*n 矩陣相乘，在最基礎的 O(n^3) 效能上，使用 Thread 等相關技巧使其加速。

運行

  • Mac OSX

      $ clang -pthread x.cpp -o x

  • Linux

      $ gcc -lpthread x.cpp -o x

測試效率

  • Mac OSX and Linux
      $ time ./a.out

測試結果

測試環境為 2013 Mac Air 1.3 GHz Intel Core i5 上對 1024 x 1024 的矩陣進行相乘的統計結果。

  • matrix.cpp
    最原始的一般寫法，直接使用 O(n^3) 。運行時間約在 20 秒左右完成。
  • matrix[v2].cpp
    使用轉置矩陣後，在進行運算，這種方式是加快作業系統中的快取層，速度提升至約在 4 秒左右完成。
  • matrix[v3].cpp
    建立在 matrix[v2].cpp 的基礎上，使用 4 條 thread，分別對處理的 column 進行分割操作，速度約在 2 秒內完成。
  • matrix[v4].cpp
    與 matrix[v3].cpp 類似，調整 thread 的數量，查看效率變化，但是速度沒有更快的趨勢。

結論

Thread 多不代表會比較快，而是該程式佔有 CPU 的機會比較高，使用的資源就會比較多。在整個作業系統中，Thread 多上下文切換的次數就會上升，對於作業系統整體效率是下降的，但是又不能沒有 Thread，看起來像是所有程式同時在運行，也要防止落入死機無法動彈的情況。

而在 thread 上面會發現，當數量達到一定程度後，速度就不會上升，有一部分是因為 CPU 超頻運作。

超頻（英語：Overclocking）是把一個電子配件的時脈速度提升至高於廠方所定的速度運作，從而提升性能的方法，但此舉有可能導致該配件穩定性下降。

可能是長時間閒置的 CPU 發現有大規模的工作運行，把時脈速度升起。

代碼

matrix.cpp

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
#define MAX_N 1024
double A[MAX_N][MAX_N];
double B[MAX_N][MAX_N];
double C[MAX_N][MAX_N];
void multiply(double A[][MAX_N], double B[][MAX_N], double C[][MAX_N]) {
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            double sum = 0;
            for (int k = 0; k < MAX_N; k++) {
                sum += A[i][k] * B[k][j];
            }
            C[i][j] = sum;
        }
    }
}
int main(void) {
    //clock_t start, finish;
    //start = clock(); // start time clock
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            A[i][j] = i;
            B[i][j] = j;
        }
    }
    multiply(A, B, C);
    //finish = clock(); // finish time clock
    //printf("Time: %lf\n", (double)(finish - start)/1000);
    return 0;
}

matrix[v2].cpp

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
using namespace std;
#define MAX_N 1024
double A[MAX_N][MAX_N];
double B[MAX_N][MAX_N];
double C[MAX_N][MAX_N];
void trans(double A[][MAX_N]) {
    for (int i = 0; i < MAX_N; i++) {
        for (int j = i+1; j < MAX_N; j++) {
            swap(A[i][j], A[j][i]);
        }
    }
}
void multiply(double A[][MAX_N], double B[][MAX_N], double C[][MAX_N]) {
    trans(B);
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            double sum = 0;
            for (int k = 0; k < MAX_N; k++) {
                sum += A[i][k] * B[j][k];
            }
            C[i][j] = sum;
        }
    }
}
int main(void) {
    //clock_t start, finish;
    //start = clock(); // start time clock
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            A[i][j] = i;
            B[i][j] = j;
        }
    }
    multiply(A, B, C);
    //finish = clock(); // finish time clock
    //printf("Time: %lf\n", (double)(finish - start)/1000);
    return 0;
}

matrix[v3].c

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
#define MAX_N 1024
double A[MAX_N][MAX_N];
double B[MAX_N][MAX_N];
double C[MAX_N][MAX_N];
void trans(double A[][MAX_N]) {
    double x;
    int i, j;
    for (i = 0; i < MAX_N; i++) {
        for (j = i+1; j < MAX_N; j++) {
            x = A[i][j];
            A[i][j] = A[j][i];
            A[j][i] = x;
        }
    }
}
#define MAX_THREAD 4
void *multiply(void *arg) {
    int id = *((int *)arg);
    int st = id * MAX_N / MAX_THREAD;
    int ed = (id + 1) * MAX_N / MAX_THREAD - 1;
    int i, j, k;
    for (i = st; i <= ed; i++) {
        for (j = 0; j < MAX_N; j++) {
            double sum = 0;
            for (k = 0; k < MAX_N; k++) {
                sum += A[i][k] * B[j][k];
            }
            C[i][j] = sum;
        }
    }
    return NULL;
}
int main(void) {
    puts("Thread version");
    //clock_t start, finish;
    //start = clock(); // start time clock
    int i, j;
    for (i = 0; i < MAX_N; i++) {
        for (j = 0; j < MAX_N; j++) {
            A[i][j] = i;
            B[i][j] = j;
        }
    }
    trans(B);
    
    pthread_t *threads;
    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, multiply, (void *)(p));
    }
    for (i = 0; i < MAX_THREAD; i++) {
        pthread_join(threads[i], NULL);
    }
    //finish = clock(); // finish time clock
    //printf("Time: %lf\n", (double)(finish - start)/1000);
    return 0;
}

其他

雖然作業可以有其他語言的相關 Thread，在 Java 作品方面可以查看 Github。

Read More +
學校課程►敏捷方法

論文選讀 Agile Development and User Experience Design ...

課程論文心得

首先，所讀這一篇的論文名稱為『Agile Development and User Experience Design Integration as an Ongoing Achievement in Practice』 所以著重點在于用戶體驗設計要怎麼融入敏捷開發的探討。

什麼是用戶體驗？先說說 UX Designer 做些什麼嗎

第一次轉UX Designer就上手（上）

第一次轉UX Designer就上手（下）

看完內容後，總之 UX Designer 算是一種設計師，與理工背景的開發人員可是天差地遠，

他們比起宅宅開發者來說，要與用戶產生關係，繪畫、表達、心理學、與現實溝通，開發人員擁有技術並且完成目標，但是行為卻不是一般使用者，最簡單的說法是『為什麼做出來的軟體只有開發者會用？』如果在軟體的需求面向是開發者們的話，這也許還不是問題，但是要做出給一般人使用的軟體，這樣是行不同的。但是開發者的邏輯古怪到自己都不明白的機率是挺高的，因此會有 UX Designer。

借由 UX design，軟體將會有耐用性、易上手、輕便化 … 等，這讓我突然想到總是會開發出根本用不著的功能，或者是相當難操作的功能。

但是要把 UX design 完全融入是有困難的，因為邏輯思維不同的人，是很難協調的，又或者會互相侵蝕。

開始談談論文的內容

這一篇論文，主要是 觀察 ，也沒有觀察到所有目前的運行方式。換句話說，不會存在唯一一個好的開發方式，根據組織的規模和文化背景，所適用的運行方式也會有所不同，在理論上百分之百照抄別人的做法運用在自己的發開方式，但是可以藉由論文中觀察的幾點來學習我們的開發方式大概需要的是哪些面向需求。

而當開發人員是怎麼樣類型的人，就可能需要運用哪些方式，這些都是需要去探討的。外國也許按照它們的方式走成功，但並不代表按照一樣的作法一樣會成功，這就所謂 新方法論 。新方法論沒有絕對的方法，說來有點玄，也就是沒有固定方法就是方法！

由於組織規模不同，彼此部門又要互相協調，在設計與開發之間的不同在於時間的週期不同，工作類型的方式不同，如果是大規模組織，『提高內聚力，降低耦合度』因此專業分工的類型將會在 Study 1 中被提及，這麼考量是有它的原因在的。

而文藝復興時期的全才－達文西類型，則可以在 Study 2 中被提及，每一個人都必須學習一點別人的領域的項目，這樣可以互相考量、共同承擔，來分散思考風險。但這樣對於一般人是相當困難的，如果是菁英組織的運行，大概就是長得這樣。

在最後的 Study 3 中，雖然使用傳統的瀑布式開發，這種神祕的設計大於開發組合相當異常，但也許是一種新的導向。在往後的時代中，當技術相對成熟穩定時，面對的將會是設計需求大於開發需求。

RESEARCH METHOD

這裡提供三種 Ethnography (社會學的一種寫作文本，中文翻譯：民族誌) 來探討敏捷開發人員和用戶體驗設計師的配置方式。

A. In the field

(田野調查的區域，民族誌運用田野工作來提供人類社會學的描述研究)

總共有三個組織中，四個團隊參與本次研究，參與研究的團隊中正在進行 UX 設計，而我們主要的工作是觀察他們的工作運行情況。

共計在三種情況進行觀察。

  • Study 1: 觀察時間為兩個星期
  • Study 2: 觀察時間為六天
  • Study 3: 觀察時間為兩天

其中 Study 1, 2 過程中會涵蓋 Sprint 會議，而 Study 3 則只有涵蓋開發人員和設計師共處一室。

B. Thematic analysis

(專題分析)

C. Study participants

(研究參與者)

ACCOUNTS OF THE DAY-TO-DAY INTEGARTION WORK

Study 1

這項研究在 14 位 developer 和 2 位 UX designer，這兩位 UX designer 並不屬於 developer team，而是屬於該公司的 UX design team，因此他們並沒有參與 Sprint meeting、Standup、Retrospective，當然開發人員也沒有參與 design meeting，developer team 和 design team 在不同樓層工作。

開發人員描述道『將 UX design 與 agile develop 分開，是基於管理層面。』這很大的原因在於要將 UX 創造力發揮到極限，不能讓軟體工程的問題阻擋他們思考。

而在 Sprint meeting 中觀察到，UX designer 會提供一個 UX design 在 sprint meeting 前送達。但在隨後的 UX design 版本則是偶爾送到 developer 手上，直到 sprint 的最後一天仍持續修改，這表示著 developer 無法依靠 UX design 考慮相關的實作項目，所以大多數的關於 UX 工作將會分配在最後幾個小時來完成。

然而如果詢問 UX designer 是否已經意識到自己時間分配所造成的影響，則他們會回答說『沒有』。但事實上，在發送 UX design 時就已經造成相當多的問題。

[UX designer]: “That was never explicitly said to me … I thinks there was and still is visibility issues to do with what they’re doing and what their timeline are.”
這表示 UX designer 從來不知道這些事情，也從來沒有直接地被告知這項問題，也是因為不知道 developer 的運行工作和時程表。

當要澄清或者是修改 UX design 時，develop 會將問題寫下，並且要求 UX designer 在他們的 feedback meeting 中討論。

[senior UX designer]: “The visual designs are pretty much parallel to the wireframes … what kind of feedback do you want to give ?”
資深 UX designer 表示道：所有的視覺設計都是在線框 (wireframe) 的基礎上完成的，能有什麼樣的反饋？

developer 並不完全了解 UX design，只能依靠 UX designer 的批准和重構，這 “批准” 主要是對於敏捷開發中的維護和支持的組成用途，但是當 developer 向 designer 發問時，往往是溝通失敗的。

2pm: There is some problem with the visual design from UX [hadn’t arrived yet]. Project manager’s been trying to get in touch with the interaction designer, however can not get in contact - mobile switched off. Project manager has heard that UX are moving desks (not all the visual designs have been delivered since the developer feedback session).

上述內容看得不明白，難道是就是單純 PM 得不到完整的 visual design，因此也就不能向互動工程師聯繫嗎？

Study 2

小型手機軟件開發的公司，這一間公司有兩支團隊，每一隊有 5 名 developer 和 1 名 UX designer。其中 UX designer 設計非功能性描述和 screen mock-ups，這幾個項目將可以幫助 developer 參考進行開發。

mock-ups 相當於一種 prototype 可以支持動作的描述，通常會帶有基礎的 action code，關於 mock-ups 的相關工具有很多，但是通常價格不菲，邊設計還能自動幫忙產生代碼是不容易的工作。網路上找不到相關的解釋，就先這樣頂替了，相較於一般手繪製圖和文件描述，這樣的方式更為容易了解。

在他們會議中，每一個角色(QA, scrum master, product owner, UX designer, developer) 都參與討論會議，創造共同意識和共享決策責任。

9:30 [developer]: How should tabs appear, is ad always right-most tab ? … UX designer tells the developer what whould happen: As new chats come in ad tab moves over to right-most tab.

開發人員: 分頁到底該如何呈現，而廣告要固定在最右側的分頁嗎？ … UX designer 告訴我們應該「當新的聊天訊息進來時，廣告要移動到最右邊的分頁嗎？」

[Product owner]: Still waiting on response for some questions from the client.

Product owner: 這仍然在等待顧客的回報訊息

[QA]: Kind of hard to do QA if we don’t have the answer … wayry of starting stories without behaviours which means we might have to change thins and that wastes time.

QA: 這件事情很難做確認，如果我們沒有接收到回報，做的任何修改也許只是浪費時間，無法確定品質。

[UX designer]: Do them anyway, they might need to go through a number of iterations before they agree this is what they want … it’s better of they see something working as soon as posssible.

UX designer: 先把這問題放一旁，這需要多次迭代才能確定這是他們想要的 … 如果他們需要高效工作，則這個方式可能比較好。

[QA]: What if an ad coes in at exactly the same time as a chat ?

QA: 那如果廣告作為一個新的聊天訊息出場的話呢？

[UX designer]: That’s extreme edge case and probably very hard to test. So leave it. QA agrees.

UX designer: 這是一個相當極端的方式，非常難測試，所以先不要管這個。

這些對話通常在每一天的工作中進行，詢問另外一個團隊問題，而另外的團隊注意這些問題。

[UX designer]: “… if developers come up with issues, these are discussed on a case-by-case basis as they come up … There are lots of small things which are easily worked out on a day-to-day basis”

UX designer: 如果 developer 在每一個 case 基礎上想出了問題，這些小問題很容易在每日解決。

從會議過程中，主要，我們可以發現的每一個角色都參與了 UX design，同時也在職權外貢獻了他們的想法 - 例如 UX designer 建議在極端情況忽略 QA testing，而在 QA 沒有指責 UX designer 所做的 QA 決策，他們接受這項意見並沒有發出任何評論。其次，在這個 UX design 討論議題中也一起討論了 non-UX 的問題(如這個 QA testing 問題)。

這次的會議的下一步行動，包括實現解決方案和傳達問題給客戶。所有的角色參與討論導致決策同時考慮的設計價值和技術考量。

而在會議中，有 developer 向其他人簡單說明，他在網路空間上有一些之前專案製作時替換視覺設計的文件可以參考，這可以讓 UI designer 可以接受這些更改的項目，增加信服力。

[UX designer]: Sometimes the developers’ decisions are better, as they are much closer to the implementation. 有時候開發者的決策會更好，因為他們更接近實作。

Study 3

在非常小的公司進行，有 1 名 developer 和 2 名 UX designer，他們擅長瀑布形式的開發，在開發過程中 developer 和 UX designer 在同一間辦公室工作，目標是使得設計和開發更接近。正如 Study 1 的時候，發現 developer 會根據 UX designer 設計的線框 (wireframe) 和 visual design 努力地工作。

觀察兩天後的結果如下:

在一般的情況下，UX designer 通常和 developer 在不同樓層工作，developer 也表示他們很少去找 designer 討論遭遇的問題。

[developer]: We often find things that don’t work, but we don’t go back to design. We just do our best. 我們常發現很多事情並不會 work，但是並沒有回去檢討設計，單純盡力而為。

在這種共同工作的情況下，designer 給予了一些回應。

[UX designer]: This style of working means we can collaborate in order to get our points across, rather than dictate because there’s no communication going on. 這種工作方式可以讓我們的觀點交換，而不是因為沒有通通合作的命令。

[Head of UX]: And when we first met with the client, the first thing they did was to present to us the findings of that initial research. So we can then go and propose what would bee the next step, which is quite different from any other type of work we’ve been invited to get involved in.

在大多數的情況，不確定性，設計師在現場談話的記錄:

[visual designer]: I just feel like I’m not getting any-where.

[IA]: I also feel that way.

但是對於另一個情況下

[developer]: Just cover the site map.

developer 和 designer 共同工作

  • 可以相互討論跟顧客對談時的內容 (當時在場的感受不同)
  • 目標計劃做些什麼，訊息可以提前知道。(想要做第二個版本)
  • 「這個設計會不會很難實作？」這些問題將會很快被反應出來。

[developer]: It would probably be just as easy.

THEME FOR ACHIEVING INTEGRATION

A. Integration as expectations about acceptable behaviour

在 Study 1 中可以發現，如果將兩者隔離，很容易造成規劃的浪費和開發者在最後期限前超時工作。UX designer 同時跨越多個專案進行設計，丟出設計之後就沒有可接收開發者的反饋，只有等到 sprint meeting 的反應才重新設計，這時可能已經為期已晚。

在 Study 2 中可以發現，頻繁確保兩者之間有相互支持，並且在 UX design 和代碼之間可以互相溝通，相較于 Study 1 上，溝通性有上升，但這些遭遇的問題將會在每個人參與討論會議的過程中的一部份。

在 Study 3 中，每一個成員都有機會被其他角色問到自己領域的問題，同時也可以在與客戶討論中的觀察，在隨後討論。這都歸因于他們在同一間辦公室工作。

B. Integration as mutual awareness

相對于 Study 1 中，Study 2, 3 擁有了共同享有決策的責任，同時提高了互動上的認識。

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

Yacc 與 Lex 練習 - UVa 11291

Problem

詳細題目請參考 UVa 11291 - Smeech

語法

1
2
<E[x]> -> <Integer> | (p <E[x]> <E[x]>)
<Integer> -> #number

目標計算出 E[X] = p * (e1 + e2) + (1 - p) * (e1 - e2)

Yacc

Yacc 主要是根據 CFG 進行解析。

其中，要對於 Yacc 語法的回傳值明白操作情況。

對於語法回傳值，我們來個最簡單的範例：

1
2
expression -> LEFT_P NUMBER expression expression RIGHT_P
    $$          $1     $2       $3         $4       $5

其中 $$ 是回傳值，其中的 $1、$2 … 等，都是得到的回傳值。

對於 yylval 形態處理：

1
2
3
4
%union {
	float 	floatVal;
	int 	intVal;
}

通常使用 union 的方式來共用記憶體，在 lex 那邊就可以根據 yylval.floatVal 進行操作。

當然，我們也要對於每一個 nonterminal 定義回傳的型態

1
2
3
%type <floatVal> NUMBER
%type <floatVal> expression
%type <floatVal> startsymbol

基本上就大功告成了。

接著要考慮如何去完成多組測資組的問題，在這裡可以利用 kleene star 來完成。

但是對於輸出順序，使用 input -> input startsymbol 跟 input -> startsymbol input 輸出順序是不同的，如果要順著輸出，請選擇前者。

file: a.y
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
%{
#include <stdio.h>
int yylex();
double ans = 0;
void yyerror(const char* message) {
	ans = -2147483647;
	printf("Invaild format\n");
};
%}
%union {
	float 	floatVal;
	int 	intVal;
}
%type <floatVal> NUMBER
%type <floatVal> expression
%type <floatVal> startsymbol
%token LEFT_P RIGHT_P NUMBER
%%
input
	: input startsymbol {
		ans = $2;
		printf("%.2f\n", ans);
	}
	| {
	}
startsymbol
	: expression {
		$$ = $1;
	}
	;
expression
	: NUMBER {
		$$ = $1;
	} 
	| LEFT_P NUMBER expression expression RIGHT_P {
		$$ = $2 * ($3 + $4) + (1.0f - $2) * ($3 - $4);
	}
	;
%%
int main() {
	yyparse();
	return 0;
}

Lex

Lex 主要是扮演切出所有的 token 的角色，相當於 Scanner。同時要將值紀錄再 yylval 中，在 Yacc 那邊則會在 $NUMBER 中得到變數值。

在 Lex 語法上要特別小心，如果兩條的前綴 (prefix) 相同時 (解析上會產生相同的 token)，則會選擇長的那一條為優先。如果長度仍相同的話，請自行測試，這裡無法給予解答。而為什麼要這麼設計？為了保證後綴不會塞入奇怪的字符，因此可以先檢查隨後接的字符情況。

file: a.l
1
2
3
4
5
6
7
8
9
10
11
12
13
%{
#include "a.tab.h"
#include <stdio.h>
%}
%%
([-]?)[0-9]*\.[0-9]*		{sscanf(yytext, "%f", &yylval.floatVal); return NUMBER;}
([-]?)[0-9]+				{sscanf(yytext, "%f", &yylval.floatVal); return NUMBER;}
"("					{return LEFT_P;}
")"					{return RIGHT_P;}
\n					{}
.					{}
%%

make file

請用以下方法建造

1
morris $ sh make.sh

代碼如下

file: make.sh
1
2
3
4
5
bison -d a.y
flex a.l
gcc -c a.tab.c
gcc -c lex.yy.c
gcc lex.yy.o a.tab.o -lfl

產生的結果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ tree 
. ├── a.l
  ├── a.out 
  ├── a.tab.c 
  ├── a.tab.h 
  ├── a.tab.o 
  ├── a.y 
  ├── input~ 
  ├── lex.yy.c 
  ├── lex.yy.o 
  ├── make.sh 
  ├── make.sh~ 
  ├── testdata 
  │   ├── ac_output 
  │   └── input

執行

執行的時候就跟標準輸入串流一樣。

1
morris $ ./a.out <input

參考範例輸入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
7
(.5 3 9)
(0.3 2 (1 1 -10))
(1.0 (1.0 (1.0 -1 -2) (1.0 -1 -2)) (1.0 (1.0 1 2) 2))
(0.99 82 (0.76 50 (0.85 (0.07 (0.88 28 (0.98 79 (0.09 77 51))) (0.30 (0.29 36 (0.36 (0.51 27 (0.68 (0.47 87 35) (0.25 85 59))) 31)) 64)) (0.14 (0.84 (0.77 29 71) (0.50 (0.99 (0.81 (0.78 (0.87 50 7) 71) 72) 14) (0.30 (0.50 9 37) (0.67 21 (0.73 86 (0.08 31 14)))))) (0.94 (0.96 (0.50 27 (0.94 (0.54 62 (0.63 89 29)) (0.81 24 (0.94 20 72)))) 4) (0.44 9 (0.59 (0.70 48 40) (0.64 (0.27 97 71) 43))))))))
(0.15 12 60)
(0.55 18 (0.95 (0.79 95 (0.97 (0.11 (0.96 (0.70 (0.38 73 66) (0.38 (0.06 (0.02 88 66) (0.39 35 37)) 69)) (0.81 3 (0.45 5 61))) (0.44 (0.67 (0.23 82 7) 38) (0.24 49 74))) 76)) (0.46 19 44)))
(0.56 62 77)
(0.03 (0.90 19 35) (0.17 50 (0.13 (0.96 74 (0.07 (0.51 78 (0.77 (0.78 (0.84 64 (0.41 7 59)) 21) (0.73 (0.95 (0.13 2 85) (0.08 29 50)) (0.24 (0.12 43 99) 71)))) 84)) (0.31 69 (0.82 31 24)))))
(0.78 73 44)
(0.09 (0.80 14 62) (0.57 (0.57 95 (0.33 94 31)) (0.70 (0.92 32 (0.13 20 (0.44 87 (0.45 83 26)))) (0.43 40 (0.51 (0.57 29 (0.65 13 (0.40 74 56))) 56)))))
(0.96 (0.96 (0.65 (0.01 (0.98 (0.34 86 (0.68 87 21)) 27) (0.26 68 68)) (0.42 28 29)) 9) 99)
(0.99 (0.60 53 27) (0.35 23 (0.15 (0.50 85 (0.73 56 (0.34 (0.44 (0.10 (0.62 (0.20 58 15) 56) (0.57 74 (0.23 20 78))) 62) (0.92 (0.72 (0.82 75 (0.08 35 93)) 43) (0.55 10 (0.45 (0.25 52 91) 71)))))) (0.61 39 (0.49 (0.92 87 (0.13 52 (0.69 (0.46 (0.82 27 72) 96) (0.27 51 99)))) (0.36 99 (0.60 68 (0.49 (0.25 (0.92 54 7) (0.48 47 32)) (0.08 (0.69 97 11) 34)))))))))
(0.87 (0.32 (0.42 (0.66 69 (0.98 0 (0.46 94 (0.25 (0.57 (0.72 25 59) (0.35 91 (0.42 29 28))) 3)))) 19) 81) (0.72 (0.06 (0.66 (0.07 22 87) 44) (0.18 33 14)) 49))
(0.72 (0.01 67 (0.13 (0.22 (0.88 11 86) (0.04 40 (0.41 (0.86 (0.81 (0.08 84 95) (0.88 19 67)) 8) 96))) 13)) (0.13 45 (0.19 (0.83 85 (0.77 (0.37 78 (0.44 44 59)) 37)) 56)))
(0.51 (0.36 2 72) 25)
(0.32 51 87)
(0.06 (0.23 (0.70 93 47) (0.22 20 (0.90 (0.03 (0.48 (0.84 18 (0.29 (0.02 (0.06 52 49) 67) (0.49 (0.69 60 74) (0.59 92 0)))) 32) 80) (0.76 78 (0.66 8 94))))) 31)
(0.29 (0.54 70 (0.64 (0.48 (0.50 25 (0.38 (0.07 (0.14 (0.44 (0.76 44 45) 67) 41) (0.15 (0.86 (0.89 87 42) (0.43 85 58)) (0.98 44 (0.48 34 28)))) (0.84 81 60))) 28) 16)) (0.84 (0.21 34 (0.78 (0.76 (0.51 82 (0.07 (0.78 (0.52 (0.65 51 58) 12) (0.05 52 (0.98 0 30))) (0.01 27 3))) (1.00 15 (0.53 (0.91 (0.38 62 (0.75 92 69)) (0.85 53 (0.84 92 83))) (0.70 (0.12 (0.24 23 83) 58) (0.62 56 38))))) 36)) (0.66 41 13)))
(0.94 (0.47 30 56) (0.78 6 (0.45 (0.45 15 94) (0.77 (0.57 25 (0.33 66 12)) (0.66 74 (0.82 (0.14 75 50) (0.22 45 43)))))))
(0.66 (0.58 (0.85 75 26) 45) (0.04 (0.94 82 (0.59 34 (0.02 (0.09 11 (0.31 (0.05 (0.92 (0.14 51 45) (0.47 25 46)) 6) 5)) 33))) (0.81 (0.09 15 (0.91 (0.77 (0.59 44 (0.57 (0.39 (0.81 18 75) (0.37 41 67)) 18)) (0.77 (0.68 (0.71 (0.31 87 94) 85) (0.00 35 (0.55 81 22))) 56)) 3)) (0.43 7 (0.98 94 3)))))
(0.13 22 80)
(0.77 45 81)
(0.61 (0.21 (0.32 (0.32 (0.81 8 60) 78) (0.19 (0.92 68 (0.56 (0.22 79 32) (0.32 72 63))) 41)) (0.30 94 31)) (0.80 59 33))

參考範例輸出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
7.00
3.00
5.60
-1.00
241.55
-30.00
32.05
71.24
25.80
97.64
-37.98
153.38
67.92
35.81
-10.21
-17.66
19.68
60.84
92.20
30.61
157.62
-37.20
88.74
-48.46

Reference

Yacc 与 Lex 快速入门

指導

Inker

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

UVa 1636 - Headshot

Problem

You have a revolver gun with a cylinder that has n chambers. Chambers are located in a circle on a cylinder. Each chamber can be empty or can contain a round. One chamber is aligned with the gun’s barrel. When trigger of the gun is pulled, the gun’s cylinder rotates, aligning the next chamber with the barrel, hammer strikes the round, making a shot by firing a bullet through the barrel. If the chamber is empty when the hammer strikes it, then there is no shot but just a click.

You have found a use for this gun. You are playing Russian Roulette with your friend. Your friend loads rounds into some chambers, randomly rotates the cylinder, aligning a random chamber with a gun’s barrel, puts the gun to his head and pulls the trigger. You hear click and nothing else — the chamber was empty and the gun did not shoot.

Now it is your turn to put the gun to your head and pull the trigger. You have a choice. You can either pull the trigger right away or you can randomly rotate the gun’s cylinder and then pull the trigger. What should you choose to maximize the chances of your survival?

Input

The input file contains several datasets. A dataset contains a single line with a string of n digits 0 and 1 ( 2 <= n <= 100). This line of digits represents the pattern of rounds that were loaded into the gun’s chambers. 0 represent an empty chamber, 1 represent a loaded one. In this representation, when cylinder rotates before a shot, the next chamber to the right gets aligned with the barrel for a shot. Since the chambers are actually located on a circle, the first chamber in this string follows the last one. There is at least one 0 in this string.

Output

For each dataset, write to the output file one of the following words (without quotes):

  • SHOOT — if pulling the trigger right away makes you less likely to be actually shot in the head with the bullet (more likely that the chamber will be empty).
  • ROTATE — if randomly rotating the cylinder before pulling the trigger makes you less likely to be actually shot in the head with the bullet (more likely that the chamber will be empty).
  • EQUAL — if both of the above choices are equal in terms of probability of being shot.

Sample Input

1
2
3
0011
0111
000111

Sample Output

1
2
3
EQUAL
ROTATE
SHOOT

Solution

題目描述：

俄羅斯輪盤，現在與一位朋友一起玩這場遊戲，然而我們已經知道左輪手槍中的填彈資訊，剛聽到朋友按下扣板，但是沒有死。現在輪到你，請問要直接按？還是隨機轉一圈再按？

題目解法：

不外乎地，我們要找到哪個機率高。

由於朋友按下沒死，也就是要考慮連續 2 個 0 的情況，下一個是 0 的機率為 czero / zero

// 在前提為 0 的情況下，下一個為 0 的機率為何，也就是考慮 00 和 01 的情況下，00 的機率為何。
// czero 是連續為 0 的個數，zero 是 0 的個數 (同時也是 00 01 的個數。)，n 是全部個數。

隨機轉一圈得到 0 的概率為 zero / 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
#include <stdio.h>
#include <string.h>
int main(){
	char s[1024];
    while(scanf("%s", s) == 1){
        int n = strlen(s);
        int zero = 0, one = 0, czero = 0;
        for(int i = 0 ; i < n ; i++ ){
            if(s[i] == '1') 
				continue;
            zero++;
            if(s[(i+1)%n] == '0') czero++;
        }
        // czero - zero * (zero / n)
        if(czero * n == zero * zero) 
			puts("EQUAL");
        else if(czero * n > zero * zero)
			puts("SHOOT");
        else 
			puts("ROTATE");
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1644 - Prime Gap

Problem

The sequence of n - 1 consecutive composite numbers (positive integers that are not prime and not equal to 1) lying between two successive prime numbers p and p + n is called a prime gap of length n . For example, 〈24, 25, 26, 27, 28〉 between 23 and 29 is a prime gap of length 6.

Your mission is to write a program to calculate, for a given positive integer k , the length of the prime gap that contains k . For convenience, the length is considered 0 in case no prime gap contains k .

Input

The input is a sequence of lines each of which contains a single positive integer. Each positive integer is greater than 1 and less than or equal to the 100000th prime number, which is 1299709. The end of the input is indicated by a line containing a single zero.

Output

The output should be composed of lines each of which contains a single non-negative integer. It is the length of the prime gap that contains the corresponding positive integer in the input if it is a composite number, or `0’ otherwise. No other characters should occur in the output.

Sample Input

1
2
3
4
5
6
10 
11 
27 
2 
492170 
0

Sample Output

1
2
3
4
5
4 
0 
6 
0 
114

Solution

題目描述：

找該數字左右相鄰的兩個質數差值。

題目解法：

線性篩法 (sieve)。

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
#include <stdio.h>
#include <stdlib.h>
#define LL long long
#define maxL (1300000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
int anaP[30], at = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1300000;
    for(i = 2; i < n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
        }
    }
}
main() {
    sieve();
    int n;
    while(scanf("%d", &n) == 1 && n) {
    	int ret = 0;
    	for(int i = n; GET(i); i++, ret++);
    	for(int i = n; GET(i) && i > 0; i--, ret++);
    	printf("%d\n", ret);
    }
    return 0;
}
Read More +