Компьютерный форум OSzone.net  

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)
-   Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)
-   -   Поиск элементов массива, чья сумма равна заданному числу (http://forum.oszone.net/showthread.php?t=71279)

Qwe1 14-09-2006 00:18 484608
Поиск элементов массива, чья сумма равна заданному числу
 
Может кто знает, как реализовать такую штуку: есть массив чисел, необходимо найти такие элменты этого массива, чтобы сумма этих чисел равнялась определенному значению (либо установить, что такой комбинации элемнтов массива нет). Интересует алгоритм или какие-то общие соображения на эту тему. Я делаю так (для комбинации из, к примеру, 4 чисел): цикл по всем возможным комбинациям. Также еще один очень важный вопрос: это (см. код) действительно все возможные комбинации?

Код:
int NUM[] = {10,20,30,40,50, <...>};
int COUNT = sizeof(NUM)/sizeof(int);
int SUM = 35;
int i,j,k,n;

<...>

for(i=0;i<COUNT;i++)
        for(j=0;j<COUNT;j++)
                for(k=0;k<COUNT;k++)
                        for(n=0;n<COUNT;n++)
                        {
                                if((i!=j && i!=k && i!=n) && (j!=k && j!=n) && (k!=n))
                                {
                                        if(NUM[i] + NUM[j] + NUM[k] + NUM[n] == SUM)
                                                printf("%d %d %d %d\n",i,j,k,n);
                                }
                        }

ivank 14-09-2006 01:37 484622
Qwe1
Элементы положительные? Ограничение сверху на сумму есть? Если есть ограничение на сумму и элементы положительные, то можно применить динамическое программирование. Вариант с перебором всех комбинаций работает только при небольшом размере массива.

Gerdewski 14-09-2006 09:02 484673
Каждый новый цикл нужно начинать с элемента, большего на 1 предыдущего.
т.е. не j=0 , а j=i+1 по-быстрее так заработает.
(наверное это имел ввиду ivank)
Складывать нужно обязательно 4 числа? А если сумма 3х, 2х или одно число равно заданному значению, как поступать тогда?

Qwe1 14-09-2006 09:31 484685
ivank
1) Элементы все положительные;
2) "Определенное начение" (с которым идет сравнение) всегда меньше суммы всех элементов (примерно в 3 раза).

Gerdewski
1) У меня изначально (в цикле for) было так i=0, j=1, k=2, n=3, но потом я решил, что для полноты перебора необходимо проинициализировать именно нулями. Так ли это (?)
2) Аналогичные циклы у меня реализованы для 2, 3, ..., 7 переменных. Для 7 переменных, если не ошибаюсь, число комбинаций = число элементов в степени 7. Для 42 элементов имеем 230 539 333 248 комбинаций. На моем компе вычислялось почти 30 минут.

