Question

Se dau numerele de la 1 la 10 și un număr a. dacă există cel puțin o combinație de operatori + și - care pusi între numerele de la 1 la 10 să formeze o expresie al cărei rezultat e a, sa se afiseze combinatia, daca nu exista nici o combinatie atunci sa se afiseze mesajul: "nu exista nici o combinatie".

Answer 1

Limitele pe care le va avea aceasta expresie vor fi date de cazurile in care toti operatorii sunt minus sau plus.
Deci, daca avem toti operatorii +
1+2+3+...+10=55
Daca avem toti operatorii - avem
1-2-3-..-10=-53
Deci daca a va fi in afara acestor limite, nu avem cum sa obtinem combinatia
Apoi, daca presupunem ca toti operatorii sunt la fel, cu exceptia unuia, sa-l notam cu n, atunci expresia se modifica in felul urmator
1+2+3+..-n+..+10=1+2+3+..+n+...+10 -n-n=55-2n, unde am adaugat un -n pentru a-l anula pe cel care l-am adaugat in suma.
Deci dupa cum vezi, daca unul are semn contrar, atunci expresia obtinuta va fi un numar impar(impar-par) Chiar daca sunt mai multe cifre cu semn negativ, folosind acelasi calcul, tot un numar par diferenta va iesi(2k sa zicem) si expresia finala va fi numar impar
In mod similar se poate arata si pentru operatorul negativ ca vom avea la sfarsit -53+2n, deci va da un nr negativ impar
Deci daca numarul a este par, nici atunci nu exista combinatie
Ca sa aflam combinatia atunci, calculam diferenta dintre limita si numarul a, sa zicem 55-a. Acea diferenta stim ca este 2n, deci n=(55-a)/2 si acest n de fapt este o suma a tuturor operatorilor cu semn negativ
Atunci putem determina care cifre adunate dau n, si pe acele cifre le afisam in combinatie cu semnul -, si restul cu semnul plus.

De exemplu daca a=49, atunci n=(55-49)/2=3
atunci
a=1+2-3+4+5+...+10
sau compuse pentru a=27 atunci n=(55-37)/2=9
dar 9 poate fi scris si ca 2+3+4
a=1-2-3-4+5+6+...+9+10
Atentie, nu toate numerele impare mai mici decat 55 pot fi exprimate
Ex. a=53, atunci n=(55-53)/2=1, deci numai cifra 1 poate forma pe n, si nu putem incepe sirul cu -1
In mod similar se face si penru numere negative

codul e mai jos
#include <iostream>
using namespace std;
int cifra_in_sir(int v[],int k,int x){

int i,gasit=0;

for(i=0;i<=k;i++){
if(v[i]==x){
gasit=1;
break;
}
}
return gasit;
}
int main(){

char combinatie[21];
int a,dif,i,n,lim_inf=0,lim_sup=0,v[10],k=0;
n=10;
cout<<"Numarul de obtinut:";
cin>>a;
for(i=1;i<=n;i++){
lim_sup=lim_sup+i;
}
for(i=-2;i>=-n;i--){
lim_inf=lim_inf+i;
}
lim_inf=lim_inf+1;

if(a<lim_inf||a>lim_sup||a%2==0){
cout<<"Nu exista combinatie!";
return 0;
}


if(a>0){
dif=lim_sup-a;
}
else{
dif=a-lim_inf;
}
dif=dif/2;
for(i=2;i<=10;i++){
if(dif-i>i){
dif=dif-i;
v[k]=i;
k++;
}
else if(dif-i==0){
dif=0;
v[k]=i;
break;
}
}
if(dif>0){
cout<<"Nu exista combinatie!";
return 0;
}
combinatie[0]='1';
for(i=1;i<18;i++){
if(i%2==1){

if(a>0&&cifra_in_sir(v,k,(i+1)/2+1)==1){
combinatie[i]='-';
}
else if (a>0&&cifra_in_sir(v,k,(i+1)/2+1)==0) {
combinatie[i]='+';
}
else if(a<0&&cifra_in_sir(v,k,(i+1)/2+1)==1){
combinatie[i]='+';
}
else{
combinatie[i]='-';
}

}
else{
combinatie[i]='0'+(i/2+1);

}
}
combinatie[18]='1';
combinatie[19]='0';

cout<<combinatie;
return 0;


}