Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts

Apr 15, 2009

毕业设计(新增加密解密工具)




1:配置文件里新增了加密的相关配置信息。主要就是两个,一个是加密的关键字符串key,另外一个是一个0~1之间的小数(最好只到小数点后两位)。它们共同构成了加密的算法。算法是我从网上搜刮来的,我改了一下。原先我将算法直接用来加密memo里的所有内容,结果发现会发生一些小概率的加密未完成便中止的现象。后来我把它改成逐行读取逐行加密就没有问题了。这个BUG真的很奇怪,我已经发给老大了,希望他有时间帮我看一下。我数学不行啊。哎~~~~~



2:该图是输入明文后的效果。这个加密工具可以独立使用也可以嵌入到任何一个工具里。只要包含了加密工具的单元,调用它的一个hasIniOriginalText或者hasIniDecodedText将其设置为true,就可以讲你要加密的内容从你的工具里导入到加密工具的明文或密文输入栏了。


3:上图为加密后的脚本内容,看不懂吧,呵呵。这个密文可以放到明文显示栏里再加密,每次加密可以更换不同的key和percent,只要记住顺序,一次次的用正确的key和percent解密就行了,很方便很强大吧。。。真是要感谢贴了这个加密算法的蝈蝈。之前上网搜了,论坛问了,有人让我用MD5加密,这个加密虽然破解还是有一定难度,可是解密也很麻烦的。当然,我对MD5甚至对密码学根本是门外汉,上述完全是凭直觉哈。

下边贴出我稍微改动后的加密算法代码:

var
frmCryptograph: TfrmCryptograph;

key: string;
percent1: Double;

implementation

{$R *.dfm}

function TfrmCryptograph.DeCode(aCryptograph, aKey: string): string;
var
i,keylen,codelen:integer;
begin
keylen :=Length(akey);
codelen:=Length(aCryptograph);
SetLength(Result, Length(aCryptograph));
for i:=1 to codelen do
begin
Result[i]:=Chr(Ord(aCryptograph[i])-Ord(aKey[(i mod KeyLen)+1]));
end;
end;


function TfrmCryptograph.EnCode(aCryptograph, aKey: string): string;
var
i,keylen,codelen:integer;
begin
keylen:=Length(akey);
codelen:=Length(aCryptograph);
SetLength(Result, Length(aCryptograph));
for i:=1 to codelen do
begin
Result[i]:=Chr(Ord(aCryptograph[i])+Ord(aKey[(i mod KeyLen)+1]));
end;
end;

function TfrmCryptograph.GetKey(aKey: string; aPercent: Double): string;
var
i:integer;
begin
SetLength(Result,Length(aKey));
for i:=1 to Length(aKey) do
begin
Result[i]:=Chr(Round(Ord(aKey[i])*aPercent));
end;
end;

procedure TfrmCryptograph.btnEncodeClick(Sender: TObject);
var
i: Integer;
str: string;
begin
mmoOutput.Clear;
pgcCryptograph.ActivePageIndex := 1;
for i := 0 to mmoInput.Lines.Count do
begin
str := EnCode(mmoInput.Lines.Strings[i],GetKey(Key,Percent1));
mmoOutput.Lines.Append(str);
end;
end;

procedure TfrmCryptograph.btnDecodeClick(Sender: TObject);
var
i: Integer;
str: string;
begin
mmoInput.Clear;
pgcCryptograph.ActivePageIndex := 0;
for i := 0 to mmoOutput.Lines.Count do
begin
str := DeCode(mmoOutput.Lines.Strings[i],GetKey(Key,Percent1)) ;
mmoInput.Lines.Append(str)
end;
end;

procedure TfrmCryptograph.FormCreate(Sender: TObject);
begin
initEnDeCodeForm(Sender);
pgcCryptograph.ActivePageIndex := 0;
end;

procedure TfrmCryptograph.initEnDeCodeForm(Sender: TObject);
var
iniFileName: string;
begin
{如果没有初始化的明文输入,则清空}
if not withIniOriginalText then
mmoInput.Clear;
if not withIniDecodedText then
mmoOutput.Clear;
iniFileName := 'config\config.ini';
with TInifile.Create(iniFileName) do
begin
percent1 := ReadFloat('CRYPTOGRAPHY','PERCENT',0);
key := ReadString('CRYPTOGRAPHY','KEY','');
Free;
end;
end;

procedure TfrmCryptograph.FormShow(Sender: TObject);
begin
initEnDeCodeForm(Sender);
end;

