[Vlad Drakula]

ivank

PHP код:

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 size)

        {

            int m = n*(n+1)/2-1; // сумма всех чисел, кроме первого



            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 = 800;

            int[] m = new int[l];



            for(int j = 0; j < l; j ++)

            {

                m[j] = l - j;

            }



            // Новый тест

            // Требуется сумма всех элементов, кроме элемента из середины массива

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

            int min = 0;

            for (int j = 0; j < l; ++j)

                if (m[j] < m[min])

                    min = j;

            int temp = m[min];

            m[min] = m[l/2];

            m[l/2] = temp;



            // Нужна сумма всех элементов за исключением равных минимальному

            int needed = 0;

            for (int j = 0; j < l; ++j)

                if (m[j] != m[l/2])

                    needed += m[j];





            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);

        }

    }

} 

ivank's time: 00:00:03.7854432
vlad's time: 00:00:00.0300432

еще раз придумаешь новый тест?