Почему у меня превышен лимит памяти?C # - PullRequest
Новая
       22

Почему у меня превышен лимит памяти?C #

0 голосов
/ 03 февраля 2019

Задача:

  1. Последовательность Трибоначи - это последовательность, в которой каждый следующий элемент состоит из суммы трех предыдущих элементов из последовательности.
  2. Напишите компьютерную программу, которая находит N-й элемент последовательности Трибоначи, если вам даны первые три элемента последовательности и число N.
  3. Я включил Ограничения в программу.Эта проблема представлена ​​в системе и существует ограничение по времени.Я превысил предел памяти, превышенный в последних 2 случаях.

Пожалуйста, помогите. 

        BigInteger a = BigInteger.Parse(Console.ReadLine());
        BigInteger b = BigInteger.Parse(Console.ReadLine());
        BigInteger c = BigInteger.Parse(Console.ReadLine());

        var fibonacciNumbers = new List<BigInteger> { a, b, c };
        BigInteger N = BigInteger.Parse(Console.ReadLine());    
        if ((a < -2000000000) || (b < -2000000000) || (c < -2000000000) || (a > 2000000000) || (b > 2000000000) || (c > 2000000000) || (N > 15000) || (N < 1))
        {
            throw new Exception("Argument out of range");
        }

        while (fibonacciNumbers.Count <= N)
        {
            var previous = fibonacciNumbers[fibonacciNumbers.Count - 1];
            var previous2 = fibonacciNumbers[fibonacciNumbers.Count - 2];
            var previous3 = fibonacciNumbers[fibonacciNumbers.Count - 3];
            fibonacciNumbers.Add(previous + previous2 + previous3);
        }

        Console.WriteLine((fibonacciNumbers[(int)N - 1]));

Ответы [ 3 ]

0 голосов
/ 03 февраля 2019

Вы не должны хранить все предыдущие значения последовательности, потому что вам нужно хранить только 3 последних числа для вычисления следующего. 

BigInteger prevPrev = BigInteger.Parse(Console.ReadLine());
BigInteger prev = BigInteger.Parse(Console.ReadLine());
BigInteger current = BigInteger.Parse(Console.ReadLine());

BigInteger N = BigInteger.Parse(Console.ReadLine());

for(int i = 3; i < N; i++)
{
    // calculate next number
    var next = prevPrev + prev + current;

    // shift all numbers
    prevPrev = prev;
    prev = current;
    current = next;
}

return current;
0 голосов
/ 03 февраля 2019

В вашем коде есть некоторые вещи, которые требуют внимания:

  • Зачем вам хранить все предыдущие числа в массиве.Как уже упоминал @ Вадим Мартынов, вам понадобятся только три предыдущих числа (это не число Фибоначчи).
  • Вы используете BigInteger для хранения счета.Вероятно, оно должно соответствовать 32-разрядному знаковому целому числу, потому что это будет уже более 2 миллиардов итераций.Со структурами BigInteger это уже займет слишком много памяти.В конце вашей текущей программы вы уже приведете обратно к int, поэтому здесь нельзя использовать BigInteger.

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

    var a = BigInteger.Parse(Console.ReadLine());
    var b = BigInteger.Parse(Console.ReadLine());
    var c = BigInteger.Parse(Console.ReadLine());

    var N = int.Parse(Console.ReadLine());
    if ((a < -2000000000) || (b < -2000000000) || (c < -2000000000) || (a > 2000000000) || (b > 2000000000) || (c > 2000000000) || (N > 15000) || (N < 1))
        throw new Exception("Argument out of range");

    var fibonacciNumbers = new BigInteger[N];
    fibonacciNumbers[0] = a;
    fibonacciNumbers[1] = b;
    fibonacciNumbers[2] = c;

    for (var i=3; i < N; ++i)
    {
        var previous = fibonacciNumbers[i - 1];
        var previous2 = fibonacciNumbers[i - 2];
        var previous3 = fibonacciNumbers[i - 3];
        fibonacciNumbers[i] = previous + previous2 + previous3;
    }

    Console.WriteLine(fibonacciNumbers[N - 1]);

Но в любом случае лучше не хранить эти элементы в массиве / списке.Я просто хотел прокомментировать другие вопросы, но, пожалуйста, используйте ответ @Vadim Martynov.

0 голосов
/ 03 февраля 2019

ЕСЛИ мы предполагаем, что вам нужно сохранить предыдущие результаты Фибоначчи в списке (если есть какая-либо цель)?

При конфигурации по умолчанию максимальный размер объекта CLR составляет 2 ГБ, даже на 64-битной.

вы сохраняете результаты Фибоначчи в List, который занимает память.вы получаете OutOfMemoryException Когда вы нажимаете 2 ГБ

Вам необходимо превысить ограничение 2 ГБ.Для этого вам нужно добавить gcAllowVeryLargeObjects в app.config

<runtime>
  <gcAllowVeryLargeObjects enabled="true" />
</runtime>

С другой стороны, если вам не нужны все предыдущие значения последовательности Фибоначчи, тогда 

    BigInteger f2 = BigInteger.Parse(Console.ReadLine());
    BigInteger f1 = BigInteger.Parse(Console.ReadLine());
    BigInteger f = BigInteger.Parse(Console.ReadLine());

    BigInteger N = BigInteger.Parse(Console.ReadLine());    
    if ((a < -2000000000) || (b < -2000000000) || (c < -2000000000) || (a > 2000000000) || (b > 2000000000) || (c > 2000000000) || (N > 15000) || (N < 1))
    {
        throw new Exception("Argument out of range");
    }

    while (fibonacciNumbers.Count <= N)
    {
        var fn = f2 + f1 + f;

        f2 = f1;
        f1 = f;
        f = fn;
    }

    Console.WriteLine(fn);
...