Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
teava rezistenta panou apa calda

Acces in Curte din Drum National

Sub mobila de bucatarie si sub fr...

Rezultat RMN
 Numar circuite IPAT si prindere t...

Pareri brgimportchina.ro - teapa ...

Lucruri inaintea vremurilor lor

Discuții despre TVR Sport HD
 Cost abonament clinica privata

Tremura toata, dar nu de la ro...

Renault Android

Recomandare bicicleta e-bike 20&#...
 Bing-Content removal tool

Nu pot accesa monitorulsv.ro de l...

Cum sa elimini urmele de acnee?

Wc Geberit
 

[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,702
  • Înscris: 24.09.2014
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

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
pai 1 7 nu este impar consecutiv, crescatoare da, dar este adunarea comutativa

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


#3
ccdsah

ccdsah

    Senior Member

  • Grup: Senior Members
  • Posts: 2,581
  • Înscris: 16.03.2013
Pun enuntul corect te rog.
De exemplu pentru 6 nu este solutie.

#4
VladBtz

VladBtz

    Active Member

  • Grup: Members
  • Posts: 1,702
  • Înscris: 24.09.2014

 MarianG, 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: Senior Members
  • Posts: 30,189
  • Înscris: 24.02.2007

 VladBtz, 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,702
  • Înscris: 24.09.2014

 dani.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,845
  • Înscris: 22.02.2009
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: Senior Members
  • Posts: 30,189
  • Înscris: 24.02.2007

 VladBtz, 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,845
  • Înscris: 22.02.2009
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,702
  • Înscris: 24.09.2014

 Cy_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,702
  • Înscris: 24.09.2014
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,845
  • Înscris: 22.02.2009

 VladBtz, 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: Senior Members
  • Posts: 30,189
  • Înscris: 24.02.2007
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

Second Opinion Second Opinion

Folosind serviciul second opinion ne puteți trimite RMN-uri, CT -uri, angiografii, fișiere .pdf, documente medicale.

Astfel vă vom putea da o opinie neurochirurgicală, fără ca aceasta să poată înlocui un consult de specialitate. Răspunsurile vor fi date prin e-mail în cel mai scurt timp posibil (de obicei în mai putin de 24 de ore, dar nu mai mult de 48 de ore). Second opinion – Neurohope este un serviciu gratuit.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate