标签: divide-and-conquer

我最近决定研究大整数的因子算法,这种"分而治之"的算法比简单的迭代方法和素因子方法更快:

def multiply_range(n, m):
    print n, m
    if n == m:
        return n
    if m < n:
        return 1
    else:
        return multiply_range(n, (n+m)/2) * multiply_range((n+m)/2+1, m)

def factorial(n):
    return multiply_range(1, n)

我理解为什么算法有效,它只是递归地将乘法分成更小的部分.我不明白的是为什么这种方法更快.

我正试图解决着名的天际线问题(见gif):

输入

(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23 ,13,29),(24,4,28)

应该返回,其他建筑物后面的点应该消失,Y轴的变化坐标应该在返回的天际线中:

(1,11),(3,13),(9,0),(12,7),(16,3),(19,18),(22,3),(23,13),(29 ,0)

我试图通过对算法使用分而治之的方法来实现,以实现O(n lg n)的运行时间,但是我被困在合并部分.

每当我想到它,我都会感到困惑.例如,我检查哪个天际线是第一个,例如哪个具有较低的x坐标,然后我将其+高度添加到我的新天际线.但后来我遇到了另外两个天际线后面的天际线,我怎么才能发现这个"碰撞"？

我是否首先通过检查left.x2 <right.x1来检查天际是否有任何重叠？但是我想我应该先检查一下？在x轴上重叠优先级,一切都变成了一个鸡蛋大蛋.

也许我觉得太复杂了？我需要的是每个交叉点的最高y坐标集,我应该像这样接近吗？

对于阵列的:一个₁,一个₂,...一个_ķ,...一个_Ñ,一个_ķ是峰值当且仅当一个_K-1 ≤一个_ķ ≥一个_{K + 1}时1 <K和K <N.一个₁是,如果一个峰₁ ≥一个₂和_Ñ是,如果一个峰_N-1 ≤一个_Ñ.目标是从阵列中找到一个峰值.

分而治之的算法如下:

find_peak(a,low,high):
    mid = (low+high)/2
    if a[mid-1] <= a[mid] >= a[mid+1] return mid // this is a peak;
    if a[mid] < a[mid-1] 
        return find_peak(a,low,mid-1) // a peak must exist in A[low..mid-1]
    if a[mid] < a[mid+1]
        return find_peak(a,mid+1,high) // a peak must exist in A[mid+1..high]

为什么这个算法是正确的？我认为它可能会失去一半存在峰值的阵列.

这是个问题,我在接受采访时被问到了.

找到最小和最大数组的最佳时间复杂度是多少？

我回答:O(n).遍历数组,跟踪到目前为止发现的最大值和最小值.非常简单直接前进.

面试官问你可以用分而治之的方法来改善它.我说可能不是.然后谈话继续进行,最后我被要求实施分而治之的方法.

这里是:

