Browsed by
Month: December 2014

[Project] Huffman 压缩软件的实现 01 计划及开题报告

[Project] Huffman 压缩软件的实现 01 计划及开题报告

准备写一个Huffman压缩软件 ,通过Huffman编码来实现文件的压缩和解压 计划书如下 Huffman 文件压缩系统 ======== 1. **Functions**: 1. 对任意文件进行压缩 并且生成压缩文件保存在磁盘上 1. 读入文件并且保存在一个字符串数组内 或者保存文件指针 或文件流对象 2. 根据读入的文件 统计出字符出现的频度 频数 保存在一个优先队列内 为下一步编码做准备 3. 根据字符的频度 建立Huffman树(静态链表结构) 并且保存根节点的标号 4. 通过Huffman树来建立符号表 5. 用符号表对原始文件进行编码 并使用位操作生成新的压缩文件并且输出到文件 2. 对经过Huffman压缩的文件进行解压,把解压后的文件保存在磁盘上 1. 读入压缩后的文件并且保存在一个字符串数组内 或者文件指针 文件流对象 2. 读入压缩时使用的Huffman树 3. 依次读取文件的每一个位 并通过Huffman树对文件进行解码 并导出解压后的文件 4. (选作) 将Huffman 的树型结构展示出来(可视化) 2. **Class Definition** //Here to Put classHuffmanTree class HuffmanTree{ private: void createHuffmanTree(); void countFreq(); void generateCodingTable(); void pr_encoding(); void pr_decoding(); int root; vector<StaticHuffmanNode> HuffmanT; string codingTable[300]; string fileStr; public: void encoding(); void decoding(); void…

Read More Read More

明天解决八数码问题 恩

明天解决八数码问题 恩

明天解决八数码问题 恩   http://www.cnblogs.com/goodness/archive/2010/05/04/1727141.html http://blog.csdn.net/ouxijv/article/details/7203027 http://blog.csdn.net/q345852047/article/details/6626684 http://blog.csdn.net/acm_cxlove/article/details/7745323

[转]Fibonacci 数列的基本性质

[转]Fibonacci 数列的基本性质

fibonacci数列的性质: 1.gcd(fib(n),fib(m))=fib(gcd(n,m)) 证明:可以通过反证法先证fibonacci数列的任意相邻两项一定互素,然后可证n>m时gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m)),递归可 求gcd(fib(n),fib(m))=gcd(fib(k),fib(l)),最后k=l,不然继续递归。K是通过展转相减法求出,易证k=gcd(n,m),所以gcd(fib(n),fib(m)) =fib(gcd(n,m))。   2.如果fib(k)能被x整除,则fib(k*i)都可以被x整除。 3.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1 4.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n) 5.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1 6.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1) 7.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1 8.f(n+m)=f(n+1)·f(m)+f(n)*f(m-1) 9.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1) 10.f(2n-1)=[f(n)]^2-[f(n-2)]^2 11.3f(n)=f(n+2)+f(n-2) 12.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]

ZOJ 3707 Calculate Prime S 矩阵快速幂+Fibonacci的性质

ZOJ 3707 Calculate Prime S 矩阵快速幂+Fibonacci的性质

Calculate Prime S Time Limit: 2000MS Memory Limit: 262144KB 64bit IO Format: %lld & %llu Description Define S[n] as the number of subsets of {1, 2, …, n} that contain no consecutive integers. For each S[n], if for all i (1 ≤ i < n) gcd(S[i], S[n]) is 1, we call that S[n] as a Prime S. Additionally, S[1] is also a Prime S. For the Kth minimum Prime S, we’d like to find the minimum S[n]which is multiple of X and not less than the Kth minimum Prime S. Please tell us the corresponding (S[n] ÷ X) mod M. Input There are multiple test cases. The first line of input…

Read More Read More

快速幂算法 NEU 1391

快速幂算法 NEU 1391

本文是从以前的博客搬运而来 导致阅读效果不好请谅解 Orz 1391: Big Big Power 时间限制: 1 Sec  内存限制: 256 MB 提交: 123  解决: 14 题目描述 Calculate the power num a^(b^c) mod 1e9+7 输入 Multiple test cases,each case has three integers a,b and c . a,b,c is less than 1e9;   输出 Output the answer in each line   样例输入 2 3 2 样例输出 512 这道题的解法是快速幂 和费马小定理 正在研究 这是题解AC代码 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 typedef long long LL; 6 const LL mod = 1000000007; 7…

Read More Read More

[转]费马小定理,积模分解公式,高效幂,快速幂模 及 米勒-拉宾检验

[转]费马小定理,积模分解公式,高效幂,快速幂模 及 米勒-拉宾检验

