[Java/C++] Controllare se un numero è una somma di quadrati

[pictor]

Salve.

Ieri il prof di Informatica ci da da fare il compito ed uno degli esercizi è:

Dato un numero controllare se questo è una somma di due quadrati.

A noi l'ha dato da fare in Java, in un metodo boolean, che ritorna vero o falso; ma si può fare anche in C++, suppongo

Comunque, io sono riuscito a fare un programma con due "for" che fanno l'analisi (sfruttando un metodo che mi restituisce se un numero è o no un quadrato).
Purtroppo non ricordo il testo, ma il professore mi ha detto che c'era un metodo ancora più semplice (proprio un programma di poche righe) per controllare....

Ma per quanto ci abbia pensato non riesco a trovarlo.

Voi come lo fareste?

La curiosità mi rode

Grazie mille

[LeleFT]

Beh... effettivamente un modo c'è:

import java.io.*;

class P {
   public static void main(String [] args) throws Exception {
      BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
      String valore = br.readLine();
      boolean trovato = false;
      int tmp = 0;
      int a = Integer.parseInt(valore);
      int i = 0;
      while (!trovato && ((i*i) < a)) {
         tmp = a - (i*i);
         if (Math.sqrt(tmp) == (new Integer((int) Math.sqrt(tmp))).floatValue() ) {
            trovato = true;
         } else {
            i++;
         }
      }
      if (trovato) System.out.println("Si"); else System.out.println("No");
   }
}

L'idea è questa:
1) Trovo l'i-esimo quadrato;
2) Lo tolgo dal valore che devo testare
3) Controllo che questo sia un quadrato
4) Ciclo finchè i*i è minore del numero stesso!

Per risolvere il punto 3 basta controllare che la parte intera della radice quadrata sia uguale alla radice quadrata stessa:
|_radice(x)_| = radice(x).

In Java sembra che la condizione dell'if sia un obbrobrio, ma solamente perchè Java è ObjectOriented.


Ciao.

[Zalex]

bhe prima di tutto mi verrebbe da chiedere se il numero e' un intero o un reale;
se e' un intero bhe innanzitutto deve essere pari,se e' pari e la radice della meta' e' un intero allora e' la somma di due quadrati.

cioe'
se x e' dispari o negativo o uno return false;
altrimenti se sqrt(x/2) e' intero return true


se non e' un intero devo fare qualche prova,...mi sa che e' sempre vero....ma non voglio dire cazzate
cmq anche 4.5 e' somma di quadrati(1.5^2 + 1.5^2) ma anche 4.6 insomma nei reali tutti i numeri hanno radice reale

[LeleFT]

Originariamente inviato da Zalex
bhe prima di tutto mi verrebbe da chiedere se il numero e' un intero o un reale;
se e' un intero bhe innanzitutto deve essere pari,se e' pari e la radice della meta' e' un intero allora e' la somma di due quadrati.

Io ho supposto (come il suo prof, credo) che si trattasse di interi.

Ma non è detto che debba per forza essere pari, per essere somma di due quadrati:

13 = 2*2 + 3*3
45 = 3*3 + 6*6

ecc...

Somma di quadrati non significa somma di due numeri uguali, ma somma di due numeri, che entrambo sono dei quadrati, altrimenti il problema non sussiste: basta dividere per 2 e controllare se il risultato è un quadrato...

Ciao.

[pictor]

Semplice e geniale...

Non ho capito bene la sintassi dell'if (sono ancora agli inizi col java), comunque ho capito cosa fa

Beh, anche se mi fosse venuto in mente non sarei riuscito ad implementarlo

Io avevo fatto una cosa tipo questa:

public static boolean quadrato(int a)
{
/* ....
   quadrato è un metodo boolean che restituisce True 
   se il numero passato è un quadrato, altrimenti
   restituisce False
   ....
*/
}

public static boolean controlla(int a)
{
int num1,num2,
for(num1=0;num1<a;num1++)
  if(quadrato(num1))
     for(num2=0;num2<a-num1;num2++)
        if(quadrato(num2))
           if(num1+num2==a)
              return True;

return False;
}

Mi pare qualcosa del genere...
Non sono neanche troppo sicuro che funzioni ed è molto macchinoso:

Il ragionamento è simile ma c'è un for in più che appesantisce il tutto...

Come ti/vi sembra la mia soluzione?
(non siate troppo cattivi sono niubbo )

Grazie

[pictor]

Originariamente inviato da LeleFT
Io ho supposto (come il suo prof, credo) che si trattasse di interi.

Si, si supponeva che il numero fosse intero e positivo

Ma non è detto che debba per forza essere pari, per essere somma di due quadrati:

13 = 2*2 + 3*3
45 = 3*3 + 6*6

ecc...

Somma di quadrati non significa somma di due numeri uguali, ma somma di due numeri, che entrambo sono dei quadrati, altrimenti il problema non sussiste: basta dividere per 2 e controllare se il risultato è un quadrato...

Ciao.

Anche qua è vero...infatti molti in classe mia hanno sbagliato, pensando che i numeri fossero uguali o pari....cosa che avrebbe portato il programma alla banalità (almeno a pensarci così su due piedi)

Thanks

[LeleFT]

Beh... per funzionare funziona... su questo non ci piove.

Certo è un po' pesante, se si considera che ci sono 2 for annidati e, dentro ad ognuno di essi, si richiama una procedura che richiede tempo esponenziale (a meno che qualcuno non conosca l'algoritmo AFK che, proprio ultimamente, ha ridotto la complessità da esponenziale a polinomiale, di grado 12).



Ciao.

[pictor]

Algoritmo AFK?

Dove posso trovare informazioni (in italiano possibilmente :tongue: )?

Grazie

[LeleFT]

Ehm... errore di battitura: l'algoritmo di chiama AKS.
Trovi delle informazioni in Italiano QUI. Questa pagina ti linka anche alla pagina della tesi dei tre indiani (A.K.S.) che hanno sviluppato anche l'algoritmo (quest'ultima, però, è in inglese e fa un uso pesantissimo di nozioni e notazioni matematiche!!!)


Ciao.

[iguana13]

Interessantissimo!

Me lo leggo tutto