|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 23 Feb 2002 00:42:25
To : Sergey Pereslavcev
Subject : Re: imho нелегкий алгоритм, но нужен...
--------------------------------------------------------------------------------
Sergey Pereslavcev wrote:
> Дык вот программа должна так расставить знаки +-*/ между числами первого ряда,
> чтоб получилось второе число, либо сказать, что задача неразрешима никак.
По-моему, это NP-задача. Решается только методом полного перебора.
Количество операций - пропорционально факториалу от длины входной строки.
Это вытекает из того, что в системе возможны как +, так и -, да еще и миграция
символов между цифрами, то невозможно написать целевую функцию-ограничитель
отсечения ветвей без рассмотрения последних.
То есть нужен полный перебор.
Доказательство опускаю. Если хочешь построить его - используй метод
мат.индукции,
рассмотрев строку сначала из 2-х символов, а потом что происходит, если добавить
3-й,
потом 4-й и так далее.
> Только ответ о неразрешимости должен быть правильным, т.к. преп будет сам на
> бумажке решать :-)
Как писать программу: я бы делал рекурсивной функцией, разбирая строку слева
направо.
> C уважением, Sergey Pereslavcev.
> ... Воронежский Государственный Университет. ФизФак.
Обалдели совсем! Чем физиков мучают!
Я понимаю - будущих программеров, но физикам то оно зачем?
Мда, преп явно хочет тебя завалить...
Ладно, попробуй написать прогу сам. А если будет явно невмоготу -
спрашивай мылом - я так и быть, потрачу на твою задачку пару часов,
да так напишу, что у препа башня сьедет. Что ни говори, а такие
откровенные подставы надо наказывать!
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: imho нелегкий алгоритм, но нужен... 
