Browsed by
月份:2014年12月

[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**

 
3. **Library to Use**
1. Qt (For Graphic User Interface)
2. STL (vector priority_queue sort …)

4. **Develop Plan** [Hard Deadline Week 19 Date:2014-1-14]
1. Core [Time Planned **5Days**]
1. Structure Build & Function Prototype(vector and class) [5-6h and 2 days]
2. make the Functions work [15h and 2days ]
3. Debugging and inmproving [5h 1day]
2. GUI [Time Planned **5Days**]
1. Study Qt Lib in 5 Days
2. Visualizing

*******
**2014-12-30 By VOID001**

先这么放着~  本系列文章会随开发进度进行更新  有一些需要学的东西~~~感觉不错~

明天解决八数码问题 恩

明天解决八数码问题 恩

 

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 is an integer T indicating the number of test cases.

For each test case, there are 3 integers K (1 ≤ K ≤ 106), X (3 ≤ X ≤ 100) and M (10 ≤ M ≤ 106), which are defined in above description.

Output

For each test case, please output the corresponding (S[n] ÷ X) mod M.

Sample Input

culate Prime S
Sample Output 

解决这个问题需要的知识储备为 :

  1. Fibonacci数列的性质
  2. 矩阵快速幂计算Fibonacci
  3. 取模运算的性质 (a/b)%c=(a%b*c)/b

在这里有Fibonacci数列的基本性质 ,   快速幂的知识在这里有,矩阵快速幂的代码在下面 ,理解了快速幂之后很好理解 。

本题首先要读清题目,本题涉及的元素较多 ,滤清思路之后 本题要求的 是 不小于 第 K 个 Prime S 的能被X整除的S 序列里的数字 ,而经过我们小数据打表发现 S序列为Fibonacci数列从第三项开始 也就是 2 3 5 8 13 … 而 Prime S 为 Fibonacci数列里的素数 ,由Fibonacci的性质知,Fibonacci中 第n项为Fibonacci素数的条件是 n为质数 当 n>=5时成立  ,所以我们可以通过这个性质 结合素数表 来获得 第 K个Fibonacci素数在Fibonacci数列里的下标  在代码的注释里有具体例子 。然后 我们就可以往后枚举这个下标 用 矩阵快速幂的方法来求第n个Fibonacci数 ,然后找到能被X整除的 ,并进行 S/X %C = (S%XC)/X 的运算把结果输出即可 由于我的素数生成函数(筛法)把count的初值设置错误 导致开始一直在错, 另外需要注意 p[1] 和 p[2]的值要特殊处理 至于为何前面已经讲过了 

下面是代码

 

快速幂算法 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

 

样例输入

样例输出

复制代码

快速幂的代码 :

复制代码

复制代码

 

这个题的AC代码如下 需要用到费马小定理 模幂周期性的知识

 

复制代码

复制代码

 

 

 

下面是手写的整理笔记 当时不会用公式编辑器请谅解:

构造素数

的既约剩余系

因为

,由引理3可得

也是p的一个既约剩余系。由既约剩余系的性质,

易知

,同余式两边可约去

,得到

这样就证明了费马小定理。[1]

快速幂取模算法

在网站上一直没有找到有关于快速幂算法的一个详细的描述和解释,这里,我给出快速幂算法的完整解释,用的是C语言,不同语言的读者只好换个位啦,毕竟读C的人较多~

所谓的快速幂,实际上是快速幂取模的缩写,简单的说,就是快速的求一个幂式的模(余)。在程序设计过程中,经常要去求一些大数对于某个数的余数,为了得到更快、计算范围更大的算法,产生了快速幂取模算法。我们先从简单的例子入手:求= 几。

算法1.首先直接地来设计这个算法:

int ans = 1;

for(int i = 1;i<=b;i++)

{

ans = ans * a;

}

ans = ans % c;

这个算法的时间复杂度体现在for循环中,为O(b.这个算法存在着明显的问题,如果a和b过大,很容易就会溢出。

那么,我们先来看看第一个改进方案:在讲这个方案之前,要先有这样一个公式:

.这个公式大家在离散数学或者数论当中应该学过,不过这里为了方便大家的阅读,还是给出证明:

引理1:

 

上面公式为下面公式的引理,即积的取余等于取余的积的取余。

 

证明了以上的公式以后,我们可以先让a关于c取余,这样可以大大减少a的大小,

于是不用思考的进行了改进:

算法2:

int ans = 1;

a = a % c; //加上这一句

for(int i = 1;i<=b;i++)

{

ans = ans * a;

}

ans = ans % c;

聪明的读者应该可以想到,既然某个因子取余之后相乘再取余保持余数不变,那么新算得的ans也可以进行取余,所以得到比较良好的改进版本。

算法3:

int ans = 1;

a = a % c; //加上这一句

for(int i = 1;i<=b;i++)

{

ans = (ans * a) % c;//这里再取了一次余

 

}

ans = ans % c;

这个算法在时间复杂度上没有改进,仍为O(b),不过已经好很多的,但是在c过大的条件下,还是很有可能超时,所以,我们推出以下的快速幂算法。

快速幂算法依赖于以下明显的公式,我就不证明了。

 

我们可以看到,如果我们在上式中把a = a mod c;改成a=(a*a) mod c;便可以把时间复杂度变成O(b/2),当然,这样子治标不治本,但是,如果我们每次都把a平方一次取余,便可以显著减少要运算的次数,即进行以下的迭代:

 

形如上式的迭代下去后,当b=0时,所有的因子都已经相乘,算法结束。于是便可以在O(logb的时间内完成了。于是,有了最终的算法:快速幂算法。

算法4:快速幂算法

int ans = 1;

a = a % c;

while(b>0)

{

 

if(b % 2 = = 1)

ans = (ans * a) % c;

b = b/2;

a = (a * a) % c;

}

将上述的代码结构化,也就是写成函数:

int PowerMod(int a, int b, int c)

{

int ans = 1;

a = a % c;

while(b>0)

{

 

if(b % 2 = = 1)

ans = (ans * a) % c;

b = b/2;

a = (a * a) % c;

}

return ans;

}

本算法的时间复杂度为O(logb),能在几乎所有的程序设计(竞赛)过程中通过,是目前最常用的算法之一。

以下内容仅供参考:

扩展:有关于快速幂的算法的推导,还可以从另一个角度来想。

=? 求解这个问题,我们也可以从进制转换来考虑:

将10进制的b转化成2进制的表达式:

那么,实际上,.

 

所以

 

注意此处的要么为0,要么为1,如果某一项,那么这一项就是1,这个对应了上面算法过程中b是偶数的情况,为1对应了b是奇数的情况(不要搞反了哦,读者自己好好分析,可以联系10进制转2进制的方法),我们先计算依次到中的项。计算后一项的结果时用前一项的结果的平方取余,为0项时ans不用再算,为1项时要乘以此项再取余。这个算法和上面的算法在本质上是一样的,读者可以自行分析,这里我说不多说了,希望本文有助于读者掌握快速幂算法的知识点,当然,要真正的掌握,不多练习是不行的。

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

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

好文章,整理收藏。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函数

 

 


4.”蒙格马利”快速幂模算法

 

蒙格马利极速版:


5.素数判断
  根据费马小定理,对于两个互质的素数N和P,必有:N^(P-1)%P=1  费马测试  算法思路是这样的:

对于N,从素数表中取出任意的素数对其进行费马测试,如果取了很多个素数,N仍未测试失败,那么则认为N是素数。当然,测试次数越多越准确,但一般来讲50次就足够了。费马测试并不完全可靠。
现在我们发现了重要的一点,费马定理是素数的必要条件而非充分条件。这种不是素数,但又能通过费马测试的数字还有不少,数学上把它们称为Carmichael数,现在数学家们已经找到所有10 ^ 16以内的Carmichael数,最大的一个是9585921133193329。我们必须寻找更为有效的测试方法。数学家们通过对费马小定理的研究,并加以扩展,总结出了多种快速有效的素数测试方法,目前最快的算法是米勒-拉宾检验算法。
米勒-拉宾检验 wikipedia : Miller–Rabin primality test

    米勒-拉宾检验是一个不确定的算法,只能从概率意义上判定一个数可能是素数,测试用的素数表越多,准确率越高,但并不能确保。算法流程如下:
1.选择T个随机数A,并且有A<N成立。
2.找到R和M,使得N=2*R*M+1成立。
快速得到R和M的方式:N用二进制数B来表示,令C=B-1。因为N为奇数(素数都是奇数),所以C的最低位为0,从C的最低位的0开始向高位统计,一直到遇到第一个1。这时0的个数即为R,M为B右移R位的值。
3.如果A^M%N=1,则通过A对于N的测试,然后进行下一个A的测试
4.如果A^M%N!=1,那么令i由0迭代至R,进行下面的测试
5.如果A^((2^i)*M)%N=N-1则通过A对于N的测试,否则进行下一个i的测试
6.如果i=r,且尚未通过测试,则此A对于N的测试失败,说明N为合数。
7.进行下一个A对N的测试,直到测试完指定个数的A

通过验证得知,当T为素数,并且A是平均分布的随机数,那么测试有效率为1 / ( 4 ^ T )。如果T > 8那么测试失误的机率就会小于10^(-5),这对于一般的应用是足够了。如果需要求的素数极大,或着要求更高的保障度,可以适当调高T的值。

下面是代码:

在2^31-1以下,有一些伪素数可以通过{2,3,5,7,11}的测试,已知的有 29341 = 13 * 37 * 61 , 3215031751 = 151 * 751 * 28351

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

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

 

35 BEST PLACES TO LEARN HOW TO CODE QUICKLY

 

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 to cut hair yourself.

So if you are not someone that has knowledge about coding and designing can you still get into this business? We say yes! Why not? We will guide you to a few brilliant resources where you can learn the basics as well as advanced level coding and you can sharpen your skills while having fun.

The biggest problem in learning coding and designing is that it was never easy, it requires a lot of time and can be really boring. However, we have a list of online resources and websites that simplify coding and make it look like a child play.

These websites are interactive and use the best practices of learning which means one gains instant interest and does not have to sit through the boring process of learning coding and designing the hard way.

With these websites, you can also interact with like minded people and understand and solve problems which can arise over the period of development.  As it is said, “better safe than sorry”. So even if you are good at coding and designing it is better to understand issues other people face before it starts hurting your business.

I make learning how to code, design very simple for you, and don’t believe me see for yourself.

1) MIT Open Courses Ware

MIT course ware has a number of courses related engineering and computer science. It provides all the free resources as exams, assignments, design and analysis algorithms and more.

 

best resources to learn code online - mitopencourseware

2) Mozilla Developer Network 

Mozilla provides a development network for programmers where they can learn new technologies and get a great collection of resources to get you started. This network helps you learn HTML, CSS, Javascript, graphics include tutorials, reference guide, demos and developers guide.

 

mdn

3) The Code Player