public class MinMaxInArray {
    public static int[] findMinMax(int[] array, int i, int j){
        // base cases
        int arrLen = j - i + 1;
        if (arrLen == 1)
            return new int[]{array[i], array[j]};    //j and i are the same

        if (arrLen == 2){
            int min = Math.min(array[i], array[j]);
            int max = Math.max(array[i], array[j])           
            return new int[]{min, max};
        }

        // actual divide and conquer        
        int mid = i + (j-i)/2;
        int[] leftMinMax = findMinMax(array, i, mid);
        int[] …

对不起,我有一个使用强力算法O(n ^ 2),除法和征服O(nlogn)和Kadane算法O(n)来解决最大子阵列问题的任务.(我的代码不同).

" 例如,对于值序列,{?2, 1, ?3, 4, ?1, 2, 1, ?5, 4}具有最大总和的连续子数组是[4, ?1, 2, 1]和6. " - 来自Wiki页面.

我完成了Kadane和BruteForce,其中我所需的输出不仅仅是找到总和,还有找到的子数组的起始索引和结束索引.

我当前的DivideAndConquer代码得到了正确的总和.但是,由于我以递归方式(当然)实现了索引,因此无法看到跟踪索引的方法.我不知道在这种情况下唯一的方法是使用全局变量(我不喜欢)..你能帮忙解决这个问题吗？或者我需要改变整个设计吗？

#include <iostream>

int DivideAndConquer(int[], int);

int main()
{
    // Example 1
    //const int MyArraySize = 16;
    //int MyArray[MyArraySize] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 }; // answer: Index 7 -> 10, sum = 43

    // Example 2
    const int MyArraySize = 8;
    int …

作为家庭作业,我应该采用分而治之的方法来对大整数进行求幂.我知道Karatsuba的乘法算法,我可以应用什么分而治之的算法来得到x ^ y的结果,两者都是大整数？

我有一个整数列表,我试图通过使用递归算法来识别整数列表中的倾角来实现O(log n).下降是紧随其后的任何数字,并且遵循等于或大于其自身的数字,并且遵循,使得x> = dip <= y.只要它们旁边的数字大于或等于这些元素,就可以将第一个和最后一个元素视为倾角.

我已经能够通过简单地遍历列表来实现O(n),但是我正在尝试使用类似于二进制搜索算法的方法来实现更快的结果.我只需要在列表中找到一个下降点.

我的问题是当我将列表分成中点的左侧和右侧时,我最终会使用一个/两个元素到达较小的列表,但它们不一定是坑,因为它们没有考虑到它们切片之外的数字.

谁能帮我？

def find_dip(lst):
     if len(lst) == 1:
          return 0
     elif len(lst) == 2:
          if lst[0] <= lst[1]:
               return 0
          else:
               return 1
     else:
          ans = False
          mid = len(lst) // 2
          print("test")
          if lst[mid-1] >= lst[mid] <= lst[mid+1]:
               ans = mid
          elif ans == False and len(lst[mid:]) > 2:
               if lst[mid] >= lst[mid+1] <= lst[mid+2]:
                    ans = mid+1
          elif ans == False and len(lst[:mid]) > 2:
               if lst[mid-2] >= lst[mid-1] <= lst[mid]: …

我正在尝试使用C++ 库中的lower_bound和upper_bound函数algorithm来查找以下内容：

• 小于或等于数字 X 的最大值。
• 大于或等于数字 X 的最小值。

我写了以下代码：

#include <iostream>
#include <algorithm>

int main() {

    using namespace std;

    int numElems;
    cin >> numElems;

    int ar[numElems];
    for (int i = 0; i < numElems; ++i)
        cin >> ar[i];
    stable_sort(ar,ar+numElems);

    cout << "Input number X to find the largest number samller than or equal to X\n";
    int X;
    cin >> X;

    int *iter = lower_bound(ar,ar+numElems,X);
    if (iter == ar+numElems)
        cout << "Sorry, no …

分而治之和分而治之有什么区别。

在Fomin和Kratsch的《精确指数算法》中，分支和约简算法使用两种类型的规则：

• 归约规则用于简化问题实例或中止算法
• 分支规则用于通过递归解决问题的较小实例来解决问题实例。

对我来说，这听起来很像维基百科上关于分而治之的定义：

分而治之（D＆C）是一种基于多分支递归的算法设计范例。分而治之算法的工作原理是将问题递归分解为两个或多个相同或相关类型的子问题，直到这些子问题变得足够简单以至于可以直接解决。

但是，当比较分支和约简算法（例如k可满足性或计算最大独立集）来划分和征服算法（例如快速排序和合并排序）时，它们对我而言并不相同。

那么分治与分枝，减少之间有区别吗？如果是这样，什么特征使它们与众不同。

假设我们有两个数组 A[n] 和 b[n]，目标是将 A 中的每个元素与 B 中的元素进行比较。然后返回一个列表 result[n]，记录 A 中每个元素的个数大于B 中的元素

例如，

A = [38, 24, 43, 3], B = [9, 82, 10, 11]

由于 38 比 9、10、11 大，所以 result[0] 为 3。则 result 为 [3, 3, 3, 0]。

如果能提供一些伪代码那就最好了。

谢谢。