Знал бы, как прикреплять сюда файлы, выложил бы весь исходник :(


ivank 14-09-2006 10:31 484720
Qwe1
Так чему равна максимальная сумма? Приблизительно?

Если перебирать все комбинации, то это будет "цэ из эн по ка" операций, т.е. n!/(k!*(n-k!), где n - размер массива, k - число элементов в комбинации. Это выражение растёт очень быстро, а посему не подходит ни в одном практическом случае. Это я к тому, что перебор - не выход.

Qwe1 14-09-2006 11:00 484742
ivank
"цэ из эн по ка" - это, вроде, число сочетаний - количество способов выбрать K из N различных предметов. Вычисляется по следующей формуле: CNK = ANK/K! = N*(N-1)*...*(N-K+1)/K! = N!/(K!*(N-K)!). Так что, я не прав по поводу числа комбинаций (см. здесь).

Мне нужен хотя бы какой-нибудь способ. Я бы запустил алгоритм "в лоб" на каком-нибудь более-менее мощном компе и получил бы результат (здесь отрицательный результат - тоже результат). Поэтому хотелось бы этот алгоритм хоть как-нибудь соорудить. Если предложенный мною способ вычисления для 4 переменных верный, то я запулю еще для 8-ми переменных и поставлю на вычисление!! Хотя, если кто-то предложит более быстрый и т.д. код, буду рад :)

ivank 14-09-2006 11:30 484762
Qwe1
ВЫ упорно не отвечаете на мой вопрос. Какова максимальная сумма всех элементов? Каков максимальный размер массива? От этого зависит применимость того решения, которое есть у меня. Его асимптотическая сложность O(mn), где m - размер массива, n - максимальная сумма. Затраты памяти - O(n). Таким образом при отсутвии ограничения на максимальную сумму нам банально не хватит времени и памяти.

P.S. В предыдущем посте я наврал. На самом деле при "лобовом подходе" перебирать надо даже SUM(k=1, n, C_n_k). Т.е. сумма всех цэ из эн по ка для всех ка от 1 до эн. Это ещё хуже.

Qwe1 14-09-2006 12:02 484776
Вот реальный пример набора данных: 42 элемента, сумма = 1 233 188, значение для сравнения = 350 000. Сам массив:
int NUM[] = {
197900,70584,65006,39893,27638,
29448,17220,7750,39032,2870,
2010,22386,93275,20090,10906,
36162,4133,40180,64575,34440,
6027,8754,22960,4879,22960,
18311,39893,27638,58896,24108,
22386,2727,36162,4879,4133,
34440,5740,2727,15355,1665,
34440,8610};

Все остальные наборы примерно такие же. Их сумма и значение для сравнения - тоже примерно такого же порядка.

ivank 14-09-2006 12:24 484791
Ну тогда всё просто. (Если среда нормальная 32-битная и не проблема выделить 5 метров памяти).

Примерно так.
Код:
int sum = 0;
int i, j;
for (i = 0; i < size; ++i)
    sum += NUM[i];

int *way = new int[sum+1];
for (i = 0; i < size; ++i)
    way = 0;

way[0] = 1;

for (i = 0; i < size; ++i)
    for (j = sum; j > 0; --j)
        if (j >= NUM[i] && way[j-NUM[i]] != 0)
            way[j] = NUM[i];

// n - требуемая сумма
if (!way[n])
    printf("Всё плохо\n");
else
{
    printf("Всё хорошо, путь:\n");
    for (i = n; i != 0; i -= way[i])
        printf("%d\n", way[i]);
}

delete[] way;
Не проверял, так как сейчас времени нет. Вечером может проверю. Но идея ясна, я надеюсь.

Qwe1 14-09-2006 12:48 484809
ivank
Честно, мне не очень понятно :blush:
Всего 42 элемента. Надо найти такие, чья сумма равнялась 350 000. Теоритически их может быть и 2. Для предложенного набора - не 2 и не 3 точно. Может 6 или 7. А скорее всего - их вообще нет. Это и надо проверить!

Поэтому, если n - требуемая сумма (т.е. 350 000), то way[350000] ??

ivank 14-09-2006 17:01 484927
Qwe1
Ладно. Рассмотрим всё по порядку. Пусть у нас есть m целых положительных элементов a[i] и трубеится найти можно ли из них составить сумму равную n. Создадим массив can[i][k] размера m на n+1. can[i][k] = 1, если мы можем получить каким-то образом суммируя только элементы a[0]...a[i] сумму равную k. Нас интерисует значение can[m][n], т.е. можем ли мы получить используя элементы a[0]...a[m] сумму n.

Очевидно can[0][k] = 0, для всех k != a[0] и k != 0. can[0][0] = 1 и can[0][a[0]] = 1. Т.е. используя один элемент мы можем получить только сумму равную 0 или этому элементу.

Рассмотрим как по массиву can[i-1] можно построить can[i]. Очевидно, что используя i элементов всегда можно получить те же суммы, что и используя i=1 элемент (просто не добавляя к прежним суммам i-й элемент). Т.е. если can[i-1][k]=1, то can[i][k]=1 так же. Кроме того, к любой из прежних сумм мы можем добавить i-й элемент, т.е. если can[i-1][k]=1, то can[i][k+a[i]]=1 так же. Во всех остальных случаях can[i][k]=0.

Реализация вышеописанного в (псевдо)коде будет выглядеть вот так:
Код:
int can[m][max_sum+1], i, j;
for (i = 0; i < m; ++i)
    for (j = 0; j <= max_sum; ++j)
        can[i][j] = 0;
can[0][0] = can[0][a[0]] = 1;
for (i = 1; i < m; ++i)
{
    for (j = 0; j < max_sum; ++j)
        can[i][j] = can[i-1][j];
    for (j = 0; j < max_sum; ++j)
        if (can[i-1][j])
            can[i][j+a[j]] = 1;
}
Пользуясь тем фактом, что у нас в can[i] по сравнению с can[i-1] только дописываются единички, а так же тем, что все элементы мы можем модифицировать массив прям на месте, вместо того, что бы иметь цепочку массивов can[0]...can[m].

Вот так:
Код:
int can[max_sum], i, j;
for (i = 0; i <= max_sum; ++i)
    can[i] = 0;
can[0] = 1;
for (i = 0; i < m; ++i)
    for (j = max_sum; j > 0; --j)
        if (j >= a[i] && can[j-a[i]])
            can[j] = 1;
В результате can[n] = 1, если можно получить сумму равную n.

Теперь, если вместо 1 в can[k] ставить то, число которое мы добавили для получения суммы k, то можно будет получить список всех чисел, которые необходимо было просуммировать.
b1 = can[k] - первое число
b2 = can[k-b1] - второе число
b3 = can[k-b1-b2] - третье число
b4 = can[k-b1-b2-b3] - четвёртое число.
итд

В коде это будет так:
Код:
printf("Всё хорошо, путь:\n");
for (i = n; i != 0; i -= way[i])
    printf("%d\n", way[i]);

Vlad Drakula 23-09-2006 22:41 488714
ivank
чего то ваш алгоритм есть слишком много памяти...
мне вот кажется что придумать алгоритм который есть в max_sum+1 раз меньше памяти не так и сложно...
чтобы не быть голословным скоро приведу пример...

Vlad Drakula 23-09-2006 23:46 488726
код на C# котонрый выводит все элементы...
PHP код:
using System;

namespace summ
{
    class Class1
    {
        static void 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);
                }
                else if(corsize + m[i] < size)
                {
                    s[p + 1] = i;
                    su(m, s, i + 1, p + 1, l, size, corsize + m[i]);
                }
            }
        }

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

        static void Main(string[] args)
        {
            int l = 1000;
            int[] m = new int[l];

            for(int j = 0; j < l; j ++)
            {
                m[j] = j;
            }

            summ(m,l, 10);
        }
    }
} 

