1847 - VectorSumPrim REC

Cerinţa

Scrieți definiția completă a subprogramului recursiv P care primeşte prin intermediul parametrului n un număr natural nenul (n≤100), iar prin intermediul parametrului x un tablou unidimensional cu n componente întregi, de maximum șase cifre fiecare. Subprogramul furnizează prin intermediul parametrului s suma elementelor din tabloul x care au valori numere prime.

Date de intrare

Se va introduce de la tastatură un număr natural care va fi transmis ca perimetru

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse." În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse.".

Restricţii şi precizări

0 < n ≤ 100 numele subprogramului cerut este P parametrii sunt, în această ordine: x, n, s elementele vectorului x sunt indexate de la zero se recomandă realizarea unei soluții recursive

Exemplu

Dacă n=6 și x=(12, 7, 6, 3, 8, 5), după apel s=15.

def P(x, n, s=0):
   if n == 0:  # cazul de bază: s-a parcurs întregul vector
       return s
   if este_prim(x[n-1]):  # dacă ultimul element este prim, îl adunăm la suma s
       s += x[n-1]
   return P(x, n-1, s)  # apelăm recursiv subprogramul pentru restul vectorului
def este_prim(nr):
   if nr < 2:  # 0 și 1 nu sunt prime
       return False
   if nr == 2 or nr == 3:  # 2 și 3 sunt prime
       return True
   if nr % 2 == 0 or nr % 3 == 0:  # eliminăm multiplii de 2 și 3
       return False
   i = 5
   while i * i <= nr:  # căutăm divizorii până la radicalul numărului
       if nr % i == 0 or nr % (i+2) == 0:
           return False
       i += 6  # trecem la următorii potențiali divizori (6k-1 și 6k+1)
   return True
# Exemplu de utilizare
n = 6
x = [12, 7, 6, 3, 8, 5]
if n > 0 and n <= 100:
   print("Datele de intrare corespund restrictiilor impuse.")
   s = P(x, n)
   print(f"Suma elementelor prime din vector este {s}.")
else:
   print("Datele de intrare nu corespund restrictiilor impuse.") #Rezultatul afișat pe ecran va fi: Suma elementelor prime din vector este 15.

Rezolvare

def is_prime(n):
   Verifică dacă un număr este prim.
   if n < 2:
       return False
   for i in range(2, int(n ** 0.5) + 1):
       if n % i == 0:
           return False
   return True
def P(x, n, s=0):
   Calculează suma elementelor dintr-un tablou care au valori prime.
   if n == 0:
       return s
   if is_prime(x[n-1]):
       s += x[n-1]
   return P(x, n-1, s)
# Citire date de intrare
n = int(input())
# Verificare restricții date de intrare
if n <= 0 or n > 100:
   print("Datele de intrare nu corespund restricțiilor impuse.")
else:
   print("Datele de intrare corespund restricțiilor impuse.")
   x = []
   for i in range(n):
       x.append(int(input()))
   # Apelare funcție și afișare rezultat
   s = P(x, n)
   print(s)