Numeri amicabili in C++

Numeri amicabili in C++

In questa lezione realizzeremo un algoritmo sui numeri amicabili in C++, ovvero quei due numeri per i quali la somma dei divisori propri dell’uno è uguale all’altro e viceversa.

Per divisori propri si intendono tutti i divisori tranne il numero stesso.

Facciamo un esempio di numeri amicabili, considerando i numeri 220 e 284.

Il numero 220 ha come divisori propri: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 e 110.

Se sommiamo questi divisori otteniamo il numero 284.

Allo stesso modo, prendiamo il numero 284, questo ha come divisori: 1, 2, 4, 71, 142. Sommandoli otteniamo il numero 220.

Ecco dunque che i numeri 220 e 284 sono amicabili

Algoritmo per i numeri amicabili in C++

Prendere in input due numeri e visualizzare sullo schermo se sono amicabili.

Innanzitutto dichiariamo le variabili che ci servono:

a, b – Sono le due variabili intere che indicano i numeri per cui vogliamo verificare l’ipotesi iniziale.

div – Rappresenta il divisore che, partendo da 1, verrà incrementato opportunamente all’interno dei cicli.

s – Rappresenta la variabile che contiene la somma dei divisori.

Dopo aver dichiarato le variabili, chiediamo all’utente di inserirle in input, poi impostiamo il div a 1 e la somma a 0 (ciò si poteva fare anche prima).

Impostiamo nel ciclo while la condizione che div sia minore o uguale al primo numero. Dunque, finché questa condizione è vera, troviamo tutti i divisori di un numero e li sommiamo nella variabile s.

Dopo controlliamo se la somma così ottenuta è uguale al primo numero.

Se ciò è verificato allora procediamo a trovare i divisori del secondo numero e confrontiamo se la loro somma è uguale al primo numero.

Solo se questa condizione è verificata allora i due numeri sono amicabili.

Ecco dunque il codice completo che rappresenta l’algoritmo sui numeri amicabili in C++:

#include <iostream>
using namespace std;

main() {
	int a,b,div,s;

	cout<<"Inserisci un numero: ";
	cin>>a;
	cout<<"Inserisci il secondo numero: ";
	cin>>b;
		
	div=1;
	s=0;
	
	while(div<=a/2) {
		if (a%div==0)
			s+=div;
		div++;
	}
	
	if(s==b){
		div=1;
		s=0;
		while(div<=b/2) {
			if (b%div==0)
				s+=div;
			div++;
		}
		if(s==a) 
			cout<<"I due numeri sono amicabili";
		else
			cout<<"I numeri non sono amicabili";
	}
	else 
		cout<<"I numeri non sono amicabili";
	
	return 0;
}

Chiaramente si poteva procedere in altri modi per trovare la soluzione all’algoritmo sui numeri amicabili in C++, proponete pure la vostra nei commenti sotto.

Alcuni link utili

Indice argomenti linguaggio C++

1- Introduzione al linguaggio C++

2- Variabili in C++

3- Operatori di assegnazione in C++

4- Esempi in C++

5- Casting in C++

Successione di Fibonacci in C++

Insertion sort in C++

Insertion sort in C++

In questa lezione affronteremo l’insertion sort in C++, un algoritmo di ordinamento che utilizza un metodo molto simile a quello usato da un essere umano per ordinare un mazzo di carte.

L’algoritmo di ordinamento insertion sort è molto semplice da implementare e non utilizza un array di appoggio, è dunque un algoritmo in place. In questo modo si risparmia memoria.

L’algoritmo utilizza due indici, ad esempio i e j, dove i punta al secondo elemento, mentre j punta al primo.

Quindi, per un ordinamento crescente, si confrontano i due elementi e se l’elemento puntato dall’indice j è maggiore dell’elemento puntato dall’indice i si scambiano, altrimenti l’indice avanza.

Il procedimento si ripete finché non si trova la posizione dove inserire l’elemento. In questo modo gli elementi maggiori vengono spostati verso destra.

Se volessimo ordinare l’array in ordine decrescente, dovremmo agire in maniera opposta.


Insertion sort – Esempio funzionamento

Facciamo subito un esempio per capire la logica di funzionamento.

Partiamo dunque da un array con questi elementi:

6 2 4 9 1 8

Innanzitutto confrontiamo 6 con 2

– dato che 6 è maggiore di 2 si sposta il 6 e si procede all’inserimento del 2.

Primo passaggio: 2 6 4 9 1 8

Adesso si confronta 6 con 4

– dato che 6 è maggiore di 4 si dovrebbero scambiare ma prima dobbiamo confrontare il 4 anche con il 2. Dato che 2 non è maggiore di 4 si può scambiare la posizione del 6 con quella del 4.

Secondo passaggio: 2 4 6 9 1 8

Dopo viene confrontato 6 con 9,

 – dato che 6 non è maggiore di 9 non si fa nulla, si incrementa solo l’indice.

Terzo passaggio: 2 4 6 9 1 8

Poi si confronta 9 con 1

– dato che 9 è maggiore di 1 si continua a confrontare 1 con gli altri elementi. Quindi, in questo caso essendo tutti maggiori, si sposteranno verso destra lasciando libera la prima posizione dove poter inserire l’elemento.

Quarto passaggio: 1 2 4 6 9 8

Infine si confronta il 9 con il 8,

– dato che è superiore si procede a confrontare il numero 8 con il 4, ma essendo superiore scambiamo il 9 con il numero 8.

Quinto passaggio: 1 2 4 6 8 9


Sviluppo insertion sort in C++

Per realizzare l’algoritmo chiediamo innanzitutto di inizializzare un array a[] con i valori inseriti da tastiera.

Dopo, per l’ordinamento, si utilizza un ciclo esterno con indice i che parte da 1 e una variabile temporanea temp nella quale memorizziamo il secondo valore (a[1]). L’indice j parte da 0.

Quindi inizialmente i punta al secondo elemento mentre j punta al primo. Dopo utilizziamo il while che si ripete finché è vera questa condizione: il valore puntato dall’indice j è maggiore di temp e j>=0.

All’interno del while memorizziamo il valore puntato dall’indice j nella posizione successiva a j e decrementiamo j di 1.

Quando si finisce il ciclo più interno (while) allora nella posizione j+1 memorizziamo il valore di temp.

Continuiamo finché si verifica questa condizione: i<n.

Ecco il listato completo dell’insertion sort in C++.

#include<iostream>
using namespace std;

#define MAX 10 

int main() { 
	int n, a[MAX], i, j, temp; 
	
	cout<<"Quanti elementi?: "; 
	cin>>n; 
	
	for(i=0;i<n;i++) {
		cout<<"Elemento numero "<<i+1<<": "; 
		cin>>a[i]; 
	}
	
	cout<<"Ordiniamo l'array \n"; 
	for(i=1;i<n;i++) { 
		temp=a[i]; 
                j=i-1; 
		while((a[j]>temp) && (j>=0)) { 
			a[j+1]=a[j]; 
                        j--;
                } 
		a[j+1]=temp; 
		} 
		
		cout<<"Array dopo l'ordinamento: \n"; 
		for(i=0; i<n; i++) 
			cout<<a[i]<<" ";
	
	return 0; 
}

Algoritmo insesrtion sort in C++ spiegato passo passo:

Partiamo da questo array non ordinato:

6 2 4 9 1 8

Il ciclo esterno verrà eseguito 5 volte, perchè partiamo dalla seconda posizione.

Prima iterazione

for(i=1;i<n;i++) // Inizialmente l’indice i parte da 1, cioè i=1

temp=arr[i]; //temp=2

j=i-1; //j=0

while(a[j]>temp && j>=0)

/*6>2 vero j>=0 vero. Dunque la condizione è vera*/

