1019 - Maxim 6
De la Universitas MediaWiki
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
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()