概率算法

概率算法求助
问题：一堆二进制，大小0.1-4Kbit不等长度，找出1分布最集中的地区
举例：00000000001000001010010000100111110011110111100000000000110001010001000011100001
                                   这边就是要查找的位置


请教各位大虾，怎么构思！
谢谢 算法
[解决办法]
a[k]表示1~k里1的个数。你要做宽度为m的最密集1，就等价于找i使得a[i+m]-a[i]最大化。
[解决办法]

引用:

Quote: 引用:

a[k]表示1~k里1的个数。你要做宽度为m的最密集1，就等价于找i使得a[i+m]-a[i]最大化。

 可是这个m怎么确定？

看你需求。要理论最密的话m最后肯定取1，但是估计这肯定不是你想要的。
[解决办法]
如果查找次数很多的话，　可以建一棵线段树。
[解决办法]

把首尾都是1，并且这中间0的个数小于1的个数，这样的集合都找出来然后比较
这样应该差不多了吧

[解决办法]
 int[] func(string s)
        {
            int[] a = new int[2];
            int begin = 0, end = 0, n = 0;
            double d = 1;
            double k = 0.45;
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == '1')
                {
                    n = 1;
                    if (begin == 0)
                    {
                        begin = i;
                        end = i;
                    }
                    for (int j = i + 1; j < s.Length; j++)
                    {

                        if (s[j] == '1')
                        {
                            n++;
                            double tmp = (double)n / (j - i + 1);
                            if (tmp >= k)
                            {
                                tmp = tmp * Math.Sqrt(((double)(j - i)));
                                if (tmp > d)
                                {
                                    d = tmp;
                                    begin = i;
                                    end = j;
                                }
                            }
                            else break;

                        }
                    }
                }
            }
            a[0] = begin;
            a[1] = end;
            return a;
        }

看看这个如何
[解决办法]
把1修改成一个较大的正数

把0修改成相应的负数
使得要求的1111100111101111的密度刚好大于0

就可以直接用最大子段和来做了
[解决办法]
总长为n,所求段长为m
令b[i]=0;i<m
  b[i]=a[i]-b[i-m] i>=m
a[i]00000000001000001010010000100111110011110111100000000000110001010001000011100001
b[i]1000001010-1...
然后求b[i]最大子串和

查看更多 下一篇