The code player helps you learn HTML5, CSS3, Javascript and many more advance technologies that include videos and view source code.

 

best resources to learn code online - codeplayer

4) Codecademy

Join the community of codecademy and learn to code javascript, HTML/CSS, PHP, Python, Ruby and more. Build your profile and start to learn code with free resources and create apps, games and interactive websites.

 

best resources to learn code online - codecademy

5) Udacity

It provides a big number of online computer science, salesforce, mobile development, web development, AI courses, etc and you can also create projects and received a verified completion certificate recognized by the industry.

 

best resources to learn code online - udacity

6) Learneroo

Learn about programming with Java and new skills by solving challenges to learn the basics of Java coding with variables, loops, strings and array.

 

learneroo

7) Koding

 

best resources to learn code online - koding

8) Talent Buddy

Talent Buddy provides a place for programmers where they can find the exercise of languages C, C#, C++, javascript, PHP, Python, Ruby and enjoyable interview oriented way.

 

best resources to learn code online - talentbuddy

9) Code Avengers

Code avengers have courses with code challenges of HTML, CSS, JavaScript to learn how to program games, apps and websites. This is a place where beginners can learn a lot and make awesome projects.

 

best resources to learn code online - codeavengers

10) Plural Sight

 

best resources to learn code online - pluralsight

