Тогда бы и писали "скорость работы". Нет, эффективность зависит от требований предъявляемых к системе и может принимать самые разнообразные формы.
Нужно решить простейший пример
Добавлено: 20 дек 2013, 22:05
NT
zykov писал(а):Source of the post Нет, эффективность зависит от требований предъявляемых к системе и может принимать самые разнообразные формы.
А вот это мне интересно послушать. Задача поставлена найти указанную сумму (если есть). Решаем с привлечением комп.техники, собственно ищим оптимальный алгоритм решения на компьютере. Вот в рамках комп. техники, эффективность подразумевает затраты машинных ресурсов и машинного времени. Какие могут быть предьявлены иные требования к этим алгоритмам?
Нужно решить простейший пример
Добавлено: 20 дек 2013, 22:53
YuriiS
balans писал(а):Source of the post ............................ ............................ ............................ S=30.5*a1 + 108.2*a2+ 236.9*a3+ 293.2*a4+338.5*a5+377.8*a6+ 532.1*a7+772.3*a8+ 928.1*a9 if ( (S-2403)*(S-2400)<0) then print *,a1,a2,a3,a4,a5,a6,a7,a8,a9,S end if....................................................................................
IS=5*a1 + 2*a2+ 9*a3+ 2*a4+5*a5+8*a6+ 1*a7+3*a8+ 1*a9 if ( MOD(IS,10) .EQ. 2) then IS=IS+300*a1 + 1080*a2+ 2360*a3+ 2930*a4+3380*a5+3770*a6+ 5320*a7+7720*a8+ 9280*a9 if ( IS.EQ.24012) then S=2401.2 print *,a1,a2,a3,a4,a5,a6,a7,a8,a9,S end if end if
Нужно решить простейший пример
Добавлено: 20 дек 2013, 22:58
zykov
NT писал(а):Source of the post Какие могут быть предьявлены иные требования к этим алгоритмам?
Самые разные. Скорость разработки, надёжность работы, совместимость, сложность дальнейшей поддержки и т.д.
Никогда ни в одной книге по алгоритмам и программированию не слышал о другом критерии, кроме как временная эффективность и использование памяти. Конечно, в книгах по коммерции и бизнесу, не спорю, - тут попадалось, что самое главное - написать программу быстро и дорого продать, а как она будет работать - вопрос второй. Но мы же не обсуждаем бизнес-проблему?
О конкретной проверке на практике, кому интересно - читайте...
Поскольку задача NP-полная (см. Кормен, "Алгоритмы. Построение и анализ", 3 изд., с. 1147-1151), в общем случае точное решение на сегодняшний день только полный перебор.
В обоснование своего мнения о том, что тут эффективнее применить код Грея (алгоритм взят из "Искусства программирования", т. 4а, с. 338) написал программку с замером времени. Не стал заморачиваться ни с целыми числами (тогда должно быть быстрее...), ни с тем, что в конкретном случае должно быть от 4 до 7 чисел в наборе. Чисто в общем виде. Более того, будем даже считать, что чисел не более 32, чтоб поместиться в 32-битовое число - все равно перебор такого количества уже на грани разумного...
Код приведен далее. Время меряется с помощью QueryPerformanceCounter, т.е. ну очень малые кусочки времени
Понятно, что сравнивать имеет смысл только время полного перебора, т.е. когда решение не найдено. Даже при нашем варианте в 9 чисел время на разбор битов числа примерно в 6-8 раз больше, чем с использованием кода Грея. Для 12 чисел держится уже на уровне 10-11, при 15 - раз в 13-14.
Что касается краткости и прозрачности - сравнивайте сами, насколько 23 (ну, с натяжкой - 25) строк больше 21
Вложенные циклы для конкретной задачи не писал, решая более общую. Кто хочет - допишите, посмотрим, что там...
// Для точного измерения времени... long long muTime() { static class getFreq { public: getFreq() { LARGE_INTEGER f; QueryPerformanceFrequency(&f); freq = f.QuadPart; } long long Freq() { return freq; }; private: long long freq; } F; LARGE_INTEGER t; QueryPerformanceCounter(&t); return (t.QuadPart * 1000000L)/F.Freq(); }
// Конечно, эффективнее умножить все на 10 и работать с целыми числами, // но оставим все как есть double v[] = { 30.5, 772.3, 338.5, 293.2, 532.1, 377.8, 108.2, 236.9, 928.1 };
const int N = sizeof(v)/sizeof(v[0]);
double tgt = 2401.2; double eps = 0.01; // Чтоб ну совсем по правилам :)
bool version1() { // Ну, будем считать, что чисел не слишком много (до 32), // и что нулевая сумма нас точно не интересует... for(unsigned long i = (1<<N)-1; i; --i) { double sum = 0.0; for(unsigned long j = i, k = 0; j; j>>=1, ++k) { if (j&1) sum += v[k]; } if (fabs(sum-tgt) < eps) { for(unsigned long j = i, k = 0; j; j>>=1, ++k) { if (j&1) printf("%.1lf ",v[k]); } printf("= %.1lf\n",sum); return true; } } return false; }
bool version2() { int f[N+1], a[N] = {0}; double sum = 0.0; for(int i = 0; i <= N; ++i) f[i] = i; for(int j;;) { j = f[0]; f[0] = 0; if (j == N) break; f[j] = f[j+1]; f[j+1] = j+1; if (a[j] = 1 - a[j]) sum += v[j]; else sum -= v[j]; if (fabs(sum-tgt) < eps) { for(int i = 0; i < N; ++i) { if (a[i]) printf("%.1lf ",v[i]); } printf("= %.1lf\n",sum); return true; } } return false; }
int main(int argc, const char * argv[]) { bool res; long long start = muTime(); res = version1(); long long stop = muTime(); printf("Version 1 = %Ld, result: %d\n",stop-start,res); start = muTime(); res = version2(); stop = muTime(); printf("Version 2 = %Ld, result: %d\n",stop-start,res); }
Нужно решить простейший пример
Добавлено: 21 дек 2013, 14:59
geh
Использование случайных чисел тоже решает эту задачу. Используется один цикл и внутри него определяется включать то или иное число в сумму или нет. Кроме того все числа были увеличены в 10 раз. То есть я работал с целыми длинными числами. А это увеличивает скорость программы. Я получил тот же результат. Надо отдать себе отчет, что это не полный перебор. Но при достаточном количестве оборотов цикла он дает хорошие результаты.
Нужно решить простейший пример
Добавлено: 21 дек 2013, 15:11
kiv
geh писал(а):Source of the post Использование случайных чисел тоже решает эту задачу.
Вся беда в том, что оно не дает гарантии, что перебраны все варианты. Если решение есть - на него можно наткнуться случайно (но запросто можно и не наткнуться!), но если нет - вы не имеете гарантии, что его и в самом деле нет...