标签: divide-and-conquer

首先说我有一个问题,计算10亿个Pi的数字,计算一个大数的阶乘,或者在一个大的列表上执行mergesort.我想将问题分成较小的任务,并同时执行每个任务并合并结果.首先,这种类型的并发性的名称是什么？如何在Clojure中执行此操作？

给定形式的2维平面上的一组n个点(x,y),目的是找到所有点的对的数量,(xi,yi)并且(xj, yj)使得连接这两个点的线具有负斜率.

假设没有两个xi人具有相同的价值.假设所有点都在[-100,100]或在其他范围内.

我们有两个大小为n的数据库,包含没有重复的数字.所以,我们总共有2n个元素.可以通过一次查询到一个数据库来访问它们.查询是这样的,你给它ak,它返回该数据库中的第k个最小的条目.我们需要在O(logn)查询中的所有2n个元素中找到第n个最小的条目.我的想法是使用分而治之,但我需要一些帮助来思考这个问题.谢谢!

免责声明:这是一项任务.我不是要求显式代码,只是有足够的帮助来理解所涉及的算法,以便我可以修复代码中的错误.

好的,所以你可能熟悉最大的子阵列问题:计算并返回数组中最大的连续整数块.很简单,但这个任务需要我以三种不同的复杂性来做:O(n ^ 3),O(n ^ 2)和O(n log n).我已经得到了前两个没有太多麻烦(蛮力),但第三个让我头疼......字面意思.

我理解该算法应该如何工作:一个数组被传递给一个函数,该函数递归地将它分成两半,然后比较各个组件以找到每一半中的最大子数组.然后,因为最大子阵列必须完全位于左半部分或右半部分,或者在与两者重叠的部分中,所以必须找到与左右重叠的最大子阵列.比较每种情况的最大子阵列,最大值将是您的返回值.

我相信我已经编写了充分执行该任务的代码,但在评估中我似乎错了.我一直在努力联系教练和助教,但是我觉得我不能随便找到他们中的任何一个.下面是我到目前为止编写的代码.如果你发现任何明显错误,请告诉我.同样,我不是在寻找明确的代码或答案,而是帮助理解我做错了什么.我已经查看了这里提供的所有类似案例,但没有找到任何可以帮助我的东西.我也做了大量的谷歌搜索指导,但这也没有多大帮助.无论如何,这是有问题的代码:

