2915 - Sum Square: Difference between revisions

From Bitnami MediaWiki
Paul Ungur (talk | contribs)
320 edits
Pagină nouă: ==Cerința== Se dă numărul natural <span style=“color: red”>n</span>. Determinați dacă numărul se poate scrie ca sumă de două pătrate perfecte. Dacă da, afișați două pătrate perfecte a căror sumă este <span style=“color: red”>n</span>, în ordine crescătoare, sau mesajul <span style=“color: red”>NU</span> în caz contrar. ==Date de intrare== Programul citește de la tastatură numărul <span style=“color: red”>n</span>; ==Date de ieșire== Pr...
 
Paul Ungur (talk | contribs)
320 edits
No edit summary
 
(2 intermediate revisions by the same user not shown)
Line 6: Line 6:


==Date de ieșire==
==Date de ieșire==
Programul va afișa pe ecran cele <span style=“color: red”>2</span> pătrate care alcătuiesc numărul sau mesajul <span style=“color: red”>NU</span> în cazul în care nu există.
Dacă datele sunt introduse corect, pe ecran se va afișa: '''"Date de intrare valide."''', apoi programul va afișa pe ecran cele <span style=“color: red”>2</span> pătrate care alcătuiesc numărul sau mesajul <span style=“color: red”>NU</span> în cazul în care nu există. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: '''"Date de intrare invalide".'''


==Restricții și precizări==
==Restricții și precizări==
Line 14: Line 14:
==Exemplu:==
==Exemplu:==
Intrare
Intrare
169
: 169


Ieșire
Ieșire
25 144
: Date de intrare valide
: 25 144


==Rezolvare==
==Rezolvare==
Line 23: Line 24:
import math
import math


def validate_input(n):
 
def validare_date(n):
     """Functie de validare"""
     """Functie de validare"""
     if not 1 <= n <= 10**15:
     if not 1 <= n <= 10**15:
Line 30: Line 32:
     return True
     return True


def read_input():
    """Functie de citire"""
    n = int(input("Introduceti numarul: "))
    if not validate_input(n):
        return read_input()
    return n


