Scomposizione in fattori primi (scuola media)

Da Wikiversità, l'apprendimento libero.
Jump to navigation Jump to search
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 richesta 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.

Istruzioni Immagini
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
CatScratch Scratch3GreenFlagBlock Inizio del programma
CatScratch DeleteAllFattori Svuotiamo la lista dei fattori
CatScratch SetDivisoreTo Poniamo il divisore uguale a
CatScratch scratch block Il gatto ci pone la domanda Numero? e assegna la risposta a tutte e due le variabili Numero e NumeroIniziale
CatScratch SetQuozienteToNumero Il Quoziente, il primo Quoziente, viene posto uguale al Numero, altro non è che il risultato della prima divisone 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
CatScratch 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.
CatScratch 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.
CatScratch IfNotDivisoreNumeroAndNumeroModDivisore Condizioni per l'interruzione del ciclo, avviene se individuato un fattore, cioè un divisore che da 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
CatScratch AddDivisoreFattori Questo è il blocco che aggiunge il divisore-fattore alla lista dei fattori primi
CatScratch 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.
CatScratch 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.
CatScratch SetQuozienteToNumero Il quoziente, risultato della divisone 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
CatScratch 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.
CatScratch 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
CatScratch ScomposizioneScratchCode Codice completo del progetto.

Stage del progetto[modifica]

Stage Istruzioni
ScratchScomposizioneStage 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]