Рубрики

Проблема пролета запаса

Проблема пролета акций — это финансовая проблема, когда у нас есть серия из n ежедневных котировок цены на акцию, и нам нужно рассчитать интервал цены акции для всех n дней.
Интервал Si цены акции в данный день i определяется как максимальное количество последовательных дней непосредственно перед данным днем, для которых цена акции в текущий день меньше или равна ее цене в данный день. ,
Например, если массив цен на 7 дней задан как {100, 80, 60, 70, 60, 75, 85}, то значения интервала для соответствующих 7 дней равны {1, 1, 1, 2, 1, 4 , 6}

Простой, но неэффективный метод
Пройдите через входной ценовой массив. Для каждого посещаемого элемента перемещайте элементы слева от него и увеличивайте значение диапазона, в то время как элементы слева меньше.

Ниже приведена реализация этого метода.

C ++

// C ++ программа для метода грубой силы
// для расчета значений запаса
#include <bits/stdc++.h>

using namespace std; 

  
// Заполняет массив S [] значениями диапазона

void calculateSpan(int price[], int n, int S[]) 

    // Значение диапазона первого дня всегда 1

    S[0] = 1; 

  

    // Рассчитать значение диапазона оставшихся дней

    // путем линейной проверки предыдущих дней

    for (int i = 1; i < n; i++) 

    

        S[i] = 1; // Инициализировать значение диапазона

  

        // Пройдите влево, пока следующий элемент

        // слева меньше цены [i]

        for (int j = i - 1; (j >= 0) && 

                (price[i] >= price[j]); j--) 

            S[i]++; 

    

  
// Вспомогательная функция для печати элементов массива

void printArray(int arr[], int n) 

    for (int i = 0; i < n; i++) 

        cout << arr[i] << " "

  
// Код драйвера

int main() 

    int price[] = { 10, 4, 5, 90, 120, 80 }; 

    int n = sizeof(price) / sizeof(price[0]); 

    int S[n]; 

  

    // Заполняем значения диапазона в массиве S []

    calculateSpan(price, n, S); 

  

    // выводим рассчитанные значения диапазона

    printArray(S, n); 

  

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для метода грубой силы для расчета значений запаса
#include <stdio.h>

  
// Заполняет массив S [] значениями диапазона

void calculateSpan(int price[], int n, int S[])

{

    // Значение диапазона первого дня всегда 1

    S[0] = 1;

  

    // Рассчитать значение диапазона оставшихся дней путем линейной проверки

    // предыдущие дни

    for (int i = 1; i < n; i++) {

        S[i] = 1; // Инициализировать значение диапазона

  

        // Перемещение влево, когда следующий элемент слева меньше

        // чем цена [я]

        for (int j = i - 1; (j >= 0) && (price[i] >= price[j]); j--)

            S[i]++;

    }

}

  
// Вспомогательная функция для печати элементов массива

void printArray(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        printf("%d ", arr[i]);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int price[] = { 10, 4, 5, 90, 120, 80 };

    int n = sizeof(price) / sizeof(price[0]);

    int S[n];

  

    // Заполняем значения диапазона в массиве S []

    calculateSpan(price, n, S);

  

    // выводим рассчитанные значения диапазона

    printArray(S, n);

  

    return 0;

}

Джава

// Реализация Java для метода грубой силы для расчета значений запаса

  

import java.util.Arrays;

  

class GFG {

    // метод для расчета значений на складе

    static void calculateSpan(int price[], int n, int S[])

    {

        // Значение диапазона первого дня всегда 1

        S[0] = 1;

  

        // Рассчитать значение диапазона оставшихся дней путем линейной проверки

        // предыдущие дни

        for (int i = 1; i < n; i++) {

            S[i] = 1; // Инициализировать значение диапазона

  

            // Перемещение влево, когда следующий элемент слева меньше

            // чем цена [я]

            for (int j = i - 1; (j >= 0) && (price[i] >= price[j]); j--)

                S[i]++;

        }

    }

  

