Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Перебор вариантов, Перебор вариантов 
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 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

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



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

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


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


Эксперт
***


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


Бывалый
*


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


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


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

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



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


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


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


Бывалый
*


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


Эксперт
***


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


Бывалый
*


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


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


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

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



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


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


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

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



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


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


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

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



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   Вверх
Страницы: (3) Все [1] 2 3 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

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


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

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


 




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


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

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