Archived

20
Gen

Archived

purple street lights kansas city, awosting falls cliff jump, luigi’s akron ohio salad dressing recipe, microsoft to do eisenhower matrix, howard, ks obituaries, house hunters couples where are they now, minecraft world won’t load xbox series x, steven pettis us army, binghamton police arrests, une seconde chance, liverpool fc ceo salary, mmcf to mcf, lucid group glassdoor, c bruno guitar serial numbers, nj lottery retailer,

Continua la lettura su: https://www.famacademy.it/blog/2023/01/20/archived/ Autore del post: Famacademy Fonte: https://www.famacademy.it/

Articoli Correlati

Quicksort Python

Implementiamo l’algoritmo quicksort in Python, noto anche come l’algoritmo di ordinamento che è basato sull’approccio divide et impera!

Il suo funzionamento è basato sul pivot, ovvero un elemento che può essere selezionato in vari modi. Nel corso della presente guida studieremo i vari modi. Infatti, ad esempio, il pivot può essere il primo elemento, oppure l’ultimo o ancora l’elemento di mezzo ed infine può anche essere un elemento scelto a caso.

Il ragionamento che sta alla base di questo algoritmo è la partizione, ovvero la suddivisione di un array in sottoarray. Metteremo gli elementi più piccoli del pivot alla sua sinistra mentre gli elementi più grandi saranno posizionati alla sua destra.

Quicksort in Python – funzionamento

Lista di partenza:

number_list = [10,5,12,1,9,7]

I passaggi per ordinare una qualsiasi lista con il quicksort sono questi:

Divide – Dividendo la lista da ordinare scomponiamo il problema in sotto-problemi.Impera – Si risolve l’algoritmo e si applica la ricorsione.Combina – Si combinano gli output precedenti ottenuti dalle chiamate ricorsive.

Iniziamo con il primo passo, ovvero la partizione.

Scegliamo come pivot l’ultimo elemento: 7. Per estrarlo uso semplicemetne il metodo pop di Python, dunque avremo:

pivot = number_list.pop()

Dopo creiamo due liste vuote, low and high per contenere rispettivamente gi elemnti più piccoli e quelli più grandi del pivot.

low, high = [], []

Confrontiamo ciascun elemento con il pivot e lo inseriamo nella lista opportuna.

number_list = [10,5,12,1,9,7]
pivot = number_list.pop()
high, low = [], []

for number in number_list:
if number > pivot:
high.append(number)
else:
low.append(number)

print(number_list)
print(high)
print(low)

In questo modo la lista number_list non conterrà più l’ultimo elemento perchè è stato estratto e le due liste high e low sono popolate con gli elementi più grandi e più piccoli del pivot, rispettivamente.

L’output prodotto sarà questo:

number_list: [10, 5, 12, 1, 9] #manca l’elemento 7, ovvero il pivothigh: [10, 12, 9] #tutti gli elementi maggiori di 7low: [5, 1] #tutti gli elementi minori o uguali a 7

Come possiamo notare le due liste high e low non sono ordinate. Cosa possiamo fare?

Sicuramente possiamo applicare lo stesso metodo a queste due sotto-liste. Dunque richiamiamo la funzione in maniera ricorsica.

Ricordiamo di controllare la lunghezza della lista e fermarci quando non ha più elementi.

Scriviamo dunque tutto l’algoritmo che ci consente di risolvere l’ordinamento utilizzando il quicksort in Python.

def quick_sort(numbers):
length = len(numbers)
if length = 1:
return numbers

pivot = numbers.pop()
high, low = [], []
for number in numbers:
if number > pivot:
high.append(number)
else:
low.append(number)
return quick_sort(low) + [pivot] + quick_sort(high)
number_list = [10,5,12,1,9,7]
print(quick_sort(number_list))

Potete provare l’algoritmo nel compiler online sotto:

La soluzione più classica dell’algoritmo quicksort è questa:

def quicksort(numbers, p, r):
“””indichiamo con:
p – l’indice della sottolista di sinistra
r – l’indice della sottolista di destra
“””
if p r:
q = partition(numbers, p, r)
quicksort(numbers, p, q – 1)
quicksort(numbers, q + 1, r)

def partition(numbers, p, r):
pivot = numbers[r] #definiamo il pivot assegnando l’ultimo elemento
i = p – 1 #inizilizziamo l’indice dell’array di sinistra

