Получить заданное число m сложением/вычитанием цифр

Очень-очень нужна помощь!
дано n (n>=2) количество цифр от 1 до 9 и любое число m. Написать программу расстановки между каждой парой чисел, записанных именно в таком порядке, знаков "+" и "-" так, чтобы значение полученного выражения равнялось m.

0

_Ivana, да пока работает. ща еще тестов погенерю.

Добавлено через 1 минуту
_Ivana, вначале мейна пишешь freopen("output.txt", "w", stdout);

0

Сообщение от _Ivana Помоги мне убрать деление на 0 и чтобы консоль не закрывалась и можно было смотреть все тесты.

....

Добавлено через 3 минуты
О блин! Консоль держать не научился, а перенаправлять выходной поток в файл зато научился Спасибо, буду теперь файл смотреть Но ты думаю сам разберешься что поправить, чтобы писала только нужное тебе в вывод.

0

_Ivana, да. я короче как тест найду, напишу сюда. я могу потестить на тестах, где числа массива до 1000?

0

SlavaSSU, проверил твои тесты, все работают и выдают YES. Можешь еще хоть 10^9 чисел массив задать - будет так же быстро. На некоторых типах входных данных алгоритм может не находить вариант, надо дописать вторую часть.
Если надо числа массива до 1000 - увеличь диапазон трех моих массивов до 1000 и начинай счетчик цикла с 999.

Добавлено через 2 минуты
Структура моего вывода понятна? Как там знаки расставлены и как это проверить видно?

0

_Ivana, а у тебя с отрицательным m работает?

Добавлено через 11 минут
_Ivana, тест
5 3
1 2 3 4 5

твой ответ NO
правильный ответ YES: 1 - 2 + 3 - 4 + 5

лечге было руками найти, чем генерить)))

0

SlavaSSU, да, я еще вчера находил такие случаи. Например,
5 5
8 6 2 8 7
У меня выдаст NO, а вариант есть. Поэтому и говорю, что нужна дополнительная последующая шлифовка результата напильником, и ее алгоритм тоже понятен. Можно реализовать, в принципе.

0

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

0

Если кто-то говорит что что-либо невозможно, то это еще не повод не попробовать. И даже если этот кто-то не ошибается, то запросто может случиться так, что имелось в виду "невозможно в общем случае", а применительно к ограниченному диапазону от 1 до 9 очень может быть что возможно. Но ведь мое решение действительно не зависит от входных данных (длины массива), не так ли? И неужели мой алгоритм с его неприличной скоростью не заслуживает внимания? Честно говоря, я сам не могу сказать, что вижу алгоритм допиливания стопроцентно ясно и гарантирую, что он не пропустит ни одного решения, это для моего низкого уровня не самая простая задача. Но и увидеть, что мой алгоритм допиливания гарантированно пропустит какие-то удачные варианты я тоже не могу. И наверное я переключу свои силы на что-нибудь другое Но посоревновались имхо все равно интересно

Добавлено через 7 минут
ЗЫ и тем не менее я очень-очень подозреваю, что можно придумать хороший алгоритм допиливания. По крайней мере, на всех обнаруженных мной по сей момент вариантах исходных данных, приводящих к ошибкам исходного алгоритма, мой текущий алгоритм допиливания приводит все в порядок и выдает правильный ответ.

0

_Ivana, эти кто-то - это ученые либо вики уже не помню или статься какая-нить. ну короче не пацан с улицы сказал, а авторитетный источник.

0

SlavaSSU, ссылку в студию. И посмотрим на авторитет этого источника

0

_Ivana, раз, два, три.

1

Спасибо, почитаю.

Добавлено через 2 часа 32 минуты
После читания некоторого количества интернета по теме выяснилось, что я реализовал максимально оптимизированный жадный алгоритм сложности О(1) (не зависящий от объема входных данных), который более чем имеет право на жизнь в группе приближенных алгоритмов NP-полных задач, не всегда находящих решение. И еще выяснилось, что существует тайный алгоритм Писинжера, решающий данную задачу точно за линейное время О(N). На русском публикаций по нему не нашел, на английском тоже не в свободном доступе - http://www.citeulike.org/user/... le/7333571

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

0

_Ivana, xD. такой алгоритм только у меня, и у Писинжера. а если серьезно, то я думая навряд ли. Если он какой-то тайный и поддался только ему. Ну он крут че, за линию умеет такую задачу решать.

0

Не, ну понятно, что если он его придумал только в 2000 году, а до этого тоже не дураки над задачей думали, то это может о чем-то говорить Хотя, с другой стороны, чем мы хуже? Может и придумали бы Есть шанс попросить на научном форуме эту его статью, может у кого есть.
А теперь про ваш алгоритм - у вас ДП? Точный? О(N^2)? Или нет? Я просто не разбирал ваш алгоритм, своим был занят

0

_Ivana, алгоритм точный. да ДП. работает за O(n * SumOfAllNumbers);

0

Вот и срываются покровы и маски А у меня (как вы наверное догадались) - жадный с оптимальным итеративным разбиением чисел от бОльших (9) к меньшим (1), оптимальное разбиение на каждой стадии, но оно не гарантирует глобального оптимального разбиения.

0

Сообщение от _Ivana чтобы консоль не закрывалась

Вот.

0

_Ivana, SlavaSSU, вы б на ideone тестили. и результаты бы видно было и время объективно
типа
http://ideone.com/hwNYas
http://ideone.com/BfW4dk

0

gru74ik, не поможет. Когда у меня по умолчанию ввод/вывод был ассоциирован с консолью, это прокатывало. А когда я переключил ввод на файл, то system("pause") не отрабатывало, приходилось на ноль делить - см. мой код, я же его привел.

pycture, спасибо, оказывается онлайн-компиляторы и время работы меряют. Правда не знаю, читают ли из файла, и если да, то можно ли его загрузить. Насколько я понял, вы свою программу на F# написали, хотя по ссылке не видно вообще какой выбран язык. И если мерить скорость, то я бы конечно переписал свою рекурсию на 2 переменных функции вместо 6, чтобы зря контекст лишний не хранить. Но тогда нужны были бы пара глобальных переменных, зато выполнение было бы еще быстрее.

ЗЫ а, вру - в правом углу написан выбранный язык.

0

Сообщение от _Ivana Правда не знаю, читают ли из файла

там при редактировании исходника или после форка есть кнопка stdin

0