Vai al contenuto

Scomposizione in fattori primi (scuola media)

Da Wikiversità, l'apprendimento libero.
lezione
lezione
Scomposizione in fattori primi (scuola media)
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Informatica per la scuola media 1
Avanzamento Avanzamento: lezione completa al 100%

Scomposizione in fattori primi (scuola media)

[modifica]

Trovare i fattori primi di un numero. Si può fruire di questo tutorial in forma di mappa mentale su wiki2map

Versione di Scratch utilizzata

[modifica]

La versione di scratch usata in questo progetto è scratch 3.0 online.


Cosa richiede l'esercizio

[modifica]

Fornito un numero numero in input, rispondendo alla richiesta del gatto, il calcolatore restituisce l'elenco dei fattori primi, compresi quelli ripetuti.

Come funziona

[modifica]

La velocità di calcolo del PCVK permette di eseguire molti calcoli in poco tempo, questa capacità di lavoro ci permette di affrontare il problema per tentativi, avendo però l'accortezza di produrre i nostri tentativi in modo ordinato, cosa che ci permetterà di essere esaustivi, cioè di smettere di calcolare solo dopo aver individuato tutti i fattori.
Per individuare tutti i fattori non faremo altro che fare tentativi ripetuti.
Dato il numero iniziale, una parte del programma si occuperà di provare a dividerlo per tutti i numeri. Se il resto è diverso da zero il divisore viene incrementato di uno e si riprova.
I tentativi si interrompono per due motivi:

  • se viene individuato un fattore, allora il quoziente ottenuto prende il posto del numero da scomporre e si ricomincia, avendo l'accortezza di usare come prima prova una seconda volta il fattore appena individuato,
  • il numero del quale si cercano i divisori è primo, cosa che si comprende dal fatto che il fattore, divisore, diventa più grande del quoziente e quindi non ci sono più possibili divisori.[1]

In questo modo vengono individuati solo i fattori primi poiché una volta diviso il numero iniziale per tutte le eventuali potenze di un fattore primo il quoziente che ne risulta non è più divisibile per quel numero primo nè per un qualsiasi suo multiplo, oppure è primo già il numero iniziale.

Esempio di funzionamento della scomposizione con scratch

[modifica]

Scomponiamo il numero 36:

  • quindi non è un numero primo, è un fattore di
    • prendiamo e lo mettiamo tra i fattori primi
    • sostituiamo con e ricominciamo.
  • quindi non è un numero primo, è un fattore di
    • prendiamo e lo mettiamo tra i fattori primi
    • sostituiamo con e ricominciamo.
  • quindi non è un divisore di : è un fattore di
    • cerchiamo il numero primo successivo e ricominciamo.
  • quindi non è un numero primo, è un fattore di
    • prendiamo e lo mettiamo tra i fattori primi
    • sostituiamo con e ricominciamo.
  • , il divisore è diventato più grande del quoziente , mettiamo tra i fattori di : .

Abbiamo finto.

Variabili e lista

[modifica]

Cominciamo con preparare le variabili necessarie (input) al funzionamento: Numero e NumeroIniziale, la variabile NumeroIniziale ci serve per archiviare il numero da scomporre, Divisore e Quoziente. L'output finale sarà una lista di fattori dobbiamo quindi predisporre anche una lista: Fattori. Per creare una variabile si deve andare nel menù variabile e Crea una variabile, in inglese Make a variable, nello stesso menù si trova anche Crea una lista, o il corrispondente Make a list.

Istruzioni Immagini
Andando nel menù variabile creiamo 4 variabili:

Numero, NumeroIniziale, Divisore, Quoziente

Eccole:

scratch block, scratch block, VariabileDivisore, VariabileQuoziente,

Creiamo la lista Fattori: che verrà compilata mano a mano che si troveranno i fattori primi ListFattori


Input e Valori iniziali

[modifica]

Il nostro programma comincia clikkando sulla bandiera verde.
Per prima cosa poniamo il divisore uguale a e poi il Gatto ci chiederà quale numero vogliamo testare.

Sprite Blocchi codice Istruzioni
Scratch3GreenFlagBlock Inizio del programma
DeleteAllFattori Svuotiamo la lista dei fattori
SetDivisoreTo Poniamo il divisore uguale a
scratch block Il gatto ci pone la domanda Numero? e assegna la risposta a tutte e due le variabili Numero e NumeroIniziale
SetQuozienteToNumero Il Quoziente, il primo Quoziente, viene posto uguale al Numero, altro non è che il risultato della prima divisione con Divisore

