PROBLEMA C++

Messaggioda Alex7337 » 21/06/2019, 12:54

Salve a tutti ragazzi, stavo tentando di scrivere un algoritmo in c++ che mi permettesse di risolvere il seguente problema:
Cleopatra sta giocando con una fila formata da $n^2$ soldatini (Dove $n$ deve essere un numero intero maggiore di 30). Per prima cosa, Cleopatra toglie dalla fila tutti i soldatini la cui posizione corrisponde a un quadrato (ossia il 1° soldatino, il 4°, il 9° e così via). Completata questa procedura, Cleopatra forma una nuova fila con i soldatini rimasti e la ripete togliendo ancora tutti i soldatini la cui posizione della nuova fila corrisponde a un quadrato. La cosa va avanti in questo modo, sempre con la stessa procedura. Quanti soldatini potrebbero essere rimasti quando Cleopatra, dopo aver completato varie volte la suddetta procedura, si stanca e smette di giocare?

ho tentato di risolverlo nel seguente modo, ma non sono sicuro che sia giusto... insomma la risposta al quesito è 132, e tale valore uscirebbe per N=33... ad ogni modo vorrei sapere se secondo voi è giusto e se si può migliorare...GRAZIE!
Codice:
int n, i, qpcont=0, cast, powN=0, esp, fila; //qpcont è il contatore per quadrati perfetti
float sq;
cout<<"inserire un numero n maggiore di 30 :\n";
cin>>n;
i=0;
for(esp=0; esp<n; esp++)
{
powN=n*n;
}
while(i<powN)
{
i++;
sq=sqrt(i);
cast=(int)sq;
  if(sq-cast==0){
      qpcont++;
    }
fila=(powN-qpcont);
powN=fila;
}
cout<<"il numero finale di soldatini e' :"<<fila<<endl;





Alex7337
New Member
New Member
 
Messaggio: 14 di 61
Iscritto il: 25/01/2019, 16:42

Re: PROBLEMA C++

Messaggioda apatriarca » 22/06/2019, 01:45

Potresti spiegare la logica del tuo programma? Ci sono infatti diverse cose che non mi sono chiare.

Il test per determinare un quadrato perfetto è a mio parere potenzialmente sbagliato. I valori in virgola mobile non rispettano necessariamente le stesse proprietà dei numeri reali, ma le operazione sono spesso soggette ad alcuni arrotondamenti. Potrebbe insomma funzionare ma mi sembra un po' fragile. Inoltre è superfluo perché puoi semplicemente iterare su tutti i quadrati direttamente senza dover verificare se un numero è un quadrato.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5241 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: PROBLEMA C++

Messaggioda Alex7337 » 22/06/2019, 09:14

il test per determinare se un numero è un quadrato perfetto è: se per esempio $i=2$ allora $√2=1.414$ e allora la forma intera di tale numero è $1$, per cui se $√2-1 !=0$ posso dire che non è un quadrato perfetto.

Cosa intendi per "iterare su tutti i quadrati direttamente?" potresti fare un esempio?
Grazie.
Alex7337
New Member
New Member
 
Messaggio: 15 di 61
Iscritto il: 25/01/2019, 16:42

Re: PROBLEMA C++

Messaggioda Super Squirrel » 22/06/2019, 15:09

Magari è un mio limite, ma la traccia dell'esercizio non l'ho proprio capita!
Dopo un certo numero di procedure (in realtà il numero esatto dovrebbe essere $2n-1$) tutti i soldatini dovrebbero essere stati rimossi dalla fila, o sbaglio?
Cosa significa: "Quanti soldatini potrebbero essere rimasti quando Cleopatra ... si stanca e smette di giocare?"
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 353 di 1486
Iscritto il: 16/05/2013, 22:05

Re: PROBLEMA C++

Messaggioda Alex7337 » 22/06/2019, 15:46

la logica dovrebbe essere , facendo un altro esempio, se ho $n=10$, allora $n^2=100$ e i quadrati da togliere sarebbero 10 :$n^2-n$, poi ne dovrei togliere $n-1 (10-1)$ cioè $n^2-n-(n-1)$ e così via... poi dato che $n$ era maggiore di 30 ho pensato di risolvere tale quesito con un programma in modo tale che l'operazione prima descritta me la facesse il computer arrivando così a un numero, ovvero 132...
Alex7337
New Member
New Member
 
Messaggio: 18 di 61
Iscritto il: 25/01/2019, 16:42

Re: PROBLEMA C++

Messaggioda apatriarca » 22/06/2019, 17:44

Le operazioni usando variabili float non hanno precisione infinita. Tuttavia in questo caso particolare credo possa in effetti funzionare. Come ti avevo tuttavia scritto, un ciclo come:
Codice:
for (int i = 1; i*i <= powN; ++i) {
    // i*i è un quadrato perfetto per definizione..
}

ti permette di ignorare la problematica di fare un test per verificare se un numero è un quadrato perfetto o no. Tuttavia non hai davvero bisogno di simulare il processo per sapere quanti valori sono stati eliminati e quindi il ciclo stesso è in effetti inutile.

Siccome
\[ (n - 1)^2 = n^2 - 2\,n + 1 = n^2 - \bigl(n + (n - 1)\bigr), \]
ogni due iterazioni ottieni il quadrato del numero precedente. Se quindi supponiamo di doverci fermare quando \(n \leq 30\) e di partire da un qualche valore \(N > 30,\) hai che il gioco si fermerà dopo \(2\,(N - 30)\) passaggi esatti. Il numero di elementi eleminati sarà inoltre semplicemente \(N^2 - 30^2\) in quanto il numero di soldatini alla fine è semplicemente \(30^2\).

EDIT: Se invece supponiamo di fermarci dopo un numero \(I\) di iterazioni la logica potrebbe essere la seguente. Ogni due iterazioni arrivi al quadrato del numero precedente per cui dopo \(k = \lfloor I/2 \rfloor \) iterazioni, il numero di soldatini sarà \( (N - k)^2 \). Se il numero di iterazioni è dispari, dovrai eliminare altri \(N - k\) soldatini. Il numero finale di soldatini sarà insomma \((N - k)\,\bigl(N - k - m \bigr)\) dove \(m = I \bmod 2.\) Svolgendo ora i calcoli per il numero di soldatini eliminati credo che la soluzione sia \( I\,N - k\,(k + m) \)
apatriarca
Moderatore
Moderatore
 
Messaggio: 5242 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite