存档在 ‘算法/数据结构’ 分类

某算法配置

2014年10月31日

该工程需要glut库,我在网上下载了以下文件,并放入在SoftEngProject目录下新建的一个文件夹3rdl(第三方库的意思):
0.glut.h
1.glut.lib
2.glut.dll
3.glut32.dll
4.glut.lib

在SoftEngProject\GL\glut.h的如下代码
#ifndef __glut_h__
#define __glut_h__
后面添加代码

#ifndef GLUT_DISABLE_ATEXIT_HACK
	#define GLUT_DISABLE_ATEXIT_HACK
#endif
#ifdef WIN32
	#include<windows.h>
#endif
#include <stdlib.h>

/*第一种配置方法*/

一,简单配置(无需修改SoftEngProject\QtProject\Mesh\MeshLoaderQt\MeshLoaderQt.pro)

1.将SoftEngProject\3rdl目录下glut.lib,glut32.lib拷贝到Qt的库下(我的为路径D:\Qt\Qt5.2.1\5.2.1\msvc2012\lib)
2.将SoftEngProject\3rdl目录下glut.dll,glut32.dll拷贝到系统的PATH路径下。(win7_32位一般为C:\Windows\System32)
3.解压SoftEngProject\VRML目录下的david.zip,会看到david.wrl文件
4.编译Qt工程即可,生成的可执行文件路径一般为(以Debug版为例,SoftEngProject\QtProject\Mesh\build-MeshLoaderQt-Desktop_Qt_5_2_1_MSVC2012_32bit-Debug\debug\MeshLoaderQt.exe)

/*第二种配置方法*/

二,标准配置(需修改.\SoftEngProject\QtProject\Mesh\MeshLoaderQt\MeshLoaderQt.pro)
1.将SoftEngProject\3rdl目录下glut.dll,glut32.dll拷贝到系统的PATH路径下。(win7_32位一般为C:\Windows\System32,不想做这一步,可在系统环境变量PATH中添加这些dll的目录)
2.解压SoftEngProject\VRML目录下的david.zip,会看到david.wrl文件
3.修改SoftEngProject\QtProject\Mesh\MeshLoaderQt\MeshLoaderQt.pro最后一行为LIBS += -L../../../3rdl/ -lglut32 -lglu32 -lopengl32

在整数序列中查找缺失的项

2013年9月19日

今天看到一个题目“有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数”前提还不能用位图。想起以前做ACM那段时间,有做过类似的题目,使用异或来找出成双的整数序列中为单的那个数。

来看下面3个题目:
1. n个数,1, 2, 3, …, n,除了其中的一个数以外,其它所有数都出现了2次,要求找出那个数。
将所有的数进行异或,两个相同的数异或结果为0,故最终的结果就是只出现一次的那个数。

2. n个数中,除了2个数以外,其它所有数都出现了2次,找出那两个数。
假设这两个数为A,B,依然用前面异或的思路,最终异或的结果将是A^B的结果。虽然现在不能还不能确定这两个数,但是考虑到异或结果不为0,其结果的二进制表示中,肯定有为1的bit,找出该bit。
这两个数的该bit必定一个为0,一个为1.根据该bit的值是否为1,将原来所有数分为两组,其中一组该bit为0,另外一组该bit为1. 这里再分别对这两组进行异或,得到的两个值就是最终要找的那两个数。

3. 有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数
与上面提到的第2个问题类似,只不过这里所有值都只出现了一次,并且缺失了2个。这里我们把1,2,…,10w这10w个数补充到原数组中,就与问题2一样了,用问题2的解法即可解决该问题。

筛法求素数

2013年9月4日

1. 筛法求素数(只能被1和自身整除的正整数是素数)。
用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。如有:
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
1不是素数,去掉。剩下的数中2最小,是素数,去掉2的倍数,余下的数是:
3 5 7 9 11 13 15 17 19 21 23 25 27 29
剩下的数中3最小,是素数,去掉3的倍数,如此下去直到所有的数都被筛完,求出的素数为:
2 3 5 7 11 13 17 19 23 29
写程序时,采用一个数组,用数组的下标表示自然数,如果一个数不在筛中就将其对应的元素值赋0,如果仍在筛中,则那个元素值为1.

36d6a74bd11373f0c2bbe702a50f4bfbfaed0438.jpg

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<time.h>
using namespace std;
bool key[2010];//true表示是素数
int main()
{
         int n;
         while(scanf("%d",&n)&&n)
         {
                   for(int i=2;i<=sqrt(n+0.0001);i++)
                   {
                            if(!key[i]){
                                     if(i<sqrt(n+0.0001)/i)
                                          for(int j=i*i;j<=n;j+=i)key[j]=true;
                             }
                   }
                   key[1]=true;
                   for(int i=1;i<=n;i++)
                            if(!key[i])printf("%d ",i);
                   printf("\n");
         }
}   

快慢指针求单链表环

2013年8月30日

问题描述:在单向链表中,每个结点都包含一个指向下一个结点的指针,最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点,就会形成一个环,在顺序遍历链表的时候,程序就会陷入死循环。如下即为一个带环的单链表。link_circle
      如何检测一个链表中是否有环,如果检测到环,如何确定环的入口点(即求出环长,环前面的链长)。
      想象一下在跑道上跑步:两个速度不同的人在操场跑道上一圈一圈地跑,他们总会有相遇的时候。因此我们只需要准备两个指针,同时从链表头出发,一个每次往前走一步,另一个每次往前走两步。如果链表没有环,那么经过一段时间,第二个(速度较快的)指针就会到达终点;但如果链表中有环,两个指针就会在环里转圈,并会在某个时刻相遇。
     大家也许会问,这两个指针要在环里转多少圈才能相遇呢?会不会转几千几万圈都无法相遇?
     实际上,第一个(速度慢的)指针在环里转满一圈之前,两个指针必然相遇。不妨设环长为L,第一个指针P1第一次进入环时,第二个指针P2在P1前方第a个结点处(0 < a < L),设经过x次移动后两个指针相遇,那么应该有x = a + 2x (mod L)[因为P1刚进入环,P2已经在环中移动了a步,那么P1在环里移动x步(P1还没有完成一圈)后,P2则应该在环里共移动了2*x+a步,这个2*x+a可能是p2已经遍历该环很多次],由x = a + 2x (mod L)
      当P2未完成一圈时,x = -a;
      当P2已经超出一圈时,x = L-a;
      显然x = L-a即可满足。
     下面这张图可以清晰地表明这种关系,经过x = L-a次移动,P1向前移动了L-a个位置(相当于后退了a),到达P1′处,而P2向前移动了2L-2a个位置(相当于后退了2a),到达P2′处,显然P1′和P2′是同一点。故在P1还未走满一周时,两快慢指针即可相遇。

two_pointers_in_ring

       在知道链表内有环后,求环长是一件非常简单的事情,只要从刚才那个相遇点开始,固定P2,继续移动P1,直到P1与P2再次相遇,所经过的步数就是环长。

       怎么求环前面那段子链的长度呢?很简单,有两种方法:

       1.让P1和P2都回到链表起点,然后让P2先往前走L次(每次往前走一步),然后P1和P2再同时往前走,当它们再次相遇时,P1所走的步数就是环前面的子链长度。道理很简单:设链的总长度为m,那么前边的子链长度为m-l,所以让指针P2先走L次,则剩下m-l次就可以到达环的相遇点,而P1距离环的相遇点距离也为m-l.

      2.让P2固定在相遇点,P1回到链表头,两指针同时移动直到相遇时即为环的入口,而且P1移动的次数即为子链长度。道理也很简单,由上边的图可以知道,快慢指针相遇时,慢指针在环里移动了L-a步(或者认为后退了a步),也即是再移动a步就可以到达环的入口。另外如图当P1最开始进入环时,P2已经在环内移动了a步,我们知道p2移动的距离是P1移动距离的两倍,所以子链的长度即为a。

按a~z,aa~az,ba~bz…za…zz…aaa…aaz,aba~abz…这样的方法进行编号之类问题

2013年8月29日

文件按a~z,aa~az,ba~bz…za…zz…aaa…aaz,aba~abz…这样的方法进行编号。给定任意一个编号,输出文件是第几个文件。
把这些字符串当做26进制数即可:
a–>1
z–>26;
aa–>27
需要做的工作即是进行26进制到10进制的转换。

#include <iostream>
#include <math.h>
using namespace std;

int charToNum(char ch)
{
	return ch - 96;
}
int anyBinaryToDecimal(string num,int binary)
{
	int len = num.size();
	int decimal_num = 0;
	for(int i = 0;i < len; i++)
	{
		decimal_num+=static_cast<int>(charToNum(num[i]) * pow(static_cast<float>(binary),(int)(len - i - 1)));
	}
	return decimal_num;
}

int main()
{
	cout<<anyBinaryToDecimal("aa",26)<<endl;
	system("pause");
}

字符串匹配KMP算法

2013年8月29日

字符串匹配是计算机的基本任务之一。

  举例来说,有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串”ABCDABD”?

