Задача №5 , Расставить +/-

[trainer]

Имеется последовательность десятичных цифр 1234567890123456789
Расставить внутри этой последовательности(т.е между цифрами) знаки + и/или - так, чтобы в результате вычисления полученного выражения получилось заданное число.
Если существуют несколько вариантов - выдать тот из них, который состоит из наименьшего количества операций(сложения или вычитания).
Если вариантов нет - сообщить об этом.
Прим.: для числа 34 выражение(одно из выражений) может быть таким:
12+34-56+78-90+123-45+67-89

---

Дополнение: для простоты будем считать, что заданное число удовлетворяет следующему критерию:
0 < число < 1000000

Сообщение отредактировано: trainer - 08.04.04, 12:01

[experimenter]

задачку уже можно решать или еще это только предложение?

[trainer]

Ну если задание ясно - можно решать.

[redfred]

Какие требования накладываются на решение задачи:
Оптимизация по скорости ?
Оптимизация по памяти ?
Компактный и читабельный код ?
или достаточно просто представить какое-нибудь решение ?

Задачи интересные. Но не всегда понятно в каком виде должен быть результат

[trainer]

У кого как получится. Интересные варианты, возможно, отмечу.
Может быть и самый медленный вариант, но с очень интересным решением.
Это же задача, а не соревнование.
Хотя читабельность приветстсвуется.

[Cool_Blade]

Ну типа вот :

 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define false 0
#define true 1
 
#define maxlen 8
#define str "1234567890123456789"
 
#define max_deep 6
 
long value;
char sr[30];
 
char calc(char *s, char *sr,long t, int deep)
{
   if (deep>max_deep) return false;
 
   long temp;
   char stemp[maxlen+1];
   int i = strlen(s);
   if (i>maxlen) i=maxlen;
 
   for (;i>0; i--)
   {
      strncpy(stemp, s, i);
      stemp[i]='\0';
      temp = atol(stemp);
      if (*(s+i)=='\0')
      {
        if (t+temp==value)
        {
            strcpy(sr, "+");
            strcat(sr, stemp);
            return true;
        }
        else if (t-temp==value)
        {
            strcpy(sr, "-");
            strcat(sr, stemp);
            return true;
        }
      }
      else
      {
        if (calc(s+i, sr, t+temp, deep+1))
        {
            char ttt[30];
            strcpy(ttt, "+");
            strcat(ttt, stemp);
            strcat(ttt, sr);
            strcpy(sr, ttt);
            return true;
        }
        else if (calc(s+i, sr, t-temp, deep+1))
        {
            char ttt[30];
            strcpy(ttt, "-");
            strcat(ttt, stemp);
            strcat(ttt, sr);
            strcpy(sr, ttt);
            return true;
        }
      }
   }
   return false;
}
 
void main()
{
   scanf("%U", &value);
   if (calc(str, sr, 0, 0)) printf("%s\n", sr);
   else printf("no!\n");
   getchar(); getchar();
}

Сообщение отредактировано: Cool_Blade - 08.04.04, 10:30

[Sazabis]

как относится к первому минусу ???

You have a custom string '12345'
What number you want to receive ? 45
1+2-3+45
-1-2+3+45
Press any key...

You have a custom string '12345'
What number you want to receive ? 2344
-1+2345
Press any key...

[trainer]

Цитата

trainer, 7.04.04, 09:58
Расставить внутри этой последовательности

Т.е. можете считать, что все числа, которые могут составить полученное вражение, должны быть положительны.
P.S. Задание уточнено 8.04.04, 11:51 мск

Сообщение отредактировано: trainer - 08.04.04, 07:54

[Sazabis]

особо потестить не начем но все-таки вариантик свой выложу.
Конвертит atol'ом так что вполне возможны баги с переполнением
хотя что еще ожидать, работать с long double уже морока и немного не катит к смыслу задачи...
Прикреплённый файлplusminus.cpp (2.39 Кбайт, скачиваний: 220)

[Cool_Blade]

Исправил ошибку в программе - см. выше :)

[redfred]

(9+0123) == (9+123) ?

[trainer]

Цитата

redfred, 8.04.04, 14:22
(9+0123) == (9+123) ?

И что это значит?

[redfred]

