[ivank]

Vlad Drakula
Влад. Ты неправильно переделал мой код в C#. И не взял мою исправленную функцию из предыдущего поста. Давай помедитируем над разницей вот этого:

static void summ2(int[] num, int n, int m) { int[] way = new int[m+1]; for (int i = 0; i <= m; ++i) way[i] = 0;

и вот этого:

static void summ2(int[] num, int n, int size) { int m = n*(n+1)/2-1; // сумма всех чисел, кроме первого int[] way = new int[m+1]; for (int i = 0; i <= m; ++i) way[i] = 0;

Чуешь разницу? Не вали свои баги на меня. В исправленом коде случае. summ2(m, l, l*l); даёт именно "Всё плохо". Всё за те же 4 секунды. В то время, как твой код на аналогичном тесте вешается (при достаточно больших l, 100 уже более чем достаточно).

Ну и вот очередной тест. Сортировка не поможет. У меня всё те же несколько секунд. (Впредь прошу при тестах моего кода брать мою версию, а не то, что ты криво сконвертировал).

Всего 100 чисел. мой код - 0.08с, понятно что зависимость от l - квадратичная, так что при 1000 числах (в 10 раз больше) уже будет ~10с (в 100 раз дольше). Вуаля:

Код:

using System;

namespace summ
{
    class Class1
    {
        static bool su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
        {
            for(;i < l; i++)
            {
                if(corsize + m[i] == size)
                {
                    for(int j = 0; j <= p; j ++)
                    {
                        Console.Write("{0} + ", m[s[j]]);
                    }

                    Console.WriteLine("{0} = {1};", m[i], size);

                    return true;
                }
                else if(corsize + m[i] < size)
                {
                    s[p + 1] = i;
                    if(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        static void QSort(int[] ar, int size)
        {
            int left, right, ixLeft, ixRight;
            int[] borderLeft = new int[100];
            int[] borderRight = new int[100];
            int stach = 0;
            int copy;
            int x;
            Random r = new Random();
            borderLeft[0] = 0;
            borderRight[0] = size - 1;
            while(stach >= 0)
            {
                ixLeft = left = borderLeft[stach];
                ixRight = right = borderRight[stach];
                stach--;
                
                while(left < right)
                {
                    x = ar[r.Next(left, right)];
                    ixLeft = left;
                    ixRight = right;

                    while(ixLeft <= ixRight)
                    {
 
                        while(ar[ixLeft] > x)
                        {
                            ixLeft++;
                        }
                        while(ar[ixRight] < x)
                        {
                            ixRight--;
                        }
                    
                        if(ixLeft <= ixRight)
                        {
                            copy = ar[ixLeft];
                            ar[ixLeft] = ar[ixRight];
                            ar[ixRight] = copy;
                            ixLeft++;
                            ixRight--;
                        }
                    }

                    if(ixRight - left < right - ixLeft)
                    {
                        stach++;
                        borderLeft[stach] = ixLeft;
                        borderRight[stach] = right;
                        right = ixRight;
                    }
                    else
                    {
                        stach++;
                        borderLeft[stach] = left;
                        borderRight[stach] = ixRight;
                        left = ixLeft;
                    }
                }                
            }
        }

        static void summ(int[] m, int l, int size)
        {
            QSort(m, l);
            int[] s = new int[l];
            su(m, s, 0, -1, l, size, 0);            
        }

        static void summ2(int[] num, int n, int m)
        {
            int[] way = new int[m+1];
            for (int i = 0; i <= m; ++i)
                way[i] = 0;

            way[0] = 1;

            for (int i = 0; i < n; ++i)
                for (int j = m; j > 0; --j)
                    if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)
                        way[j] = num[i];

            if (way[m] == 0)
                Console.WriteLine("Всё плохо");
            else
            {
                Console.Write("Всё хорошо, путь: ");
                for (int i = m; i != 0; i -= way[i])
                    Console.Write("{0} ", way[i]);
                Console.WriteLine("");
            }
        }

        static void Main(string[] args)
        {
            DateTime d1, d2;
            int l = 100;
            int[] m = new int[l];

	    int needed = 0;

            for(int j = 0; j < l; j++)
            {
                m[j] = l+j+1;
                needed += m[j];
            }
            needed -= m[l/2];

            d1 = DateTime.Now;                
            summ2(m, l, needed);
            d2 = DateTime.Now;
            Console.WriteLine("ivank's time: {0}", d2 - d1);

            d1 = DateTime.Now;                
            summ(m, l, needed);
            d2 = DateTime.Now;
            Console.WriteLine("vlad's time: {0}", d2 - d1);
        }
    }
}

Кстати, я вспомнил. Это называется задачей об укладке рюкзака, частный её случай. Это NP-полная задача в общем случае. Её можно решить за "псевдо-полиномиальное" время, что я и делаю. предлагаю просесть всю статью.

Честно гворя, я считал, что в СпбГУ достаточно высокий уровень образования, что бы знать комбинаторику в объёме достаточном для понимания, что для перебора всех комбинаций из n чисел требуется 2^n операций. И что это очень большое число уже при n порядка 30.