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

Поиск:

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


Эксперт
***


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

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



Задача такова:
С клавиатуры вводится число N, затем вводится N чисел (1<N<=30).
Необходимо расставить знаки между числами (только + и *) так, чтобы получилось число S, которое тоже вводится с клавиатуры.
Задача сводится к тому, что нужно перебрать все варианты, при этом после расстановки знаков проанализировать выражение.
Как это сделать? Конечно, можно запустить 29 циклов, наставить кучу условий, ну а как-то поумнее можно?
PS анализатор выражений в инете есть, а вот перебор грамотный очень интересует.

Это сообщение отредактировал(а) Dmi3ev - 4.11.2011, 22:59


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

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


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


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

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



+ и * только , или - и . тоже можно?
Числа целые или дробные тоже бывают.

В принципе, ничего кроме полного перебора не приходит в голову, к тому-же для этих данных полный перебор будет не очень дорогим по времени решением.
однако, если числа целые, и можно только + и *, то получающийся промежуточный результат будет возрастающей последовательностью, можно сократить перебор, если стало больше S


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


Эксперт
***


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

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



Раз можно перебором, то все будет довольно просто.
* Заводим массив чисел A[1..N]
* Заводим булев массив B[2..N]. Условимся, например, что в этом массиве FALSE будет означать сложение, TRUE - умножение.

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

Если просто идем по строке, то тогда нужна только одна дополнительная переменная для суммирования Z
Код

i) Присваиваем Z = A[1]
ii) Запускаем цикл J от 2 до N (понятно, что если N=1, цикл будет выполнен 0 раз). В цикле проверяем: Если B[J]==TRUE Z=Z*A[J], а если B[J]==FALSE Z=Z+A[J]
iii) По окончании цикла проверяем равенство межде Z и S


Если приоритет операций должен соблюдаться, можно, например, использовать еще одну переменную Y.
Код

I) Z = 0 и Y = A[1]
II) Запускаем цикл J от 2 до N
III) Если B[J]==TRUE Y=Y*A[J] и идем на следующий шаг цикла
IV) Если  B[J]==FALSE Z=Z+Y после чего Y=A[J] и идем на следующий шаг цикла
V) По окончании цикла производим Z=Z+Y
VI) Проверяем равенство межде Z и S


Тепер основной алгоритм - перебор вариантов.
Код

1) Число возможных вариантов сложений-умножений можно представить двоичным числом длинной N-1. Так и делаем.
2) В цикле проходим от нуля до этого самого двоичного числа.
3) Каждую единицу в двоичном представлении счетчика цикла интерепретируем как TRUE в массиве B, а каждый ноль как FALSE
4) Проверяем условие по одному из вышеописанных алгоритмов

Пример: N=3, A={1,2,3}
Число вариантов расстановки плюсов-минусов четыре = b11 (бинарное предстваление)
Цикл 0=b00 >  1+2+3
Цикл 1=b01 >  1+2*3
Цикл 2=b10 >  1*2+3
Цикл 3=b11 >  1*2*3

Как видите, только один цикл smile 

Это сообщение отредактировал(а) _Y_ - 5.11.2011, 12:00


--------------------
Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:)
PM MAIL WWW   Вверх
Dmi3ev
Дата 6.11.2011, 00:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


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

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



Андрей Сергеевич — учитель математики в начальной школе. Вчера на уроке он записал на доске выражение вида
a1? a2 ? ... ? aN-1 ? aN = S
и попросил детей заменить вопросительные знаки на знаки сложения и умножения так, чтобы получилось верное равенство. Разумеется, дети быстро справились с заданием.
Особенно понравилось Андрею Сергеевичу то, что мальчик Петя нашел сразу два варианта расстановки знаков. Тогда он попросил класс посчитать, сколько всего существует вариантов правильной расстановки знаков. Напишите программу, которая решает данную задачу.
Формат входных данных
В первой строке входного файла input.txt содержится число N 
(1 < N < 30) - количество чисел в левой части равенства, записанного на доске и число S, записанное в правой части равенства (1 < S < 10^6). В следующей строке даны N чисел в том порядке, в каком они были выписаны на доске. Все числа неотрицательные и не превышают 10^6.
Формат выходных данных
Выведете на экран одно число — количество различных вариантов расстановки знаков между числами, приводящих к правильному результату в записанном на доске выражении.
PS приоритет операций должен соблюдаться!
+ есть ограничение "ограничение по времени – 2 секунды"
Цитата

