0410 - CMMDC 2

Cerinţa

Se dă un număr natural n. Acest număr se “împarte” în alte două numere a și b, astfel: a este format din cifrele din prima jumătate a lui n, b este format din cifrele din a doua jumătate a lui n. Dacă n are număr impar de cifre, cifra din mijloc se ignoră. De exemplu, dacă n=9183792, atunci a=918, iar b=792. Să se determine cel mai mare divizor comun al lui a și b.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieşire

Programul afișează pe ecran numărul cmmdc, reprezentând valoarea cerută.

Restricții și precizări

• n ∈ Ν
• 0 ⩽ n ⩽ 1.000.000.000

Exemplu1

Intrare

9183792

Ieșire

Datele de intrare corespund restricțiilor impuse.

18

Exemplu2

Intrare

2847956

Ieșire

Datele de intrare corespund restricțiilor impuse.

4

Rezolvare

<syntaxhighlight lang="python" line> def validare_date(numar):

   flag = False
   if numar.isdigit():
       if 10 <= int(numar) <= 1_000_000_000:
           flag = True
   return flag

def CMD(numar1, numar2):

   while numar2:
       r = numar1 % numar2
       numar1, numar2 = numar2, r
   cmmdc = numar1
   return cmmdc

def cel_mai_mare_divizor(numar):

   n = str(numar)
   if len(n) % 2 == 1:
       n = n[:len(n) // 2] + n[len(n) // 2 + 1:]
   jumatate = len(n) // 2
   a = int(n[:jumatate])
   b = int(n[jumatate:])
   cmmdc = CMD(a, b)
   print(cmmdc)

if __name__ == '__main__':

   numar = input()
   if validare_date(numar):
       print("\nDatele de intrare corespund restricțiilor impuse.\n")
       cel_mai_mare_divizor(numar)
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicație

Codul calculează cel mai mare divizor comun dintre două numere, reprezentate de jumătățile unui număr introdus de la tastatură. Mai întâi, se validează inputul pentru a se asigura că respectă restricțiile impuse, apoi se calculează jumătățile numărului și se aplică algoritmul lui Euclid pentru a găsi cel mai mare divizor comun. Rezultatul este afișat în final.