Come trovare il GCD di due numeri? "Turbo Pascal" e un po 'di matematica

Spesso i programmatori alle prime armi si familiarizzano con l'ambiente Turbo Pascal attraverso semplici attività. I primi compiti che l'utente implementa nel codice: visualizza qualsiasi testo, trova il GCD e il NOC numeri naturali calcola quanti giovedì ci sono in un mese, ecc. Spesso ci sono compiti con un pregiudizio matematico. Prima di implementare le tue conoscenze nel codice del programma, devi studiare materiale aggiuntivo. Ad esempio, come trovare il GCD e il NOC di due numeri in Turbo Pascal.

Trovare il gcd in matematica

Il più grande fattore comune è il numero che è considerato il massimo quando si decompone in componenti. Viene registrata la forma breve della definizione come GCD. Ad esempio, considera un disegno. Qui vengono indicati i numeri 140 e 175. Il loro massimo divisore è 35, cioè GCD (140,175) = 35.

Per evitare ulteriori domande su come trovare il GCD di due numeri, è necessario seguire questo algoritmo:

• Trova i divisori più semplici del primo numero.
• La stessa operazione viene eseguita con il secondo numero.
• Per trovare indicatori comuni nel set di divisori del primo e del secondo numero.
• Cerchili con una penna di un altro colore.
• Moltiplicare i divisori comuni (se ce ne sono diversi) o scrivere l'unico (se i numeri sono primi allora il loro gcd sarà uguale a 1).

Considera la seguente figura. Mostra che anche numeri grandi come 816 e 455 non hanno GCD, tranne 1.

C'è un secondo modo per trovare il compito. L'algoritmo euclideo in matematica è il seguente:

• Dati i numeri.
• Selezionare dovrebbe essere il massimo.
• È diviso nel minimo.
• Ora il secondo numero specificato deve essere diviso per il saldo risultante.
• Il primo saldo è diviso per il secondo, risultante dall'operazione precedente.
• La seconda parte residua è divisa per la terza, ecc.
• L'operazione di divisione viene eseguita finché il resto è uguale a 0.
• L'ultimo divisore e soddisfa il criterio NOD.

Per trovare GCD più di tre numeri naturali, si consiglia di seguire lo schema di lavoro (prendere i numeri 140, 96, 64):

• Nel primo passaggio, ripetere l'algoritmo precedente per i primi due numeri.
• Trova il GCD del divisore trovato e il terzo numero specificato.
• Trova il GCD del divisore risultante e il quarto numero, ecc.

Trovare il NOC in matematica

Se la programmazione pone la domanda su come trovare il GCD di due numeri, allora è necessariamente associato al secondo: il ritrovamento del NOC. Il minimo comune multiplo di due numeri è un numero naturale minimo che può essere condiviso dal primo e dal secondo.

Il primo modo:

• Dato due o più numeri.
• Scrivi tutti i multipli per ogni posizione.
• Seleziona il minimo comune multiplo.

Il secondo modo:

• Distribuisci tutti i numeri in fattori primi.
• Scrivi nella riga tutti i divisori del primo numero e aggiungi qui quei fattori che si trovano in altre espansioni, ma che mancano nel primo.
• Calcola il prodotto.

GCD in Pascal: l'algoritmo del lavoro

Come trovare il GCD di due numeri? "Pascal" è un linguaggio di programmazione in cui verrà scritto il codice. Per prima cosa devi seguire l'algoritmo sopra menzionato. E qui la matematica viene in soccorso. L'algoritmo del compito aiuterà a trovare il GCD di due numeri naturali. In Turbo Pascal, sarà simile a questo:

• Mostra la richiesta di inserire 2 numeri non negativi dalla tastiera.
• Eseguire il ciclo while, dove la condizione è il numero 1 <> numero 2 (condizionalmente, a e b).
• Il corpo del ciclo include le seguenti azioni: se a> b, allora a: = a - b, altrimenti b: = b - a.
• Mostra il risultato.

NOD in Pascal: soluzione euclidea

Come trovare il GCD di due numeri attraverso un metodo semplice ma efficace?

• Inserimento di numeri positivi.
• Una chiamata a una funzione scritta che calcola gcd. La funzione stessa esegue le seguenti azioni: verifica della condizione, quale numero è maggiore; l'assegnazione di dati iniziali ad altre variabili; nel ciclo con una precondizione (r2 <> 0, cioè fino a quando la variabile è uguale a 0), viene trovato il resto della divisione e i risultati vengono assegnati alle variabili; assegnare il nome della funzione del risultato finale.
• Mostra il risultato sullo schermo.

Molti programmatori ritengono che entrambe le opzioni per la ricerca di GCD siano molto simili, quindi su Internet il primo metodo può essere fornito come un algoritmo euclideo.

NOC in Pascal: come è organizzato il programma?

Sono già stati considerati 2 algoritmi, che spiegano come trovare il GCD di due numeri. Ora resta da sapere come appare il programma di ricerca NOC in Turbo Pascal. L'algoritmo di lavoro durante la programmazione è il seguente:

• Inserire due numeri.
• Assegnazione di altre due variabili a determinati valori.
• Trovare il prodotto degli elementi originali.
• In un ciclo con una precondizione (while), disponi la condizione: se il primo numero è maggiore del secondo (n> m), puoi trovare il risultato (n: = n - m) sottraendo; altrimenti, eseguire questa operazione, ma nella direzione opposta (m: = m - n).
• Mostra il risultato, in cui il prodotto trovato sarà diviso per la funzione div per il numero m.

Per quali sono le due variabili a e b introdotte? Per visualizzare correttamente il risultato. In un ciclo con una precondizione, i valori originali delle variabili vengono persi, quindi è impossibile generare i valori m, n specificati dall'utente tra parentesi. Ovviamente, la riga 21 può essere notevolmente semplificata scrivendo solo writeln (proizv div m). Ma l'utente, che conoscerà il programma per la prima volta, non capirà cosa viene visualizzato sullo schermo.

Tracciamento manuale:

Come puoi vedere, non c'è nulla di difficile nel trovare una soluzione al GCD e al NOC: né in Pascal, né, di fatto, in matematica.