1 2 3 4 5 6 7 8 9 | class quick_sort { public: typedef int T; explicit quick_sort(T* src, int beg, int end); private: void sub_sort(int beg, int end); T* m_src; }; |
Archive for ‘之算法神奇’ Category
June 28, 2009
May 25, 2009
1、 并行计算：
并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统，它是将多个处理器通过网络连接以一定的方式有序地组织起来。
May 18, 2009
题目描述：
Felicia的LCD当然与众不同，她的显示器是有许多许多坏点的，此外，
她的显示器只能显示两种颜色（黑和白，分别对应亮与暗），显示器中任意相邻的点不能同时亮，
一次你遇到漂亮的Felicia，你被迷倒了，于是你想帮助她换一台新的LCD，
但她却考你能算出她的LCD一共能够显示出多少种不同的图案，
智慧的你能不能完成这个任务呢？
May 12, 2009
May 10, 2009
题目描述：
算出n!的完整结果，其中n!=1*2*3*…*n
输入：
多组测试数据，一行一组，每行仅一个数n
其中0<=n<=10000
输出：
输出相应的n!的结果，必须精确到个位
样例输入：
10
20
100
样例输出：
3628800
2432902008176640000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
问题描述：
所谓子序列，就是在原序列里删掉若干个元素后剩下的序列，以字符串”abcdefg”为例子，去掉bde得到子序列”acfg”
现在的问题是，给你一个数字序列，你要求出它最长的单调递增子序列。
输入：
多组测试数据，每组测试数据第一行是n(1<=n<=10000)，下一行是n个比1e9小的非负整数
输出：
对于每组测试数据输出一行，每行内容是最长的单调递增子序列的长度
样例输入：
5
1 2 4 8 16
5
1 10 4 9 7
9
0 0 0 1 1 1 5 5 5
样例输出：
5
3
3
题目描述：
给你一个数字，你要判断它是不是回文数字。例如134431或者242这种左右对称的数就叫做回文数。现在你需要编写一个Rev函数，其声明为int Rev(int n);
你需要判断输入的n是不是回文数字，如果是，请返回1，否则请返回0
样例输入：
123
12321
样例输出：
0
1
May 1, 2009
算法：
1 2 3 4 5 | for i = 2:n, for (k = i; k > 1 and a[k] < a[k-1]; k--) swap a[k,k-1] → invariant: a[1..i] is sorted end |
算法性质：
- 稳定
- 需要O(1)的额外空间开销
- 需要O(n2)复杂度的比较和交换。
- 具有自适应性：当待排序序列接近有序时，复杂度为O(n)。
- 开销较低
讨论：
虽然在最坏情况下，插入法排序的复杂度为O(n2)，但当序列已经接近有序(算法具有自适应性)或者问题规模比较小(空间开销很小)时，插入法排序还是一种比较好的选择。所以，插入法排序，通常可以作为其他诸如归并排序、快速排序等递归递归排序的基础。
April 28, 2009
POJ 的一道题，算法很简单：
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 <string> #include <iostream> using namespace std; int main() { int n; char b2h[17] = "0123456789ABCDEF"; int flag[4] = {1,2,4,8}; cin>>n; while (n--) { string s;cin>>s; int len = s.length(); int mod = len%4; int num = 0; for (int i=mod;i>0;i--) { if (s[mod-i]=='1') { num += flag[i-1]; } } if (mod) cout<<b2h[num]; for (int i=mod;i<len;i+=4) { num = 0; for (int j=0;j<4;j++) { if (s[i+j]=='1') { num += flag[3-j]; } } cout<<b2h[num]; } cout<<endl; } return 0; } |