ivank 24-09-2006 02:59 488767
Vlad Drakula
Ты просто рекурсивно перебираешь все возможные суммы. Выше уже давалась оценка их количества. Если коротко: афигеть как много. Твой код будет мягко говоря очень долго думать в любом сколь-нибудь сложном случае (время его работы в худшем случае - 2^n, где n - число чисел). Мой гарантированно закончится за O(m*n), где n - число чисел, m - требуемая сумма (максимальная нас не интересует, тут я немножко слажал в описании выше.) Памяти потребуется m. Да, это много. Но это разумная плата за полиномиальное время работы алгоритма вместо экспоненциального.

Сейчас mono соберу и приведу тест, на котором твой код сильно задумается.

ivank 24-09-2006 03:41 488768
Скачал моно. Прогнал простейший тест.

Итак, сначала моя программа в первый раз доведённая до работающего состояния (читай: в первый раз скормил компилятору и поправил очевидные очепятки).
Код:
#include <stdio.h>

int main()
{
/*
        // тест, приведённый оригинальным автором поста
        int num[] = {
                197900,70584,65006,39893,27638,
                29448,17220,7750,39032,2870,
                2010,22386,93275,20090,10906,
                36162,4133,40180,64575,34440,
                6027,8754,22960,4879,22960,
                18311,39893,27638,58896,24108,
                22386,2727,36162,4879,4133,
                34440,5740,2727,15355,1665,
                34440,8610
                };
        const int n = sizeof(num)/sizeof(int);
        const int m = 350000;
*/
        // мой тест, вешает программу Влада
        const int n = 1000; // количество чисел в наборе
        int num[n]; // сами числа. Втупую подряд
        for (int i = 0; i < n; ++i)
                num[i] = 1+i;
        const 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])
            printf("Всё плохо\n");
        else
        {
            printf("Всё хорошо, путь:\n");
            for (int i = m; i != 0; i -= way[i])
                printf("%d\n", way[i]);
        }

        delete[] way;
        return 0;
}
Отрабатывает за секунду в случае "сложного" теста. Мгновенно на примере приведённом автором вопроса.