Система надеюсь, десятичная. Можно ведь и на такой вариант напороться:

  
if( (9+0123) == (9+123)  ) printf("(9+0123) == (9+123)\n" );
                   else    printf("(9+0123) != (9+123)\n" );

Что, собственно, у меня и получилось

Добавлено в 08.04.04, 12:49:
Думаю, что я народ запутал:)
Спрошу иначе: При переборе вариантов могут получаться слагаемые с 0 впереди. Некоторые функции воспринимают его как восьмеричное число. Я так полагаю, что, перевод в число строки "0123" должен быть таким же как перевод в число "123". Так или нет ?

[trainer]

Цифры(и числа) десятичные.
Это дополнение уже внесено в условие(см. #1)

P.S. Рассматривайте задачу с точки зрения математики. C/C++ в данном случае - инструмент реализации.

Сообщение отредактировано: trainer - 08.04.04, 12:55

[experimenter]

вот мое решение.

 
#include <string>
#include <iostream>
 
using namespace std;
string s;
 
long len,n,N, top;
struct PlusMinus
{
    long offset;
    char c;
};
 
PlusMinus Plus[10000];
 
void CalculateIt(int offset,int num);
 
 
int main(int argc, char* argv[])
{
 
    long nMax, i, j;
 
    while(true)
    {
        std::cin>>s;
        std::cin>>N;
        len = s.length();
        
        nMax = len - 1;
        try
        {
         for(n = 0; n <= nMax; n++)
         {
             top = -1;
             CalculateIt(1,n);
         }
         cout<<"The solution doesn't exist.I'm really sorry."<<endl;
         continue;
        }
        catch(int k)
        {
            if(k != 1) break;
            string sTemp,sOut;
            // êîððåêòèðîâêà âûõîäíîé ïîñëåäîâàòåëüíîñòè, ò.å. ÷òîáû âûâîä íå ñîäåðæàë
            // ÷èñåë, íà÷èíàþùèõñÿ ñ íóëÿ
            for(i = 0, j = 0; i < len; i++)
            {
                sTemp += s[i];
                if(j < top + 1 )
                if(i == Plus[j].offset - 1 && top != -1)
                {
                    sTemp += char(Plus[j++].c);
                }
            }
            j = sTemp.length();
            char PrevSign = 0;
            for(i = 0; i < j; i++)
            {
                sOut += sTemp[i];
                if(sTemp[i] == '0' && i + 1 != j &&
                   (sTemp[i + 1] != '-' || sTemp[i + 1] != '+') &&
                   ((sTemp[i - 1] == '-' || sTemp[i - 1] == '+') || PrevSign))
                {
                    if(!PrevSign)
                    {
                        PrevSign = sTemp[i - 1];
                        sOut += PrevSign;
                    }
                    else
                     sOut += PrevSign;
                }
                else
                    PrevSign = 0;
            }
            // âûâîä ðåçóëüòàòà
            cout<<sOut<<endl;
        }
 
    }
    return 0;
}
 
void CalculateIt(int offset, int num)
{
int i, sum, j, t, POW, off, MaxOff, k;
 
    if(!num)
    {
        //âû÷èñëåíèå ðåçóëüòàòà
        for(j = top, i = len - 1, sum = 0; j > - 1; j--)
        {
            t = 0; k = 0;
            POW = 1;
            do
            {
                t += int(s[i] - '0')*POW;
                POW *= 10;
                i--;
                k++;
            }while(i >= Plus[j].offset);
            sum += (Plus[j].c == '+') ? t : -t;
        }
    
        t = 0;
        POW = 1;
        do
        {
                t += int(s[i] - '0')*POW;
                POW *= 10;
        }while(--i != -1);
        sum += t;
        if(sum == N) throw int(1);
    }
    else
    {
        
        MaxOff = len -  num;
        // çàñîâûâàåì ìèíóñû è ïëþñû
        for(off = offset; off <= MaxOff; off++)
        {
            top++;
            Plus[top].c = '-';
            Plus[top].offset = off;
            CalculateIt(off + 1, num - 1);
 
            Plus[top].c = '+';
            CalculateIt(off + 1, num - 1);
            top--;
 
        }
    }
 
return;
}

Сообщение отредактировано: experimenter - 09.04.04, 04:51