Ajutor - programare structurata

[•alexthebest08]

Salut!
Vreau sa va intreb daca am elaborat corect algoritmii la cateva probleme.
Daca faceam programul pe calculator il compilam si vedeam daca imi aparea vreo eroare, dar in pseudocod nu am nicio sursa de verificare.

1) Sa se afiseze toti divizoirii comuni a 2 nr. naturale
am zis asa:
    
          a, b, k intreg
        citeste a, b
       {daca a < b
               executa
        {pentru k <- 1, b
               executa
           {daca a % k = b % k
                   atunci
                         scrie k
                   altfel
            }            scrie "nu se pot determina divizorii comuni"
      }
             
}


2) Sa se afle toate nr nat < 2000 care impartie la 24, 30, 18 dau restul 7
    
v - integ
v <- 1
{cat timp v < 2000
       executa
      v <- v + 1
   {daca v % 24 = 7 si v % 30 si v % 18 = 7
           atunci
             scrie v
  }
}

Va rog sa imi spuneti daca am scris corect algoritmii, si daca stiti vreun mod de a ma putea verifica.                  



        

[•TheNechiz]

Singurul mod de a te a verifica e cu creionul pe hârtie. Să faci un tabel cu valorile variabilelor la fiecare pas și să iei mai multe cazuri (mai multe seturi de date de intrare ) și să verifici dacă datele de ieșire sunt cele așteptate.

La primul algoritm nu ar trebui să ai o ramură de "altfel" la "daca a < b atunci" ? Ce se întâmplă dacă b e mai mare ? În locul tău, m-aș fi ajutat de CMMDC.
Al doilea algoritm e bun.

Chiar dacă făceai programul pe calculator și îl compilai, nu ți-ar fi dat eroare dacă algoritmul e greșit. Erorile pe care ți le-ar arăta compilatorul ar fi erori de sintaxă, de alocare a memoriei, etc. El nu are cum să știe dacă algoritmul tău e bun sau nu, asta e sarcina ta.

[•alexthebest08]

1) Sa se afiseze toti divizoirii comuni a 2 nr. naturale
am zis asa:
 
        a, b, k intreg
        citeste a, b
       {daca a < b
               executa
        {pentru k <- 1, b
               executa 
           {daca a % k = b % k
                   atunci
                         scrie k
                   altfel
            }            scrie "nu se pot determina divizorii comuni"
      }
             
}

         {daca b < a
                executa
           { pentru k <- 1, a
                      executa
             {  daca a % k = b % k
                      atunci
                           scrie k
                      altfel
             }        scrie "nu se pot determina divizorii comuni" 
      }
}

Acum e corecta prima problema?

As mai avea o intrebare la o problema, daca am scris corect algoritmul si daca nu e corect, cum ar trebui rezolvata, dar as vrea si explicatii sa pot intelege.Te rog mult
2) Sa se afiseze nr. naturale mai mici sau egale decat n, nr natural dat, care au suma cifrelor mai mica sau egala decat n
am zis asa:

         n, i, s intreg
         s <- 0
         citeste n
        {pentru i <- 1, n
                  executa
              {daca s % i < = n
                  atunci
               s <- s + i
                        scrie s
      }
}

[•TheNechiz]

1) Nu e corectă. Tu verifici dacă a È™i b dau acelaÈ™i rest la împărÈ›irea cu k, iar de aici nu rezultă că ele îl au ca divizor comun pe k ( de exemplu: a=3 b=7 k=2 3%2=1 7%2=1. însă 2 nu e divizor nici pentru a,nici pentru b ) CondiÈ›ia ar trebui să fie „a%k = 0 È™i b%k = 0”. Ar trebui să începi cu k de la 2 până la a/2 (b/2) [o să încerc să explic asta mai jos], orice număr se împarte la 1. ÃŽn afară de asta, am văzut că ai vrut să tratezi cazul în care numerele nu au divizori comuni. Nu poÈ›i face pur È™i simplu o ramură de "altfel". Poate că acea condiÈ›ie nu e adevărată pentru k=2 È™i e adevărată pentru k=3, în cazul ăsta, algoritmul afiÈ™ează: "nu se pot determina divizorii comuni 3...". ( de exemplu: a = 3 b = 12  când k = 2 algoritmul scrie "nu se pot determina divizorii comuni" È™i, la pasul următor, scrie 3 ). Trebuie să iei o variabilă logică, să îi spunem ok. Dacă ok = 0, atunci nu ai găsit niciun divizor comun. Dacă ok = 1, atunci ai găsit cel puÈ›in un divizor comun. ÃŽl iniÈ›ializezi pe ok cu 0 È™i în momentul când găseÈ™ti un divizor îi atribui lui ok 1. ÃŽn rest, ar trebui să meargă.
Cum am zis mai sus, eu m-aș fi folosit de Cel Mai Mare Divizor Comun și aș fi scris ceva de genu ăsta:

a,b,copa,copb,r,k,cmmdc,ok întreg
citește a,b

copa = a
copb = b

cât timp b != 0 execută
r = a%b
a = b
b = r
sfârșit cât timp

cmmdc = a
a = copa
b = copb
ok = 0
pentru k <- 2,cmmdc execută
    dacă a%k == 0 È™i b%k == 0 atunci
        scrie k
        ok = 1
    sfârÈ™it dacă

dacă ok = 0 atunci
    scrie "Numerele nu au divizori comuni."
sfârșit dacă

Explicație pentru k <- 2,număr/2:
O proprietatea a oricărui număr întreg este că se împarte la 1 și la el însuși. Asta se știe. Nu știu dacă se poate demonstra, e ceva evident.

Mai întâi să luăm un exemplu, să spunem că numărul e 24. Divizorii lui 24 sunt 2,3,4,6,8,12. Ce înseamnă că numărul x este divizor a lui y ? Rezultă că există z întreg ( natural în cazul ăsta ) astfel încât y = x*z.
24 = 2*12
24 = 3*8
24 = 4*6
24 = 6*4
24 = 8*3
24 = 12*2

Dacă am merge peste jumătatea numărului, ar ieși ceva de genul ăsta număr = (număr/2+1)*2 =>
număr = ((număr+2)/2)*2 =>
număr = număr+2 ceea ce este imposibil.

2) Îți voi spune mai întâi ce face algoritmul tău pentru problema 2. Citește un n, verifică dacă n dă un rest mai mic decât n la împărțirea cu numerele de la 1 la n, ceea ce e adevărat pentru fiecare i ( i <-1,n ). Și însumează numerele de la 1 la n în variabila s. Algoritmul, pentru n = 5, afisează: 1,3,6,10,15.

Tu trebuie să faci suma cifrelor lui i în variabila s și apoi să verifici dacă e mai mică sau egală cu n.