Модераторы: maxim1000

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Перебор вариантов, Перебор вариантов 
V
    Опции темы
maxdiver
Дата 6.11.2011, 20:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18



Ну вот я закодил эту идею с динамическим программированием, и оставил на час выполняться на случайных данных. Самое медленное время работы - 250 мс, что действительно гораздо меньше двух секунд smile


ksnk, да, извиняюсь, не посмотрел ваш код - он действительно работает за 2^29. Правда, надо понимать, что одно дело - 2^29 рекурсивных вызовов, а другое - пусть даже столько же по количеству, но гораздо более простых операций (сложение двух чисел и обращение к массиву).

Цитата
 Возможно ее можно оценить более точно? 

К сожалению, я не представляю, как точно оценить это число "на бумажке", но вот после часа работы не нашлось ни одного теста, на котором было бы достижимо больше, чем 1/4 состояний динамики. Таким образом, "экспериментальное" время работы - около 100 млн операций.
PM MAIL WWW ICQ   Вверх
ksnk
Дата 7.11.2011, 12:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


прохожий
****


Профиль
Группа: Комодератор
Сообщений: 6810
Регистрация: 13.4.2007
Где: СПб

Репутация: 7
Всего: 383



maxdiver, да, метод работает и достаточно эффективно smile 

Код

var numbers=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30],
    time=new Date().valueOf(),
    store=[];

/**
 *  calculate cell NxM by calculating past values
 */
function calcval(n,m){
    var i,val=0,
        tmp = 1;
    for (i=n-1;i>=0;i--){
        tmp = tmp *numbers[i] ;
        var x = m-tmp;
        if(x<0) continue;
        if(n>0 && (typeof(store[i][x])=='undefined')){
           calcval(i,x);
        }
        val +=store[i][x]||0;
    }
            
    return store[n][m]=val;
}

// fill them at start
for(var i=0;i<=numbers.length;i++)store[i]=[0];
store[0][0]=1;

// so let' find it
alert([calcval(30,2751),new Date().valueOf()-time]);


выдает 2972 варианта при несущественном времени выполнения...



--------------------
Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! user posted image
PM MAIL WWW Skype   Вверх
ksnk
Дата 8.11.2011, 01:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


прохожий
****


Профиль
Группа: Комодератор
Сообщений: 6810
Регистрация: 13.4.2007
Где: СПб

Репутация: 7
Всего: 383



maxdiver, Попытался оценить сложность вычисления и внезапно обнаружил, что сложность по этому методу факториальна. То есть при увеличении массива исходных чисел до n+1 получаем увеличение времени на n+1 в худшем случае. А совсем даже не в 2 раза, как при полном переборе. 
Я что-то понимаю неправильно?


--------------------
Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! user posted image
PM MAIL WWW Skype   Вверх
maxdiver
Дата 8.11.2011, 11:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18



ksnk
Не совсем понял. Откуда факториальная, если во-первых мы не считаем никакое состояние (n,m) дважды, а во-вторых нам не нужны m больше s, т.е. больше 1000000?
Сложность работы - O (n^2 * m), поскольку у нас есть n * m ячеек, каждая из которых считается за O(n).
PM MAIL WWW ICQ   Вверх
ksnk
Дата 8.11.2011, 11:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


прохожий
****


Профиль
Группа: Комодератор
Сообщений: 6810
Регистрация: 13.4.2007
Где: СПб

Репутация: 7
Всего: 383



Цитата(maxdiver @  8.11.2011,  11:07 Найти цитируемый пост)
нам не нужны m больше s, т.е. больше 1000000?

Откуда взялся миллион? C клавиатуры можно ввести число от 1 до 2147483648, если ограничиться натуральными числами и стандартным longint, не связываясь с "длинной" арифметикой...

Сложность не факториальна, да...
Пусть сложность вычисления для n оценивается функцией o(n). Тогда для n+1, сложность алгоритма, описанного выше,  можно оценить
o(n)+o(n-1)+...+o(0). А если упростить для n-1 и так далее - то получится сложность степени 2... примерно то-же, что и для перебора.

Добавлено через 2 минуты и 20 секунд
Чтобы получить длительное время выполнения - достаточно поставить большое число в правую часть равенства. Так не будут срабатывать "отсечения" лишних веток пребора


--------------------
Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! user posted image
PM MAIL WWW Skype   Вверх
maxdiver
Дата 8.11.2011, 12:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18



Ну так по условию число не более миллиона:
Цитата
и число S, записанное в правой части равенства (1 < S < 10^6)

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

А вот при наличии данного ограничения динамика сильно улучшает перебор, т.к. например на тесте N=30, S=30, все a_i = 1 перебор будет перебирать все 2^29 вариантов, а динамика отработает мгновенно.



Впрочем, сейчас мне придумалось другое решение, гораздо более быстрое, и которое не использует факта, что S маленькое.

Идея называется "meet-in-the-middle".

В общем, давайте будем разбивать задачу на две части размера не более 15. А именно, любое подходящее выражение можно разбить на три части:
1) несколько первых слагаемых
2) слагаемое, содержащее N/2-ое число
3) несколько последних слагаемых

