Решение задачи "Выражение" с Меньшиков

Без пояснения   Просмотров: 16


Даны N целых чисел X1, X2, ..., XN. Расставить между ними знаки "+" и "-" так, чтобы значение получившегося выражения было равно заданному целому S.

Код

#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
int x[25];
char sign[25];
int sum,n;
void input()
{
    cin>>n>>sum;
    for (int i=0;i<n;i++)
        cin>>x[i];
}
void output()
{
    cout<<x[0];
    for (int i=1;i<n;i++)
        cout<<sign[i]<<x[i];
    cout<<"="<<sum;
 
    exit(0);
}
 
void rec(int curSum, int curIndex)
{
    if (curSum == sum) // ответ найден
        output();
    if (curIndex == n) // терминальное условие
        return;
 
    sign[curIndex] = '+';
    rec(curSum + x[curIndex], curIndex+1);
   
    sign[curIndex] = '-';
    rec(curSum - x[curIndex], curIndex+1);
}
void solve()
{
    rec(x[0],1);
    cout<<"No solution";
}
int main()
{
    input();
    solve();
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться