Нужно решить простейший пример

СергейП
Сообщений: 4145
Зарегистрирован: 17 июл 2009, 21:00

Нужно решить простейший пример

Сообщение СергейП » 20 дек 2013, 21:06

zykov писал(а):Source of the post
kiv писал(а):Source of the post Плохо - надо разбирать число на биты...
Почему "плохо"?
Вообще "хорошо-плохо" - оно вещи относительные.
В данном случае код будет короче и прозрачнее.
Сначала бы следовало определиться кто какой язык имеет в виду.
Всё таки с битиками ковыряться - очень по разному будет
Последний раз редактировалось СергейП 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
zam2
Сообщений: 3760
Зарегистрирован: 13 авг 2013, 21:00

Нужно решить простейший пример

Сообщение zam2 » 20 дек 2013, 21:09

А где написано, что нельзя одно число использовать больше одного раза?
Последний раз редактировалось zam2 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
zykov
Сообщений: 1777
Зарегистрирован: 02 ноя 2009, 21:00

Нужно решить простейший пример

Сообщение zykov » 20 дек 2013, 21:33

kiv писал(а):Source of the post Вообще-то эффективность - это скорость работы...
Тогда бы и писали "скорость работы".
Нет, эффективность зависит от требований предъявляемых к системе и может принимать самые разнообразные формы.
Последний раз редактировалось zykov 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
NT
Сообщений: 3384
Зарегистрирован: 25 янв 2010, 21:00

Нужно решить простейший пример

Сообщение NT » 20 дек 2013, 22:05

zykov писал(а):Source of the post
Нет, эффективность зависит от требований предъявляемых к системе и может принимать самые разнообразные формы.
А вот это мне интересно послушать.
Задача поставлена найти указанную сумму (если есть).
Решаем с привлечением комп.техники, собственно ищим оптимальный алгоритм решения на компьютере.
Вот в рамках комп. техники, эффективность подразумевает затраты машинных ресурсов и машинного времени.
Какие могут быть предьявлены иные требования к этим алгоритмам?
Последний раз редактировалось NT 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

YuriiS
Сообщений: 123
Зарегистрирован: 17 фев 2012, 21:00

Нужно решить простейший пример

Сообщение YuriiS » 20 дек 2013, 22:53

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
Последний раз редактировалось YuriiS 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
zykov
Сообщений: 1777
Зарегистрирован: 02 ноя 2009, 21:00

Нужно решить простейший пример

Сообщение zykov » 20 дек 2013, 22:58

NT писал(а):Source of the post Какие могут быть предьявлены иные требования к этим алгоритмам?
Самые разные.
Скорость разработки, надёжность работы, совместимость, сложность дальнейшей поддержки и т.д.
Последний раз редактировалось zykov 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

YuriiS
Сообщений: 123
Зарегистрирован: 17 фев 2012, 21:00

Нужно решить простейший пример

Сообщение YuriiS » 21 дек 2013, 06:20

YuriiS писал(а):Source of the post
1*a7+3*a8+ 1*a9

Можно и так:
a7+3*a8+ a9
Последний раз редактировалось YuriiS 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
kiv
Сообщений: 1012
Зарегистрирован: 02 дек 2011, 21:00

Нужно решить простейший пример

Сообщение kiv » 21 дек 2013, 08:53

Ну, пора вставить свои 5 копеек

Никогда ни в одной книге по алгоритмам и программированию не слышал о другом критерии, кроме как временная эффективность и использование памяти. Конечно, в книгах по коммерции и бизнесу, не спорю, - тут попадалось, что самое главное - написать программу быстро и дорого продать, а как она будет работать - вопрос второй. Но мы же не обсуждаем бизнес-проблему?

О конкретной проверке на практике, кому интересно - читайте...
Поскольку задача NP-полная (см. Кормен, "Алгоритмы. Построение и анализ", 3 изд., с. 1147-1151), в общем случае точное решение на сегодняшний день только полный перебор.

В обоснование своего мнения о том, что тут эффективнее применить код Грея (алгоритм взят из "Искусства программирования", т. 4а, с. 338) написал программку с замером времени. Не стал заморачиваться ни с целыми числами (тогда должно быть быстрее...), ни с тем, что в конкретном случае должно быть от 4 до 7 чисел в наборе. Чисто в общем виде. Более того, будем даже считать, что чисел не более 32, чтоб поместиться в 32-битовое число - все равно перебор такого количества уже на грани разумного...

Код приведен далее. Время меряется с помощью QueryPerformanceCounter, т.е. ну очень малые кусочки времени

Понятно, что сравнивать имеет смысл только время полного перебора, т.е. когда решение не найдено. Даже при нашем варианте в 9 чисел время на разбор битов числа примерно в 6-8 раз больше, чем с использованием кода Грея. Для 12 чисел держится уже на уровне 10-11, при 15 - раз в 13-14.

Что касается краткости и прозрачности - сравнивайте сами, насколько 23 (ну, с натяжкой - 25) строк больше 21

Вложенные циклы для конкретной задачи не писал, решая более общую. Кто хочет - допишите, посмотрим, что там...

Код вот:

Код: Выбрать все

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <windows.h>

// Для точного измерения времени...
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);
}


Последний раз редактировалось kiv 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

geh
Сообщений: 224
Зарегистрирован: 09 дек 2013, 21:00

Нужно решить простейший пример

Сообщение geh » 21 дек 2013, 14:59

Использование случайных чисел тоже решает эту задачу.
Используется один цикл и внутри него определяется включать
то или иное число в сумму или нет. Кроме того все числа были
увеличены в 10 раз. То есть я работал с целыми длинными числами.
А это увеличивает скорость программы. Я получил тот же результат.
Надо отдать себе отчет, что это не полный перебор. Но при достаточном
количестве оборотов цикла он дает хорошие результаты.
Последний раз редактировалось geh 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
kiv
Сообщений: 1012
Зарегистрирован: 02 дек 2011, 21:00

Нужно решить простейший пример

Сообщение kiv » 21 дек 2013, 15:11

geh писал(а):Source of the post
Использование случайных чисел тоже решает эту задачу.


Вся беда в том, что оно не дает гарантии, что перебраны все варианты. Если решение есть - на него можно наткнуться случайно (но запросто можно и не наткнуться!), но если нет - вы не имеете гарантии, что его и в самом деле нет...
Последний раз редактировалось kiv 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test


Вернуться в «Computer Science»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 0 гостей