Основная идея - что мы будем перебирать только слагаемые 2) и 1), а вот слагаемое 3) мы переберём заранее.

Таким образом, мы предварительно перебираем все выражения из <=N/2 последних чисел, посчитаем каждое такое выражение, и построим такую табличку - сколько раз каждое возможное значение у нас получилось. Этот шаг выполняется за O (2^{n/2} * log (2^{n/2})), т.е. за O (n * 2^{n/2}).

Затем мы перебираем все выражения из <=N/2 первых чисел (это часть #1), а также перебираем, сколько следующих чисел мы относим к части #2. Для каждого получившегося числа мы просто отнимаем его от S и заглядываем в табличку для части 3), прибавляя к ответу количество подходящих частей #3. Этот шаг также можно реализовать за O (n * 2^{n/2}).

Итого - O (n * 2^{n/2}), т.е. при наших ограничениях это около 30 * 2^16, т.е. порядка миллиона операций.

Закодил - для N=30 работает вообще мгновенно, ну как и следовало ожидать.
PM MAIL WWW ICQ   Вверх
ksnk
Дата 8.11.2011, 12:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


прохожий
****


Профиль
Группа: Комодератор
Сообщений: 6810
Регистрация: 13.4.2007
Где: СПб

Репутация: 7
Всего: 383



Да, про миллион это я пропустил... 

Цитата(maxdiver @  8.11.2011,  12:01 Найти цитируемый пост)
 любое подходящее выражение можно разбить на три части:

особенно то, где все кусочки нужно перемножить... или только с одним плюсом...  smile 

Что-то мне кажется, что не все так просто. Надо будет подумать smile


--------------------
Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! user posted image
PM MAIL WWW Skype   Вверх
maxdiver
Дата 8.11.2011, 12:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18



Ну части #1 и #3 могут быть пустыми. Главное, что всегда найдётся среднее слагаемое, разбивающее выражение на две половинки с <=15 числами каждая.

Вообще я эту идею стрессил, т.е. сравнивал на случайных тестах с динамикой, и ответы сходятся.
PM MAIL WWW ICQ   Вверх
Dmi3ev
Дата 8.11.2011, 19:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: нет
Всего: 41



Пока ничего не выходит(((



--------------------

PM MAIL   Вверх
ksnk
Дата 9.11.2011, 07:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


прохожий
****


Профиль
Группа: Комодератор
Сообщений: 6810
Регистрация: 13.4.2007
Где: СПб

Репутация: 7
Всего: 383



Dmi3ev, а что конкретно не выходит? Может будет правильнее паскальный код сюда бросить?


--------------------
Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! user posted image
PM MAIL WWW Skype   Вверх
Dmi3ev
Дата 9.11.2011, 20:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: нет
Всего: 41



Нашел сайт, где указываются темы, которые необходимо изучить для ее решения.
необходимо знать:
1) Динамическое программирование
2) Перебор с отсечением
Начал курить это дело... О результатах сообщу... 


--------------------

PM MAIL   Вверх
миг
Дата 12.11.2011, 20:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 156
Регистрация: 15.9.2008

Репутация: нет
Всего: 1



Цитата(maxdiver @  8.11.2011,  12:01 Найти цитируемый пост)
и число S, записанное в правой части равенства (1 < S < 10^6)

а если S =10^6-1. то значит решений нет или существует только одно решение...  или можно сказать так, чем ближе S приближается к верхней и нижней границы тем меньше решений(если вообще есть решения).
я тут попробовал взять несколько примеров первый пример 1,2,3,4,5,6,7,8,9,10=b=1814402
Ряд брал из 10 чисел, т.к. вычисления  достаточно громоздкие.
1) Умножаем все  числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y
2) вывел ф-лу x=y/(b-z), т.е. x=3628800/(1814402-z)
3) подбираю такое z, чтобы число делилось без остатка и число х было положительным. например если z=2, то x=3628800/(1814402-2)=2
4) далее смотрим путем подбора при произведение каких, чисел можно получить число x.  Получается только x=1*2=2
5) далее из этих двух чисел нужно составить число равное z. т.е. z=1*2=2 (путем подбора варьируем знаками "*" и "+" числа местами не переставлять в других примерах это будет очень важно).
6) 1*2+3*4*5*6*7*8*9*10=1814402

второй пример 1,2,3,4,5,6,7,8,9,10=b=604806
1) Умножаем все  числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y
2) x=y/(b-z)= 3628800/(604806-z). 
3) Например если z=6 то x=3628800/(604806-6)=6 
4) далее смотрим путем подбора при произведение каких, чисел можно получить число x.  Получается только x=1*2*3=6
5) далее из этих трех чисел нужно составить число z=1+2+3=6 или 1*2*3=6
6) первое решение 1+2+3+4*5*6*7*8*9*10=604806 второе решение 1*2*3+4*5*6*7*8*9*10=604806