Число возможных вариантов сложений-умножений можно представить двоичным числом длинной N-1. Так и делаем.

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


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

PM MAIL   Вверх
миг
Дата 6.11.2011, 10:36 (ссылка)    | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

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



Цитата(Dmi3ev @  6.11.2011,  00:40 Найти цитируемый пост)
Андрей Сергеевич — учитель математики в начальной школе.

Это же "мартышкин труд". В начальном классе не учат программированию. Заставлять перебирать детей все варианты решения вручную не гуманно... Лучше бы он их логические задачи научил решать, а не чисто механически расставить знаки. От этого будет больше пользы.
--------------------
Oaks may fall when reeds stand the storm.
PM MAIL   Вверх
ksnk
Дата 6.11.2011, 10:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

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



миг, вообще-то это формулировка задачи по программированию, а не методичка по проведению уроков математики в начальной школе  smile 


Dmi3ev, какая платформа используется для решения? imho - 2 секунды довольно дофига, чтобы перебрать все 2^30 вариантов ... Для эффективности можно считать промежуточные суммы - "прмежуточный результат" и промежуточный результат незакончившегося умножения.


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


Бывалый
*


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

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



ksnk, я так понял это задали сделать 7-8 летнему ребенку, который еще толком читать не умеет. Не у всех же детей папы программисты. Если папа программист решит за ребенка задачку, то мозгов у ребенка не прибавиться, а сам ребенок будет решать ее достаточно долго. Просто не понимаю учителя математики начальной школы. А то, что эта задачка подходит больше программистам я с вами в этом не спорю.

Добавлено через 7 минут и 41 секунду
Цитата(Dmi3ev @  6.11.2011,  00:40 Найти цитируемый пост)
Вчера на уроке он записал на доске выражение вида
a1? a2 ? ... ? aN-1 ? aN = S
и попросил детей заменить вопросительные знаки на знаки сложения и умножения так, чтобы получилось верное равенство.

я бы просто тупо перебором составил все варианты
 a1+a2*...*aN-1=S
a1*a2+...+aN-1=S и т.д. Можно все варианты сохранить в файл.
А потом с помощью синтаксического анализатора проанализировать выражения и получил бы результат.

Добавлено через 12 минут и 32 секунды
Цитата(ksnk @  6.11.2011,  10:56 Найти цитируемый пост)
Dmi3ev, какая платформа используется для решения? imho - 2 секунды довольно дофига, чтобы перебрать все 2^30 вариантов ... Для эффективности можно считать промежуточные суммы - "прмежуточный результат" и промежуточный результат незакончившегося умножения. 

а если результат будет больше S, то делать "откат" назад? в некоторых случаях, чуть ли не до первого слагаемого.. По моему так уйдет еще больше времени, чем обычным перебором.
--------------------
Oaks may fall when reeds stand the storm.
PM MAIL   Вверх
_Y_
Дата 6.11.2011, 11:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


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

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



Цитата(Dmi3ev @ 6.11.2011,  00:40)
Цитата

Число возможных вариантов сложений-умножений можно представить двоичным числом длинной N-1. Так и делаем.

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

Что-то я не въезжаю:
1. Что значит "не укладываюсь"? Какие временные ограничения и на что?
2. Так это и есть тупой перебор. Вопрос стоял о количестве потребных циклов. Вот и предложено перебор делать в одном цикле.


