摘要: /Files/unixfy/考勤处理程序-MarkYang.pdf
考勤处理程序
Mark Yang
QQ: 591 247 876
Email: goonyangxiaofang@163.com
一个考勤数据最主要的三项就是：
人名 &n...
阅读全文
posted @
2012-10-25 16:06 unixfy 阅读(495) |
评论 (0) |
编辑 收藏
摘要: K-近邻法的实现
K-近邻法是根据距离最近的 k 个样例的类型来推测该样例的类型。实现中中主要的环节有：·训练样例格式和测试样例格式的定义·样例结构体的定义·训练样例和测试样例的读取·样例距离的计算，欧氏距离·距离矩阵的生成·针对每个测试样例，得到其到每个训练样例的距离，根据距离由小到大排序，更具距离和权重成反比的关系，计算每个类型的总...
阅读全文
posted @
2012-02-14 09:47 unixfy 阅读(4907) |
评论 (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 阅读(9210) |
评论 (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 阅读(1126) |
评论 (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 阅读(631) |
评论 (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 阅读(245) |
评论 (0) |
编辑 收藏
摘要: 通用产品代码 UPC
来自于《编码》
几乎每件商品上都有所谓的条形码，即通用产品代码 UPC(Universal Product Code)。其可以标识该商品是哪个厂家生产的，并且是这个厂家的哪个商品。这里面并无价格信息，可以根据其所标识的代码去查询卖家的计算机系统得到其价格。UPC 是有宽度各不相同的黑白条码组成，根据其宽度映射为一个二进制序列，总共有 95 位从左到右依次是：101 三位的...
阅读全文
posted @
2011-11-18 11:14 unixfy 阅读(741) |
评论 (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 阅读(373) |
评论 (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 阅读(473) |
评论 (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 阅读(726) |
评论 (0) |
编辑 收藏