Rezolva problema

[Patrunjel]

Consideram un sir de n (n<=100) cifre. Plasati in fata oricarei valori, unul din operatorii +,-,*. astfel incat expresia rezultata sa aiba valoarea S. Cifrele nu isi vor schimba pozitiile in cadrul sirului. Afisati, pe ecran, pe cate o linie, expresiile obtinute.

Exemplu:

S=5     n=4
2 8 1 4

-Se va afisa- 
+2+8-1-4

Orice rezolvare (in pseudocod sau C++, fiindca doar pe astea le inteleg) e rasplatita cu +rep, si like, pana la 6 jumate. La 6 jumate dau un hint, si rezolvarile se rasplatesc doar cu +rep.

Pare retardata da nu e, are o chihita care o face fututa.

*Pentru hateri: Nu am rezolvat-o. M-am prins cum se face, dar nu am rezolvat-o, tocmai din cauza chichitei, nu am putut sa-i dau de capat. TOTUSI, NU E TEMA.

Edited February 2, 2012 by Patrunjel

[em]

B?nuiesc c? se ?ine cont de prioritatea opera?iilor?

Extra, ?i c? pe prima pozi?ie nu se poate afla *?

Edited February 2, 2012 by em

[Patrunjel]

1) Da.

2) Nu.

E ca si cum ar fi o expresie normala, cum ai scrie-o intr-un caiet, plm. Doar ca daca primul numar pe care il scrii e pozitiv pui + inaintea lui (lucru care se subintelege in general)

Edited February 2, 2012 by Patrunjel

[bcman]

Ast?zi am dat ?i eu de aceast? problem?. S-a dat la clasa a VIII-a la OJI, doar c? se foloseau doar operatorii pentru adunare ?i sc?dere. Din p?cate, nu am reu?it s? o rezolv (înc?), dar nu m? dau b?tut.

[Patrunjel]

Oji e in martie(sau tu te refereai la ediitle trecute?). Fii atent la hint cand il dau, e destul de simplu doar cu + si - (da-mi un pm daca vrei si iti explic).

[flux]

one word: backtracking

[FreddieTux]

Pentru + si - e simplu. Memoram numerele intr-un vector si apoi ii atasam acestuia un alt vector in care vom face o adunare binara. Vom presupune ca 1 este + si 0 este - si vom face calculele aferente primului vector. In cazul in care rezultatul nu este s, vom mai adauga 1 vectorului atasat. Si tot asa pana cand rezultatul va fi s. In ceea ce priveste inmultirea, inca ma mai gandesc

[Patrunjel]

Da, stiu ca pentru + si - e simplu, inmultirea e tocmai capcana de care am zis eu.

Hinturi:

1) (evident) Backtracking

2) daca inmultesti elementul de pe pozitia i-1 cu elementul de pe pozitia i, aduni rezultatul la suma. Insa inainte de asta tu ai adunat ceva ce nu mai are ce cauta acolo, odata ce mergi pe varianta cu * (prioritatea operatiilor)

3) x+y*z*k*j. Think about it.

[vexyro]

Solu?ie:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* s;
char* s2;
int N = 0, S = 0;
int sir[100];

int produs() {
    char *c = strdup(s);
    int num1, num2;
    char op;

    num1 = atoi(strdup(s));

    while (*s >= '0' && *s <= '9')
        s++;
    op = *s;

    while (op == '*')
    {
        s++;
        num2 = atoi(strdup(s));

        while (*s >= '0' && *s <= '9')
            s++;
        op = *s;

        num1 *= num2;

    }
    return num1;
}

int suma() {
    int t1, t2;
    char op;
    int sgn = 1;

    if (*s == '-')
    {
        sgn = -1;
    }
    *s++;
    t1 = produs();
    t1 *= sgn;
    op = *s++;

    while (op == '+' || op == '-')
    {
        t2 = produs();
        switch (op)
        {
            case '+': t1 += t2; break;
            default : t1 -= t2; break;
        }
        op = *s++;
    }
    return t1;
}

void eval(int n)
{
    int i;

    if (n == 2*N)
    {
            s = strdup(s2);
            if (suma() == S && *s2 != '*')
                printf("%s\n",s2);
    }
    else
    {
        char c[100];
        for (i = 0; i < 3; i++)
        {
            itoa(sir[n/2],c,10);
            switch(i)
            {
                case 0: s2[n] = '+'; break;
                case 1: s2[n] = '-'; break;
                case 2: s2[n] = '*'; break;
            }
            s2[n+1] = '\0';
            itoa(sir[n/2],c,10);
            strcat(s2,c);
            eval(n+2);
        }
    }
}

int main()
{
    s=(char*) malloc(100*sizeof(char));
    s2=(char*) malloc(100*sizeof(char));
    int i;

    scanf("%d",&N);

    for (i = 0; i < N; i++)
        scanf("%d",&sir[i]);

    scanf("%d",&S);

    eval(0);
    return 0;
}

L.E.

