2915 - Sum Square: Difference between revisions

From Bitnami MediaWiki
Newer edit →
VisualWikitext
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
Line 23: Line 23:
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 31:
     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==
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 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

Revision as of 16:08, 26 April 2023

Cerința

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

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

Date de ieșire

Programul va afișa pe ecran cele 2 pătrate care alcătuiesc numărul sau mesajul NU în cazul în care nu există.

Restricții și precizări

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

Exemplu:

Intrare 169

Ieșire 25 144

Rezolvare

<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>
Retrieved from "http://wiki.universitas.ro/index.php?title=2915_-_Sum_Square&oldid=4692"