Ночной странник
Сообщения: 4050
Благодарности: 83
|
Профиль
|
Сайт
|
Отправить PM
| Цитировать
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
|