--------------------
Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:)
PM MAIL WWW   Вверх
миг
Дата 6.11.2011, 11:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

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



хотя есть одна идея с промежуточными результатами, можно и так a1+a2 =b1, a3+a4=b2,  a1*a2=c1, a3*a4=c2.  а дальше эти промежуточные значения между собой складываем или умножаем. b1+b2=d1 b1*b2=e1, b1+c1=g b1*c1=... минус в том, что будет вычисленно очень много промежуточных результатов
--------------------
Oaks may fall when reeds stand the storm.
PM MAIL   Вверх
ksnk
Дата 6.11.2011, 11:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

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



А вот вам рекурсия на JavaScript  smile 
Есть правда проблема. У меня 26 значений в массиве на моем компьютере перебираются за 1,5 секунды примерно. каждое дополнительное значение увеличивает время в 2 раза. Но это - Javascript, так что на С должно летать и для 30 значений, imho...
Код

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],
    time=new Date().valueOf(),
    xcnt = numbers.length,
    result = 351,
    rescount=0,
    resultarray=[];

function fixresult(){
   // alert(resultarray);
    rescount++;
}

function calc(n,xresult,xmult){
    if(n==xcnt){
        if (xresult+xmult==result)
            fixresult();
        return ;
    }
    //try +
   // resultarray[n]='+';
    calc(n+1, xresult+xmult,numbers[n]);
    //try *
   // resultarray[n]='*';
    calc(n+1, xresult,numbers[n]*xmult);
}

calc(1,0,numbers[0]);
alert([xcnt ,rescount,new Date().valueOf()-time]);

Результат - 2 способа


Это сообщение отредактировал(а) ksnk - 6.11.2011, 12:14


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


Опытный
**


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

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



Dmi3ev, вы пошли не в ту сторону, сразу решив, что нужен перебор.

Но 2^29 * 30 для современных компьютеров - это неподъёмно за 2 секунды.


Я думаю, эту задачу надо решать динамическим программированием.

Если по-простому - давайте научимся считать табличку d[cnt][number], где cnt - это сколько чисел мы просмотрели (от 0 до N), number - это какое число у нас получилось (от 0 до 1000000), а само значение таблички d[cnt][number] - это сколько способов получить это число из первых number чисел.

Изначально мы полагаем d[0][0] = 1, т.е. мы можем получить число 0, не потратив на это ни одно из входных чисел, а число сделать это - равно единице.

Дальше мы делаем такую штуку. Берём очередное значение d[i][j] (в порядке возрастания i и j), и если оно не ноль - то мы должны выполнить переходы динамики, т.е. обновить этими значениями следующие ячейки таблицы. Для этого мы говорим: давайте переберём, сколько чисел, начиная с i-го, мы перемножим подряд и прибавим к текущему числу j. Перебираем, получаем новое количество i' и новое число j' - соответственно, к ячейке d[i'][j'] мы должны прибавить d[i][j].

В конце концов, когда мы сделаем все переходы, в ячейке d[N][S] получится ответ на задачу - искомое количество способов.


(Иными словами, мы с помощью динамики считаем число способов разбить число S на сумму нескольких слагаемых, каждое из которых - произведение одного или нескольких чисел.)


Этот метод тоже не очень быстрый - работает за 30 * 1000000 * 30/2 операций, что есть 450 млн. Но, во-первых, на быстрых компьютерах и это успеет отработать за 2 секунды, а, во-вторых, на самом деле ненулевых ячеек d[i][j] будет не так много, так что на практике 450 млн. операций достигаться никогда не будет.
PM MAIL WWW ICQ   Вверх
ksnk
Дата 6.11.2011, 18:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

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



maxdiver, 2^29 = 536 870 912 операций, по сравнению с вашими 450 млн - не впечатляющая эффективность метода smile

Откуда взялось 30 в формуле  30*2^29? Нам, вроде нужно только перебрать 2 разных символа в 29 позициях...