Программа влада с тем же синтетическим тестом. Не заканчивается никогда.
Код:
using System;

namespace summ
{
    class Class1
    {
        static void 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);
                }
                else if(corsize + m[i] < size)
                {
                    s[p + 1] = i;
                    su(m, s, i + 1, p + 1, l, size, corsize + m[i]);
                }
            }
        }

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

        static void Main(string[] args)
        {
            int l = 1000;
            int[] m = new int[l];

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

            summ(m,l, l*(l+1)/2-1);
        }
    }
}

Vlad Drakula 24-09-2006 09:00 488802
ivank
Цитата:
Выше уже давалась оценка их количества.
1) тыкни носом в отценку.
2) дненм проведу этот тест и посмотнрю на результат.

ivank 24-09-2006 13:43 488864
Цитата:
P.S. В предыдущем посте я наврал. На самом деле при "лобовом подходе" перебирать надо даже SUM(k=1, n, C_n_k). Т.е. сумма всех цэ из эн по ка для всех ка от 1 до эн. Это ещё хуже.
Честно говоря, я склоняюсь к мысли, что эта сумма будет равна 2^n. Поскольку бинарных наборов длины n может быть всего 2^n. А каждый бинарный набор характеризует собой какую-то уникальную сумму (комбинацию чисел). Перебрать их, если делать втупую, надо все. В общем, чистая экспонента.

P.S. Только что проверил эту мысль на бумажке. Действительно, SUM(k=1, n, C_n_k) = 2^n.

Vlad Drakula 24-09-2006 14:48 488876
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 summ(int[] m, int l, int size)
        {
            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 = 500;
            int[] m = new int[l];

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

            d1 = DateTime.Now;                
            summ(m,l, l*(l+1)/2-1);
            d2 = DateTime.Now;
            Console.WriteLine("eval time: {0}", d2 - d1);

            d1 = DateTime.Now;                
            summ2(m,l, l*(l+1)/2-1);
            d2 = DateTime.Now;
            Console.WriteLine("eval time: {0}", d2 - d1);
        }
    }
} 
чтож... поставим прогмаммы в равные словия по функциональности...

int l = 500;
eval time: 00:00:00.0200288
eval time: 00:00:00.5708208
int l = 700;
eval time: 00:00:00.0300432
eval time: 00:00:03.7754288

разница в времени работы не в вашу пользу...

ivank 24-09-2006 15:47 488888
Vlad Drakula
Влад. Давай не будем подгонять входные данные. Вернее, моей программе всё равно, подгоняй их или нет. Время работы зависит только от требуемой суммы и числа элементов. Для твоей программы имеет значение то, в какой последовательности заданы элементы и какую сумму мы ищем. При определённых входных данных она подвисает, что я продемонстрировал. Понятно, что в том случае, когда первый же перебор заканчивается успешно твоя программа отработает мгновенно. Но это _подгон_.

Давай посмотрим как ты изменил мой тест:
Код:
            for(int j = 0; j < l; j ++)
            {
                m[j] = l - j;
            }

            d1 = DateTime.Now;               
            summ(m,l, l*(l+1)/2-1);
            d2 = DateTime.Now;
            Console.WriteLine("eval time: {0}", d2 - d1);
Теперь l*(l+1)/2-1 - это не сумма всех чисел кроме первого. Это сумма всех чисел, кроме последнего. При твоём порядке перебора это будет вторая возможность рассмотренная твоей программой.

