BitCell

Your IT power source

Skip to content


Suma cifrelor

Această secţiune se ocupă cu programarea, fără a ţine cont de limbaj. Dacă vrei (sau trebuie) să înveți algoritmică, aici este locul potrivit. Descrieri şi idei de algoritmi, algoritmi clasici și întrebări pe baza acestora, toate vor fi postate aici.
Post a reply

Suma cifrelor

Postby noobakaflo » 14 Apr 2011, 22:00

Simpla

Dându-se două numere naturale A şi B, aflaţi câte numere din intervalul [A, B] au suma cifrelor pară.

Date de intrare
Fişierul de intrare simpla.in conţine pe prima linie două numere naturale A şi B.
Date de ieşire
În fişierul de ieşire simpla.out veţi afişa un singur număr întreg, răspunsul căutat.
Restricţii


simpla.in 8 12 simpla.out 2
Doar numerele 8 şi 11 au suma cifrelor pară.

Daca calculez suma cifrelor pentru fiecare cifra din interval iau 40 de puncte.Pentru o solutie in care rezultatul ar fi fost (b-a)/2 obtin 50 de puncte,vazusem la exemplu..
Vreo idee ,ceva ?... :D

LE: Daca combin cele doua metode, iau 70 pct :-?
0,0p / 0 votes
User avatar
noobakaflo
Bit
 
Joined: 10 Dec 2010
Location: Ploiesti
Status: 1

Re: Suma cifrelor

Postby DarkByte » 14 Apr 2011, 22:13

Seteaza N, rezultatul tau, pe 0. Calculeaza numarul de sub-intervale de cate 10 numere (incepand cu un multiplu de 10), apoi babeste restul valorilor.

Un exemplu:

Ai intervalul [2 .. 57] ... numarul de sub-intervale de cate 10 este 4:
Line number On/Off | Expand/Contract | Select all
  1. [10 .. 19]
  2. [20 .. 29]
  3. [30 .. 39]
  4. [40 .. 49]


Pe fiecare interval ai cate 5 numere cu suma cifrelor para => N = 20. Iti ramane sa verifici, cu o functie simpla, ce numere cu suma cifrelor para ai in intervalele [2 .. 9] si [50 .. 57].

As zice ca asta ar trebui sa-ti rezolve cam toate problemele.
0,0p / 0 votes
User avatar
DarkByte
11011011
 
Joined: 29 Dec 2009
Status: 140

Re: Suma cifrelor

Postby noobakaflo » 14 Apr 2011, 22:22

Multumesc de raspuns :D. O sa incerc si varianta asta,dar cred ca m-am prins de ceva..
Iau 80 de puncte pentru solutia de mai jos..

Pentru:
[8 ,12] -> (12-8)/2 -> N=2

[8,13] -> (13-8)/2 -> N=3

[8, 14] -> (14-8)/2 -> N=3

[8,15] -> (15-8)/2 -> N=4

Deci rezultatul de fapt este daca b este par, respectiv daca este impar.
Ceva cazuri mai speciale ? :-?
0,0p / 0 votes
User avatar
noobakaflo
Bit
 
Joined: 10 Dec 2010
Location: Ploiesti
Status: 1

Re: Suma cifrelor

Postby DarkByte » 14 Apr 2011, 22:30

Nu cred ca e chiar asa de simplu ... revin cu explicatia.

L.E.
Line number On/Off | Expand/Contract | Select all
  1.      0     2     4     6     8 >> 3
  2.     11    13    15    17    19 >> 1
  3.     20    22    24    26    28 >> 3
  4.     31    33    35    37    39 >> 1
  5.     40    42    44    46    48 >> 3
  6.     51    53    55    57    59 >> 1
  7.     60    62    64    66    68 >> 3
  8.     71    73    75    77    79 >> 1
  9.     80    82    84    86    88 >> 3
  10.     91    93    95    97    99 >> 2
  11.    101   103   105   107   109 >> 1
  12.    110   112   114   116   118 >> 3
  13.    121   123   125   127   129 >> 1
  14.    130   132   134   136   138 >> 3
  15.    141   143   145   147   149 >> 1
  16.    150   152   154   156   158 >> 3
  17.    161   163   165   167   169 >> 1
  18.    170   172   174   176   178 >> 3
  19.    181   183   185   187   189 >> 1
  20.    190   192   194   196   198 >> 2
  21.    200   202   204   206   208

