ALGORITMI IN C++

di il
3 risposte

ALGORITMI IN C++

Non so da dove partire per codificare questi 2 algoritmi. Potete darmi una mano, o comunque farmi capire come devo iniziare??
1° algoritmo:
scrivere una funzione in c++ che restituisca true se il numero intero fornito come argomento è primo, altrimenti false. Scrivere un programma in c++ che, utilizzando la funzione precedente, visualizzi quali numeri primi sono presenti tra 1 e un valore N fornito in input.

2°algoritmo:
Un famoso "gioco" matematico consiste nel costruire una sequenza di numeri interi in modo che ogni numero sia la metà del precedente se esso è pari, altrimenti il successore del suo triplo: partendo da un numero qualsiasi si prosegue fino a raggiungere 1. Scrivere una funzione in c++ che abbia come argomento il numero iniziale e che restituisca come risultato il numero di iterazioni necessario per concludere la sequenza . Scrivere un programma in c++ che, utilizzando la funzione precedente,l visualizzi la lunghezza delle sequenze per numeri iniziali compresi tra due valori forniti in input .



vorrei cercare di capirli più che altro ,non mi interessa copiare algoritmi già fatti ... vi ringrazio in anticipo chiunque risponderà!!!!

3 Risposte

  • Re: ALGORITMI IN C++

    Ciao,
    partiamo dal primo. Innanzitutto la "forma" della funzione dovrà essere del tipo
    
    bool is_prime(int number);
    
    cioè dovrà prendere in ingresso, come parametro, un intero e restituire in uscita un bool che indica se il numero è primo oppure no.

    Ora veniamo al come determinare se un numero è primo: sappiamo che un numero primo è divisibile solo per 1 e per se stesso. Tradotto, questo significa che qualunque altro numero compreso tra 1 e il numero stesso non deve essere un divisore. Quindi puoi semplicemente fare un ciclo for che parta da 2 ed arrivi fino al numero che stai controllando: se sulla strada (cioè nel ciclo for) incontri un suo divisore, allora puoi dire che il numero non è primo, altrimenti lo è.

    Una banale ottimizzazione è quella di fermare il ciclo for non al numero che vuoi controllare, ma alla sua radice (eventualmente la radice+1), in modo da dover fare meno confronti, che sarebbero comunque inutili: se non trovi un divisore prima allora sei certo che non lo troverai nemmeno dopo.

    Prova e facci sapere come va. Poi guardiamo anche il secondo.
  • Re: ALGORITMI IN C++

    Queste 3 ho pensato come possibili soluzioni della funzione; per il programma finale ci pensiamo dopo...

    la prima:

    bool numeroprimo (int n)
    {
    bool risp=false;
    for(int i=2; i<=n/2; i++)
    {
    if (n%i==0)
    risp=false;
    }
    return true;

    }


    la seconda:

    oppure questo

    bool numeroprimo (int n)
    {
    bool risp=false;
    for(int i=2; i<=n/2; i++)
    {
    if (n%i!=0)
    risp=risp||true;
    else
    risp=risp||false;
    }
    return risp;
    }


    la terza:

    bool numeroprimo (int n)
    {
    bool risp=false;
    for(int i=2; i<=n/2; i++)
    {
    if (n%i==0)
    risp=false;
    else
    risp=true;
    }
    return risp;
    }

    sento che c'è un non so che di sbagliato...mah..
  • Re: ALGORITMI IN C++

    Veramente ti avevo detto di fermarti alla radice del numero, che è in generale molto minore della sua metà. Poi, soprattutto, è sbagliato il meccanismo dei return...
    Di seguito gli errori:

    1. se la condizione dell'if è verificata allora fai risp = false, poi? Dove va a finire quel risp? In ogni caso la funzione ritorna true, e questo è ovviamente un errore

    2. risp || true è sempre true, per definizione dell'operatore OR

    3. se trovi un suo divisore imposti risp = false. Se però, in una delle iterazioni successive trovi che i non è un divisore di n allora risp torna ad essere true, e questo è chiaramente sbagliato

    La sostanza è che appena trovi un divisore, puoi subito concludere che il numero non è primo. Invece, per dire che un numero è primo, devi scorrere tutti i possibili divisori e verificare che nessuno lo divide perfettamente.

    Un esempio di funzione:
    
    bool is_primo(int numero)
    {
        int radice = sqrt(numero);
    
        for(int i=2; i<radice+1; ++i) {
            if(numero % i == 0) {
                // numero e' divisibile per i --> non e' primo
                return false;
            }
        }
        // sono arrivato fino a qui senza trovare divisori --> e' primo
        return true;
    }
    
Devi accedere o registrarti per scrivere nel forum
3 risposte