Il più grande divisore comune

Question

Cerco di trovare il massimo comun divisore per due interi. Ma non capisco cosa c'è di sbagliato con il mio codice:

public class Main { 

    public static void main(String[] args) { 
     Scanner s = new Scanner(System.in); 

     int a = s.nextInt(); 
     int b = s.nextInt(); 

     while (a != 0 | b != 0) { 
      if (a >= b) { 
       a = a % b; 
      } else { 
       b = b % a; 
      } 
     } 

     if (a == 0) { 
      System.out.println(b); 
     } else { 
      System.out.println(a); 
     } 
    } 
} 

Answer 1

Basta cambiare

a != 0 | b != 0 

a

a != 0 && b != 0 

Perché si versione sarà lavoro anche a o b è uguale a 0. Ma è necessario uscire dal ciclo quando uno di loro è uguale a 0. & & - meglio di & perché nel tuo caso non è necessario controllare l'operatore destro se lasciato uguale a 0

Answer 2

È più semplice calcolare il GCD se si capisce la logica di base. Cerca di capire cosa dobbiamo fare e come lo faremo prima di implementare il programma.

Quello che stiamo cercando di trovare è il numero più grande che divide sia un e b.

Quindi la domanda sorge spontanea sul modo in cui lo faremo. Facciamo un ciclo proprio come hai fatto tu, ma per questo caso, supponiamo inizialmente che a sia maggiore di b.

Il primo passo è avviare il ciclo, mentre il calcolo non è terminato. La condizione nel nostro caso è, , che dobbiamo interrompere quando uno dei due numeri diventa zero.

while (a != 0 && b != 0) 
{ 
    // Do the calculation here. 
} 

Ora dobbiamo scrivere il calcolo. Abbiamo ipotizzato che a è maggiore di b o entrambi sono uguali.

continuiamo a assegnare la restante un diviso per b ad un.

while (a != 0 && b != 0) 
{ 
    a = a % b; 
} 

Questo rende la soluzione solo metà corretta, avremo a che fare con l'altro caso, cioè quando b è superiore un. Perché ciò avvenga dopo un certo numero di iterazioni, a diventerà inferiore a b e ciò comporterà a impostato su .

Allora, facciamo la stessa soluzione per l'altro caso, quando un è minore di b.

while (a != 0 && b != 0) 
{ 
    if (a > b) 
     a = a % b; 
    else 
     b = b % a; 
} 

E questo è quello che si voleva raggiungere. Il valore diverso da zero sarà la soluzione.

Non fermiamoci qui e vediamo perché la versione attuale non funziona. Hai avuto questo nelle tue condizioni.

la sua condizione è:

a != 0 | b != 0 

Qui, si utilizza operatore bit per bit OR, tra due booleani valori, che giunge alle seguenti. Supponiamo che uno qualsiasi di a e b sia zero.

Caso 1:

a != 0 => true 
b != 0 => false 

true | false => true 

Caso 2:

a != 0 => false 
b != 0 => true 

false | true => true 

Pertanto, come si vede nei casi sopra citati, continua a ciclo finché sia ​​diventa zero, e quindi sarà sempre essere segnalato come GCD è zero.

Spero che questo aiuti.