Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
epidemia de obezitate (si de diab...

RIP ... Jerry Lewis

Drept de mostenire

Vad in ceata
 Imigrantii- resursa de progres si...

Eroare baza de date sa-mp

Ecran pe jumatate negru

Suedia e la un pas sa devina para...
 Biserica scandaloasa din Oradea

Parintele Parodie

O vedeta de televiziune din Roman...

Renault Talisman/Megane Gt
 Liviu Pop ministrul caricatura la...

Demisie fara preaviz

vsftpd + SSL/TSL

Gigi Becali Sexolog
 
Forumul Softpedia folosește "cookies" pentru a oferi utilizatorilor o experiență completă. Vezi detalii sau închide mesaj (x)

[TEMA] n ca suma de nr consecutive impare cu bkt

  • Please log in to reply
12 replies to this topic

#1
VladBtz

VladBtz

    Active Member

  • Grup: Members
  • Posts: 1,613
  • Înscris: 24.09.2014
  • ID membru: 880,195
Fie un numar n  natural mai mic decat 100. Sa se utilizeze metoda backtracking recursiva ca sa fie scris ca si suma de numere impare consecutive (strict crescatoare).

Ex: 8  se scrie ca si 1 7 sau 3 5

#include<stdio.h>
#define true 1
#define false 0
int valid(int k, int sol[])
{
for(int i=1; i<k; i++)
	 if(sol[k]<=sol[i] ) return false;
return true;
}

int suma(int k, int n, int sol[])
{
int s=0;
for(int i=1;i<=k;i++)s+=sol[i];
if (s==n)return true;
return false;
}

void backtrack(int k,int n,int sol[])
{
if(suma())
{
	 for(int i=1;i <=n; i++) printf("%d ",sol[i]);
	 printf("\n");
} else for(sol[k]=1; sol[k]<=n; sol[k]+=2 )
			 {
			 if( valid(k,sol)) backtrack (k+1,n,sol);
			 }		
}

int main(int argc, char**argv)
{
int sol[100],n;
scanf("%d",&n);
backtrack(1,n,sol);
return 0;
}


Edited by VladBtz, 18 April 2017 - 10:47.


#2
MarianG

MarianG

    Guru Member

  • Grup: Moderators
  • Posts: 16,420
  • Înscris: 10.08.2005
  • ID membru: 43,530
  • Locație: Iasi
pai 1 7 nu este impar consecutiv, crescatoare da, dar este adunarea comutativa

Edited by MarianG, 18 April 2017 - 14:23.


#3
ccdsah

ccdsah

    Member

  • Grup: Members
  • Posts: 657
  • Înscris: 16.03.2013
  • ID membru: 803,418
Pun enuntul corect te rog.
De exemplu pentru 6 nu este solutie.

#4
VladBtz

VladBtz

    Active Member

  • Grup: Members
  • Posts: 1,613
  • Înscris: 24.09.2014
  • ID membru: 880,195

View PostMarianG, on 18 aprilie 2017 - 14:20, said:

pai 1 7 nu este impar consecutiv, crescatoare da, dar este adunarea comutativa

Doar impar crescator. n se citeste ca fiind un numar care sigur are solutie

#5
dani.user

dani.user

    Guru Member

  • Grup: Moderators
  • Posts: 21,994
  • Înscris: 24.02.2007
  • ID membru: 146,987

View PostVladBtz, on 18 aprilie 2017 - 10:42, said:

Fie un numar n  natural mai mic decat 100. Sa se utilizeze metoda backtracking recursiva ca sa fie scris ca si suma de numere impare consecutive (strict crescatoare).

Vrei review la cod sau e gresit ceva prin el si nu te prinzi ce?

#6
VladBtz

VladBtz

    Active Member

  • Grup: Members
  • Posts: 1,613
  • Înscris: 24.09.2014
  • ID membru: 880,195

View Postdani.user, on 20 aprilie 2017 - 17:52, said:

Vrei review la cod sau e gresit ceva prin el si nu te prinzi ce?

ambele. nu imi dau seama ce e gresit, debuggerul nu ma prea ajut.

Later edit, ceva mai bine dar tot nu merge:

#include<stdio.h>
#define true 1
#define false 0
int suma(int k, int n, int sol[]);
int valid(int k, int n,int sol[]);
void backtrack(int k, int n, int sol[]);

int main(int argc, char**argv)
{
int sol[100],n;
scanf("%d",&n);
backtrack(1,n,sol);
return 0;
}

int suma(int k, int n, int sol[])
{
for(int i=1, s=0; i<=k; i++) s+=sol[i];
return s;
}

int valid(int k, int n,int sol[])
{
for(int i=1; i<k; i++)
		 if(sol[k] <= sol[i] || suma(k , n, sol) >n ) return false;
return true;
}

void backtrack(int k,int n,int sol[])
{
if(suma(k,n,sol)==n)
{
		 for(int i=1; i <k; i++) printf("%d ",sol[i]);
		 printf("\n");
} else for(sol[k]=1; sol[k]<=n; sol[k]+=2 )
			 {
			 if( valid(k,n,sol)) backtrack (k+1,n,sol);
			 }
}


Edited by VladBtz, 20 April 2017 - 18:43.


#7
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,616
  • Înscris: 22.02.2009
  • ID membru: 422,002
E greu sa te ajute debugger-ul cand scrii mai multe instructiuni pe o singura linie. Altfel ai fi vazut instant ca tu aduni numere neinitializate!!! Sigur, problema apare o singura data, la prima apelare si in 99.99% din cazuri nu creeaza probleme.
Cateva observatii:
1. Daca tot postezi aici, incearca sa folosesti un standard C mai nou sau de ce nu un standard C++. Poti dupa aia sa-l transcrii inapoi in standardul in care vrei tu.
    a. in functia suma ai declarat s in interiorul for-ului. Scopul variabilelor declarate in for a fost restrans de standarde mai noi doar la blocul for.
    b. sterge definitiile pt true si false
2. De ce afisezi de la (1,k-1), dar suma o faci de la 1 la k?! (asta pare sa fie principala greseala in cod)
3. Posibil ca asa sa va fi fost predat la scoala algoritmul, dar in majoritatea limbajelor indexarea incepe cu 0!!
4. Declara functia main fara parametrii daca tot nu-i folosesti in program.

Cod usor alterat pentru a rezolva problema.
#include<cstdio>
int suma(int k, int n, int sol[]);
int valid(int k, int n,int sol[]);
void backtrack(int k, int n, int sol[]);
int main()
{
	int sol[100],n;
	scanf("%d",&n);
	backtrack(1,n,sol);
	return 0;
}
int suma(int k, int n, int sol[])
{
	int s = 0;
	for(int i=1; i<k; i++)
		s+=sol[i];
	return s;
}
int valid(int k, int n,int sol[])
{
	for(int i=1; i<k; i++)
		if(sol[k] <= sol[i] || suma(k , n, sol) > n)
			return false;
	return true;
}
void backtrack(int k,int n,int sol[])
{
	if (k>2 && suma(k,n,sol) == n ) {
		for(int i=1; i <k; i++)
			printf("%d ",sol[i]);
		printf("\n");
	} else {
		for(sol[k]=1; sol[k]<n; sol[k]+=2 ) {
			if( valid(k,n,sol))
				backtrack (k+1,n,sol);
		}
	}
}



#8
dani.user

dani.user

    Guru Member

  • Grup: Moderators
  • Posts: 21,994
  • Înscris: 24.02.2007
  • ID membru: 146,987

View PostVladBtz, on 20 aprilie 2017 - 18:26, said:

ambele. nu imi dau seama ce e gresit, debuggerul nu ma prea ajut.

Pana la debugger, compilatorul iti indica probleme grave

Quote

a.c: In function 'suma':
a.c:19:8: error: 's' undeclared (first use in this function)
return s;
    ^
a.c:19:8: note: each undeclared identifier is reported only once for each function it appears in


#9
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,616
  • Înscris: 22.02.2009
  • ID membru: 422,002
Cel mai probabil foloseste un compilator C cu standard C90 sau anterior. Am atras atentia in postarea anterioara despre scopul variabilelor pentru ca initial am dat peste aceeasi problema.

#10
VladBtz

VladBtz

    Active Member

  • Grup: Members
  • Posts: 1,613
  • Înscris: 24.09.2014
  • ID membru: 880,195

View PostCy_Cristian, on 21 aprilie 2017 - 21:08, said:

Cel mai probabil foloseste un compilator C cu standard C90 sau anterior.

C99, d-aia pot sa pun si int in for

Edited by VladBtz, 22 April 2017 - 17:55.


#11
VladBtz

VladBtz

    Active Member

  • Grup: Members
  • Posts: 1,613
  • Înscris: 24.09.2014
  • ID membru: 880,195
Nu ma mut pe C++ pana nu ajung sa cunosc in profunzime C. Imi dezvolta mai mult gandirea, sa folosesc de exemplu bkt in loc de next_permutation din STL.

Edited by VladBtz, 22 April 2017 - 20:05.


#12
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,616
  • Înscris: 22.02.2009
  • ID membru: 422,002

View PostVladBtz, on 22 aprilie 2017 - 17:52, said:

C99, d-aia pot sa pun si int in for
Nenea astia zic cu totul altceva:
http://port70.net/~n...ft.html#3.6.5.3
http://port70.net/~n...ges.html#Syntax (nr 15).
Mai exact, citand standardul:

Quote

If clause-1 is a
declaration, the scope of any identifiers it declares is the remainder of the declaration and
the entire loop, including the other two expressions;
Acolo se specifica in mod direct scopul variabilelor declarate si definite in prima expresie din for. Iar de aici reiese clar ca tu folosesti un compilator ce nu a implementat complet standardul C99.
De exemplu compilatorul C din VS nu este (sau nu era complet compatibil cu C99) si MS nici nu vroia (sa inca nu vrea) sa acopere partea asta. Au implementat partial C99.

LE: Si poti foarte bine sa lucrezi cu un compilator C++, dar cu cod pur C. Si eu zic ca ai mult mai multe avantaje decat dezavantaje. De fapt pentru teme din astea micute nici nu vad unde ai putea avea dezavantaje. Sau daca tot vrei sa inveti un C curat, treci pe GCC.

Edited by Cy_Cristian, 22 April 2017 - 21:06.


#13
dani.user

dani.user

    Guru Member

  • Grup: Moderators
  • Posts: 21,994
  • Înscris: 24.02.2007
  • ID membru: 146,987
Indiferent ce limbaj/compilator alegi, setarea lui sa tina cont de toate avertizarile si sa le transforme in erori ar trebui sa faci din instinct, pentru a-ti da peste mana cand gresesti fara sa-ti dai seama, in limita in care poate detecta compilatorul greselile.

Anunturi


0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users