Приведу генератор теста, на котором твоя программа будет виснуть всегда. Мы просто ищем сумму всех элементов, кроме элементов равных минимальному. Причём один из минимальных элементов мы кладём в середину массива. Можешь заполнять исходный массив как хочешь - программа будет думать долго всегда. Тест синтетический, но он показывает, что твой алгоритм в худшем случае не работает, и что время моего не зависит от входных данных (вернее, зависит только от m и n, но не самих суммируемых чисел).

Можешь попробовать заполнять m как хочешь. Увидишь, что твой код по прежнему очень долго думает.

Вот код. Я немного его модифицировал. В частности убрал вывод на консоль, чтобы не мешал на время смотреть. А так же сделал "свою" функцию зависимой от третьего параметра. Кроме того, поменял местами вызовы своей функции и твоей. Т.к. твоя подвисает -> до выполнения моей никогда дело не дохдит, если твоя первая.

Код:
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 summ(int[] m, int l, int size)
        {
            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 = 500;
            int[] m = new int[l];

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

            // Старый тест
            d1 = DateTime.Now;               
            summ2(m, l, l*(l+1)/2-1);
            d2 = DateTime.Now;
            Console.WriteLine("ivank's eval time: {0}", d2 - d1);

            d1 = DateTime.Now;               
            summ(m, l, l*(l+1)/2-1);
            d2 = DateTime.Now;
            Console.WriteLine("vlad's eval time: {0}", d2 - d1);

            // Новый тест
            // Требуется сумма всех элементов, кроме элемента из середины массива
            // Поиск минимального элемента и перестановка его в середину массива
            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 eval time: {0}", d2 - d1);

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

      }
    }
}
(ушёл, буду в восемь)

Vlad Drakula 24-09-2006 16:06 488894
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

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

Vlad Drakula 24-09-2006 16:25 488898
ivank
собственно ваш алгоритм не всегда корректно работат...
Всё хорошо, путь: 10 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 = 400

int l = 20;
summ2(m,l, l*l);

ivank 24-09-2006 20:31 488969
Vlad Drakula
Влад. Ты неправильно переделал мой код в C#. И не взял мою исправленную функцию из предыдущего поста. Давай помедитируем над разницей вот этого:
Цитата:
Цитата ivank
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;
и вот этого:
Цитата:
Цитата Vlad
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.

Vlad Drakula 25-09-2006 00:38 489013
ivank
приношу извинения за недогляд при портировании...

предлагаю перейти в тестах на рандомные наборы чисел...

PHP код:
using System;

namespace summ
{
    class Class1
    {
        static int su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
        {
            for(int r = 0;i < l; i++, r++)
            {
                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 0;
                }
                else if(corsize + m[i] < size)
                {
                    if(i + 1 == l)
                    {
                        return r == 0 ? -1 : 1;
                    }

                    s[p + 1] = i;

                    switch(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
                    {
                        case 0:
                            return 0;

                        case -1:
                            if(r == 0)
                            {
                                return -1;
                            }
                            break;

                        case 1:
                            r = 1;
                            break;
                    }
                }
                else if(i + 1 == l)
                {
                    return 1;
                }                
            }

            return 1;
        }

        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 bool summ(int[] m, int l, int size)
        {
            QSort(m, l);
            int[] s = new int[l];
            return su(m, s, 0, -1, l, size, 0) == 0 ? true : false;        
        }

        static bool summ2(int[] num, int n, int size)
        {
            int m = size;

            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("Всё плохо");
                return false;
            }
            Console.Write("Всё хорошо, путь: ");
            for (int i = m; i != 0; i -= way[i])
            {
                Console.Write("{0} ", way[i]);
            }
            Console.WriteLine(" = {0}", size);
            
            return true;
        }

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