E valabil codul de mai sus ?i pentru opera?ii de împ?r?ire, în expresia dat? cu urm?toarele modific?ri:

int produs() {
    char *c = strdup(s);
    int num1, num2;
    char op;

    num1 = atoi(strdup(s));

    while (*s >= '0' && *s <= '9')
        s++;
    op = *s;

    while (op == '*')
    {
        s++;
        num2 = atoi(strdup(s));

        while (*s >= '0' && *s <= '9')
            s++;
        op = *s;

        [COLOR="#FFFF00"]switch(op)
	{
		case '*': num1 *= num2; break;
		case '/': num1 /= num2; break;
	}[/COLOR]
    }
    return num1;
}

?i

void eval(int n)
{
    int i;

    if (n == 2*N)
    {
            s = strdup(s2);
            if (suma() == S && *s2 != '*' [COLOR="#FFFF00"]&& *s2 != '/'[/COLOR])
                printf("%s\n",s2);
    }
    else
    {
        char c[100];
        for (i = 0; i < 3; i++)
        {
            itoa(sir[n/2],c,10);
            switch(i)
            {
                case 0: s2[n] = '+'; break;
                case 1: s2[n] = '-'; break;
                case 2: s2[n] = '*'; break;
            }
            s2[n+1] = '\0';
            itoa(sir[n/2],c,10);
            strcat(s2,c);
            eval(n+2);
        }
    }
}

Edited February 2, 2012 by vexyro

[FreddieTux]

O solutie de incepator (citeste datele din fisierul "fisier2" care are pe prima linie s si n separate printr-un spatiu si pe a doua sirul de numere)

#include <stdio.h>

int produs(int numere[2][100],int &i,int n)
{
	long produs = 1;
	produs*=numere[0][i];
	if (numere[1][i]==0) produs*=-1;
	i++;
	while(numere[0][i]==2 && i<n)
	{
		produs*=numere[0][i];
	}
i--;
return produs;
}

int calcul(int numere[2][100],int n)
{
	int i;
	long sum=0;
	for (i=0;i<n;i++)
	{
		if (numere[1][i]==0 &&numere[1][i+1]!=2) sum-=numere[0][i];
		else
			if (numere[1][i]==1 && numere[1][i+1]!=2) sum+=numere[0][i];
				else
					sum+=produs(numere,i,n);
	}
return sum;
}

int main()
{
	int numere[2][100],n;	
	long s,sum=0;
	int i;
//citire si initializare
	FILE * rfile;
	rfile = fopen("fisier2","r");
	fscanf(rfile,"%d %d",&s, &n);
	for (i=0;i<n;i++)
	{ 
		fscanf(rfile,"%d",&numere[0][i]);	
		numere[1][i]=0;
	}

//adunare baza 3
for(sum=calcul(numere,n);sum!=s;sum=calcul(numere,n))
{

	numere[1][0]++;
	for (i=0;i<n;i++)
	{
		if (numere[1][i]>2)
		{
			numere[1][i]=0;
			numere[1][i+1]++;
		}
	}
}

//afisare
for (i=0;i<n;i++)
{
	if(numere[1][i]==0) printf("-");
	if(numere[1][i]==1) printf("+");
	if(numere[1][i]==2) printf("*");
	printf("%d",numere[0][i]);
}
printf("=%d\n",sum);
}

[Patrunjel]

@vex : Nu am putut compila. Incearca sa folosesti functii standard.Itoa apare ca nedeclarata. Am incercat sa modific din string.h in string ( pe ideea ca string.h e deprecated), tot asa.

@em: Felicitari, insa totusi are cateva bube : Nu respecta formatul datelor de iesire (daca in solutie vine -x spune +-x, desi x a fost dat ca numar pozitiv), dar asta e neimportant. Totusi, nu a trecut un test: S=12 n=4 , -2 5 3 1 . Oricum, meriti +rep, inafara de testul ala pe alte cateva si-a facut treaba.

@freddie : Pentru S=113, n=5, 2 3 5 8 9 se blocheaza intr-un loop infinit (cred)

Felicitari celor care au incercat. Indiferent de rezultat au demonstrat ca nu-s 1337 h4x0r1 si ca se descurca si cu un limbaj de programare.

@em "You must spread some Reputation around before giving it to em again." Scuze, n-am putut.

Edited February 2, 2012 by Patrunjel

[vexyro]

@Patrunjel:

1. Pe Win nu comenteaz? nimic în leg?tura cu itoa dar pe Linux face mutre pentru c? nu este o func?ie standard. Ai putea sa încerci s? recompilezi cu

sprintf(c,"%d",sir[n/2]);

în loc de

itoa(sir[n/2],c,10);

?i ar trebui s?-?i mearg?.

2. La început nu s-a precizat dac? numerele sunt sau nu pozitive. Normal c? pic? unele teste pentru c? eu unul nu am stat s? iau în considerare ?i acest aspect, dar se poate aplica un patch

Edited February 2, 2012 by vexyro