Il ciclo repeat until

[modifica]

La ricerca dei fattori primi, i divisori con resto zero, avverrà grazie ad un ciclo repeat. Il ciclo si ripete fino a che il divisore, incrementato ad ogni passaggio, non diventerà più grande del quoziente.

Sprite Blocchi codice Istruzioni
RepeatUntilDivisoreMaggioreQuoziente Il ciclo con la condizione, funzionerà fino a che il divisore non diventerà maggiore del quoziente, se il ciclo va fino in fondo continuando fino a che il divisore supera il quoziente condizione che lo termina allora, di conseguenza, il numero è primo.
scratch block Ad ogni passaggio, nell'ipotesi che il resto sia dverso da zero il divisore viene incrementato di 1. Ed il quoziente viene posto come risultato della divisione, ottenendo così che il divisore aumenta e il quoziente diminuisce. Se non si trovassero divisori, cioè se non si verificasse mai la condizione resto uguale a zero (in inglese numero mod divisore = 0) il ciclo repeat si fermerebbe al primo divisore maggiore del quoziente restituendo il fatto che il numero iniziale è primo.
IfNotDivisoreNumeroAndNumeroModDivisore Condizioni per l'interruzione del ciclo, avviene se individuato un fattore, cioè un divisore che dà resto 0.

Trovato il divisore-fattore primo:

  • lo si aggiunge alla lista dei Fattori,
  • si diminuisce di 1 il divisore in modo che alla ripresa del ciclo venga riprovato un'altra volta il fattore individuato,
  • si sostituisce il numero con il quoziente appena ottenuto e si ricomincia il ciclo con il numero portato al quoziente
AddDivisoreFattori Questo è il blocco che aggiunge il divisore-fattore alla lista dei fattori primi
ChangeDivisoreMeno1 Questa istruzione toglie 1 al divisore in modo che alla ripresa del ciclo venga provato un'altra volta il divisore del ciclo precedente, in modo da individuare quei fattori primi presenti due o più volte.
ChangeDivisoreMeno1 Questa istruzione toglie 1 al divisore in modo che alla ripresa del ciclo venga provato un'altra volta il divisore del ciclo precedente, in modo da individuare quei fattori primi presenti due o più volte.
SetQuozienteToNumero Il quoziente, risultato della divisione tra il numero e il divisore-fattore trovato, prende il posto del numero e si ricomincia a cercare altri divisore-fattori primi.

Output: i fattori primi

[modifica]

Un primo output viene fornito dalla compilazione della lista dei fattori che si conclude una volta che sono stati individuati tutti, condizione che si verifica quando l'ultimo quoziente diventa più piccolo del divisore.

Sprite Blocchi codice Istruzioni
AddNumeroFattori L'ultimo numero che si prova a dividere deve essere aggiunto alla lista come fattore primo, eventualmente come unico elemento, nel caso il numero che si è provato a scomporre fosse primo.
IfNumeroInizialeNumero Dopo aver aggiunto il numero finale, l'ultimo che si è provato a dividere si incontra una istruzione condizionale (if, se) che conclude la scomposizione. Se il numero ed il mumero iniziale sono uguali il numero da scomporre è primo, e quindi nella lista comparirà solo lui, il numero si aggiunge agli altri fattori della scomposizione elencati nella lista.


Codice completo scomposizione in fattori primi

[modifica]
Sprite Blocchi codice Istruzioni
ScomposizioneScratchCode Codice completo del progetto.

Stage del progetto

[modifica]
Stage Istruzioni
Come appare il progetto sullo stage, sulla destra è visibile la lista che a scomposizione completata si riempie di fattori

Schema progetto da montare

[modifica]

A questo link https://scratch.mit.edu/projects/361141628/ si trova il progetto scratch smontato va remixato e montato nella sequenza corretta.

Note

[modifica]
  1. Numero primo? (scuola media)

Bibliografia

[modifica]
  • Guida all’uso di Scratch Versione Studenti; Alberto Barbero, Marco Marchisotti, Alberto Davì; Associazione Dschola, Iniziativa realizzata nell’ambito del progetto Diderot della Fondazione CRT, 2014

Collegamenti esterni

[modifica]