[ivank]

Скачал моно. Прогнал простейший тест.

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

Код:

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