a[j+1]=a[j]; //a[1]=6

j–; //j=-1.

/*Dato che la condizione j>=0 non è verificata si esce dal ciclo while*/

a[j+1]=temp; //a[0]=2

Ci troveremo quindi in questa situazione:
2 6 4 9 1 8

Seconda iterazione

for(i=1;i<n;i++) //i viene incrementato di 1, quindi parte da 2, cioè i=2

temp=a[i]; //temp=4

j=i-1; //j=1

while(a[j]>temp && j>=0)

/* 6>4 vero j>=0 vero. Dunque la condizione è vera*/

a[j+1]=a[j]; //cioè ad a[2] assegno il valore di a[1]. Quindi a[2]=6

j–; //j=0

/*Dato che a[j]>temp cioè 2>4 non è verificata, non si continua con il while*/
a[j+1]=temp; // cioè a[1]=4

Questa dunque la nuova situazione:

2 4 6 9 1 8

Terza iterazione

for(i=1;i<n;i++) //i viene incrementato di 1, quindi parte da 3, cioè i=3

temp=a[i]; //temp=9

j=i-1; //j=2

while(a[j]>temp && j>=0) // 6>9 falsa. Dunque la condizione è falsa.

/*Non si entra dentro al ciclo while perciò a[2] rimane a 6, quindi la prossima istruzione sarà:*/

a[j+1]=temp; //cioè a[3]=9

 

Ecco dunque l’array fino a questo punto:
2 4 6 9 1 8

Quarta iterazione

for(i=1;i<n;i++) //i viene incrementato di 1, quindi parte da 4, cioè i=4

temp=a[i]; //temp=1

j=i-1; //j=3

while(a[j]>temp && j>=0)

/* 9>1 vero; j>=0 vero. Quindi la condizione è vera*/

a[j+1]=a[j]; //a[4]=9

j–; //j=2

/*Dato che a[j]>temp cioè 9>1 è verificata e j>=0 anche, si continua con il while*/

a[j+1]=a[j]; //a[3]=6

j–; //j=1

/*Dato che a[j]>temp cioè 6>1 è verificata e j>=0 anche, si continua con il while*/

a[j+1]=a[j]; //a[2]=4

j–; //j=0

/*Dato che a[j]>temp cioè 4>1 è verificata e j>=0 anche, si continua con il while*/

a[j+1]=a[j]; //a[1]=2

j–; //j=-1

/*Dato che a[j]>temp cioè 2>1 è verificata e j>=0 non è verificata, si esce dal while*/

a[j+1]=temp; //cioè a[0]=1

Come si può notare gli elementi 2, 4, 6, 9 sono stati shiftati a destra.

Quindi avremo:

1 2 4 6 9 8

Quinta iterazione

for(i=1;i<n;i++) // l’indice i parte da 5, cioè i=5

temp=arr[i]; //temp=8

j=i-1; //j=4

while(a[j]>temp && j>=0)

/*9>8 vero e j>=0 vero. Dunque la condizione è vera*/

a[j+1]=a[j]; //a[5]=9

j–; //j=3.

/*Dato che la condizione a[j]>temp non è verificata si esce dal ciclo while*/

a[j+1]=temp; //a[4]=8

Adesso l’indice i diventa 6 che non è minore di 6 (i<n) e quindi si esce dal for.

Ecco l’algoritmo ordinato:

1 2 4 6 8 9

Questa è l’implementazione dell’algoritmo insertion sort in C++ che volevo presentare in questa lezione.

Alcuni link utili

Esercizi con gli array in C++

Esercitazione sugli array in C++

Passaggio di parametri per valore o per riferimento

Equazioni di secondo grado in C++

Le variabili globali e loali in C++

Definizione di funzioni in C++

Come usare il for in C++

Massimo tra n numeri in C++

Esercizi con switch case in C++

Tutorial C++

Successione di Fibonacci in C++