procedure TfrmCryptograph.btnImportEncodeClick(Sender: TObject);
begin
dlgOpenCryptograph.Execute;
mmoInput.Clear;
try
mmoInput.Lines.LoadFromFile(dlgOpenCryptograph.FileName);
except
Exit;
// MessageBox(Handle, '读取文件出错,请重试', '提示', MB_OK);
end;
end;

procedure TfrmCryptograph.btnExportEncodeClick(Sender: TObject);
begin
dlgSaveCryptograph.Execute;
try
mmoInput.Lines.SaveToFile(dlgSaveCryptograph.FileName + '.sql');
except
Exit;
// MessageBox(Handle, '保存文件出错,请重试', '提示', MB_OK);
end;
end;

procedure TfrmCryptograph.btnImportDecodeClick(Sender: TObject);
begin
dlgOpenCryptograph.Execute;
mmoInput.Clear;
try
mmoInput.Lines.LoadFromFile(dlgOpenCryptograph.FileName);
except
Exit;
// MessageBox(Handle, '读取文件出错,请重试', '提示', MB_OK);
end;
end;

procedure TfrmCryptograph.btnExportDecodeClick(Sender: TObject);
begin
dlgSaveCryptograph.Execute;
try
mmoOutput.Lines.SaveToFile(dlgSaveCryptograph.FileName + '.sql');
except
Exit;
// MessageBox(Handle, '保存文件出错,请重试', '提示', MB_OK);
end;
end;

procedure TfrmCryptograph.FormClose(Sender: TObject;
var Action: TCloseAction);
begin
mmoInput.Clear;
mmoOutput.Clear;
withIniOriginalText := False;
withIniDecodedText := False;
end;

总结:这个小工具花了我一天多的时间。其中大部分用来找加密未完成却中断的原因了,结果还是没有找到,可见要成为IT中的牛人,数学是多么重要。虽然实际开发中未必用得了算法,未必要那么考虑效率,可是,对于一个程序员来说,追求完美是一种天性,应该坚持下去。

Oct 8, 2008

百度一面未果的师兄写的···

我投的是商务引擎研发工程师,后来才知道是百度的核心技术职位。笔试有3道题目,第一道是有N(N〉10000)个集合,每个集合有M个词,每个集合有集合号,现在有个待查找的词序列,返回词所在的集合号。我当时的想法是查找无非有两种好方法,一种是折半,一种是HASH。词没有联系,只能用HASH了。第二道把两个有序的序列,排列成整体有序的序列,我用的是两个折半。
今天的面试感觉发挥不是很好,先自我介绍了一下,主要是项目和获奖情况。然后让我写蜜网项目的architecture,感觉讲得不是很到位。面试官对我做得项目也不是很感兴趣。然后开始C++基础问答,诸如拷贝构造函数作用,缺省拷贝构造函数危害,虚函数作用,指针和引用。缺省拷贝构造函数危害没有答上来,其他的都还勉强。然后是一道证明题,快速排序的时间复杂度,并证明。这个就基本不会了。第一道程序题很简单,写出字符串逆序输出的代码。我很快就写完了,然后面试官就叫我在自己的程序里找错误,费了九牛二虎之力终于把错误找完了,纸上写程序真的不习惯。第二道题,vector类,包括构造函数,插入,查找。。。我就答不上来了,STL只用过LIST。还有一道题,在log文件,包括时间 网址 关键字,统计每个关键字的出现次数。我的想法是用二叉树,面试官点了一下头,应该思路是对的,然后面试官接着问如果这个log文件数据是海量,内存装不下,怎么办。我就不知道怎么回答了。还有一道智力题,大概计算一下下面那条马路的车流量,说出你的思路。我的想法是高峰时段观察5-10分钟,低谷时段考察5-10分钟,平常时段考察5-10分钟,然后加权平均


【swetter想说的话】
当时笔试百度的时候做的是和这位师兄一样的题,只是那时候的数据结构很弱,因此连个一面的机会都没有。后来为了准备微软的笔试,恶补了几天数据结构,C++后的STL也是猛看,现在再看一面的题,C++基础基本没问题,缺省拷贝构造函数的危害就在于它是浅拷贝,不小心就会造成RUNTIME ERROR。第一道程序题将字符串逆序输出,其实就可以使用STL中的vector容器,这是可置换的,使用一个迭代器,和rbegin(),rend()函数就可以轻松搞定。vector类的构造函数,插入,查找。。。只要会用向量类,这个不难。。log文件那个就不行了,哎,数据结构还需要继续加强。。。不然找不到工作啊,加油加油