            Random r = new Random();
            for (int j = 0; j < l; ++j)
            {
                m[j] = r.Next(10, 1000);
            }
            int needed = r.Next(10 * l / 3, 1000 * l / 3);
    
            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:11.3763584
vlad's time: 00:00:00.0200288

ivank 25-09-2006 01:14 489021
Vlad Drakula
Цитата:
предлагаю перейти в тестах на рандомные наборы чисел...
Слив засчитан.

Я показал, что твой алгоритм в некоторых случаях подвисает (например, когда требуемой комбинации не существует. А такое в оригинальной поставновке задачи может быть). Этого достаточно, чтобы его нельзя было применять. Мой алгоритм [i]гарантированно[i] работает всегда за O(m*n), что в оригинальной постановке задачи (n ~ 40, m ~300000) означает не более чем секундную задержку. Секундная задержка лучше, чем возможное подвисание.

Более того. Предлагаю просто протестировать на реальных данных оба метода. Реальные данные - пример от автора, в посте номер 8.
Цитата:
ivank's time: 00:00:00.2220340
vlad's time: 00:00:13.5698600
что в общем-то и требовалось доказать: в общем случае твой метод нерпиемлем. Более того, если needed=349963, то он опять же подвисает. Да, у тебя достаточно хорошая эвристика, чтобы при достаточно большом наборе чисел рапределённых равномерно быстро находить требуемую комбинацию. К сожалению, входные наборы далеко не всегда обладают такими характеристиками.

Аналогично мой метод ограничен произведением m*n. Но как раз в исходной постановке - это не проблема. А вот возможное отсутствие требуемой комбинации -- очень даже.

Код:
using System;

namespace summ
{
    class Class1
    {
        static int su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
        {
            for(int r = 0;i < l; i++, r++)
            {
                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 0;
                }
                else if(corsize + m[i] < size)
                {
                    if(i + 1 == l)
                    {
                        return r == 0 ? -1 : 1;
                    }

                    s[p + 1] = i;

                    switch(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
                    {
                        case 0:
                            return 0;

                        case -1:
                            if(r == 0)
                            {
                                return -1;
                            }
                            break;

                        case 1:
                            r = 1;
                            break;
                    }
                }
                else if(i + 1 == l)
                {
                    return 1;
                }               
            }

            return 1;
        }

        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 bool summ(int[] m, int l, int size)
        {
            QSort(m, l);
            int[] s = new int[l];
            return su(m, s, 0, -1, l, size, 0) == 0 ? true : false;       
        }

        static bool summ2(int[] num, int n, int size)
        {
            int m = size;

            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("Всё плохо");
                return false;
            }
            Console.Write("Всё хорошо, путь: ");
            for (int i = m; i != 0; i -= way[i])
            {
                Console.Write("{0} ", way[i]);
            }
            Console.WriteLine(" = {0}", size);
           
            return true;
        }