11) Scratch

Scratch has a great learning community with more than 40 Lac projects. You can create stories, games and animations then share with your friends and family around the world. Join Scratch and make your project.

 

best resources to learn code online - scratch

12) The New Boston

The New Boston is video sharing site for developers, you can get all the videos/tutorials related to your favorite topics as Ajax, C++, Java, PHP, Python, Ruby and many more technologies that you want to learn.

 

best resources to learn code online  - thenewboston

13) Coder Dojo

CoderDojo is the place where programmers to have opportunity to learn how to code. This is free and open source for everyone, join the community and start coding with Dojo.

 

best resources to learn code online - codedojo

14) Udemy

Udemy is the best instructor for programmers to learn how to code. On this site developers can get a lots of courses to learn and get knowledge to improve.

 

best resources to learn code online - udemy

15) Coderace

Coderace is one of the most popular places where you can teach web design, development and iOS easily and get code challenges to solve and improve your knowledge.

 

best resources to learn code online - coderace

16) Programmr

 

best resources to learn code online - programmr

17) Coursera

This is the best online free course provider for programmers. You can get 625 courses to learn how to code easily.

 

best resources to learn code online - courseera

18) Khan Academy

In these tutorials, you’ll learn how to use the JavaScript language and the ProcessingJS library to create fun drawings and animations.

 