Кстати, если верить в то, что все числа целые, то получается довольно приятный результат, который исполним даже на javascript (Chrome 15...)
Код

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],
    xcnt = numbers.length,
    result = 2751,res=[],
    rescount=0,
    time=new Date().valueOf(),
    resultarray=[];

function appendresult(){
    res.push('\n\r');
    res.push(resultarray);resultarray=[];
    rescount++;
}

function calc(n,xresult,xmult){
    if(n==xcnt){
        if (xresult+xmult==result)
            appendresult();
        return ;
    } else if (xresult+xmult>result)
        return ;
    //try +
    resultarray[n]='+';
    calc(n+1, xresult+xmult,numbers[n]);
    //try *
    resultarray[n]='*';
    calc(n+1, xresult,numbers[n]*xmult);
}

calc(1,0,numbers[0]);
alert([rescount,new Date().valueOf()-time,res]);

2972 варианта за 0.250 сек.


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


Опытный
**


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

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



ksnk, наверное, кроме того что перебрать все варианты расстановки знаков, надо ещё посчитать получившееся выражение? Перебирать можно и без этого, но 2^29 точно будет.

А про 450 млн. я уже писал, что это лишь оценка сверху.
PM MAIL WWW ICQ   Вверх
ksnk
Дата 6.11.2011, 19:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

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



maxdiver, мой пример считает получившееся выражение. И даже сохраняет расстановку знаков.
Цитата(maxdiver @  6.11.2011,  18:52 Найти цитируемый пост)
А про 450 млн. я уже писал, что это лишь оценка сверху

 Возможно ее можно оценить более точно? 
Если бы эффективность была хотя бы в 4-8 раз лучше, уже имело бы смысл возится, а так преимущества по сравнению с перебором не видно.




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


Эксперт
***


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

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



Цитата

1. Что значит "не укладываюсь"? Какие временные ограничения и на что?

2 секунды.
Просчитывать результат надо, в ответе необходимо указать количество верных вариантов расстановки знаков.
скобок нет, приоритет соблюдается...
рекурсия - это идея, буду пробовать... перебор вариантов работает медленно... Очень медленно.
Обычно, дается гораздо больше времени, чем занимает решение, чтобы не зависеть от языка, компилятора, компа и т.д.
Цитата

2 секунды довольно дофига, чтобы перебрать все 2^30 вариантов

2^29 и у меня вылезает за это ограничение довольно сильно... Что означает, что я использую в корне неверный подход к решению...

Добавлено @ 20:13
Я решаю эту задачу на pascal, но это неважно, можно и C++, и Java, и.... Должно работать на всех языках за 2 секунды... Запас всегда дается большой, даже очень...

Добавлено @ 20:16
Цитата

я бы просто тупо перебором составил все варианты
 a1+a2*...*aN-1=S
a1*a2+...+aN-1=S и т.д. Можно все варианты сохранить в файл.

Попробуй, если уложишься хотя бы секунд в 10-15 уже будет неплохо.
Цитата

Можно все варианты сохранить в файл

2^29 строк сохранить  в файл?
Цитата

А потом с помощью синтаксического анализатора проанализировать выражения и получил бы результат.

читать из файла 2^29 строк и анализировать?
Сколько это времени займет? как сам думаешь?

Это сообщение отредактировал(а) Dmi3ev - 6.11.2011, 20:17


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

PM MAIL   Вверх
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 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


Профиль
Группа: Комодератор
Сообщений: 6813
Регистрация: 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 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


Профиль
Группа: Комодератор
Сообщений: 6813
Регистрация: 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 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


Профиль
Группа: Комодератор
Сообщений: 6813
Регистрация: 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 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


Профиль
Группа: Комодератор
Сообщений: 6813
Регистрация: 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 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


Профиль
Группа: Комодератор
Сообщений: 6813
Регистрация: 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
  Дата 17.10.2019, 10:47 (ссылка)  





  Вверх
Страницы: (2) [Все] 1 2 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

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


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

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


 




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


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

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