|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 24 Feb 2002 22:08:34
To : Sergey Pereslavcev
Subject : imho нелегкий алгоритм, но нужен...
--------------------------------------------------------------------------------
22 Фев 02 23:42, Oleg I. Khovayko wrote to you:
>> Дык вот программа должна так расставить знаки +-*/ между числами
>> первого
OK> ряда,
>> чтоб получилось второе число, либо сказать, что задача неразрешима
>> никак.
OK> По-моему, это NP-задача. Решается только методом полного перебора.
OK> Количество операций - пропорционально факториалу от длины входной
OK> строки. Это вытекает из того, что в системе возможны как +, так и -,
OK> да еще и миграция
Исходя из моего опыта препод скорее всего хочет обычную рекурсивную прогу, я
как-то кому-то такую задачу решал, только найти не могу жалко. Вообщем делать
надо "в лоб" рекурсивно и не париться.
>> Только ответ о неразрешимости должен быть правильным, т.к. преп
>> будет сам на бумажке решать :-)
OK> Как писать программу: я бы делал рекурсивной функцией, разбирая строку
OK> слева направо.
>> C уважением, Sergey Pereslavcev.
>> ... Воронежский Государственный Университет. ФизФак.
OK> Обалдели совсем! Чем физиков мучают!
OK> Я понимаю - будущих программеров, но физикам то оно зачем?
OK> Мда, преп явно хочет тебя завалить...
OK> Ладно, попробуй написать прогу сам. А если будет явно невмоготу -
OK> спрашивай мылом - я так и быть, потрачу на твою задачку пару часов,
OK> да так напишу, что у препа башня сьедет. Что ни говори, а такие
OK> откровенные подставы надо наказывать!
Да брось ты. Hечего там такого жуткого нету. Вот нашёл укороченный вариант без
интерфейса и только с операциями "+" "-":
Program Num;
Uses Crt;
Type tStr = String[20];
Var N:Integer;{Искомое число}
(***************************************************************)
Procedure Find(s1:tStr;{Решение}
s:Integer;{Hайденная сумма}
k:Integer;{Последнее число}
i:Integer{проверяемое число});
Var d:Char;
Begin
if i>9 Then
if (S+K) = N Then
Begin
WriteLn(s1+' = ':25,N);
ReadKey;
End
else
Else
Begin
d:=Char(i+Byte('0'));{i - в символьной форме}
{1. Знак конкатинации}
Find(s1+d,s,K*10+i,i+1);
{2. Знак '+'}
if s1='' THen Find(d,s+k,i,i+1)
Else Find(s1+'+'+d,s+k,i,i+1);
{3. Знак '-'}
Find(s1+'-'+d,s+k,-i,i+1);
End;
End;
Begin
WriteLn('Введите число');
ReadLn(n);
Find('',0,0,1);
End.
Andrey
... Эх, раз, ещё раз, ещё много много раз (E:\WIN95\setup.exe).
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
