Найти минимальное и максимальное значения с одной рекурсивной структурой Псевдокод - PullRequest
Новая
       28

Найти минимальное и максимальное значения с одной рекурсивной структурой Псевдокод

0 голосов
/ 12 декабря 2018

Я ищу один алгоритм рекурсивной структуры, чтобы найти как максимальные, так и минимальные значения массива.Здесь я обнаружил следующий псевдокод: 

FindMaxAndMin(A, max, min)
    if (|A| == 1)
        if (max < A[1])
            max = A[1]
        if (min > A[1])
            min = A[1]
        return (min, max)
    cen = |A| /2
    l = A[:cen-1]
    h = A[cen:]
    (min, max) = FindMaxAndMin(l, min, max)
    (min, max) = FindMaxAndMin(h, min, max)
    return (min, max)

Поэтому мне было интересно, во-первых, считается ли это одной рекурсивной структурой, поскольку все это происходит при первом if.Если это единственная рекурсивная структура, мне сначала было интересно, что | A |представляет, не может найти его где-нибудь в Интернете, и как это будет работать звонить по вызову, когда, например, A = (3,2,4,1)?

1 Ответ

0 голосов
/ 12 декабря 2018

| | - это просто длина массива

, которую вы можете отладить и выполните следующие действия:

(потому что я использую js, я не могу вернуть 2 значения, поэтому я изменяюсьдля массива

имейте в виду, что minMax [0] = min

и minMax [1] = max

я инициализировал minMax [0] (мин) с MAX_SAFE_INTEGER

и minMax [0] (макс.) с MIN_SAFE_INTEGER ) 

const FindMaxAndMin = (A, minMax)=>{
    if (A.length === 1){
        if (minMax[1] < A[0])
            minMax[1] = A[0]
        if (minMax[0] > A[0])
            minMax[0] = A[0]
        return minMax
    }
    let cen = A.length /2
    let l = A.slice(0,cen)
    let h = A.slice(cen,A.length)
    minMax = FindMaxAndMin(l, minMax)
    minMax = FindMaxAndMin(h, minMax)
    return minMax
  }
  
  console.log(FindMaxAndMin([3,4,1,2],[Number.MAX_SAFE_INTEGER , Number.MIN_SAFE_INTEGER]))
...