best resources to learn code online - khanacademy

19) HTML5 Rocks

HTMl5rocks is the place where HTML developers can learn how to code in HTML and make it useful for your projects. Provides a lot of tutorials that help developers most.

 

best resources to learn code online - html5rocks

20) Learn Python the Hardway

 

learnpython

 

21) Team TreeHouse

Learn from over 1000 videos created by our expert teachers on web design, coding, business, and much more. Our library is continually refreshed with the latest on web technology so you’ll never fall behind.

 

teamtreehouse

22) Lynda

Whether you want to design and create a website for the first time or you’ve been designing websites for years, Lynda’s expert-taught video tutorials have something for you. Learn to use WordPress or jQuery, design with CSS or write HTML, and even publish content.

Every online course includes free video tutorials. Become a member to keep learning, with unlimited access to every course in  library.

lynda

23) Codepen

CodePen is a playground for the front end side of the web. It’s all about inspiration, education, and sharing. Need to build a reduced test case to demonstrate and figure out a bug? CodePen is great for that. Want to show off your latest creation and get feedback from your peers? CodePen is great for that. Want to find example of a particular design pattern for you project? CodePen is great for that.

 

codepen

24) P2PU2  School of Webcraft

Learn web development at School of Webcraft.

 

p2pu

25) Dev Opera

 

dev-opera

26) Code School

Code School teaches web technologies in the comfort of your browser with video lessons, coding challenges and screencasts. Code School opens the door to a new way of learning by combining video, coding in the browser, and gamification to make learning a new technology fun!

codeschool

27) Academic Earth

Academic Earth believes everyone deserves access to a world-class education, which is why we continue to offer a comprehensive collection of free online college courses from the world’s top universities. And now, we take learning outside the classroom with our original series of thought-provoking videos, designed to spark your intellectual curiosity and start a conversation. Watch, learn, share, debate. After all, only through questioning the world around us, can we come to better understand it.

academicearth

28)  Open Learn

 

openlearn

29) W3C

Welcome to the Web Education Community Group Wiki! This page contains resources to help you teach or learn modern web development.

w3c

30) Develop PHP