        static void Main(string[] args)
        {
            DateTime d1, d2;
            int l = 42;
            int[] m = {
                197900,70584,65006,39893,27638,
                29448,17220,7750,39032,2870,
                2010,22386,93275,20090,10906,
                36162,4133,40180,64575,34440,
                6027,8754,22960,4879,22960,
                18311,39893,27638,58896,24108,
                22386,2727,36162,4879,4133,
                34440,5740,2727,15355,1665,
                34440,8610
            };

            int needed = 350000; // Попробуй 349963
   
            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 25-09-2006 01:29 489024
P.P.S. последний кусочек статистики.
int[] m = {
197900,70584,65006,39893,27638,
29448,17220,7750,39032,2870,
2010,22386,93275,20090,10906,
36162,4133,40180,64575,34440,
6027,8754,22960,4879,22960,
18311,39893,27638,58896,24108,
22386,2727,36162,4879,4133,
34440,5740,2727,15355,1665,
34440,8610
};
Максимальная сумма - 1233188. При этом невозможно получить 306002 различных сумм с помощью данного набора. То есть, если выбирать needed случайно, с вероятностью 1/4 твоя программа зависнет.

Код:
using System;

namespace summ
{
    class Class1
    {
        static int su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
        {
            for(int r = 0;i < l; i++, r++)
            {
                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 0;
                }
                else if(corsize + m[i] < size)
                {
                    if(i + 1 == l)
                    {
                        return r == 0 ? -1 : 1;
                    }

                    s[p + 1] = i;

                    switch(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
                    {
                        case 0:
                            return 0;

                        case -1:
                            if(r == 0)
                            {
                                return -1;
                            }
                            break;

                        case 1:
                            r = 1;
                            break;
                    }
                }
                else if(i + 1 == l)
                {
                    return 1;
                }               
            }

            return 1;
        }

        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 bool summ(int[] m, int l, int size)
        {
            QSort(m, l);
            int[] s = new int[l];
            return su(m, s, 0, -1, l, size, 0) == 0 ? true : false;       
        }

        static bool summ2(int[] num, int n, int size)
        {
            int m = size;

            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("Всё плохо");
                return false;
            }
            Console.Write("Всё хорошо, путь: ");
            for (int i = m; i != 0; i -= way[i])
            {
                Console.Write("{0} ", way[i]);
            }
            Console.WriteLine(" = {0}", size);
           
            return true;
        }

        static void Main(string[] args)
        {
            DateTime d1, d2;
            int l = 42;
            int[] m = {
                197900,70584,65006,39893,27638,
                29448,17220,7750,39032,2870,
                2010,22386,93275,20090,10906,
                36162,4133,40180,64575,34440,
                6027,8754,22960,4879,22960,
                18311,39893,27638,58896,24108,
                22386,2727,36162,4879,4133,
                34440,5740,2727,15355,1665,
                34440,8610
            };
            Random r = new Random();
            while (true)
            {
                int needed = r.Next(1665, 1233188);

                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);
            }
        }
    }
}
Проверил. Реально задумывается гораздо чаще.

pva 25-09-2006 08:04 489065
Постановка задачи про рюкзак (bounded knapsack problem) дико напоминает линейное программирование. Или я не прав? (смотрел ссылку, они решили как задачу дискретного оптимального управления)

ivank 25-09-2006 12:13 489174
pva
Честно говоря, не очень представляю как это можно сделать. Все известные мне методы линейного программирования, которые ищут дискретные коэфициенты, в конечном счёте NP-полные (читай: сводятся всё к тому же перебору). Кстати, нашёл описание именно нашего частного случая на википедии: http://en.wikipedia.org/wiki/Subset_sum_problem . Там прямо сказано, что это не задача оптимизации (т.е. линейное программирование не применимо. По крайней мере в чистом виде).

Vlad Drakula 26-09-2006 01:42 489556
ivank
соглашусь что ваш алгоритм для данной задачи (типов наборов чисел) лучьше...(пока я не придумал алгорим быстрее)
но веть и быстрая сортировка имеет шанс работать по n*n, и ничего пользуются...

+ еще одно но:
а как на счет реализации?
если по оптимизировать то можно сократить время работы в 3-7 раз... ;)

ivank 26-09-2006 03:31 489563
Vlad Drakula
Цитата:
но веть и быстрая сортировка имеет шанс работать по n*n, и ничего пользуются...
Я не спорю. Есть сортировка с помощью кучи, которая гарантированно работает за n*logn, но ею не пользуются, т.к. в среднем случае она в несколько раз медленнее быстрой сортировки (которая, кстати называется сортировкой Хоара, на самом деле). Средние случаи встречаются значительно чаще, чтобы перевешивать превосходство хип-сорта над кусортом в худшем случае.

Аналогично в среднем случае твой алгоритм значительно лучше. Вот только на предполагаемых наборах чисел (25-50) вероятность влететь в худший случай максимальна (т.к. чем больше чисел (n>50), тем больше вероятность получить требуемую сумму с помощью твоей эвристики. А при малом n (<25), даже если требуеммую сумму получить нельзя, стоимость полного перебора невелика).

Цитата:
а как на счет реализации? если по оптимизировать то можно сократить время работы в 3-7 раз...
Да это вроде не требуется по условию. Человек готов был ждать по пол-часа и более. И вообще, не умею я оптимизировать на "не-алгоритмеческом" уровне, доверяю компилятору.


Время: 02:19.

Время: 02:19.
© OSzone.net 2001-