这段程序是干什么的~~ - 设计与修改 - 轩辕春秋文化论坛 20周年


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#1

发表于 2005-1-29 21:58 资料主页个人空间短消息看全部作者

是a的n-1次方

[广告] 《精忠报国岳飞传完整版》火热发布


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#2

发表于 2005-1-29 23:53 资料主页个人空间短消息看全部作者

QUOTE:

原帖由月之魂魄于2005-01-29, 23:22:53发表
delphi.

作用：寻找1-S之间素数？？

离答案接近了

最好还能说出原理和缺点

[广告] 《精忠报国岳飞传完整版》火热发布


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#3

发表于 2005-1-30 16:29 资料主页个人空间短消息看全部作者

首先发奖~~

MAXWELL 2005-01-30 ￥ 200 轩辕通宝

其次精神鼓励一下VAN的算法

其次评价一下算法：

随机化素数判定算法的稳定性取决于，对合数n，在[1,n-1]内满足an-11 (mod n)的a值的个数。记该个数为H(n)，则算法判定n的稳定性为(1-H(n)/n)s。事实上，大多数n的H(n)/n都可达到98%，几乎所有n的H(n)/n都不小于50%，在10000内，H(n)/n小于50%的不超过10个。我们有理由相信，只要s取适当的值，就能使算法有很高的稳定性。如取s=50，则算法对几乎所有n的稳定性至少为1-2-50>99%。即使取较小的s(如s=5)，算法也未必会得到错误的结果。
随机化素数判定算法的时间效率比朴素的素数判定算法高许多，这可从它们各自的时间复杂度看出。实际运用中，取s=50，n=761838257287(是素数)，将两种算法对应程序各运行100次，前者需20秒，后者需102秒。其实素数判定通常只是作为一个子程序被调用，其实际使用次数可能还不止100次。可见这两种算法的差距是明显的。

[广告] 真诚支持说岳，携手共创辉煌


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#4

发表于 2005-1-30 16:38 资料主页个人空间短消息看全部作者

下面再来一个，依然是200通宝~~

AA(A,lo,hi)
{ r:=RANDOM(hi-lo+1)+lo
  交换A[lo]和A[r]
return AAA(A,lo,hi)    <-AAA函数将A[lo..hi]分解为A[lo..p]和A[p+1..hi]两部分}
}

BB(A,lo,hi)
{
if A[lo..hi]足够小 then Sort(A,lo,hi) {排序}

else

begin

if lo < hi
p=AA(A,lo,hi)
BB(A,lo,p)
BB(A,p+1,hi)
end;
}

同样请说出程序做了什么，有什么优点和缺点。

[广告] 真诚支持说岳，携手共创辉煌


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#5

发表于 2005-1-30 21:42 资料主页个人空间短消息看全部作者

QUOTE:

原帖由霸王孙策于2005-01-30, 17:49:14发表
呵呵，变量总应该定义类型吧，虽然由代码能看得出。
其次问这个好像挺无聊的，代码干了什么相信学过编程的都知道，但是用来干什么的可能各有各的用法。

少了一个函数，现在对了。

霸王孙策看见过伪代码定义变量类型的吗

代码干了什么和用来干什么是一个意思，这里主要问的是为什么要这样干。

[广告] 《精忠报国岳飞传完整版》火热发布


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#6

发表于 2005-1-30 21:51 资料主页个人空间短消息看全部作者

的确是排序，而且很明显是快排。
光快排算法一般是不带上（SORT）这段的。

现在修改一下问题，只问这样做快排的好处和缺点~~

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#7

发表于 2005-1-30 22:09 资料主页个人空间短消息看全部作者

QUOTE:

原帖由斜出正入于2005-01-30, 21:59:25发表
伪码也不能“an-1”呀，也不给点挑错奖
快给钱~~

我选择性失明

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#8

发表于 2005-1-31 15:36 资料主页个人空间短消息看全部作者

QUOTE:

原帖由Maxwell于2005-01-30, 22:38:30发表
好处是快，不好处最坏情况下慢，不稳定。呵呵，随便扯两句。

这怎么看都是在想当然嘛

肯定没经过实验

[广告] 真诚支持说岳，携手共创辉煌


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#9

发表于 2005-2-3 05:31 资料主页个人空间短消息看全部作者

QUOTE:

原帖由Maxwell于2005-02-01, 18:37:41发表
呵呵，不好意思，被你说中了，现在在外面，没有时间仔细试试看，等回去有空再看

MEXWELL

[广告] 真诚支持说岳，携手共创辉煌


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#10

发表于 2005-2-4 16:00 资料主页个人空间短消息看全部作者

经分析我们看到，快速排序是十分有效的排序法，其平均时间复杂度为O(nlog2n)。但是在最坏情况下，它的时间复杂度为O(n2)，当n较大时，速度就很慢(见本节后部的算法性能对照表)。其实，如果照前面的假设，输入中出现各种排列都是等概率的，那么出现最坏情况的概率小到只有O(1/n!)，且在O()中隐含的常数是很小的。这样看来，快速排序还是相当有价值的。
但是实际情况往往不符合该假设，可能对某个问题来说，我们遇到的输入大部分都是最坏情况或次坏情况。一种解决的办法是不用x=A[lo]划分A[lo..hi]，而用x=A[hi]或x=A[(lo+hi) div 2]或其它的A[lo..hi]中的数来划分A[lo..hi]，这要看具体情况而定。但这并没有解决问题，因为我们可能遇到的这样的输入：有三类，每一类出现的概率为1/3，且每一类分别对于x=A[lo]，x=A[hi]，x=A[(lo+hi) div 2]为它们的最坏情况，这时快速排序就会十分低效。
我们将快速排序随机化后可克服这类问题。随机化快速排序的思想是：每次划分时从A[lo..hi]中随机地选一个数作为x对A[lo..hi]划分。只需对原算法稍作修改就行了。

随机化没有改动原来快速排序的划分过程，故随机化快速排序的时间效率依然依赖于每次划分选取的数在排好序的数组中的位置，其最坏，平均，最佳时间复杂度依然分别为O(n2)，O(nlog2n)，O(nlog2n)，只不过最坏情况，最佳情况变了。最坏，最佳情况不再由输入所决定，而是由随机函数所决定。也就是说，我们无法通过给出一个最坏的输入来使执行时出现最坏情况(除非我们运气不佳)。
正如引论中所提到的，我们现在来分析随机化快速排序的稳定性。按各种排列的出现等概率的假设(该假设不一定成立)，快速排序遇到最坏情况的可能性为O(1/n!)。假设RANDOM(n)产生n个数的概率都相同(该假设几乎一定成立)，则随机化快速排序遇到最坏情况的可能性也为O(1/n!)。如果n足够大，我们就有多于99%的可能性会“交好运”。也就是说，随机化的快速排序算法有很高的稳定性。
下面是原来的快速排序和随机化后的快速排序的性能对照表。

小结
从以上分析看出，执行结果确定的随机化算法原理是：用随机函数全部或部分地抵消最坏输入的作用，使算法的时间效率不完全依赖于输入的好坏。
通过对输入的适当控制，使得执行结果相对稳定，这是设计这一类随机化算法的常用方法。例如，在随机化快速排序算法中，我们每次随机地选取x来划分A[lo..hi]。这一方法的效应等价于在排序前先随机地将A中的数打乱。又如在建立查找二叉树时，可先随机地将待插入的关键字的顺序打乱，然后依次插入树中，以获得较平衡的查找二叉树，提高以后查找关键字的效率。

图片附件: 1.jpg (2005-2-4 16:00, 42.59 K)

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！