您的位置：程序门 -> .net技术 -> vb.net



请高手指教下面这个问题的效率最高的算法！？


[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]


请高手指教下面这个问题的效率最高的算法！？[已结贴,结贴人:qiluncjx]
发表于：2007-02-21 21:10:45 楼主
在vb.net中，从一个double型数组arr[100]中查找满足条件   abs（（a*c)/（b*d))-p <0.00001（误差范围）的四个元素a,b,c,d，其中变量p由文本框输入的值决定。求效率最高的算法。。请高手指教！！！

例如数组中有20，40，30，60，50，100,120共七个数值，p=0.25,则可以有
a=20,b=40,c=30,d=60
a=20,b=40,c=50,d=100
a=30,b=60,c=50,d=100
a=20,b=40,c=60,d=120
而不允许存在
a=20,b=40,c=20,d=40
a=20,b=20,c=30,d=12
之类的组合存在
发表于：2007-02-21 21:41:341楼 得分:0
再来一把，统一下

我的初步想法


    排序、过滤重复的

    for   a=0   to   99
        for   b=a+1   to   99
            for   c=b+1   to   99
                for   d=c+1   to   99
                   
                    if   not（   bb   或者   dd   等于0)     then   '（除数不能为0)
                        if   not   四个数彼此相等的   then
                   
                            计算、判断
                        end   if
                    end   if


   

发表于：2007-02-21 21:51:322楼 得分:0
谢谢楼上的，可是不行啊，计算太慢了。。。
发表于：2007-02-22 00:05:003楼 得分:0
效率分为2部分,     1是计算本身的效率;2是计算次数的多少.

计算次数上,思路如下:先用快速排序算法对100个数排序（这里其实用什么算法问题不大,因为就算你用的是最慢的起泡法,总的用时在这个问题上也可以忽略的)

然后因为你计算的是（a*c)/（b*d)   的值约等于p   ,由于这个p的值是用户给出,因此我们难以对特定的p进行优化,最多只能是
如果p接近0,
如果p约等于1/n,（n> =2)
如果p接近1,
对于所有的p大于1,我们都另p=1/p,然后再计算,这样所有的p> 1的情况都不存在了.

对上面3种情况分别使用不同的循环策略,这样可以预期靠更少的循环次数达到结果.

由于你不是需要找出一组满足条件的数字,而是找出全部,那么无论如何循环次数都少不到哪里去的,加上对double做运算本来就不快,所以你别对最后的结果有太多期望,快也不会快到哪里去,因为运算量摆那里了.

至于（a*c)/（b*d)的计算效率,由于对你的具体数组中的内容并不确定,因此也无法靠数字间的特殊性提供投机取巧的算法.

总的说来,你如果希望有好的执行效率,同时又对影响效率的重要因素都不能加以限制,成果不会太大.  

不过事先排序一下是有帮助的,另外在某些地方暂时性地把数字强制转换成int,也能提供一些帮助.但不会太大.


发表于：2007-02-22 00:05:334楼 得分:0
你的问题本身就需要大量计算,所以计算慢是必然的,不是所有问题都有捷径的.
发表于：2007-02-22 00:10:255楼 得分:10
如果你的数组是常量,还可以用查表的方式,这样效率就大大提高了,比如100的数组,其实表里只要一万条记录记录这100个数字两两相乘的结果.然后计算时候就省去了了乘法运算了,变成

（p-0.00001)*x
（p+0.00001)*x
然后去查表.再去重复,会快得多,不过如果你的数组是变化的,就不好办了,因为构建这张表就要很多时间了.
发表于：2007-02-22 00:41:316楼 得分:0
谢谢syeerzy，终于找到了一个学习编程的好地方了。。。这些知识在课堂上可学不来啊！
这个问题我在vb区也问了。结果也有位热心人用vb2005帮我写出来了。。。大家一起参考一下吧！以后还请大家多多指教。。

public   class   form1

        structure   recorditem
                dim   ratio   as   double
                dim   indexa   as   integer
                dim   indexb   as   integer
        end   structure

        private   sub   form1_load（byval   sender   as   system.object,   byval   e   as   system.eventargs)   handles   mybase.load
                dim   data（100)   as   integer
                dim   records（5050)   as   recorditem
                dim   x   as   integer,   y   as   integer,   n   as   integer
                dim   value   as   double

                for   x   =   0   to   99
                        data（x)   =   rnd（)   *   100   +   1
                next   x

                n   =   0
                '   程序开始
                for   x   =   0   to   99
                        for   y   =   x   to   99
                                records（n).ratio   =   data（x)   /   data（y)
                                records（n).indexa   =   x
                                records（n).indexb   =   y
                                n   =   n   +   1
                        next   y
                next   x

                '   排序
                mergesort（records,   0,   5049)

                y   =   -1
                n   =   0
                '   搜索第一对可能值
                while   y   =   -1
                        for   x   =   n   to   5049
                                if   records（n).ratio   *   records（x).ratio   >   1   then
                                        y   =   x
                                        exit   while
                                end   if
                        next   x
                        n   =   n   +   1
                end   while

                '   搜不到的概率很小，万一失败需要倒过来实现

                for   x   =   n   to   5049
                        value   =   records（x).ratio   *   records（y).ratio   -   1
                        if   value   <   0   then
                                y   =   y   +   1
                                continue   for
                        elseif   value   <   0.00001   then
                                msgbox（str（data（records（x).indexa))   +   "* "   +   str（data（records（y).indexa))   +   "/ "   +   str（data（records（x).indexb))   +   "/ "   +   str（data（records（y).indexb)))
                        else
                                y   =   y   -   1
                                if   y   <   x   then   exit   for
                        end   if
                next   x

        end   sub

        public   sub   mergesort（byref   items（)   as   recorditem,   byval   from   as   integer,   byval   endto   as   integer)
                dim   item   as   recorditem
                dim   n   as   integer,   m   as   integer,   k   as   integer

                if   endto   -   from   <=   1   then
                        if   items（from).ratio   >   items（endto).ratio   then
                                item   =   items（from)
                                items（from)   =   items（endto)
                                items（endto)   =   item
                        end   if
                else
                        n   =   from   +   int（（endto   -   from)   /   2)
                        '   分治
                        mergesort（items,   from,   n)
                        mergesort（items,   n   +   1,   endto)
                        m   =   from
                        k   =   n   +   1
                        '   合并
                        while   m   <=   n   and   k   <=   endto
                                if   items（m).ratio   >   items（k).ratio   then
                                        item   =   items（m)
                                        items（m)   =   items（k)
                                        items（k)   =   item
                                        k   =   k   +   1
                                end   if
                                m   =   m   +   1
                        end   while
                end   if
        end   sub
end   class

相关文章
其他资讯

快速检索
分类导航标签a

最新资讯
热门点击