许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth。

 这种算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer的文章,我才真正理解这种算法。下面,我用自己的语言,试图写一篇比较好懂的KMP算法解释。

  1.

  首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

  2.

  因为B与A不匹配,搜索词再往后移。

  3.

  就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

  4.

  接着比较字符串和搜索词的下一个字符,还是相同。

  5.

  直到字符串有一个字符,与搜索词对应的字符不相同为止。

  6.

  这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。

  7.

  一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是,设法利用这个已知信息,不要把”搜索位置”移回已经比较过的位置,继续把它向后移,这样就提高了效率。

  8.

  怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

  9.

  已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。查表可知,最后一个匹配字符B对应的”部分匹配值”为2,因此按照下面的公式算出向后移动的位数:

  移动位数 = 已匹配的字符数 – 对应的部分匹配值

  因为 6 – 2 等于4,所以将搜索词向后移动4位。

  10.

  因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2(”AB”),对应的”部分匹配值”为0。所以,移动位数 = 2 – 0,结果为 2,于是将搜索词向后移2位。

  11.

  因为空格与A不匹配,继续后移一位。

  12.

  逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 – 2,继续将搜索词向后移动4位。

  13.

  逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 – 0,再将搜索词向后移动7位,这里就不再重复了。

  14.

  下面介绍《部分匹配表》是如何产生的。

  首先,要了解两个概念:”前缀”和”后缀”。 “前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。

  15.

  ”部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例,

  - ”A”的前缀和后缀都为空集,共有元素的长度为0;

  - ”AB”的前缀为[A],后缀为[B],共有元素的长度为0;

  - ”ABC”的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

  - ”ABCD”的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

  - ”ABCDA”的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为”A”,长度为1;

  - ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为”AB”,长度为2;

  - ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

  16.

  ”部分匹配”的实质是,有时候,字符串头部和尾部会有重复。比如,”ABCDAB”之中有两个”AB”,那么它的”部分匹配值”就是2(”AB”的长度)。搜索词移动的时候,第一个”AB”向后移动4位(字符串长度-部分匹配值),就可以来到第二个”AB”的位置。

大阿里的数星星题目

2013年5月13日

题目:A和B,晚上闲来无事,开始数星星,每次只能数k个,20<=k<=30,A先数,谁数完最后一组谁获胜,问星星总数为4个选项中哪一个的时候,A必胜。(我觉的这个题最后应该补充一句:最后一组可以小于20)u=2826513163,3587603888&fm=59
思路:A第一次数20-30之间。为了让自己胜利,他在游戏最后留给B的星星数为31-50(也就是当剩下31-50颗星星时,无论B怎么数,A一定取胜)。
并且从第二次开始,A数的星星个数为50-B数的星星个数。当这两个条件同时满足时,A一定取胜。 至于为什么是50,现给出解释:
如果是49,则当B数30个时,留给A的是19,不满足条件;当是51,则当B数20个时候,留给A的是31,不满足条件;只有当是50时,无论B怎么数,留给A的都符合条件。此题的关键就是找出这个50。当明白了以上几点的话,下面写出大体公式

星星总数:20~30+50*k+31~50(也就是总数除以50的余数得同时满足开始条件20~30和结束条件31~50)

以第一个选项2013为例,2013%50=13,这个时候得向高位借50,即2013/50=39,2013%50=63.接下来验证63是否满足开始条件和结束条件。63-(20~30)都落在31~50之间,满足条件。(貌似这个题只有选项2013满足)
下面举个反例2888,2888%50=38(38向不向高位借50都不满足,如果借50则余数为88),验证38或88不同时满足初始条件和结束条件。

分叉树递归列方程法解概率问题

2013年5月12日

题目:一个骰子,6面,1个面是 1, 2个面是2, 3个面是3, 问平均掷多少次能使1,2,3都至少出现一次?
这个问题实际上就是求数学期望,至少出现1,2,3各一次的总掷期望数。如下采用分叉树递归列方程法来解决(有该算法资料的同学麻烦发送给我哦creater@vip.qq.com)
这样分叉树的每个节点表示期望的一个结果,每个分叉表示一次投掷结果。将期望出现1、2、3各至少一次的记作L123,将希望出现2,3各至少一次记作L23,其他一次类推。
QQ图片20130513212230
根据这个树状结构和其中的递归关系,这个方程组就是:
L123 = p1 (L23+ 1) + p2 (L13+1) + p3 (L12 + 1) = p1 L23 +p2 L13+ p3 L12 + 1
(以这个L123为例,投掷1的概率是p1而由此得到的结果是需要期待后续2和3各至少出现一次,于是长度期望是L23+ 1,加1是因为投掷了一次,亦即即增进一级)
L23 = p1 L23 +p2 L3+ p3 L2 + 1
L13 = p1 L3 +p2 L13+ p3 L1 + 1
L12 = p1 L2 +p2 L1+ p3 L12 + 1
L1 =p1 ·1 + p2 (L1+1) + p3 (L1 +1) = p2 L1+ p3 L1 + 1
L2 = p1 L2 + p3 L2 + 1
L3 = p1 L3 +p2 L3+ 1
带入p1=1/6,p2=1/3,p3=1/2即可得到。