def main():
def sum_square(n):
     n = read_input()
     ok = False
    for i in range(1, int(math.sqrt(n // 2)) + 1):
        x = i * i
        y = n - x
        j = int(math.sqrt(y))


    for a in range(int(math.sqrt(n))+1):
         if j * j == y and not ok:
         b = math.sqrt(n - a*a)
             print(min(y, x), max(x, y))
        if b == int(b):
             ok = True
             print(a, int(b))
 
             return
    if not ok:
        print("NU")


    print("NU")


if __name__ == '__main__':
if __name__ == '__main__':
     main()
     n = int(input())
    if validare_date(n):
        print("Date de intrare valide")
        sum_square(n)
    else:
        print("Date de intrare invalide")
   </syntaxhighlight>
   </syntaxhighlight>
 
==Explicatie cod: ==
==Explicatie==
Funcția validare_date(n) primește un număr n și verifică dacă acesta se află în intervalul [1, 10^15]. Dacă numărul nu respectă această condiție, se afișează un mesaj de eroare și se returnează False. În caz contrar, se returnează True.
Funcția validate_input verifică dacă numărul n se încadrează în restricțiile impuse și returnează True dacă este valid sau False dacă nu este valid.
Funcția sum_square(n) primește un număr n și calculează perechile de numere x și y, astfel încât x^2 + y^2 = n. Pentru a verifica această condiție, se utilizează două bucle for. Prima buclă iterează de la 1 până la radicalul pătrat al lui n // 2, iar în interiorul primei bucle se calculează x = i*i și y = n - x. Apoi, se verifică dacă y este un pătrat perfect (adica j * j == y) și se afișează perechea (x, y) dacă această condiție este îndeplinită. Se folosește o variabilă ok pentru a se asigura că se afișează doar prima pereche găsită.
 
În blocul if __name__ == '__main__':, se citește de la intrare un număr n utilizând funcția input(). Apoi, se verifică dacă numărul este valid utilizând funcția validare_date(). Dacă numărul este valid, se afișează un mesaj de confirmare și se apelează funcția sum_square() pentru a găsi și afișa perechile (x, y). În caz contrar, se afișează un mesaj de eroare.
Funcția read_input primește input-ul de la utilizator și verifică dacă este valid folosind funcția validate_input. Dacă input-ul este valid, funcția returnează valoarea citită, altfel cere utilizatorului să introducă din nou un input valid.
 
Funcția main citește input-ul folosind funcția read_input. Apoi, parcurgem toate valorile a de la 0 la rădăcina pătrată a lui n, căutând o valoare b astfel încât aa + bb = n. Dacă găsim o astfel de valoare, afișăm cele două pătrate perfecte și ieșim din program cu return. Dacă nu găsim nicio pereche de pătrate perfecte, afișăm "NU".
 
Pentru a determina dacă un număr poate fi scris ca sumă de două pătrate perfecte, putem folosi teorema lui Fermat: orice număr prim de forma 4k+1 poate fi scris ca sumă de două pătrate perfecte. Mai mult decât atât, un număr întreg pozitiv poate fi scris ca sumă de două pătrate perfecte dacă și numai dacă fiecare factor prim din reprezentarea sa care este congruent cu 3 modulo 4 apare de un număr par de ori. În acest caz, putem găsi cele

Latest revision as of 18:56, 29 June 2023

Cerința[edit]

Se dă numărul natural n. Determinați dacă numărul se poate scrie ca sumă de două pătrate perfecte. Dacă da, afișați două pătrate perfecte a căror sumă este n, în ordine crescătoare, sau mesajul NU în caz contrar.

Date de intrare[edit]

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

Date de ieșire[edit]

Dacă datele sunt introduse corect, pe ecran se va afișa: "Date de intrare valide.", apoi programul va afișa pe ecran cele 2 pătrate care alcătuiesc numărul sau mesajul NU în cazul în care nu există. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Date de intrare invalide".

Restricții și precizări[edit]

1≤n≤1015 dacă există mai multe perechi de pătrate perfecte a căror sumă este n, poate fi afișată oricare

Exemplu:[edit]

Intrare

169

Ieșire

Date de intrare valide
25 144

Rezolvare[edit]

<syntaxhighlight lang="python" line> import math


def validare_date(n): 

   """Functie de validare"""
   if not 1 <= n <= 10**15:
       print("Numarul introdus trebuie sa fie intre 1 si 10^15.")
       return False
   return True


def sum_square(n): 

   ok = False
   for i in range(1, int(math.sqrt(n // 2)) + 1):
       x = i * i
       y = n - x
       j = int(math.sqrt(y))

       if j * j == y and not ok:
           print(min(y, x), max(x, y))
           ok = True

   if not ok:
       print("NU")


if __name__ == '__main__': 

   n = int(input())
   if validare_date(n):
       print("Date de intrare valide")
       sum_square(n)
   else:
       print("Date de intrare invalide")
 </syntaxhighlight>

Explicatie cod:[edit]

Funcția validare_date(n) primește un număr n și verifică dacă acesta se află în intervalul [1, 10^15]. Dacă numărul nu respectă această condiție, se afișează un mesaj de eroare și se returnează False. În caz contrar, se returnează True. Funcția sum_square(n) primește un număr n și calculează perechile de numere x și y, astfel încât x^2 + y^2 = n. Pentru a verifica această condiție, se utilizează două bucle for. Prima buclă iterează de la 1 până la radicalul pătrat al lui n // 2, iar în interiorul primei bucle se calculează x = i*i și y = n - x. Apoi, se verifică dacă y este un pătrat perfect (adica j * j == y) și se afișează perechea (x, y) dacă această condiție este îndeplinită. Se folosește o variabilă ok pentru a se asigura că se afișează doar prima pereche găsită. În blocul if __name__ == '__main__':, se citește de la intrare un număr n utilizând funcția input(). Apoi, se verifică dacă numărul este valid utilizând funcția validare_date(). Dacă numărul este valid, se afișează un mesaj de confirmare și se apelează funcția sum_square() pentru a găsi și afișa perechile (x, y). În caz contrar, se afișează un mesaj de eroare.

Retrieved from "http://wiki.universitas.ro/index.php?title=2915_-_Sum_Square&oldid=6847"