1019 - Maxim 6

Cerința

Se consideră un șir cu n elemente, numere naturale. Folosind metoda Divide et Impera, determinați cel mai mare element din acest șir.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.

Date de ieșire

Programul va afișa pe ecran numărul M, cel mai mare element al șirului.

Restricții și precizări

• 1 ≤ n ≤ 1000
• elementele șirului vor fi mai mici decât 1.000.000
• se recomandă folosirea metodei Divide et Impera

Exemplu1

Intrare

6
4 1 8 4 3 5 

Ieșire

8

Exemplul 2

Intrare

1001

Ieșire

Numărul de elemente trebuie să fie între 1 și 1000. Programul se încheie.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def max_element_divide_conquer(arr, left, right):

   if left == right:
       return arr[left]
   
   mid = (left + right) // 2
   
   max_left = max_element_divide_conquer(arr, left, mid)
   max_right = max_element_divide_conquer(arr, mid + 1, right)
   
   return max(max_left, max_right)

def main():

   # Citim numărul de elemente
   n = int(input("Introduceți numărul de elemente (1 <= n <= 1000): "))
   
   # Verificăm restricția pentru n
   if not 1 <= n <= 1000:
       print("Numărul de elemente trebuie să fie între 1 și 1000. Programul se încheie.")
       return
   
   # Citim elementele șirului
   arr = []
   for i in range(n):
       element = int(input(f"Introduceți elementul {i + 1} (elemente < 1.000.000): "))
       
       # Verificăm restricția pentru elementele șirului
       if not 0 <= element < 1000000:
           print("Elementele șirului trebuie să fie mai mici decât 1.000.000. Programul se încheie.")
           return
       
       arr.append(element)
   
   # Calculăm și afișăm rezultatul
   result = max_element_divide_conquer(arr, 0, n - 1)
   print(f"Cel mai mare element din șir este: {result}")

if __name__ == "__main__":

   main()

</syntaxhighlight>