好文章,整理收藏。1.费马小定理: 有N为任意正整数,P为素数,且N不能被P整除(显然N和P互质),则有: N^P%P=N(即:N的P次方除以P的余数是N)   或  (N^(P-1))%P=1 互相变形: 原式可化为: (N^P-N)%P=0 (N*(N^(P-1)-1))%P=0 所以,N*(N^(P-1)-1)是N和P的公倍数 又因为 N与P互质,而互质数的最小公倍数为它们的乘积 所以一定存在正整数M使得等式成立:N*(N^(P-1)-1)=M*N*P 所以N^(P-1)-1=M*P 因为M是整数 所以(N^(P-1)-1)%P=0 即: N^(P-1)%P=1  2.积模分解公式 引理, 若:X%Z=0,则(X+Y)%Z=Y%Z 设有X、Y和Z三个正整数,则必有:(X*Y)%Z=((X%Z)*(Y%Z))%Z 证明: 1. 当X和Y都比Z大时,必有整数A和B使下面的等式成立: X=Z*I+A(1) Y=Z*J+B(2)除模运算的性质 将(1)和(2)代入(X*Y)modZ得: ((Z*I+A)(Z*J+B))%Z 所以 (Z*(Z*I*J+I*A+I*B)+A*B)%Z(3) 所以 Z*(Z*I*J+I*A+I*B)能被Z整除 概据引理,(3)式可化简为:(A*B)%Z 又因为:A=X%Z,B=Y%Z,代入上式,成为原式右边。 2. 当X比Z大而Y比Z小时: X=Z*I+A 代入(X*Y)%Z得: (Z*I*Y+A*Y)%Z 根据引理,转化得:(A*Y)%Z 因为A=X%Z,又因为Y=Y%Z,代入上式,即得到原式右边。 同理,当X比Z小而Y比Z大时,原式也成立。 3. 当X比Z小,且Y也比Z小时,X=X%Z,Y=Y%Z,所以原式成立。  3.快速乘方算法 可参见http://www.cnblogs.com/bl4nk/archive/2011/04/20/2022998.html  中的power函数   unsigned Power(unsigned n, unsigned p) //n^p { unsigned ans = 1; while (p > 1) { if (( p & 1 )!=0)  ans *= n; n *= n;  p /= 2; } return n * ans; }…

Read More Read More

[转] 35 BEST PLACES TO LEARN HOW TO CODE QUICKLY

[转] 35 BEST PLACES TO LEARN HOW TO CODE QUICKLY

  WEB DEVELOMENT 35 BEST PLACES TO LEARN HOW TO CODE QUICKLY MARCH 7, 2014 ROGER   Everyone secretly yearns to be an entrepreneur and with the Tech startup industry and opportunities on a boom these days I see more Online start-up companies than real physical ones. As the name suggests a tech start-up means that your business if more often than not online. For such a venture one needs to understand coding and designing. I mean, how can you think of opening a barber shop without knowing how…

Read More Read More

[MARK]各种字符串hash算法

[MARK]各种字符串hash算法

// RS Hash Function unsigned int RSHash(char* str) { unsigned int b = 378551 ; unsigned int a = 63689 ; unsigned int hash = 0 ; while (*str) { hash = hash * a + (*str ++ ); a *= b; } return (hash & 0x7FFFFFFF ); } // JS Hash Function unsigned int JSHash(char* str) { unsigned int hash = 1315423911 ; while (*str) { hash ^= ((hash << 5 ) + (*str ++ ) + (hash >>…

Read More Read More

hash 算法基础

hash 算法基础

首先来看一下什么是hash hash 实际上就是一个映射函数 ,使得把某一个不满足条件的量(可能难于存储 可能没法表示)映射到一个满足条件的量上 举个简单的例子理解一下 : 某学校要对2014级新生进行入学成绩统计 要用数组来存储学生的信息 而大家的学号都是 2014**** 这样的形式且每人的学号唯一确定  那么如果开一个数组大小为  20150000肯定是足够我们使用了 ,不过 在这个大数组里 ,最多只用了 10000个值,所以我们考虑用一个后四位作为存储的数组下标而不是整个学号 这其实就是一个hash的思想  我们相当于建立了一个hash函数 f(x)=x%10000 这样的话我们节省了空间 同样也使效率变得高 最简单的hash思想 桶排序 参见 HDU 的 1425题 (排序复杂度可以简化到 n) 冲突 我们通过上面学生的例子 能够发现,一个理想的hash函数应该是个一一映射的函数 即仅存在唯一一组y,x使得f(x)=y 但是 ,实际使用的时候 ,hash函数的这个性质很难保证甚至根本不能保证 举个例子 :把1000000个数映射到100个hash表上 (hash表就是指存hash映射关系的那个数组) 那么 一定会有多个不同值映射到了一个地址上 ,这样的现象叫做 冲突(collision)   那么如何解决冲突就成为了很重要的问题 我们在这里介绍几个方式 主要介绍第一个方式 线性探测再散列 线性探测再散列 这个方法的思想就是 如果遇到了冲突,那么就去查找它的下一个地址处是否已经有值,一直走下去 (走到头的话就回到数组首端) 直到遇到没有值的地方或者是又再次回到了f(k)处 结束循环 成功找到的话把值放进去 ,否则hash散列失败 举个例子如下 我们对这六个数字进行散列操作 有 23%7=2 46%7=4 19%7=5 55%7=6 38%7=3 233%7=2 我们会发现 在地址2处产生了冲突,因此我们使用线性探测再散列 按照由左到右的顺序来执行hash 在处理233之前的结果为下图 这时 由于f(233)=2但是 2处已经有值 所以 执行下面操作 :逐次循环后移直到找到hash表内值为空的地方再放入233 结果就是 : 这就是线性探测再散列法处理冲突 代码如下 int hash[MOD]; //存储映射关系 int num[MOD]; //检查hash表该位置是否为空…

Read More Read More

HDU 1496 Equations 数值hash

HDU 1496 Equations 数值hash

题目: Equations Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5612    Accepted Submission(s): 2228 Problem Description Consider equations having the following form: a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 a, b, c, d are integers from the interval [-50,50] and any of them cannot be 0. It is consider a solution a system ( x1,x2,x3,x4 ) that verifies the equation, xi is an integer from [-100,100] and xi != 0, any i ∈{1,2,3,4}. Determine how many solutions satisfy the given equation. Input The input…

Read More Read More