третий пример 1,2,3,4,5,6,7,8,9,10=b=1814403
1) Умножаем все  числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y
2) x=y/(b-z)= 3628800/(1814403-z). 
3) Например если z=3 то x=3628800/(1814403-3)=2 
4) далее смотрим путем подбора при произведение каких, чисел можно получить число x.  Получается только x=1*2=2
5) далее из этих двух чисел нужно составить число z=1+2=3
6)  решение 1+2+3*4*5*6*7*8*9*10=1814403

четвертый пример 1,2,3,4,5,6,7,8,9,10=b=604805
1) Умножаем все  числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y
2) x=y/(b-z)= 3628800/(604805-z). 
3) Например если z=5 то x=3628800/(604805-5)=6 
4) далее смотрим путем подбора при произведение каких, чисел можно получить число x.  Получается только x=1*2*3=6
5) далее из этих трех чисел нужно составить число z=1*2+3=5
6)  решение 1*2+3+4*5*6*7*8*9*10=604805

пятый пример 1,2,3,4,5,6,7,8,9,10=b=151210
1) Умножаем все  числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y
2) x=y/(b-z)= 3628800/(604805-z). 
3) Например если z=10 то x=3628800/(151210-10)=24
4) далее смотрим путем подбора при произведение каких, чисел можно получить число x.  Получается только x=1*2*3*4=24
5) далее из этих четырех чисел нужно составить число z=1*2*3+4=10 или z=1+2+3+4=10
6)  решение 1*2*3+4+5*6*7*8*9*10=151210 или z=1+2+3+4+5*6*7*8*9*10=151210

шестой пример 1,2,3,4,5,6,7,8,9,10=b=604807
1) Умножаем все  числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y
2) x=y/(b-z)= 3628800/(604807-z). 
3) Например если z=7 то x=3628800/(604807-7)=6
4) далее смотрим путем подбора при произведение каких, чисел можно получить число x.  Получается только x=1*2*3=6
5) далее из этих  чисел нужно составить число z=1+2*3=7
6)  решение 1+2*3+4*5*6*7*8*9*10=604807

седьмой пример 1,2,3,4,5,6,7,8,9,10=b=55
1) Умножаем все  числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y
2) x=y/(b-z)= 3628800/(55-z). 
3) Например если z=54 то x=3628800/(55-54)=3628800
4) далее смотрим путем подбора при произведение каких, чисел можно получить число x.  Получается  x=2*3*4*5*6*7*8*9*10=3628800=y или x=1*2*3*4*5*6*7*8*9*10=3628800=y
5) далее из этих  чисел нужно составить число z=2+3+4+5+6+7+8+9+10=54
6)  решение 1+2+3+4+5+6+7+8+9+10=55

восьмой пример 1,2,3,4,5,6,7,8,9,10=b=789
1) Умножаем все  числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y
2) x=y/(b-z)= 3628800/(789-z). 
3) Например если z=69 то x=3628800/(789-69)=5040
4) далее смотрим путем подбора при произведение каких, чисел можно получить число x.  Получается только  х=1*2*3*4*5*6*7=5040
5) далее из этих  чисел нужно составить число   z=1+2*3+4*5+6*7=69. путем подбора либо по формуле в пункте 2.
6)  одно из решений 1+2*3+4*5+6*7+8*9*10=789 .. возможно еще есть решение я просто не пробовал его найти вручную.. а может и нет решения))
Вообщем в пункте 2 если варьировать числом z от 0 до b-1.. Возможно найти еще решения.

Это сообщение отредактировал(а) миг - 13.11.2011, 11:42
--------------------
Oaks may fall when reeds stand the storm.
PM MAIL   Вверх
миг
Дата 13.11.2011, 10:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 156
Регистрация: 15.9.2008

Репутация: нет
Всего: 1



1,2,3,4,5,6,7,0,8,9,10=S. если в ряде присутствуют нулевые и вещественные числа, то такое решение не подходит.  Правда нулевые числа можно обойти. например сразу записать несколько вариантов условий 1,2,3,4,5,6,7+0+8,9,10=S или так 1,2,3,4,5,6+7*0+8,9,10=b или 1*2*3*4*5*6*7*0*8*9*10=b 1,2,3,4,5,6+7*0*8*9+10=b. только в этом случае в ряде будет гораздо меньше чисел, чем планировалось.


Это сообщение отредактировал(а) миг - 14.11.2011, 18:00
--------------------
Oaks may fall when reeds stand the storm.
PM MAIL   Вверх
Bunybi
Дата 27.6.2019, 11:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 1
Регистрация: 26.6.2019

Репутация: нет
Всего: нет



Правильные порядок в расчете очень важен, сначала умножение или сложение, а затем все остальное. Правильный порядок арифметических действий в математике зависит от их типа и условий конкретного примера. Знание правил очередности необходимо, поскольку они являются основой как для многих бытовых операций (покупки, измерения), так и более сложных расчетов.

PM MAIL   Вверх
Google
  Дата 22.9.2019, 00:23 (ссылка)  





  Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1246 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.