Scomposizione in fattori primi (scuola media)

lezione Scomposizione in fattori primi (scuola media)
	Tipo: lezione
	Materia: Informatica per la scuola media 1
	Avanzamento: lezione completa al 100%

Scomposizione in fattori primi (scuola media)

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

Versione di Scratch utilizzata

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

Cosa richiede l'esercizio

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

Come funziona

La velocità di calcolo del PC^VK 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

Scomponiamo il numero 36:

$36:2=18$ quindi $36$ non è un numero primo, $2$ è un fattore di $36$
- prendiamo $2$ e lo mettiamo tra i fattori primi $36=2\ \cdot {\underbrace {18} _{\text{non primo}}}=2\ \cdot {\underbrace {...} _{\text{fattori primi}}}$
- sostituiamo $36$ con $18$ e ricominciamo.
$18:2=9$ quindi $18$ non è un numero primo, $2$ è un fattore di $36$
- prendiamo $2$ e lo mettiamo tra i fattori primi $36=2^{2}\cdot ...$
- sostituiamo $18$ con $9$ e ricominciamo.
$9:2=numero\ con\ la\ virgola$ quindi $2$ non è un divisore di $9$ : è un fattore di $36$
- cerchiamo il numero primo successivo $3$ e ricominciamo.
$9:3=3$ quindi $9$ non è un numero primo, $3$ è un fattore di $36$
- prendiamo $3$ e lo mettiamo tra i fattori primi $36=2^{2}\cdot 3\cdot ...$
- sostituiamo $3$ con $3$ e ricominciamo.
$3:3=1$ , il divisore è diventato più grande del quoziente $3>1$ , mettiamo $3$ tra i fattori di $36$ : $36=2^{2}\cdot 3^{2}$ .

Abbiamo finto.

Variabili e lista

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: , , , ,
Creiamo la lista Fattori: che verrà compilata mano a mano che si troveranno i fattori primi

Input e Valori iniziali

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

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

Il ciclo repeat until

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
		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.
		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.
		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
		Questo è il blocco che aggiunge il divisore-fattore alla lista dei fattori primi
		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.
		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.
		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

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
		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.
		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

Sprite	Blocchi codice	Istruzioni
		Codice completo del progetto.

Stage del progetto

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

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

Note

↑ Numero primo? (scuola media)

Bibliografia

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

[1] Numero primo? (scuola media)

[1]