PROBLEMA C++

[Alex7337]

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!

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;

[apatriarca]

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.

[Alex7337]

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.

[Super Squirrel]

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?"

[Alex7337]

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...

[apatriarca]

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:

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) \)