时间复杂度的计算

一个是时间复杂度,一个是渐近时间复杂度。前者是某个算法的时间耗费,它是该算法所求解问题规模n的函数,而后者是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度,因此,在算法分析时,往往对两者不予区分,经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度,其中的f(n)一般是算法中频度最大的语句频度。 此外,算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度,按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 下面我们通过例子加以说明,让大家碰到问题时知道如何去解决。
1、设三个函数f,g,h分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn 请判断下列关系是否成立: (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n^1.5) (4) h(n)=O(nlgn) 这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n)),这里的"O"是数学符号,它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数,则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C?f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时,两者的比值是一个不等于0的常数。这么一来,就好计算了吧。
◆ (1)成立。题中由于两个函数的最高次项都是n^3,因此当n→∞时,两个函数的比值是一个常数,所以这个关系式是成立的。
◆ (2)成立。与上同理。
◆ (3)成立。与上同理。
◆ (4)不成立。由于当n→∞时n^1.5比nlgn递增的快,所以h(n)与nlgn的比值不是常数,故不成立。 2、设n为正整数,利用大"O"记号,将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0 while(i (2) x=n; // n>1 while (x>=(y+1)*(y+1)) y++; 解答:T(n)=n1/2 ,T(n)=O(n1/2), 最坏的情况是y=0,那么循环的次数是n1/2次,这是一个按平方根阶递增的函数。 (3) x=91; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; 解答: T(n)=O(1), 这个程序看起来有点吓人,总共循环运行了1000次,但是我们看到n没有? 没。这段程序的运行是和n无关的,就算它再循环一万年,我们也不管他,只是一个常数阶的函数。

Oct 3, 2008

【典藏】NP问题

 NP完全问题是不确定性图灵机在P时间内能解决的问题,是世界七大数学难题之一。
  NP完全问题排在百万美元大奖的首位,足见他的显赫地位和无穷魅力。
  数学上著名的NP问题,完整的叫法是NP完全问题,也即“NP COMPLETE”问题,简单的写法,是 NP=P?的问题。问题就在这个问号上,到底是NP等於P,还是NP不等於P。证明其中之一,便可以拿百万美元大奖。
  这个奖还没有人拿到,也就是说,NP问题到底是Polynomial(意思是多项式的),还是Non-Polynomial,尚无定论。
  NP里面的N,不是Non-Polynomial的N,是Non-Deterministic(意思是非确定性的),P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题。
  什么是非确定性问题呢?有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出来。比如,找大质数的问题。有没有一个公式,你一套公式,就可以一步步推算出来,下一个质数应该是多少呢?这样的公式是没有的。再比如,大的合数分解质因数的问题,有没有一个公式,把合数代进去,就直接可以算出,它的因子各自是多少?也没有这样的公式。
  这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式时间内算出来,就叫做多项式非确定性问题。而如果这个问题的所有可能答案,都是可以在多项式时间内进行正确与否的验算的话,就叫完全多项式非确定问题。
  完全多项式非确定性问题可以用穷举法得到答案,一个个检验下去,最终便能得到结果。但是这样算法的复杂程度,是指数关系,因此计算的时间随问题的复杂程度成指数的增长,很快便变得不可计算了。
  人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案,都可以在多项式时间内计算,人们於是就猜想,是否这类问题,存在一个确定性算法,可以在指数时间内,直接算出或是搜寻出正确的答案呢?这就是著名的NP=P?的猜想。
  解决这个猜想,无非两种可能,一种是找到一个这样的算法,只要针对某个特定NP完全问题找到一个算法,所有这类问题都可以迎刃而解了,因为他们可以转化为同一个问题。另外的一种可能,就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。
  前段时间轰动世界的一个数学成果,是几个印度人提出了一个新算法,可以在多项式时间内,证明某个数是或者不是质数,而在这之前,人们认为质数的证明,是个非多项式问题。可见,有些看来好象是非多项式的问题,其实是多项式问题,只是人们一时还不知道它的多项式解而已。
  如果判定问题π∈NP,并且对所有其他判定问题 π∈NP,都有π'多项式变换到π(记为π'∞π),则称判定问题π 是NP完全的。
  对P类,NP类及NP完全问题的研究推动 了计算复杂性理论的发展,产生了许多新概念,提出了许多新方法。但是还有许多难题至今没有解决,P=NP?就是其中之一。许多学者猜想P≠NP,但无法证明。
Powered By Blogger