Codifica in c++
salve a tutti, ho visto la sessione ''informatica'' quindi ho pensato che magari potreste aiutarmi 
si tratta di una codifica in C++ ... potete?
in sintesi, dovrei fare in C++ questo problema: ''dato un numero, bisogna individuare tutti i fattori di questo''
il prof mi ha dato delle indicazioni: se il numero è 500, allora il primo fattore è 2. Divido 500 per 2, quindi ho 250. Ora, non devo trovare più i fattori di 500, ma di 250; divido 250 per 2 e ottengo 125. Così adesso devo trovare i fattori di 125: provo con 3, ma non va; quindi passo al 5 e mi viene 25..e così via.
Ho provato di tutto, il ragionamento l'ho capito, ma non riesco a tradurre in C++!
Inoltre il prof ha detto che un contatore c'è, ma non è sempre incrementato: viene incrementato solo in alcuni casi. Aiutoo! :S
(PS. dovrei fare tutto nella funzione main)
si tratta di una codifica in C++ ... potete?
in sintesi, dovrei fare in C++ questo problema: ''dato un numero, bisogna individuare tutti i fattori di questo''
il prof mi ha dato delle indicazioni: se il numero è 500, allora il primo fattore è 2. Divido 500 per 2, quindi ho 250. Ora, non devo trovare più i fattori di 500, ma di 250; divido 250 per 2 e ottengo 125. Così adesso devo trovare i fattori di 125: provo con 3, ma non va; quindi passo al 5 e mi viene 25..e così via.
Ho provato di tutto, il ragionamento l'ho capito, ma non riesco a tradurre in C++!
Inoltre il prof ha detto che un contatore c'è, ma non è sempre incrementato: viene incrementato solo in alcuni casi. Aiutoo! :S
(PS. dovrei fare tutto nella funzione main)
Risposte
Spero di aver capito bene ti allego qll che ho fatto io all'università con il mio prof.
spero di essere stato d'aiuto senno scusa per averti fatto perdere tempo
#include <stdio.h>
int main()
{
int n, i;
printf("Inserisci un numero positivo: ");
scanf("%d", &n);
while (n <= 0)
{
printf("Inserisci un numero positivo: ");
scanf("%d", &n);
}
printf("I divisori sono: ");
i = 1; while (i <= n)
{
if (n % i == 0)
printf("%d ",i);
i++;
}
printf("\n");
system ("PAUSE");
return 0;
}spero di essere stato d'aiuto senno scusa per averti fatto perdere tempo
"peppelio93":
Spero di aver capito bene ti allego qll che ho fatto io all'università con il mio prof.
#include <stdio.h> int main() { int n, i; printf("Inserisci un numero positivo: "); scanf("%d", &n); while (n <= 0) { printf("Inserisci un numero positivo: "); scanf("%d", &n); } printf("I divisori sono: "); i = 1; while (i <= n) { if (n % i == 0) printf("%d ",i); i++; } printf("\n"); system ("PAUSE"); return 0; }
spero di essere stato d'aiuto senno scusa per averti fatto perdere tempo
solo k apposto del printf e scanf devi mettere cout e cin che sono i propt per il c++ visto che io lo avevo fatto il c. bye
Il codice di peppelio93 è un inizio ma il problema era trovare i fattori che non sono proprio i divisori.
Ad esempio nel caso di $500$ i fattori primi sono $2, 2, 5, 5, 5$ infatti $500 = 2^2 \cdot 5^3$ mentre tra i divisori compare anche il $10$.
Ad esempio nel caso di $500$ i fattori primi sono $2, 2, 5, 5, 5$ infatti $500 = 2^2 \cdot 5^3$ mentre tra i divisori compare anche il $10$.
ciao, grazie per la tua risposta
la codifica è perfetta, ma sono io che non ho capito nulla..sono una frana!
ad esempio, %d e &n per che cosa stanno?
la codifica è perfetta, ma sono io che non ho capito nulla..sono una frana!
ad esempio, %d e &n per che cosa stanno?
comunque ho provato e riprovato, ma non funziona...grazie lo stesso per il tuo tempo
Ciao, questa è una prima idea funzionante ma un po' rudimentale. Prova a ragionarci un po' sopra e poi ne parliamo.
#include <iostream>
using namespace std;
int main()
{
int num;
cout << "Inserire un numero: ";
cin >> num;
for(int i=2; i<=num; i++) {
while(num % i == 0) {
cout<<i<<endl;
num /= i;
if(i == 1)
break;
}
}
return 0;
}
ciao minomic..ti ringrazio per il tuo aiuto 
il ragionamento l'ho capito finalmente, è anche molto semplice!
in pratica, devo dividere il numero per i (che sarebbe il contatore, giusto?); poi se il resto della divisione tra in numero ed i è uguale a 0, do in output i. Però non ho capito alcune cose: cosa significa num /=i ? E, dopo if (i==1), cosa significa break?
Sono alle prime armi, quindi molte cose per me sono nuove.
ti ringrazio!
il ragionamento l'ho capito finalmente, è anche molto semplice!
in pratica, devo dividere il numero per i (che sarebbe il contatore, giusto?); poi se il resto della divisione tra in numero ed i è uguale a 0, do in output i. Però non ho capito alcune cose: cosa significa num /=i ? E, dopo if (i==1), cosa significa break?
Sono alle prime armi, quindi molte cose per me sono nuove.
ti ringrazio!
"engy":
in pratica, devo dividere il numero per i (che sarebbe il contatore, giusto?); poi se il resto della divisione tra in numero ed i è uguale a 0, do in output i. Però non ho capito alcune cose: cosa significa num /=i ? E, dopo if (i==1), cosa significa break?
Esatto, l'unica accortezza è il while: stampa in output il numero finchè è divisore del numero considerato. Questo permette di stampare correttamente i fattori che compaiono più volte. Ad esempio nel caso di $8$ stampa $2, 2, 2$.
Scrivere
num /= iè la stessa cosa che scrivere
num = num/icioè sostituisco il numero iniziale con quello che rimane dopo la divisione per i.
Il break serve per uscire dal ciclo for senza che il contatore i arrivi per forza alla fine del suo percorso: quando il numero iniziale è arrivato a $1$ significa che ho già individuato tutti i suoi fattori e quindi esco.
"minomic":
Il break serve per uscire dal ciclo for senza che il contatore i arrivi per forza alla fine del suo percorso: quando il numero iniziale è arrivato a $1$ significa che ho già individuato tutti i suoi fattori e quindi esco.
Non mi torna. La variabile "i" non assume mai valore 1: parte da 2 e viene solo incrementata. L'esecuzione non entra mai dentro l'if, semplicemente esce dal while quando la condizione "num % i == 0" diventa falsa.
Inoltre, se anche arrivasse all'istruzione break, uscirebbe dal ciclo più interno, che è il while, non il for. Dal ciclo for si esce comunque appena possibile perché "num" prima o poi arriva ad 1, che è minore di qualsiasi "i".
X Claudio86: non capisco i tuoi dubbi, semplicemente elimina divisori in ordine crescente (tutti primi eliminando i fattori primi di volta in volta). In ogni caso alla fine si avrà senz'altro i = num, e in quel ciclo si porta num a 1. Si può chiudere in entrambi i modi.
"claudio86":
Non mi torna.
Ci credo, ho sbagliato a scrivere...
L'idea era mettereif(num == 1)
break;e infatti poi l'ho spiegato a engy come se avessi scritto quello. Però forse non ci va lo stesso...
"vict85":
X Claudio86: non capisco i tuoi dubbi, semplicemente elimina divisori in ordine crescente (tutti primi eliminando i fattori primi di volta in volta). In ogni caso alla fine si avrà senz'altro i = num, e in quel ciclo si porta num a 1. Si può chiudere in entrambi i modi.
Quello che non mi tornava era
if (i == 1)
break;"minomic":
[quote="claudio86"]Non mi torna.
Ci credo, ho sbagliato a scrivere...
L'idea era mettereif(num == 1)
break;e infatti poi l'ho spiegato a engy come se avessi scritto quello. Però forse non ci va lo stesso...[/quote]Ok, così in effetti ha un po' più senso. Anche se non è necessario lo stesso, "1 % i != 0" sempre se "i > 1", quindi esce correttamente dal while.
Ho pensato a un piccolo miglioramento.
In questo modo si può anche uscire dal programma prima che il ciclo for termini. Ad esempio, si vogliano trovare i fattori di $16$.
Lo divido per $2$, ottengo $8$, divido per $2$, ottengo $4$, divido per $2$, ottengo $2$, divido per $2$, ottengo $1$ ed esco. Tutto questo senza aver mai incrementato la variabile $i$.
if(num == 1)
return 0;In questo modo si può anche uscire dal programma prima che il ciclo for termini. Ad esempio, si vogliano trovare i fattori di $16$.
Lo divido per $2$, ottengo $8$, divido per $2$, ottengo $4$, divido per $2$, ottengo $2$, divido per $2$, ottengo $1$ ed esco. Tutto questo senza aver mai incrementato la variabile $i$.
"minomic":
Ho pensato a un piccolo miglioramento.
if(num == 1) return 0;
In questo modo si può anche uscire dal programma prima che il ciclo for termini. Ad esempio, si vogliano trovare i fattori di $16$.
Lo divido per $2$, ottengo $8$, divido per $2$, ottengo $4$, divido per $2$, ottengo $2$, divido per $2$, ottengo $1$ ed esco. Tutto questo senza aver mai incrementato la variabile $i$.
Miglioramento in che senso? Probabilmente rende il codice meno chiaro, sotto questo punto di vista mi sembra più un peggioramento.
Xclaudio: Avevo letto male infatti
X minomic: Sta attento ai numeri negativi! Con quelli il tuo codice fallisce, usa gli unsigned int piuttosto.
Sinceramente penso che si possa ridurre in qualche modo, a parte ovviamente considerare \(2\), \(3\) e \(5\) a parte e ridurre del \(73 \%\) le \(i\) controllate. Il caso peggiore è quello in cui \(n\) è primo, infatti in questo caso la complessità diventa lineare, quando basta fermarsi a \(\sqrt{n}\) per rendersene conto. La stessa cosa succede quando \(n\) diventa un numero primo ad un certo punto. Probabilmente si può risolvere con una funzione ricorsiva.
X minomic: Sta attento ai numeri negativi! Con quelli il tuo codice fallisce, usa gli unsigned int piuttosto.
Sinceramente penso che si possa ridurre in qualche modo, a parte ovviamente considerare \(2\), \(3\) e \(5\) a parte e ridurre del \(73 \%\) le \(i\) controllate. Il caso peggiore è quello in cui \(n\) è primo, infatti in questo caso la complessità diventa lineare, quando basta fermarsi a \(\sqrt{n}\) per rendersene conto. La stessa cosa succede quando \(n\) diventa un numero primo ad un certo punto. Probabilmente si può risolvere con una funzione ricorsiva.
ringrazio tutti, gentilissimi! Mi è tutto chiaro
"engy":
ringrazio tutti, gentilissimi! Mi è tutto chiaro
Bene, adesso continuiamo a litigare tra di noi!
"claudio86":
Miglioramento in che senso? Probabilmente rende il codice meno chiaro, sotto questo punto di vista mi sembra più un peggioramento.
Non so se ho pensato una cosa giusta però provo a fare un esempio. Vogliamo calcolare i fattori di $32768$. So che è una potenza del $2$ (in particolare $2^{15}$). Comincia il ciclo for con $i=2$: continuando a dividere per $2$ il numero diventa $1$ quindi abbiamo già finito. Senza quel break secondo me la i verrebbe incrementata comunque e controllata fino a $32768$. Non so se mi sono spiegato bene e soprattutto non so se ci sia davvero un miglioramento in termini di efficienza ma era un'idea che mi era venuta e ho pensato di proporvela.
In realtà avrebbe più senso fermarsi a i = num che num = 1. Ogni volta che dividi num non possiede divisori minori di i. Quindi è evidente che i raggiungerà prima o poi num. Anzi puoi fermarti alla sua radice quadrata in quanto un numero non-primo ha divisori minori della sua radice quadrata. D'altra parte la complessità del calcolo della radice quadrata rende il tutto meno conveniente.
"minomic":
Non so se ho pensato una cosa giusta però provo a fare un esempio. Vogliamo calcolare i fattori di $32768$. So che è una potenza del $2$ (in particolare $2^{15}$). Comincia il ciclo for con $i=2$: continuando a dividere per $2$ il numero diventa $1$ quindi abbiamo già finito. Senza quel break secondo me la i verrebbe incrementata comunque e controllata fino a $32768$.
No, perché nel frattempo "num" è diventato 1, quindi la condizione del for "i <= num" è falsa.
"minomic":
Non so se mi sono spiegato bene e soprattutto non so se ci sia davvero un miglioramento in termini di efficienza ma era un'idea che mi era venuta e ho pensato di proporvela.
L'unico vantaggio è che ti risparmi un incremento della variabile "i", che sarà dell'ordine dei nanosecondi. Inoltre paghi con un if ad ogni iterazione, che spesso risulta in un calo delle prestazioni (il discorso è abbastanza complesso, ma la linea guida è "evita confronti (if, switch...) nei cicli più interni"). Anche se probabilmente il tutto sarà irrilevante.
Stai violando le due regole dell'ottimizzazione
:- Don’t do it.
- (For experts only!): Don’t do it yet.
(C'è anche la terza, volendo)
Se proprio si volesse ottenere miglioramenti tangibili, si dovrebbe migliorare l'algoritmo. Per esempio, se si volessero calcolare i divisori di molti numeri abbastanza grandi, si potrebbe calcolare una tantum un grosso insieme di numeri primi, e poi testare solo questi ultimi come possibili divisori.
"claudio86":
No, perché nel frattempo "num" è diventato 1, quindi la condizione del for "i <= num" è falsa.
Hai ragione!! Credo che seguirò le regole dell'ottimizzazione e non farò proprio nulla!
Grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo