求助,pascal编程搜索算法的优化,呼叫大牛!!!
发布网友
发布时间：2022-06-23 03:04
共2个回答
热心网友
时间：2024-12-05 15:40
深度搜索每个字母的值
显然O(n!)的复杂度会超时，那就必然要剪枝
下面来说一下优化
对于一个测试数据
5
ABCED
BDACE
EBBAA
一：剪枝：
如最后一列的D,E,A
如果D，E，A的值都已经搜出来一种方案了，那么A =(D+E) mod n 即D+E除以n的余数是A，因为D+E有可能〉n并且进位，所以要mod n，详细一点即，对于搜索出来的D，E，A如果上一位进位则 A=（D+E+1）mod n，不进位则A=（D+E）mod n,不知道是否进位则(A=（D+E+1）mod n)or( A=（D+E）mod n)，如果满足这些条件则继续，否则退出。
如果只知道D，E则（D+E）mod n（如进位则是（D+E+1）mod n）这个数没被赋值到其他的字母上去就可以继续搜，同样只知道E，A和D，A也可以这样剪枝。
E，A：[A-E mod n] (进位则是 (A-E-1) mod n)没被赋给除D外的其它字母
D，A：[A-D mod n] (进位则是 (A-D-1) mod n)没被赋给除E外的其它字母
二：优化：
还有一个优化就是从搜索顺序的优化：搜索顺序的改变也成为大大提高程序效率的关键：从右往左，按照字母出现顺序搜索，有很大程度上提高了先剪掉废枝的情况。
三：注意：
进位情况要特别注意：
（1）
如果D，E，A都知道，那么（D+E）DIV n<>0则进位否则不进（上一位进位则（D+E+1）DIV n<>0 ）
（2）
如果知道D，E那么（D+E）DIV n<>0则进位否则不进（上一位进位则（D+E+1）DIV n<>0 ） 特殊情况：如果上一位不确定是否进位那么又要分情况讨论：○1如果进位，不进位两种情况中只有一种情况合法（即所确定的数符合剪枝条件）,那么就按这种情况确定是不是进位。○2如果两种情况都合法则，如果两种情况的进位是否都相同，那么可以确定这一位是否进位，不同的话则进位状态赋值为待定。
（3）
知道A，E那么 A<E则进位否则不进（上一位进位则（A-1）<E ） 特殊情况：同（2）。
（4）
知道A，D那么 D<E则进位否则不进（上一位进位则（A-1）<D ） 特殊情况：同（2）。
（5）
只知道D,E,A中一个的值，则进位状态待定。
附：
总结：
搜索解决这道题是最容易想到的，但普通的搜索显然会超时，所以剪枝非常重要。
剪枝的原则
1、正确性
枝条不是爱剪就能剪的。如果随便剪枝，把带有最优解的那一分支也剪掉了的话，剪枝也就失去了意义。所以，剪枝的前提是一定要保证不丢失正确的结果。 2、准确性 在保证了正确性的基础上，我们应该根据具体问题具体分析，采用合适的判断手段，使不包含最优解的枝条尽可能多的被剪去，以达到程序“最优化”的目的。可以说，剪枝的准确性，是衡量一个优化算法好坏的标准。 3、高效性 设计优化程序的根本目的，是要减少搜索的次数，使程序运行的时间减少。但为了使搜索次数尽可能的减少，我们又必须花工夫设计出一个准确性较高的优化算法，而当算法的准确性升高，其判断的次数必定增多，从而又导致耗时的增多，这便引出了矛盾。 因此，如何在优化与效率之间寻找一个平衡点，使得程序的时间复杂度尽可能降低，同样是非常重要的。倘若一个剪枝的判断效果非常好，但是它却需要耗费大量的时间来判断、比较，结果整个程序运行起来也跟没有优化过的没什么区别，这样就太得不偿失了。 综上所述，我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。
还有搜索题除了要掌握一般的技巧，也要对每道题的内涵进行挖掘，找到其特性。对症下药才可有用。
热心网友
时间：2024-12-05 15:40
len:longint;
a,b:array[1..100] of longint;
begin
read(n);
a[1]:=1;
for i:=1 to n do
begin
k:=0;
for l:=1 to 100 do
begin
h:=a[l]*i+k;
a[l]:=h mod 10;
k:=h div 10;
end;
k:=0;
for l:=1 to 100 do
begin
h:=b[l]+a[l]+k;
b[l]:=h mod 10;
k:=h div 10;
end;
end;
len:=100;
while b[len]=0 do len:=len-1;
for j:=len downto 1 do
write(b[j]);
end.追问大哥，你丢个程序在这啥也不说，而且我看着似乎不对，你是不是来装牛的？我没的兜给你套着，下次别来装了.
