摘要: /Files/unixfy/考勤處理程序-MarkYang.pdf
考勤處理程序
Mark Yang
QQ: 591 247 876
Email: goonyangxiaofang@163.com
一個考勤數據最主要的三項就是：
人名 &n...
閱讀全文
posted @
2012-10-25 16:06 unixfy 閱讀(518) |
評論 (0) |
編輯 收藏
摘要: K-近鄰法的實現
K-近鄰法是根據距離最近的 k 個樣例的類型來推測該樣例的類型。實現中中主要的環節有：·訓練樣例格式和測試樣例格式的定義·樣例結構體的定義·訓練樣例和測試樣例的讀取·樣例距離的計算，歐氏距離·距離矩陣的生成·針對每個測試樣例，得到其到每個訓練樣例的距離，根據距離由小到大排序，更具距離和權重成反比的關系，計算每個類型的總...
閱讀全文
posted @
2012-02-14 09:47 unixfy 閱讀(4952) |
評論 (0) |
編輯 收藏 1 /*
2 特征向量相似度和距離的計算
3
4 相似度：
5 ·夾角余弦
6 ·相關系數
7 ·Dice
8 ·Jaccard
9
10 距離
11 ·明氏距離
12 ·歐氏距離
13 ·馬氏距離
14 ·Jffreys & Matusita 距離
15 ·Mahalanobis 距離，未實現，協方差矩陣
16 ·Camberra 距離（Lance 距離，Williams 距離）
17 */
18
19 #include <iostream>
20 #include <vector>
21 #include <cassert>
22 #include <cmath>
23 using namespace std;
24
25 double dotProduct(const vector<double>& v1, const vector<double>& v2)
26 {
27 assert(v1.size() == v2.size());
28 double ret = 0.0;
29 for (vector<double>::size_type i = 0; i != v1.size(); ++i)
30 {
31 ret += v1[i] * v2[i];
32 }
33 return ret;
34 }
35
36 double module(const vector<double>& v)
37 {
38 double ret = 0.0;
39 for (vector<double>::size_type i = 0; i != v.size(); ++i)
40 {
41 ret += v[i] * v[i];
42 }
43 return sqrt(ret);
44 }
45
46 // 夾角余弦
47 double cosine(const vector<double>& v1, const vector<double>& v2)
48 {
49 assert(v1.size() == v2.size());
50 return dotProduct(v1, v2) / (module(v1) * module(v2));
51 }
52
53 double mean(const vector<double>& v)
54 {
55 assert(v.size() != 0);
56 double ret = 0.0;
57 for (vector<double>::size_type i = 0; i != v.size(); ++i)
58 {
59 ret += v[i];
60 }
61 return ret / v.size();
62 }
63
64 double cov(const vector<double>& v1, const vector<double>& v2)
65 {
66 assert(v1.size() == v2.size() && v1.size() > 1);
67 double ret = 0.0;
68 double v1a = mean(v1), v2a = mean(v2);
69
70 for (vector<double>::size_type i = 0; i != v1.size(); ++i)
71 {
72 ret += (v1[i] - v1a) * (v2[i] - v2a);
73 }
74
75 return ret / (v1.size() - 1);
76 }
77
78 // 相關系數
79 double coefficient(const vector<double>& v1, const vector<double>& v2)
80 {
81 assert(v1.size() == v2.size());
82 return cov(v1, v2) / sqrt(cov(v1, v1) * cov(v2, v2));
83 }
84
85 // Dice 系數
86 double dice(const vector<double>& v1, const vector<double>& v2)
87 {
88 assert(v1.size() == v2.size());
89 return 2.0 * dotProduct(v1, v2) / (dotProduct(v1, v1) + dotProduct(v2, v2));
90 }
91
92 // Jaccard 系數
93 double jaccard(const vector<double>& v1, const vector<double>& v2)
94 {
95 assert(v1.size() == v2.size());
96 return dotProduct(v1, v2) / (dotProduct(v1, v2) + dotProduct(v2, v2) - dotProduct(v1, v2));
97 }
98
99 // Minkowsky 距離
100 double minkowsky(const vector<double>& v1, const vector<double>& v2, double m)
101 {
102 assert(v1.size() == v2.size());
103 double ret = 0.0;
104 for (vector<double>::size_type i = 0; i != v1.size(); ++i)
105 {
106 ret += pow(abs(v1[i] - v2[i]), m);
107 }
108 return pow(ret, 1.0 / m);
109 }
110
111 // Euclidean 距離
112 double euclidean(const vector<double>& v1, const vector<double>& v2)
113 {
114 assert(v1.size() == v2.size());
115 return minkowsky(v1, v2, 2.0);
116 }
117
118 // Manhattan 距離
119 double manhattan(const vector<double>& v1, const vector<double>& v2)
120 {
121 assert(v1.size() == v2.size());
122 return minkowsky(v1, v2, 1.0);
123 }
124
125 // Jffreys & Matusita 距離
126 double jffreysMatusita(const vector<double>& v1, const vector<double>& v2)
127 {
128 assert(v1.size() == v2.size());
129 double ret = 0.0;
130 for (vector<double>::size_type i = 0; i != v1.size(); ++i)
131 {
132 ret += (sqrt(v1[i]) - sqrt(v2[i])) * (sqrt(v1[i]) - sqrt(v2[i]));
133 }
134 return sqrt(ret);
135 }
136
137 // Mahalanobis 距離
138 double mahalanobis(const vector<double>& v1, const vector<double>& v2)
139 {
140 assert(v1.size() == v2.size());
141 return 0.0;
142 }
143
144 // Camberra 距離（Lance 距離，Williams 距離）
145 double camberra(const vector<double>& v1, const vector<double>& v2)
146 {
147 assert(v1.size() == v2.size());
148 double ret = 0.0;
149 for (vector<double>::size_type i = 0; i != v1.size(); ++i)
150 {
151 ret += abs(v1[i] - v2[i]) / abs(v1[i] + v2[i]);
152 }
153 return ret;
154 }
155
156 int main()
157 {
158 double a[] = {1, 2, 3, 4, 5};
159 double b[] = {5, 4, 3, 2, 1};
160 vector<double> v1(a, a + sizeof (a) / sizeof (*a)), v2(b, b + sizeof (b) / sizeof (*b));
161
162 cout << cosine(v1, v2) << endl;
163 cout << coefficient(v1, v2) << endl;
164 cout << dice(v1, v2) << endl;
165 cout << jaccard(v1, v2) << endl;
166
167 cout << minkowsky(v1, v2, 5.0) << endl;
168 cout << euclidean(v1, v2) << endl;
169 cout << manhattan(v1, v2) << endl;
170 cout << jffreysMatusita(v1, v2) << endl;
171 cout << mahalanobis(v1, v2) << endl;
172 cout << camberra(v1, v2) << endl;
173
174 return 0;
175 }
posted @
2012-02-13 15:18 unixfy 閱讀(9262) |
評論 (1) |
編輯 收藏在已排序數組中查找出現最多的數字
http://www.vanjor.org/blog/2011/04/puzzle-array-find-most/
這里有個前提是數組已排好序
如果出現最多的數字出現次數大于一般，那么這個出現次數最多的數字就是位于數組中中間位置的數，這里需要考慮數組中的元素個數是奇數還是偶數
出現次數最多的數字的出現次數是大于元素數目的一般
如果數組是未排序的情況呢？
可以先把數組排好序，然后再把按照已排序的情況處理
也可以不排序，直接處理，這種情況下某個數的出現次數大于元素數目的一般比較好解決
1.
這里要解決的第一個問題是：
·已排序
·查找出現最多的數字，這個數字的出現次數不一定大于所有元素數目的一半
時間復雜度是 O(N)
程序：
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 bool isSorted(const vector<int>& data)
6 {
7 for (vector<int>::size_type i = 0; i != data.size() - 1; ++i)
8 {
9 if (data[i + 1] < data[i])
10 {
11 return false;
12 }
13 }
14 return true;
15 }
16
17 int findMaxTimesNumber(const vector<int>& data)
18 {
19 if (data.size() <= 0)
20 {
21 return -10000;
22 }
23 int count = 0;
24 int recorder = data[0];
25 int times = 1;
26 count = times;
27 for (vector<int>::size_type i = 1; i != data.size(); ++i)
28 {
29 if (data[i] == data[i - 1])
30 {
31 ++times;
32 }
33 else
34 {
35 if (times > count)
36 {
37 count = times;
38 recorder = data[i - 1];
39 }
40 times = 1;
41 }
42 }
43 if (times > count)
44 {
45 count = times;
46 recorder = data[data.size() - 1];
47 }
48 return recorder;
49 }
50
51 int main()
52 {
53 vector<int> data;
54 int n;
55 while (cin >> n)
56 {
57 data.push_back(n);
58 }
59 if (!isSorted(data))
60 {
61 cerr << "Error!" << endl;
62 return 1;
63 }
64 cout << findMaxTimesNumber(data) << endl;
65 }
===
這種解法本質上并不要求數組是已排好序的
只是要求相等的數字必須是在一起連續的
2.
第二種情況
數組是已排好序的，并且有一個數字出現次數大于數組中元素的總數目
時間復雜度：O(1)
如果總數目是奇數：
int foo(const vector<int>& data)
{
return data[data.size() / 2];
}
出現次數必須大于一半
如果總數目是偶數：
int foo(const vector<int>& data)
{
return data[data.size() / 2];
}
出現次數必須大于一半，其大小情況不必有嚴格要求，因為只要次數大于一半，該出現最多的數字一定是中間的那個 data[data.size() / 2]
3.
第三種情況
不是未排序的數組
但是有一個數字的出現次數大于數組元素數目的一半
時間復雜度：O(N)
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 int findMaxTimesNumber(const vector<int>& data)
6 {
7 if (data.size() <= 0)
8 {
9 return -10000;
10 }
11 int ret = data[0];
12 int count = 1;
13 for (vector<int>::size_type i = 1; i != data.size(); ++i)
14 {
15 if (data[i] == ret)
16 {
17 ++count;
18 }
19 else
20 {
21 --count;
22 if (count == 0)
23 {
24 count = 1;
25 ret = data[i];
26 }
27 }
28 }
29 if (count > 1)
30 {
31 return ret;
32 }
33 else
34 {
35 return -10000;
36 }
37 }
38
39 int main()
40 {
41 vector<int> data;
42 int n;
43 while (cin >> n)
44 {
45 data.push_back(n);
46 }
47 cout << findMaxTimesNumber(data) << endl;
48 return 0;
49 }
posted @
2011-12-29 12:29 unixfy 閱讀(1154) |
評論 (0) |
編輯 收藏求字符串中包含所有字符的最小全集子串
http://www.vanjor.org/blog/2011/05/find-dic-substring/
這其實也是一個最短文摘生成方法
實現方式是：用兩個 left 和 right 指針順序掃描母字符串。
時間復雜度：O(N)
實現：
1 #include <iostream>
2 #include <string>
3 #include <map>
4 #include <cstring>
5 using namespace std;
6
7 string foo(const string& s, const string& t)
8 {
9 int tmap[256], ts[256];
10 memset(tmap, 0, sizeof (tmap));
11 memset(ts, 0, sizeof (ts));
12 int tSize = 0;
13 for (string::size_type i = 0; i != t.size(); ++i)
14 {
15 if (tmap[t[i]] == 0)
16 {
17 tmap[t[i]] = 1;
18 ++tSize;
19 }
20 }
21 string::size_type left = 0, right = s.size() - 1, i = 0, j = 0;
22 int count = 0;
23 while (i < s.size() && tmap[s[i]] == 0)
24 {
25 ++i;
26 }
27 if (i >= s.size())
28 {
29 return string("Not found!");
30 }
31 bool find = false;
32 for (j = i; j < s.size(); ++j)
33 {
34 if (tmap[s[j]] == 1)
35 {
36 ++ts[s[j]];
37 if (ts[s[j]] == 1)
38 {
39 ++count;
40 if (count == tSize)
41 {
42 find = true;
43 if (j - i < right - left)
44 {
45 left = i;
46 right = j;
47 }
48 while (i < s.size())
49 {
50 if (tmap[s[i]] == 1)
51 {
52 --ts[s[i]];
53 if (ts[s[i]] == 0)
54 {
55 --count;
56 if (j - i < right - left)
57 {
58 left = i;
59 right = j;
60 }
61 ++i;
62 break;
63 }
64 }
65 ++i;
66 }
67 while (i < s.size() && tmap[s[i]] == 0)
68 {
69 ++i;
70 }
71 if (i >= s.size())
72 {
73 if (find)
74 {
75 return s.substr(left, right - left + 1);
76 }
77 else
78 {
79 return string("Not found!");
80 }
81 }
82 }
83 }
84 }
85 }
86 if (find)
87 {
88 return s.substr(left, right - left + 1);
89 }
90 else
91 {
92 return string("Not found!");
93 }
94 }
95
96 int main()
97 {
98 string s, t;
99 while (cin >> s >> t)
100 {
101 cout << foo(s, t) << endl;
102 }
103
104 return 0;
105 }
===
http://www.vanjor.org/blog/2011/05/sorting-collections/http://www.vanjor.org/blog/2011/05/find-dic-substring/http://coolshell.cn/articles/3933.htmlhttp://coolshell.cn/http://jsdo.it/norahiko/oxIy/fullscreenhttp://jsdo.it/
posted @
2011-12-28 23:12 unixfy 閱讀(650) |
評論 (0) |
編輯 收藏
摘要: 來自于《Let's Build A Compiler!》
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 // parse program 2 &n...
閱讀全文
posted @
2011-12-27 17:36 unixfy 閱讀(265) |
評論 (0) |
編輯 收藏
摘要: 通用產品代碼 UPC
來自于《編碼》
幾乎每件商品上都有所謂的條形碼，即通用產品代碼 UPC(Universal Product Code)。其可以標識該商品是哪個廠家生產的，并且是這個廠家的哪個商品。這里面并無價格信息，可以根據其所標識的代碼去查詢賣家的計算機系統得到其價格。UPC 是有寬度各不相同的黑白條碼組成，根據其寬度映射為一個二進制序列，總共有 95 位從左到右依次是：101 三位的...
閱讀全文
posted @
2011-11-18 11:14 unixfy 閱讀(781) |
評論 (0) |
編輯 收藏
摘要: 來自于《編碼》
布萊葉盲文用六個點組成，位置分別為 1 2 3 4 5 6根據六個點是否突起來代表不同的字母，總共有 2 ^ 6 = 64 個情況。
用一個字節表示一個編碼，0-5 位分別對應 1-6 個位置。例如e：@..@..對應的一個字節為00010001即為 17
編碼表如下，brailleCode.txt:
Code highlighting produced by Actipr...
閱讀全文
posted @
2011-11-15 18:20 unixfy 閱讀(416) |
評論 (0) |
編輯 收藏來自于《編碼》
電報中用的莫爾斯編碼，對電報一直感到很神奇，dita data...
基本原理就是用的二進制方式，用兩種形式，即短信號和長信號，分別用兩種形式表示
可以是
點和劃
也可以是
0 和 1
| 和 -
a 和 b
等。
一種編碼最重要的是如何對每個符號進行編碼，這里需要考慮
編碼的效率，哪些是常用的？哪些是非常用的？
編碼的形式，前綴碼？
如何編碼，編碼的實現？
如何解碼，解碼的實現？
莫爾斯已經給出了各個符號的編碼，例如 morseCode.txt：
1 A .-
2 B -
3 C -.-.
4 D -..
5 E .
6 F ..-.
7 G --.
8 H .
9 I ..
10 J .---
11 K -.-
12 L .-..
13 M --
14 N -.
15 O ---
16 P .--.
17 Q --.-
18 R .-.
19 S
20 T -
21 U ..-
22 V -
23 W .--
24 X -..-
25 Y -.--
26 Z --..
27 1 .----
28 2 ..---
29 3 --
30 4 .-
31 5 ..
32 6 -.
33 7 --
34 8 ---..
35 9 ----.
36 10 -----
37 . .-.-.-
38 , --..--
39 ? ..--..
40 : ---
41 ; -.-.-.
42 - -.-
43 / -..-.
44 " .-..-.
45 ' .----.
46 ( -.--.
47 ) -.--.-
48 = --
49 + .-.-.
50 $ -..-
51 | .-.-..
52 _ ..--.-
這樣針對一句話，可以進行編碼了，例如這句話：
Before the police moved in, they set up a battery of klieg lights and aimed them into the park.
編碼得到：
-... . ..-. --- .-. . - .... . .--. --- .-.. .. -.-. . -- --- .
..- . -.. .. -. --..-- - .... . -.-- ... . - ..- .--.
.- -... .- - - . .-. -.-- --- ..-. -.- .-.. .. . --. .-.. ..
--. .... - ... .- -. -.. .- .. -- . -.. - .... . -- .. -. - ---
- .... . .--. .- .-. -.- .-.-.-
在針對這個編碼進行解碼得到：
BEFORE THE POLICE MOVED IN, THEY SET UP A BATTERY OF KLIEG LIGHTS AND AIMED THEM
INTO THE PARK.
字母都是按照大寫處理的。
Before the police moved in, they set up a battery of klieg lights and aimed them
into the park.
-... . ..-. --- .-. . - .... . .--. --- .-.. .. -.-. . -- --- .
..- . -.. .. -. --..-- - .... . -.-- ... . - ..- .--.
.- -... .- - - . .-. -.-- --- ..-. -.- .-.. .. . --. .-.. ..
--. .... - ... .- -. -.. .- .. -- . -.. - .... . -- .. -. - ---
- .... . .--. .- .-. -.- .-.-.-
BEFORE THE POLICE MOVED IN, THEY SET UP A BATTERY OF KLIEG LIGHTS AND AIMED THEM
INTO THE PARK.
這就是莫爾斯電碼。
實現：
1 #include <iostream>
2 #include <fstream>
3 #include <string>
4 #include <map>
5 #include <cctype>
6 using namespace std;
7
8 string encode(const string& sentence, const map<char, string>& encoding)
9 {
10 string tmp;
11 for (string::size_type i = 0; i != sentence.size(); ++i)
12 {
13 map<char, string>::const_iterator cit = encoding.find(static_cast<char>(toupper(sentence[i])));
14 if (cit != encoding.end())
15 {
16 tmp += cit->second;
17 tmp += ' ';
18 }
19 else
20 {
21 tmp += '\t';
22 }
23 }
24 return tmp;
25 }
26
27 string decode(const string& mc, const map<string, char>& decoding)
28 {
29 string tmp, m;
30 for (string::size_type i = 0; i != mc.size(); ++i)
31 {
32 if (mc[i] == ' ')
33 {
34 map<string, char>::const_iterator cit = decoding.find(m);
35 if (cit != decoding.end())
36 {
37 tmp += cit->second;
38 }
39 m.clear();
40 }
41 else if (mc[i] == '\t')
42 {
43 tmp += ' ';
44 }
45 else
46 {
47 m += mc[i];
48 }
49 }
50 return tmp;
51 }
52
53 int main()
54 {
55 ifstream fin("morseCode.txt");
56 if (!fin)
57 {
58 cerr << "File error!" << endl;
59 return 1;
60 }
61 char a;
62 string b;
63 map<char, string> encoding;
64 map<string, char> decoding;
65 while (fin >> a >> b)
66 {
67 encoding[a] = b;
68 decoding[b] = a;
69 }
70 fin.close();
71 string sentence;
72 string mc;
73 while (getline(cin, sentence))
74 {
75 mc = encode(sentence, encoding);
76 cout << mc << endl;
77 sentence = decode(mc, decoding);
78 cout << sentence << endl;
79 }
80 return 0;
81 }
82
posted @
2011-11-15 17:13 unixfy 閱讀(505) |
評論 (0) |
編輯 收藏非遞增序列
給定 10 * 5 的牌，即由 5 組，每組分別是 1 - 10
從每組中隨機選擇一張牌，得到的序列是非遞減的情況有多少種？
例如 1 1 2 5 9 是符合要求的
但是 2 5 3 7 9 是不符合要求的
最簡單的辦法是采用 5 個循環求解
1 #include <iostream>
2 using namespace std;
3
4 int main()
5 {
6 int total = 0;
7 for (int a = 1; a != 11; ++a)
8 {
9 for (int b = a; b != 11; ++b)
10 {
11 for (int c = b; c != 11; ++c)
12 {
13 for (int d = c; d != 11; ++d)
14 {
15 for (int e = d; e != 11; ++e)
16 {
17 ++total;
18 cout << a << ' '
19 << b << ' '
20 << c << ' '
21 << d << ' '
22 << e << endl;
23 }
24 }
25 }
26 }
27 }
28 cout << total << endl;
29 }
得到 2002 種情況。
但是采用 5 個循環的方式只是一種最為直觀的解法，如果改成 m * n 的情況如何辦？
更好的解法應該是用遞歸。
1 #include <iostream>
2 using namespace std;
3
4 int a[100];
5 int total = 0;
6
7 void foo(int t, int k, int m, int n)
8 {
9
10 if (k >= n)
11 {
12 ++total;
13 for (int i = 0; i != n; ++i)
14 {
15 cout << a[i] << ' ';
16 }
17 cout << endl;
18 return;
19 }
20 else
21 {
22 for (int i = t; i != m + 1; ++i)
23 {
24 a[k] = i;
25 ++k;
26 foo(i, k, m, n);
27 --k;
28 }
29 }
30 }
31
32 void bar(int m, int n)
33 {
34 foo(1, 0, m, n);
35 cout << total << endl;
36 }
37
38 int main()
39 {
40 bar(10, 5);
41 }
42
posted @
2011-11-02 19:57 unixfy 閱讀(754) |
評論 (0) |
編輯 收藏