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

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

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

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

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

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

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


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

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

Пример: 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

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

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

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

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

Это же "мартышкин труд". В начальном классе не учат программированию. Заставлять перебирать детей все варианты решения вручную не гуманно... Лучше бы он их логические задачи научил решать, а не чисто механически расставить знаки. От этого будет больше пользы.

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


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

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

Добавлено через 7 минут и 41 секунду

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

Добавлено через 12 минут и 32 секунды

а если результат будет больше S, то делать "откат" назад? в некоторых случаях, чуть ли не до первого слагаемого.. По моему так уйдет еще больше времени, чем обычным перебором.

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

хотя есть одна идея с промежуточными результатами, можно и так a1+a2 =b1, a3+a4=b2,  a1*a2=c1, a3*a4=c2.  а дальше эти промежуточные значения между собой складываем или умножаем. b1+b2=d1 b1*b2=e1, b1+c1=g b1*c1=... минус в том, что будет вычисленно очень много промежуточных результатов

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

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


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

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 млн. операций достигаться никогда не будет.

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

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

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

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

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

А про 450 млн. я уже писал, что это лишь оценка сверху.

maxdiver, мой пример считает получившееся выражение. И даже сохраняет расстановку знаков.

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

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

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

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

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

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

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

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

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