Să se determine câte dintre perechile de elemente din vector sunt formate din valori cu aceeași sumă a cifrelor.
Last Updated: Jun 24 2019 20:03, Started by
MateiGafita
, Jun 20 2019 13:03
·
0
#1
Posted 20 June 2019 - 13:03
Buna! As vrea sa ma ajutati la aceasta problema. Se dă un vector cu n numere naturale. Să se determine câte dintre perechile de elemente din vector sunt formate din valori cu aceeași sumă a cifrelor.
Date de intrare Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spaţii, reprezentând elementele vectorului. Date de ieșire Programul afișează pe ecran numărul C, reprezentând valoarea cerută. Intrare 6 51 842 15 28 77 132 Ieșire 4 #include <iostream> using namespace std; int a[100],n,i,j,s1,s2,cif,pairs=0; int main() { cout<<"n= "; cin>>n; for(i=0; i<n; i++) { cout<<"a["<<i<<"]= "; cin>>a[i]; } for(i=0; i<n; i++) { s1=0; while(a[i]!=0) { cif=a[i]%10; s1=s1+cif; a[i]=a[i]/10; } for(j=i+1; j<n; j++) { s2=0; while(a[j]!=0) { cif=a[j]%10; s2=s2+cif; a[j]=a[j]/10; } if(s1==s2) { pairs++; } } } cout<<pairs; return 0; } Edited by MateiGafita, 20 June 2019 - 13:06. |
#2
Posted 20 June 2019 - 13:46
Problema în codul tău e că modifici valorile elementelor din șir în timp ce îl parcurgi. Specific, valorile lui a[j].
De la a doua iterație în sus, valorile lui a[j] or să fie toate 0. Folosește variabile auxiliare pentru a[i] și a[j] când aduni cifrele (de exemplu x și y). E.g. s2 = 0; y = a[j]; while(y != 0) { cif = y % 10; s2 = s2 + cif; y = y / 10; } "cif" nu îți trebuie, poți să pui direct "s2 = s2 + y % 10". În plus, ai putea să optimizezi puțin codul, să nu faci operațiile astea la fiecare iterație. Edited by pexCom, 20 June 2019 - 13:54. |
#3
Posted 20 June 2019 - 13:54
Ai copiat gresit programul ala de adunat cifrele: https://www.sanfound...-sum-of-digits/
Aici - a[i]=a[i]/10; - se modifica valorile originala, deci dupa aia se da peste cap tot programul. Si cele 2 rinduri care efectiv aduna cifrele, tu le-ai facut 3... nu stiu exact de ce. #include <iostream> using namespace std; int a[100],n,i,j,s1,s2,cif,pairs=0,num; int main() { cout<<"n= "; cin>>n; for(i=0; i<n; i++) { cout<<"a["<<i<<"]= "; cin>>a[i]; } for(i=0; i<n; i++) { s1=0; num=a[i]; while(num!=0) { s1 = s1 + num % 10; num = num / 10; } cout << "The sum of the digits of " << a[i] << " is " << s1 << endl; for(j=i+1; j<n; j++) { s2=0; num=a[j]; while(num!=0) { s2 = s2 + num % 10; num = num / 10; } cout << "The sum of the digits of " << a[j] << " is " << s2 << endl; if(s1==s2) { pairs++; } } } cout<<pairs; return 0; } |
#5
Posted 20 June 2019 - 15:12
Cum as putea sa optimizez algoritmul ?
#include <iostream> using namespace std; int a[100001],n,i,j,s1,s2,pairs=0,x,y; int main() { cin>>n; for(i=0; i<n; i++) cin>>a[i]; for(i=0; i<n; i++) { x=a[i]; s1=0; while(x!=0) { s1=s1+x%10; x=x/10; } for(j=i+1; j<n; j++) { y=a[j]; s2=0; while(y!=0) { s2=s2+y%10; y=y/10; } if(s1==s2) { pairs++; } } } cout<<pairs; return 0; } |
#6
Posted 20 June 2019 - 15:27
Poți construi suma încă de la citirea numerelor.
În loc să citești n, citești caracter cu caracter si aduni. In vector nu salvezi numarul, ci suma cifrelor. Ba mai mult, tot la citire poți contoriza câte sunt la fel într-un map ca histograma. Deci vei avea două bucle, una pentru citirea datelor si calcule, și una pentru afisarea rezultatelor. Nu mai multe, si nu imbricate. Pardon, cea de citire are una imbricata. Oricum ai da-o, complexitate O(n), iar la calculul perechii ia o abordare mai matematica, nu ++ |
#7
Posted 20 June 2019 - 15:38
#include <iostream> using namespace std; int a[100001],n,i,j,s1,s2,pairs=0,x,y; int main() { cin>>n; for(i=0; i<n; i++) { cin>>a[i]; s=0; while(a[i]!=0) { s=s+a[i]%10; a[i]=a[i]/10; } a[i]=s; } Edited by MateiGafita, 20 June 2019 - 15:39. |
#8
Posted 20 June 2019 - 15:44
Am zis sa citești cifra cu cifra. E anapoda sa citești tot numărul (care e făcut de biblioteca standard tot cifră cu cifră), ca mai apoi să descompui numărul în cifre.
Deci fa din start ce ai nevoie. Fiecare număr în parte nici nu te interesează. Doar suma cifrelor te interesează. |
#9
Posted 20 June 2019 - 15:49
Programul tau(varianta intiala) refactorizat:
#include <iostream> #include <string> using namespace std; int suma_cifre(int num) { int s = 0, x= num; while(num!=0){ s += num % 10; num /= 10; } cout << "The sum of the digits of " << x << " is " << s<< endl; return s; } int* date_user(int n) { static int a[100]; for(int i=0; i<n; i++){ cout<<"a["<<i<<"]= "; cin>>a[i]; } return a; } int main(){ int n= 0, pairs = 0; cout<<"n= "; cin>>n; int* a = date_user(n); for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ pairs += suma_cifre(a[i]) == suma_cifre(a[j])? 1:0; } } cout<<pairs; return 0; } Edited by Iulius-Foyas, 20 June 2019 - 15:54. |
#10
Posted 20 June 2019 - 16:03
de ce are o functie "int " cout in interior?
Pentru exemplul dat, care sunt cele 4 numere (perechi)? |
|
#13
Posted 20 June 2019 - 17:14
#14
Posted 20 June 2019 - 17:17
MateiGafita, on 20 iunie 2019 - 15:38, said: #include <iostream> using namespace std; int a[100001],n,i,j,s1,s2,pairs=0,x,y; int main() { cin>>n; for(i=0; i<n; i++) { cin>>a[i]; s=0; while(a[i]!=0) { s=s+a[i]%10; a[i]=a[i]/10; } a[i]=s; } OriginalCopy, on 20 iunie 2019 - 15:44, said:
Am zis sa citești cifra cu cifra. E anapoda sa citești tot numărul (care e făcut de biblioteca standard tot cifră cu cifră), ca mai apoi să descompui numărul în cifre. Deci fa din start ce ai nevoie. Fiecare număr în parte nici nu te interesează. Doar suma cifrelor te interesează. |
#15
Posted 20 June 2019 - 17:25
Acesta este codul momentan, dar tot depășește limita de timp.
[<CODE>] #include <iostream> using namespace std; int a[100001],n,i,j,s,pairs=0; int main() { cin>>n; for(i=0; i<n; i++) { s=0; cin>>a[i]; while(a[i]!=0) { s+=a[i]%10; a[i]/=10; } a[i]=s; } for(i=0; i<n; i++) for(j=i+1;j<n;j++) if(a[i]==a[j])pairs++; cout<<pairs; return 0; } [<CODE>] Edited by MateiGafita, 20 June 2019 - 17:27. |
|
#16
Posted 20 June 2019 - 17:31
MateiGafita, on 20 iunie 2019 - 17:25, said:
Acesta este codul momentan, dar tot depășește limita de timp. [<CODE>] #include <iostream> using namespace std; int a[100001],n,i,j,s,pairs=0; int main() { cin>>n; for(i=0; i<n; i++) { s=0; cin>>a[i]; while(a[i]!=0) { s+=a[i]%10; a[i]/=10; } a[i]=s; } for(i=0; i<n; i++) for(j=i+1;j<n;j++) if(a[i]==a[j])pairs++; cout<<pairs; return 0; } [<CODE>] In secventa cu rosu, tu nu citesti cifra cu cifra, ci citesti tot numarul, si apoi calculezi suma cifrelor. Altfel spus, iterezi de doua ori cifrele, o data prin biblioteca standard (asta face cin >> a[i]), si o data in bucla while marcata cu rosu. Asta e una dintre ineficiente. Daca vrei ajutor, trebuie sa fii ajutabil, nu sa-ti bati joc de timpul oamenilor. |
#17
Posted 20 June 2019 - 17:38
Am înțeles ce vrei să spui doar că nu știu cum să citesc cifra cu cifra.
|
#18
Posted 20 June 2019 - 17:49
Da, e mai eficient sa citesti cifra cu cifra, dar putin probabil sa fie asta motivul pentru depasirea timpului. Mai degraba e din cauza algoritmului O(n2) folosit ulterior.
Edited by dani.user, 20 June 2019 - 17:51. |
Anunturi
Bun venit pe Forumul Softpedia!
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users