    // Вспомогательная функция для печати элементов массива

    static void printArray(int arr[])

    {

        System.out.print(Arrays.toString(arr));

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        int price[] = { 10, 4, 5, 90, 120, 80 };

        int n = price.length;

        int S[] = new int[n];

  

        // Заполняем значения диапазона в массиве S []

        calculateSpan(price, n, S);

  

        // выводим рассчитанные значения диапазона

        printArray(S);

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Python-программа для метода грубой силы для расчета значений запаса

  
# Заполняет список S [] значениями диапазона

def calculateSpan(price, n, S):

      

    # Значение диапазона первого дня всегда равно 1

    S[0] = 1

  

    # Рассчитать значение диапазона оставшихся дней линейно

    # проверка предыдущих дней

    for i in range(1, n, 1):

        S[i] = 1   # Инициализировать значение диапазона

  

        # Пройдите влево, пока следующий элемент слева

        # меньше, чем цена [я]

        j = i - 1

        while (j>= 0) and (price[i] >= price[j]) :

                       S[i] += 1

                       j -= 1

                         
# Полезная функция для печати элементов массива

def printArray(arr, n):

  

    for i in range(n):

        print(arr[i], end = " ")

  
# Программа драйвера для проверки вышеуказанной функции

price = [10, 4, 5, 90, 120, 80]

n = len(price)

S = [None] * n

  
# Заполните значения диапазона в списке S []
calculateSpan(price, n, S)

  
# вывести рассчитанные значения диапазона
printArray(S, n)

  

  
# Этот код предоставлен Sunny Karira

C #

// реализация C # для метода грубой силы
// для расчета значений запаса

using System;

  

class GFG {

  

    // метод для расчета значений на складе

    static void calculateSpan(int[] price,

                              int n, int[] S)

    {

  

        // Значение диапазона первого дня всегда 1

        S[0] = 1;

  

        // Рассчитать значение диапазона оставшихся

        // дни с линейной проверкой предыдущего

        // дни

        for (int i = 1; i < n; i++) {

            S[i] = 1; // Инициализировать значение диапазона

  

            // Пройдите влево, пока следующий

            // элемент слева меньше

            // чем цена [я]

            for (int j = i - 1; (j >= 0) && (price[i] >= price[j]); j--)

                S[i]++;

        }

    }

  

    // Утилита для печати элементов

    // массива

    static void printArray(int[] arr)

    {

        string result = string.Join(" ", arr);

        Console.WriteLine(result);

    }

  

    // Функция драйвера

    public static void Main()

    {

        int[] price = { 10, 4, 5, 90, 120, 80 };

        int n = price.Length;

        int[] S = new int[n];

  

        // Заполняем значения диапазона в массиве S []

        calculateSpan(price, n, S);

  

        // выводим рассчитанные значения диапазона

        printArray(S);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для метода грубой силы
// для расчета значений запаса

  
// Заполняет массив S [] значениями диапазона

function calculateSpan($price, $n, $S)

{

      

    // Диапазон значений первого

    // день всегда 1

    $S[0] = 1;

      

    // Рассчитать значение диапазона

    // оставшиеся дни линейно

    // проверка предыдущих дней

    for ($i = 1; $i < $n; $i++)

    {

          

        // Инициализировать значение диапазона

        $S[$i] = 1; 

      

        // Пройдите влево, пока следующий

        // элемент слева меньше

        // чем цена [я]

        for ($j = $i - 1; ($j >= 0) && 

            ($price[$i] >= $price[$j]); $j--)

            $S[$i]++;

    }

      

        // выводим рассчитанный

        // значения диапазона

        for ($i = 0; $i < $n; $i++)

        echo $S[$i] . " ";;

      

          
}

  

    // Код драйвера

    $price = array(10, 4, 5, 90, 120, 80);

    $n = count($price);

    $S = array($n);

  

    // Заполняем значения диапазона в массиве S []

    calculateSpan($price, $n, $S);

  
// Этот код предоставлен Sam007
?>


Выход :

1 1 2 4 5 1

Сложность времени вышеупомянутого метода составляет O (n ^ 2). Мы можем рассчитать значения запаса за время O (n).

Метод линейной временной сложности
Мы видим, что S [i] в день i можно легко вычислить, если мы знаем ближайший день, предшествующий i, так что цена больше, чем в тот день, чем цена в день i. Если такой день существует, назовем его h (i), в противном случае мы определим h (i) = -1.
Пролет теперь рассчитывается как S [i] = i — h (i). Смотрите следующую диаграмму.

Чтобы реализовать эту логику, мы используем стек в качестве абстрактного типа данных для хранения дней i, h (i), h (h (i)) и так далее. Когда мы переходим от дня i-1 к i, мы выталкиваем дни, когда цена акции была меньше или равна цене [i], а затем возвращаем значение дня i обратно в стек.

Ниже приводится реализация этого метода.

C ++

// C ++ линейное решение по времени для задачи на складе
#include <iostream>
#include <stack>

using namespace std;

  
// Эффективный метод для расчета стека
// значения на складе

void calculateSpan(int price[], int n, int S[])

{

    // Создаем стек и отправляем индекс первого

    // элемент к нему

    stack<int> st;

    st.push(0);

  

    // Значение диапазона первого элемента всегда равно 1

    S[0] = 1;

  

    // Вычисляем значения диапазона для остальных элементов

    for (int i = 1; i < n; i++) {

        // извлекаем элементы из стека, в то время как стек не

        // пусто, а вершина стека меньше

        // цена [я]

        while (!st.empty() && price[st.top()] <= price[i])

            st.pop();

  

        // Если стек становится пустым, то price [i]

        // больше, чем все элементы слева от него,

        // то есть цена [0], цена [1], .. цена [i-1]. еще

        // цена [i] больше, чем элементы после

        // вершина стека

        S[i] = (st.empty()) ? (i + 1) : (i - st.top());

  

        // Вставить этот элемент в стек

        st.push(i);

    }

}

  
// Вспомогательная функция для печати элементов массива

void printArray(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int price[] = { 10, 4, 5, 90, 120, 80 };

    int n = sizeof(price) / sizeof(price[0]);

    int S[n];

  

    // Заполняем значения диапазона в массиве S []

    calculateSpan(price, n, S);

  

    // выводим рассчитанные значения диапазона

    printArray(S, n);

  

    return 0;

}

Джава

// Java линейное временное решение для задачи на складе

  

import java.util.Stack;

import java.util.Arrays;

  

public class GFG {

    // Эффективный метод для расчета стека

    // значения на складе

    static void calculateSpan(int price[], int n, int S[])

    {

        // Создаем стек и отправляем индекс первого элемента

        // к этому

        Stack<Integer> st = new Stack<>();

        st.push(0);

  

        // Значение диапазона первого элемента всегда равно 1

        S[0] = 1;

  

        // Вычисляем значения диапазона для остальных элементов

        for (int i = 1; i < n; i++) {

  

            // извлекаем элементы из стека, в то время как стек не

            // пусто, а вершина стека меньше

            // цена [я]

            while (!st.empty() && price[st.peek()] <= price[i])

                st.pop();

  

            // Если стек становится пустым, то price [i]

            // больше, чем все элементы слева от него, т.е.

            // цена [0], цена [1], .. цена [i-1]. Еще цена [я]

            // больше элементов после вершины стека

            S[i] = (st.empty()) ? (i + 1) : (i - st.peek());

  

            // Вставить этот элемент в стек

            st.push(i);

        }

    }

  

    // Вспомогательная функция для печати элементов массива

    static void printArray(int arr[])

    {

        System.out.print(Arrays.toString(arr));

    }

  

    // Метод драйвера

    public static void main(String[] args)

    {

        int price[] = { 10, 4, 5, 90, 120, 80 };

        int n = price.length;

        int S[] = new int[n];

  

        // Заполняем значения диапазона в массиве S []

        calculateSpan(price, n, S);

  

        // выводим рассчитанные значения диапазона

        printArray(S);

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Линейное временное решение Python для задачи на складе

  
# Эффективный метод расчета стека

def calculateSpan(price, S):

      

    n = len(price)

    # Создайте стек и вставьте в него индекс первого элемента

    st = [] 

    st.append(0)

  

    # Значение диапазона первого элемента всегда равно 1

    S[0] = 1

  

    # Рассчитать значения диапазона для остальных элементов

    for i in range(1, n):

          

        # Pop элементы из стека, если стек не

        # пусто, а вершина стека меньше цены [i]

        while( len(st) > 0 and price[st[-1]] <= price[i]):

            st.pop()

  

        # Если стек становится пустым, то цена [i] больше

        # чем все элементы слева от него, то есть цена [0],

        # цена [1], .. цена [i-1]. Иначе цена [я]

        # больше элементов после вершины стека

        S[i] = i + 1 if len(st) <= 0 else (i - st[-1])

  

        # Вставьте этот элемент в стек

        st.append(i)

  

  
# Полезная функция для печати элементов массива

def printArray(arr, n):

    for i in range(0, n):

        print (arr[i], end =" ")

  

  
# Программа драйвера для проверки вышеуказанной функции

price = [10, 4, 5, 90, 120, 80]

S = [0 for i in range(len(price)+1)]

  
# Заполните значения диапазона в массиве S []
calculateSpan(price, S)

  
# Распечатать рассчитанные значения диапазона

printArray(S, len(price))

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # решение для линейного времени
// проблема с запасами

using System;

using System.Collections;

  

class GFG {

    // линейное временное решение для

    // проблема складского запаса Стек

    // эффективный метод расчета

    // значения на складе

    static void calculateSpan(int[] price, int n, int[] S)

    {

        // Создать стек и нажать

        // индекс первого элемента к нему

        Stack st = new Stack();

        st.Push(0);

  

        // Диапазон значений первого

        // элемент всегда 1

        S[0] = 1;

  

        // Вычисляем значения диапазона

        // для остальных элементов

        for (int i = 1; i < n; i++) {

  

            // выталкиваем элементы из стека

            // пока стек не пуст

            // и верх стека меньше

            // чем цена [я]

            while (st.Count > 0 && price[(int)st.Peek()] <= price[i])

                st.Pop();

  

            // Если стек становится пустым, то price [i]

            // больше, чем все элементы слева от него, т.е.

            // цена [0], цена [1], .. цена [i-1]. Еще цена [я]

            // больше элементов после вершины стека

            S[i] = (st.Count == 0) ? (i + 1) : (i - (int)st.Peek());

  

            // Вставить этот элемент в стек

            st.Push(i);

        }

    }

  

    // Вспомогательная функция для печати элементов массива

    static void printArray(int[] arr)

    {

        for (int i = 0; i < arr.Length; i++)

            Console.Write(arr[i] + " ");

    }

  

    // Метод драйвера

    public static void Main(String[] args)

    {

        int[] price = { 10, 4, 5, 90, 120, 80 };

        int n = price.Length;

        int[] S = new int[n];

  

        // Заполняем значения диапазона в массиве S []

        calculateSpan(price, n, S);

  

        // выводим рассчитанные значения диапазона

        printArray(S);

    }

}

  
// Этот код предоставлен Арнабом Кунду


Выход:

1 1 2 4 5 1

Сложность времени : O (n). На первый взгляд, это больше, чем O (n). Если мы посмотрим поближе, то увидим, что каждый элемент массива добавляется и удаляется из стека не более одного раза. Таким образом, всего 2n операций. Предполагая, что операция стека занимает O (1) времени, мы можем сказать, что сложность времени составляет O (n).

Вспомогательное пространство : O (n) в худшем случае, когда все элементы отсортированы в порядке убывания.

Другой подход: (без использования стека)

C ++

// C ++ программа для линейного решения времени на складе
// проблема span без использования стека
#include <iostream>
#include <stack>

using namespace std;

  
// Эффективный метод для расчета значений запаса
// реализуем ту же идею без использования стека

void calculateSpan(int A[], int n, int ans[])

{

    // Значение диапазона первого элемента всегда равно 1

    ans[0] = 1;

  

    // Вычисляем значения диапазона для остальных элементов

    for (int i = 1; i < n; i++) {

        int counter = 1;

        while ((i - counter) >= 0 && A[i] > A[i - counter]) {

            counter += ans[i - counter];

        }

        ans[i] = counter;

    }

}

  
// Вспомогательная функция для печати элементов массива

void printArray(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int price[] = { 10, 4, 5, 90, 120, 80 };

    int n = sizeof(price) / sizeof(price[0]);

    int S[n];

  

    // Заполняем значения диапазона в массиве S []

    calculateSpan(price, n, S);

  

    // выводим рассчитанные значения диапазона

    printArray(S, n);

  

    return 0;

}

Джава

// Java программа для линейного времени
// решение проблемы с запасами
// без использования стека

class GFG {

  

    // Эффективный метод для расчета

    // значения диапазона запасов, реализующие

    // та же идея без использования стека

    static void calculateSpan(int A[],

                              int n, int ans[])

    {

        // Значение диапазона первого элемента всегда равно 1

        ans[0] = 1;

  

        // Вычисляем значения диапазона для остальных элементов

        for (int i = 1; i < n; i++) {

            int counter = 1;

            while ((i - counter) >= 0 && A[i] > A[i - counter]) {

                counter += ans[i - counter];

            }

            ans[i] = counter;

        }

    }

  

    // Вспомогательная функция для печати элементов массива

    static void printArray(int arr[], int n)

    {

        for (int i = 0; i < n; i++)

            System.out.print(arr[i] + " ");

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int price[] = { 10, 4, 5, 90, 120, 80 };

        int n = price.length;

        int S[] = new int[n];

  

        // Заполняем значения диапазона в массиве S []

        calculateSpan(price, n, S);

  

        // выводим рассчитанные значения диапазона

        printArray(S, n);

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

C #

// C # программа для линейного времени
// решение проблемы с запасами
// без использования стека

using System;

public class GFG {

  

    // Эффективный метод для расчета

    // значения диапазона запасов, реализующие

    // та же идея без использования стека

    static void calculateSpan(int[] A,

                              int n, int[] ans)

    {

        // Значение диапазона первого элемента всегда равно 1

        ans[0] = 1;

  

        // Вычисляем значения диапазона для остальных элементов

        for (int i = 1; i < n; i++) {

            int counter = 1;

            while ((i - counter) >= 0 && A[i] > A[i - counter]) {

                counter += ans[i - counter];

            }

            ans[i] = counter;

        }

    }

  

    // Вспомогательная функция для печати элементов массива

    static void printArray(int[] arr, int n)

    {

        for (int i = 0; i < n; i++)

            Console.Write(arr[i] + " ");

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        int[] price = { 10, 4, 5, 90, 120, 80 };

        int n = price.Length;

        int[] S = new int[n];

  

        // Заполняем значения диапазона в массиве S []

        calculateSpan(price, n, S);

  

        // выводим рассчитанные значения диапазона

        printArray(S, n);

    }

}
// Этот код предоставлен 29AjayKumar

Выход:

1 1 2 4 5 1

Ссылки:
http://en.wikipedia.org/wiki/Stack_(abstract_data_type)#The_Stock_Span_Problem
http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/Stack-I.pdf

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проблема пролета запаса

0.00 (0%) 0 votes