int conquer(int arr[], int first, int mid, int last) {

    int i = 0;
    int maxLeft = 0;
    int maxRight = 0;

    int temp = 0;
    for (i = mid; i >= first; i--) {
        temp = temp + arr[i];
        if (maxLeft < temp) {
            maxLeft = temp;
        }
    }
    temp = 0;
    for (i = (mid + 1); i <= last; i++) {
        temp = temp + arr[i];
        if …

假设坐标(x1,y1)处的一个点支配另一个点(x2,y2),如果x1≤x2且y1≤y2;

我有一组点(x1,y1),....(xn,yn),我想找到支配对的总数.我可以通过将所有点相互比较来使用蛮力来做到这一点,但这需要时间O(n ²).相反,我想使用分而治之的方法在时间O(n log n)中解决这个问题.

现在,我有以下算法:

• 绘制一条垂直线,将点集点分为P _左和_右两个相等的子集.作为基础案例,如果只剩下两点,我可以直接比较它们.

• 递归计算P _left和P _right中支配对的数量

• 一些征服步骤？

问题是我无法看到"征服"步骤应该在这里.我想计算从P _左边到P _右边有多少支配对,但我不知道如何在不比较两个部分中的所有点的情况下这样做,这需要时间O(n ²).

任何人都可以给我一个关于如何做征服步骤的提示吗？

所以y坐标的两半是:{1,3,4,5,5}和{5,8,9,10,12}

我绘制分界线.

可能重复:
在数组中查找缺失数字的最快方法

输入:未排序的数组A [1,..,n],其中包含0,...,n范围内的除整数之外的所有整数

问题是在O(n)时间内确定缺失的整数.A的每个元素以二进制表示,唯一可用的操作是函数位(i,j),它返回A [i]的第j位的值并占用恒定时间.

有任何想法吗？我认为某种分而治之的算法是正确的,但我想不出我应该做什么.提前致谢!

我正在尝试为树木编写一个分而治之的算法.对于除法步骤,我需要一种算法,通过移除节点将给定的无向图G =(V,E)与n个节点和m个边分割成子树.所有子图应具有不包含超过n/2个节点的属性(树应尽可能分割).首先,我尝试以递归方式从树中删除所有叶子以找到最后剩余的节点,然后我尝试在G中找到最长的路径并删除它的中间节点.下面给出的图表显示两种方法都不起作用:

是否有一些工作算法可以满足我的需要(在上述情况下返回节点H).

我需要计算列表中字符串之间的余弦相似度.例如,我有一个超过1000万个字符串的列表,每个字符串必须确定它自己与列表中的每个其他字符串之间的相似性.什么是我可以用来有效和快速完成这项任务的最佳算法？分而治之算法是否适用？

编辑

我想确定哪些字符串与给定字符串最相似,并且能够获得与相似性相关的度量/分数.我认为我想做的事情与群集相符合,群集的数量最初并不为人所知.

如果函数中只有一个递归调用,我就能轻松理解递归.但是,当我在同一个函数中看到两个或多个递归调用时,我真的很困惑.例:

int MaximumElement(int array[], int index, int n)
    {  
        int maxval1, maxval2; 
        if ( n==1 ) return array[index];
        maxval1 = MaximumElement(array, index, n/2); 
        maxval2 = MaximumElement(array, index+(n/2), n-(n/2));
        if (maxval1 > maxval2)
            return maxval1;
        else
            return maxval2;
    }

我理解在每次递归调用期间n会减半的一件事.我只是不明白下一个递归调用是如何工作的.它变得混乱和我的理解,直到那一点崩溃,我放弃了.如果有人可以用一个简洁的例子手动说明,我真的很感激.我已经完成了编程,并打印了输出.但是,我不明白这项工作背后的计算方法.这是我的理解,直到一切都变得一无所获:

int a [] = {1,2,10,15,16,4,8}

初始调用:MaximumElement(a,0,7)

该函数开始:第一次调用:MaximumElement(a,0,7/2)n现在变为7/2 = 3

第二次调用:MaximumElement(2,0,3/2)n现在变为3/2 = 1

满足基本条件,max1得到[0] = 1

这里是所有地狱破裂的地方:第二次递归调用从索引0开始,n =索引+ n/2 = 0 + 1/2 = 0？当我打印值时,程序在第二次调用时显示3作为n的值.

我已经进行了广泛的编程,但我真的对此有一个噩梦.非常感谢有人可以为我打破这个!

这是上面的伪代码,但是看到我编写的java代码(如果你试图运行它可能会让你更容易):

        public int MAXIMUMELEMENT(int a[], int i, int n)
        {
        int max1, max2;

        System.out.println("1: " + …

我正在阅读Robert Sedgewick的算法第4版,他有以下任务:

假设你有一个N层建筑和2个鸡蛋.假设如果鸡蛋被扔掉F楼或更高楼层,鸡蛋就会被打破,否则就会破裂.您的成本模型是投掷次数.设计一个策略来确定F,使某些常数c的投掷数量为~c√F.

任务的第一部分是在2√N步骤中找到F,这是一个解决方案:

第1部分的解决方案:

• 要达到2*sqrt(N),请在楼层sqrt(N),2*sqrt(N),3*sqrt(N),...,sqrt(N)*sqrt(N)下降鸡蛋.(为简单起见,我们假设sqrt(N)是一个整数.)
• 假设蛋在k*sqrt(N)水平处破裂.
• 然后使用第二个蛋,您应该在区间(k-1)*sqrt(N)到k*sqrt(N)中执行线性搜索.
• 总共可以在最多2*sqrt(N)的试验中找到F楼.

他还提供了~c√F部分的提示(第2部分):

第2部分的提示:1 + 2 + 3 + ... k~1/2 k ^ 2.

那么~c√F步骤的算法是什么？