Aiuto su algoritmo di euclide

di
Shinigami
il
1 risposte
Shinigami
Shinigami
Pochi posts
Iscritto da
gen, 2015
Messaggi:
10

Aiuto su algoritmo di euclide

Ho già cercato sul forum se fosse stato discusso l'argomento ma vorrei migliorare il mio codice .
premetto che non so programmare e faccio confusione quando c'è da fare una ricorsione ( e questo è il motivo per il quale non le uso ) ma in questo caso non posso farne a meno ...
ho un esercizio da fare ma non ce la faccio proprio a capire come si fa
di seguito vi incollo la traccia

Scrivere un programma C++ che, letti da input un intero N e un array di interi di dimensione N, stampi la
stringa SI se nell’array sono presenti almeno due numeri coprimi, e la stringa NO altrimenti. Due numeri si
dicono coprimi se il loro unico divisore comune è 1. Si può supporre che l’array contenga almeno 2
elementi, ossia N>=2.
Esempio
Se l’array contenesse i valori 15 43 75 89 64 44 il programma dovrebbe stampare SI, infatti sono
presenti almeno due numeri coprimi, ad esempio 15=1*3*5 e 44=1*2*2*11 sono comprimi perché hanno
come unico divisore comune 1.

questo di seguito è il mio codice ( incompleto , anzi peggio ) 
#include <iostream>
using namespace std ; 
int main () 
{
	int n ; 
	int vet [ n ] ,a , b ,r = 0, temp;
	
	cin >> n ; 
	
	for ( int i = 0 ; i < n ; i ++ ){
		cin >> vet [i]; 
	}
	for ( int i = 0 ; i < n ; i++){
		for (int j = 1; j < n-1 ; j++){
		if ( vet [i] != 0 && vet[j] != 0 ){
			while (vet [i]/ vet [j]!= 1){
			
			if ( vet [i] % vet [j]!= 0){
				r = vet [i] % vet [j];
				vet[i]= vet [j]; 
				vet [j]= r ;
				}
			}	 
		}
	}
}
return 0 ;	
}
chiedo venia per le parentesi chiuse male

se ho fatto degli strafalcioni nell'impostare siate il più brutali possibili

1 Risposte

  • Korr
    Korr
    Pochi posts
    Iscritto da
    mag, 2015
    Messaggi:
    41

    Re: Aiuto su algoritmo di euclide

    Non capisco perche' parli di ricorsione, che nel programma non usi;
    il docente ha chiesto di usare l'algoritmo di Euclide ricorsivo?

    La ricorsione si ha quando una funzione contiene al proprio interno
    una chiamata a se' stessa.

    Il problema e' risolvibile facilmente anche senza utilizzare la ricorsione.

    Il mio compilatore g++ compila il tuo codice, ma all'avvio del programma
    si verifica un errore di segmentazione; l'errore sparisce se dimensiono
    l'array vet[] nel codice da compilare con istruzioni tipo int vet[10]
    o int vet[n], dove n e' stato predefinito con la direttiva #define n 10

    Si vede che non tutti i compilatori supportano il dimensionamento
    di un array in fase di esecuzione (mi pare di aver letto che e' una
    caratteristica del C99).

    Se il problema chiede espressamente che sia l'utente a indicare in anticipo
    quanti numeri vuole inserire, si puo' risolvere allocando dinamicamente
    la memoria nella quantita' necessaria per poi accedere ai numeri tramite puntatore
    (o usando la stessa notazione degli array o con l'aritmetica dei puntatori): 
    
...........
int *vet; // puntatore a interi
...........
cin>>n;   // lettura numero di elementi da allocare
...........
vet=new int[n];  // allocazione della memoria per ospitare n interi
...........
cin>>vet[i];     // inserimento di un numero nella memoria allocata
...........
delete [] vet  // deallocazione quando la memoria non serve piu' 
...........
vet=NULL    // assegnamento di NULL a vet prima della fine del programma
...........
    Ho constatato che la condizione (vet / vet [j]!= 1)
    associata al ciclo while fa entrare in un ciclo infinito.
    Ma prima di entrare nel merito della questione ti consiglio
    di creare una funzione apposita, per calcolare il mcd,
    tipo:     
    
int mcd(int a, int b)
 {
  algoritmo di Euclide
 }
    cosi' il programma sarebbe molto piu' leggibile
    e potresti individuare piu' facilmente l'errore.
    Inoltre capita in vari programmi di dover calcolare il mcd,
    cosi' ti troveresti la funzione gia' pronta anche per altre occasioni.
    Se cerchi su Google, troverai subito degli esempi di tale funzione,
    sia ricorsiva che non.
Devi accedere o registrarti per scrivere nel forum
1 risposte