La fiecare set de 10 numere, aduni 1 sau 3 pentru urmatorul numar cu suma cifrelor para ... mai putin in cazul in care treci de la 100 la alta suta :P ... n-am verificat mai departe.

La prima ta formula incearca intervalul [0 .. 22] - ar trebui sa-ti dea 12, dar iti da 11. S-ar putea ca a doua formula a ta sa fie buna, da' nu am nervi sa verific toate cazurile.

Have fun :P
0,0p / 0 votes
User avatar
DarkByte
11011011
 
Joined: 29 Dec 2009
Status: 140

Re: Suma cifrelor

Postby noobakaflo » 14 Apr 2011, 22:56

Pana la urma am luat 100 . Am folosit a doua formula .. :X
0,0p / 0 votes
User avatar
noobakaflo
Bit
 
Joined: 10 Dec 2010
Location: Ploiesti
Status: 1

Re: Suma cifrelor

Postby eni4ever » 14 Apr 2011, 23:21

Felicitări!
Se poate să faci rost de teste? pentru că nu mi se pare ceva în ordine ... Victor a observat bine : există cazuri în care, chiar și la ordine mici, formula nu se aplică. La numere mai mari, ar trebui demonstrație.

Sau te-ai folosit de observația lui pentru a scoate o soluție ?
0,0p / 0 votes
Image

"Rațiunea vine în umbre scurte numite suferințe." Victor Adăscăliței
"Bender: Anything less than immortality is a complete waste of time.
Zoidberg: Then suicide it is! Step into my office ..." Futurama S06E06
User avatar
eni4ever
DWord
 
Joined: 03 Jan 2010
Location: Timișoara
Status: 57.83

Re: Suma cifrelor

Postby noobakaflo » 15 Apr 2011, 11:15

O sa incerc sa fac rost de teste..
Asta e sursa pe care iau 100 ..
Line number On/Off | Expand/Contract | Select all
  1.  
  2. #include<iostream>
  3. #include<fstream>
  4. using namespace std;
  5. ifstream f("simpla.in");
  6. ofstream g("simpla.out");
  7.  
  8.  
  9.  
  10. long long egali(long long a)
  11. {
  12.     long long s=0;
  13.         while (a!=0)
  14.         {
  15.             s=s+a%10;
  16.             a/=10;
  17.         }
  18.       if (s%2==0)
  19.           return 1;
  20.       else
  21.           return 0;
  22. }   
  23.  
  24. long long solving(long long a,long long b)
  25. {
  26.  
  27.     long long nr=0,i,s,c;
  28.     for (i=a; i<=b; i++)
  29.     {
  30.         s=0;
  31.         c=i;
  32.         while (c!=0)
  33.         {
  34.             s=s+c%10;
  35.             c=c/10;
  36.         }
  37.         if (s%2==0)
  38.             nr++;
  39.    
  40.     }
  41.    
  42.     return nr;
  43. }
  44.  
  45. int main()
  46. {
  47.     long long a,b;
  48.     f >> a >> b;
  49.    
  50.     if (a==b)
  51.         g << egali(a);
  52.     else
  53.        
  54.     if (b<=1000000)
  55.       g << solving(a,b);
  56.     else
  57.     {   
  58.  
  59.     if (b%2==0)
  60.         g<<(b-a)/2;
  61.     if (b%2!=0)
  62.         g<< ((b-a)/2)+1;
  63.    
  64.     }
  65.     return 0;
  66.    
  67.     f.close();
  68.     g.close(); 
  69. }
  70.  
  71.  
  72.  
0,0p / 0 votes
User avatar
noobakaflo
Bit
 
Joined: 10 Dec 2010
Location: Ploiesti
Status: 1

Re: Suma cifrelor

Postby DarkByte » 15 Apr 2011, 11:55

Deci calculezi "manual" daca ai maxim 1 milion de numere ... dar folosesti formula in rest ? Nu e cam ... ciudat ?