DevelopPHP.com is a growing educational system packed with videos and written material that you can access 24/7 100% free. The focus here in 2013 is spread between five technologies: HTML, CSS, JavaScript, PHP and MySQL. Learn programming theory, database interaction, web design, animation, graphics editing, vector art, 3D modeling, and much more.

developphp

31) Bloc

 

bioc

32) How to Code

 

howtocode

33) Developers Google

 

css

34) Learnable

 

learnabale

35) Bento Box

 

bento

[MARK]各种字符串hash算法

[MARK]各种字符串hash算法

 

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 结果就是 :

这就是线性探测再散列法处理冲突

代码如下

 

其它方式处理冲突

除了线性探测 我们还有

  1. 平方探测再散列 如果冲突则查看 addr+-1 +-4 +-9 …直到找到空位置为止
  2. 随机探测再散列 如果冲突则查看 addr+-一伪随机整数 直到找到空位置位置
  3. 再哈希法 顾名思义 再次对这个地址值用一个hash函数来处理
  4. 链地址法 把hash值相同的元素都存在同一个链表中
  5. 公共溢出区 ,这个是很实际中应用广泛的实用的方式,建立一个二维表,原理与链地址法相通,不过,这个是有限长度,那么为了处理个别的超出长度的量,建立一个溢出区来处理
以上是我对hash的一点理解和解读 请大神们看了多多批评指正  _(・ω・」 ∠)__(・ω・」 ∠)_ _(・ω・」 ∠)_ _(・ω・」 ∠)_ _(・ω・」 ∠)_爬呀爬_(・ω・」 ∠)_ _(・ω・」 ∠)_ 我们中出了两个叛徒!

 

 

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 consists of several test cases. Each test case consists of a single line containing the 4 coefficients a, b, c, d, separated by one or more blanks.
End of file.
Output
For each test case, output a single line containing the number of the solutions.
Sample Input
1 2 3 -4
1 1 1 1
Sample Output
39088 0
这个题目,如果直接去暴力枚举三重循环的话 ,会导致超时,因此 不能简单枚举来做, 想到另一个方法 我们可以把式子变为

这样之后 ,我们可以先枚举 x1 x2求出 a*x1*x1+b*x2*x2的所有可能值出现的次数 并把次数存在数组里 num[a*x1*x1+b*x2*x2]=次数 然后 再用另一个二重循环枚举x3 x4 来看 c*x3*x3+d*x4*x4里有多少个值和之前重复且异号,然后 就可以直接将次数加上 不过 注意写好 由判断正负性来决定的存储在哪个数组的函数

本题开了两个数组 一个 hashpos存 正的结果 hashneg存负的结果,那么在循环 枚举x3x4的时候 ,就要判断好 什么时候域hashneg对应 什么时候与hashpos对应 我就是因为这个问题错了好几次  在我的这个代码下 应该是 当算出 c*x3^2+d*x4^2<0时 与hashpos对应 而 >=0与hashneg对应 这千万不要搞错!

AC代码如下

改进策略 线性探测再散列+小数组

这个代码能够 AC 不过还有可以继续用hash改进的地方 因为数组开的很大的时候 需要初始化数组的时间也很长,而 两个数字枚举最多产生10000种不同的结果 所以考虑开小数组来节省空间并且用线性探测再散列技术(linear-re hash detection 不知道这么翻译标准么 有待确定) 来处理冲突 那么就有下面的代码了

其中 用了两个数组,一个数组来存储hash映射关系 另一个存 hash(k)出现的次数  注意写好线性探测的循环条件 这个hash是通过一个函数既能查找到已有的映射关系又能建立新的映射关系,具体的代码说明见文章 hash算法基础(超链接)  这代码当时我写了好久然后发现样例不对,找了半天没找到问题后来发现是在散列函数里if后自己多写了个else = = SB了 改了就过了 时间由 1404MS->93MS 内存8988K->1566K hash大法好啊                 _(・ω・」 ∠)_