[quote]原帖由[i]天痕[/i]于2005-01-29, 21:48:13发表
ISPRIME_R(n, s)    （其中S是个比较大的数）


1  for i：=1 to s
2    a：=RANDOM(n-1)+1
3    if an-1<>1 (mod n)
4      return FALSE
5  return TRUE [/quote]
没本事赚这钱
那个an是啥东东呢？

是a的n-1次方

这是什么语言的,老六只知道C

delphi.

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

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

作用：寻找1-S之间素数？？ [/quote]
离答案接近了      

最好还能说出原理和缺点

根据糍粑说，Prime的意思就是“素数的”，所以楼主的程序应该是求素数啦。又根据素数的原理：
一个数如果只能被1和它本身整除，那么这个数是一个素数。
如果是一段DELPHI代码，那么用RANDOM函数之前应该运行RANDOMISE函数来分配种子的。其他的，当N比较大时，A的N-1次方可能会超出A的数值范围。
其他的，可能用GOOGLE会更清楚。

[quote]原帖由[i]天痕[/i]于2005-01-29, 23:53:31发表
[quote]原帖由[i]月之魂魄[/i]于2005-01-29, 23:22:53发表
delphi.

作用：寻找1-S之间素数？？ [/quote]
离答案接近了      

最好还能说出原理和缺点  [/quote]


不好意思，我没学过delphi...只学了vc和vb，（当然只是菜鸟级  ）

这段程序好像是用随机方式决定的说～～但后面为虾米要加个mod求余呢？

看起来像加密中用的素数测试，只是随机检查一些数，从概率上保证有很大可能是素数即可。
缺点自然是不能保证一定是素数。

搜索了一下，应该是Miller-Rabin概率测试。

[quote]原帖由[i]Maxwell[/i]于2005-01-30, 9:01:03发表
看起来像加密中用的素数测试，只是随机检查一些数，从概率上保证有很大可能是素数即可。
缺点自然是不能保证一定是素数。 [/quote]
這個應該是答案了，那個數好像叫哥爾既赫猜想甚麼的……

注：b_SPRP是比上面更严格的测试，不仅测t=n-1，还要测还要测t/2。。。直到变成奇数

首先发奖~~

  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次。可见这两种算法的差距是明显的。

下面再来一个，依然是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;
}

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

AA写错了吧
应该是return r吧

看起来像排序，不过没比较。。。难道是洗牌？现在没时间，留给别人猜吧  
不过如果程序不改恐怕只有一个作用。。。溢出

呵呵，变量总应该定义类型吧，虽然由代码能看得出。
其次问这个好像挺无聊的，代码干了什么相信学过编程的都知道，但是用来干什么的可能各有各的用法。

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

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

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

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

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

伪码也不能“an-1”呀，也不给点挑错奖
快给钱~~

[quote]原帖由[i]斜出正入[/i]于2005-01-30, 21:59:25发表
伪码也不能“an-1”呀，也不给点挑错奖
快给钱~~  [/quote]
我选择性失明

好处是快，不好处最坏情况下慢，不稳定。呵呵，随便扯两句。

[quote]原帖由[i]Maxwell[/i]于2005-01-30, 22:38:30发表
好处是快，不好处最坏情况下慢，不稳定。呵呵，随便扯两句。 [/quote]
这怎么看都是在想当然嘛   

肯定没经过实验

呵呵，不好意思，被你说中了，现在在外面，没有时间仔细试试看，等回去有空再看

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

晕，才七个字母，就给拼错了一个  

今天翻书看了一眼，快速排序确实是不稳定的算法，另外在最坏情况下（已排好序）性能退化严重，这个好像说的没错啊
具体到这段程序  等我有空再看。。。

经分析我们看到，快速排序是十分有效的排序法，其平均时间复杂度为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中的数打乱。又如在建立查找二叉树时，可先随机地将待插入的关键字的顺序打乱，然后依次插入树中，以获得较平衡的查找二叉树，提高以后查找关键字的效率。

搞什么东东，眼花！偶只用算法库。

[quote]原帖由[i]oomph[/i]于2005-02-04, 18:07:24发表
搞什么东东，眼花！偶只用算法库。 [/quote]
呵呵，算法库也有不好使的时候。