Оптимизация кода c# с большими числами (long)

265

09 декабря 2016, 08:57

Задача следующая: пользователью дают последовательность чисел от 1 до n, мы проверяем может ли произведение двух чисел из последовательности равняться сумме всех чисел последовательности не считая эти 2 числа. Например: ряд от 1 до n, где n = 26. Произведение чисел 15 и 21 равно сумме всех чисел не считая 21 и 15. Вот код:

using System.Collections.Generic;
public class RemovedNumbers
{
    public static int Sum(long n)
    {
        int sum=0;
        for(int i =1;i<=n;i++)
        {
            sum+=i;
        }
        return sum;
    }
    public static List<int[]> removNb(long n)
    {
        int sum=Sum(n); 
        List <int[]> list = new List<int []>();
        int i,j;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(i*j == sum-(i+j))
                {
                    list.Add(new int [] {i,j});
                    list.Add(new int [] {j,i});
                    return list;
                }
            }
        }
        return list; 
    }
}

Код выполняется за 0.015 секунд, нужно оптимизировать до 0.008, что посоветуете ?

Answer 1

В двойном цикле вы дважды пробегаете все пары чисел (поскольку у вас может быть и i > j и i < j).
Поэтому вы легко можете удвоить скорость.

Вместо:

int i,j;
for(i=1;i<=n;i++)
{
    for(j=1;j<=n;j++)
    {
        ...
    }
}

Запишите:

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

Плюс, как правильно указал @pavel, сумму натурального ряда разумнее вычислять не в цикле, а по формуле:

int sum = n * (n + 1) / 2;

Answer 2

Ну хотя бы так могу посоветовать: (для N = 1) не работает.

 const int N = 26;
 int r;
 int sum = N*(N+1)/2;
 for (int i=N/2;i<=N;i++)
    if ( (sum - i) % (i+1) == 0) 
        if ( (r = (sum - i) / (i+1) ) <= N)
            // {i,r} ответ

Можно дальше чуть подумать в этом направлении.

А причём тут большие числа? Наоборот все числа меньше 1000.

Кстати если ограничения на N небольшие, то есть смысл предпросчитать всё заранее

Answer 3

Увы, не знаком с C#. Но - как минимум достаточно проверять числа, большие n/2 и до n+1, в качестве делителей n(n+1)/2-1 - тогда первое число на единицу меньше, ну, а второе понятно... Получаем как минимум O(n) вместо O(n^2).

На C++ это выглядит так:

bool check(int n, int&k, int&m)
{
    int s = n*(n+1)/2 + 1;
    for(m = n/2 + 1; m <= n + 1; ++m)
        if (s%m == 0)
        {
            k = (n*(n+1)+2)/2/m-1;
            if (k == m-1) continue;
            m--;
            return true;
        }
    return false;
}

Как я понимаю, числа не должны быть одинаковы? типа, 1+2+3+4+5 = 15, 15-6 = 9, 9 = 3*3 - не годится?