for j in range(p, r):
if numbers[j] = pivot:
i += 1
numbers[i], numbers[j] = numbers[j], numbers[i] #scambio i valori
numbers[i + 1], numbers[r] = numbers[r], numbers[i + 1] #scambio i valori
return i + 1

number_list = [10,5,12,1,9,7]
quicksort(number_list,0,len(number_list)-1)
print(number_list)

Chiaramente ci possono essere tante altre soluzioni sull’algoritmo quicksort in Python, provate ad implementare la vostra e lasciatela nei commenti sotto.

Alcuni link utili

Indice tutorial sul linguaggio Python

1 – Introduzione al linguaggio Python

2 – Le variabili

3 – Operatori aritmetici e di assegnazione

4 – Stringhe

5 – Casting

6 – Input e print

7 – Primi esercizi in Python

8 – Errori in Python

9 – Script Python

10 – Scambio di variabili

11 – Modulo math

For list Python

In questa lezione farò alcuni esempi di utilizzo del ciclo for con l’elemento list in Python.

For list Python – Stampare una lista in ordine inverso utilizzando il ciclo for

Questo problema può avere diverse soluzioni, ne analizzeremo alcune.

La prima soluzione fa uso della funzione reversed(), per invertire una lista, la seconda che fa uso della lunghezza della lista, la funzione len().

Cominciamo analizzando in dettaglio la prima soluzione.

Innanzitutto creiamo una lista di elementi: numbers = [1, 2, 3, 4, 5], dopo utilizziamo la funzione esistente reversed() per invertire gli elementi di una lista. Dunque stampiamo gli elementi invertiti utilizzando il ciclo for in Python sulla lista.

Di seguito ecco una possibile soluzione:

numbers = [1, 2, 3, 4, 5]
numbers_reversed = reversed(numbers)
for number in numbers_reversed:
print(number)

Realizziamo adesso una seconda soluzione, calcolando la lunghezza della lista a cui sottrarremo uno. In questo modo troviamo l’indice dell’ultimo elemento della lista. Poi utilizzeremo il ciclo for opportuno.

Ecco il codice completo della seconda soluzione al nostro algoritmo che utilizza il for sulle liste in Python:

numbers = [1, 2, 3, 4, 5]
n_numbers = len(numbers) – 1
for i in range (n_numbers, -1, -1):
print(numbers[i])

For list Python – Calcolare il cubo di tutti gli elementi di una lista

Creiamo una lista di numeri interi. Con il ciclo for calcoliamo il cubo di ciascun elemento e stampiamo la lista. Utilizziamo la funzione len per determinare la lunghezza della lista. Infine cicliamo la lista modificata per stampare gli elementi.

numbers = [1, 2, 3, 4, 5]

for i in range(len(numbers)):
numbers[i] = numbers[i] * numbers[i] * numbers[i]

for number in numbers:
print(number)

Una seconda soluzione prevede semplicemente l’uso della funzione in Python per calcolare le potenze di un numero, la funzione pow().

Nel nostro caso ci servirà elevare al cubo. Poi cicliamo sulla lista con il ciclo for in Python.

Ecco il codice di esempio completo:

numbers = [1, 2, 3, 4, 5]

for i in range(len(numbers)):
numbers[i] = pow(numbers[i],3)

for number in numbers:
print(number)

Questi sono solo alcuni semplici esempi di utilizzo del ciclo for con sulle liste in Python, nelle prossime lezioni sviluppermo tanti altri esempi.

Alcuni link utili

Indice tutorial sul linguaggio Python

1 – Introduzione al linguaggio Python

2 – Le variabili

3 – Operatori aritmetici e di assegnazione

4 – Stringhe

5 – Casting

6 – Input e print

7 – Primi esercizi in Python

8 – Errori in Python

9 – Script Python

10 – Scambio di variabili

11 – Modulo math

Vuoi rimanere aggiornato sulle nuove tecnologie per la Didattica e ricevere suggerimenti per attività da fare in classe?

Sei un docente?

soloscuola.it la prima piattaforma
No Profit gestita dai

Volontari Per la Didattica
per il mondo della Scuola. 

 

Tutti i servizi sono gratuiti. 

Associazione di Volontariato Koinokalo Aps

Ente del Terzo Settore iscritta dal 2014
Tutte le attività sono finanziate con il 5X1000