Unde anume iei 100 pe sursa asta ? Accepta si Pascal / Delphi ? M-as baga si eu cu o sursa ...
0,0p / 0 votes
User avatar
DarkByte
11011011
 
Joined: 29 Dec 2009
Status: 140

Re: Suma cifrelor

Postby smith » 15 Apr 2011, 13:09

Offtopic
0,0p / 0 votes
Ilea Cristian
User avatar
smith
Enum
 
Joined: 29 Dec 2009
Location: Cluj-Napoca
Status: 82

Re: Suma cifrelor

Postby noobakaflo » 15 Apr 2011, 13:09

Problema e aici !
Nu..
Daca a,b sunt sub un milion pentru fiecare numar din interval fac suma cifrelor . Altfel fac cu formula..
E putin ciudat,stiu.. dar daca am obtinut punctaj maxim :"> ...Totusi,incerc sa fac si printr-o alta modalitate cat de curand..
0,0p / 0 votes
User avatar
noobakaflo
Bit
 
Joined: 10 Dec 2010
Location: Ploiesti
Status: 1

Re: Suma cifrelor

Postby DarkByte » 15 Apr 2011, 13:11

Thanks, o sa incerc si eu metoda mea :)
0,0p / 0 votes
User avatar
DarkByte
11011011
 
Joined: 29 Dec 2009
Status: 140

Re: Suma cifrelor

Postby noobakaflo » 15 Apr 2011, 13:16

smith wrote:Offtopic


Ar fi foarte binevenit un asemenea tutorial ! Sau daca nu are nimeni vointa/timp sa faca, recomandati-mi va rog un articol din afara forumului ! Chiar vreau sa invat si eu a scrie mai 'descifrabil' :D
0,0p / 0 votes
User avatar
noobakaflo
Bit
 
Joined: 10 Dec 2010
Location: Ploiesti
Status: 1

Re: Suma cifrelor

Postby Cosmin_NTG » 16 Apr 2011, 16:29

Ca o mica observatie referitoare la cod, poti folosi cate un prototip de functie pentru cele 2 functii din program:
Line number On/Off | Expand/Contract | Select all
  1. long long egali&#40;long long a&#41;
  2.  

Line number On/Off | Expand/Contract | Select all
  1. long long solving&#40;long long a,long long b&#41;
  2.  
si astfel le poti pozitiona dupa int main(). Cel putin eu cred ca este mult mai structurat codul asa.

L.E. (-- 16 Apr 2011, 15:29 --)

Am observat ceva in codul tau. De ce inchizi fisierele dupa "return 0"? Adica...din cate stiu eu, "return 0" in functia principala "int main" inseamna incheierea programului. Deci mai inchide programul fisierele dupa ce si-a terminat executia? :-/
0,0p / 0 votes
Thinking about solutions is better than thinking about problems
User avatar
Cosmin_NTG
Byte
 
Joined: 11 Jan 2011
Location: 192.2L1.44G
Status: 10

Re: Suma cifrelor

Postby DarkByte » 16 Apr 2011, 16:34

Da, aia e o greseala, da' nu e prea mare. Smith se referea la altceva cand zicea "cod mai fain".

Are bucati de cod redundante - putea face o functie care sa fie apelata din mai multe locuri. Putea sa faca o singura rezolvare pentru toate cazurile ... dar are cazuri speciale pentru numere mai mari sau mai mici de 1 milion. Cred ca sunt si altele, dar cred ca asta e de ajuns :)
0,0p / 0 votes
User avatar
DarkByte
11011011
 
Joined: 29 Dec 2009
Status: 140

Re: Suma cifrelor

Postby noobakaflo » 16 Apr 2011, 16:58

Cosmin_NTG wrote:Am observat ceva in codul tau. De ce inchizi fisierele dupa "return 0"? Adica...din cate stiu eu, "return 0" in functia principala "int main" inseamna incheierea programului. Deci mai inchide programul fisierele dupa ce si-a terminat executia? :-/

Am rectificat,probabil eram cam obosit.. :D
0,0p / 0 votes
User avatar
noobakaflo
Bit
 
Joined: 10 Dec 2010
Location: Ploiesti
Status: 1
Post a reply

Return to Algoritmică

Who is online

Users browsing this forum: No registered users and 0 guests


Powered by phpBB © phpBB Group