0492 - Numarare3

Sursa: - Numarare3

---

Cerinţa

Se dă un vector cu n numere naturale. Să se determine câte dintre perechile de elemente egal depărtate de capetele vectorului sunt prime între ele.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi șirul de n numere naturale, separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul c, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ⩽ n ⩽ 200
• elementele vectorului vor fi cuprinse între 0 și 1000

Exemple

Exemplul 1

Intrare

6

50 18 15 28 35 40

Ieșire

Datele nu corespund restricțiilor impuse.

2

Exemplul 2

Intrare

5

10 2 -3 4 5

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

# 0492

def cate_perechi_de_el_egal_departate_prime_intre_ele(vector, n):
    c = 0
    for i in range(n // 2):
        a, b = vector[i], vector[n-i-1]
        if b == 0:
            b = a
        else:
            while a % b != 0:
                r = a % b
                a = b
                b = r
        if b == 1:
            c += 1
    print(c)


def citire_conform_restrictiilor(vector, n):
    if n < 1 or n > 200:
        print("Datele nu corespund restricțiilor impuse.")
        exit()
    for x in vector:
        if x < 0 or x > 1000:
            print("Datele nu corespund restricțiilor impuse.")
            exit()
    if n != len(vector):
        print("Datele nu corespund restricțiilor impuse.")
        exit()
    print("Datele sunt introduse corect.")


if __name__ == '__main__':
    n = int(input())
    vector = list(map(int, input().split()))
    citire_conform_restrictiilor(vector, n)
    cate_perechi_de_el_egal_departate_prime_intre_ele(vector, n)

Explicație rezolvare

   Programul de mai sus conține două funcții, funcția cate_perechi_de_el_egal_departate_prime_intre_ele(vector, n) și funcția citire_conform_restrictiilor(vector, n), care se vor rula în interiorul main-ului (if __name__ == '__main__' , linia 33) după citirea numărului n (linia 34) și celor n numere pe care le vom pune în șirul „vector” (linia 35).
   După ce am citit elementele, se va apela funcția citire_conform_restrictiilor(vector, n) care primește doi parametri: vectorul „vector” și lungimea sa, reprezentată de variabila „n”. Funcția verifică dacă lungimea vectorului n este între 1 și 200 (linia 20), dacă elementele vectorului sunt cuprinse între 0 și 1000 (liniile 23, 24) și dacă n este lungimea vectorului „vector” (linia 27). Dacă oricare dintre condiții este încălcată, se va afișa mesajul „Datele nu corespund restricțiilor impuse.” și se va ieși din program cu comanda exit(). Dacă toate condițiile sunt respectate, se va afișa mesajul „Datele sunt introduse corect.” (linia 30) și se va continua programul.
   Dacă s-au introdus corect datele, se va apela funcția cate_perechi_de_el_egal_departate_prime_intre_ele(vector, n) care primește ca parametrii vectorul „vector” și dimensiunea sa „n”.  În interiorul funcției:
-> se initializează o variabilă c cu valoarea 0, care va fi folosită pentru a număra câte astfel de perechi sunt găsite în vector;
-> se parcurge vectorul utilizând o buclă for care iterează de la 0 la jumătatea numărului total de elemente din vector (n // 2). Aceasta se face pentru a evita să se numere de două ori aceeași pereche de elemente;
-> pentru fiecare pereche de elemente consecutive din vector, se extrag valorile celor două elemente în variabilele a și b utilizând indexarea vectorului;
-> se verifică dacă b este egal cu 0. Dacă da, atunci b este actualizat cu valoarea lui a, pentru a evita împărțirea la zero ulterior;
-> se aplică algoritmul pentru a determina cel mai mare divizor comun dintre a și b. Acesta constă în aplicarea succesivă a restului împărțirii până când restul devine 0. În timpul acestui proces, valorile lui a și b sunt actualizate în consecință;
-> se verifică dacă b este egal cu 1. Dacă da, înseamnă că a și b sunt coprime (adică nu au niciun divizor comun în afara valorii 1) și deci numărul de elemente departate între ele este un număr prim. În acest caz, variabila c este incrementată cu 1;
-> se afișează valoarea variabilei c la finalul funcției, care reprezintă numărul total de perechi de elemente consecutive din vector care îndeplinesc condițiile specificate în problemă.