Quale numero troviamo nella milionesima posizione?

Discuti dei problemi relativi alla programmazione nel tuo linguaggio preferito!

Moderatori: cb_123, thrantir, tonertemplum

Quale numero troviamo nella milionesima posizione?

Messaggiodi MauriAxel il 04 apr 2008, 10:03

ragazzi mi serve una mano, devo scrivere un programma in C++. questa è la consegna:

Una sequenza di numeri è costruita nel modo seguente:

si scrive il numero 1 una volta, il numero 2 due volte, il numero 3 tre volte, il numero 4 quattro volte, il numero 5 cinque volte, il numero n n volte.

Si scriva un programma in grado di rispondere al seguente quesito:

Quale numero troviamo nella milionesima posizione?

Dopo aver scritto il programma in grado di fornire la risposta, si rifletta sulla possibilità di ottenere lo stesso risultato con una formula chiusa.

I primi due studenti che postano il programma avranno una valutazione di 8 i secondi due di 7.
Immagine
Avatar utente
MauriAxel
Luce delle stelle
Luce delle stelle
 
Messaggi: 1605
Iscritto il: 11 giu 2005, 20:48
Località: Provincia di Como

 

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi dannyb78 il 04 apr 2008, 10:42

non ricordo il c++ ma l'algoritmo potrebbe essere questo. La complessità mi sembra valida anche se forse si potrebbe ridurla.

i_max= 1.000.000 (puoi anche chiederlo come input per vedere chi sta nella posizione i_max, così fai una cosa elegante
i=1;
num=1;
while (i<=1_max)
{ i=i+num;
num++;
}

alla fine del while num è il risultato che ti interessa. tutte le var sono interi.
CM Cosmos S | CM Pro Real Power 1000W | ASUS P6T6 WS Revolution | intel i7 965 extreme | CM V8 | Corsair DHX 1600C8 6*2GB | ASUS EAH4870X2 | Creative X-Fi Titanium Fatal1ty Champion Series | WD Velociraptor 300 +Seagate 1,5TB | ASUS Bluray BC-08B1ST | NZXT Sentry LX | Panasonic TH-D42PT84

MTB CLUB CECINA - XII GRANFONDO COSTA DEGLI ETRUSCHI - Marina di Bibbona ||| Foto edizione 2009!!!
Avatar utente
dannyb78
Luce delle stelle
Luce delle stelle
 
Messaggi: 2648
Iscritto il: 26 giu 2005, 16:33
Località: Cecina

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi tonertemplum il 04 apr 2008, 13:48

dannyb78 ha scritto:non ricordo il c++ ma l'algoritmo potrebbe essere questo. La complessità mi sembra valida anche se forse si potrebbe ridurla.

i_max= 1.000.000 (puoi anche chiederlo come input per vedere chi sta nella posizione i_max, così fai una cosa elegante
i=1;
num=1;
while (i<=1_max)
{ i=i+num;
num++;
}

alla fine del while num è il risultato che ti interessa. tutte le var sono interi.


Farei anche io allo stesso modo, cambiando una sola istruzione...

Codice: Seleziona tutto
i_max= 1.000.000
i=1;
num=1;
while (i!=1_max) //cambierei questa istruzione
{ i=i+num;
num++;
}


Cioè direi "Finchè il contatore NON è UGUALE (
Codice: Seleziona tutto
!=
) a 1.000.000 (o al numero dato in input)
ASUS M3N78-PRO -- AMD ATHLON 64 X2 5200+@3100 vcore default -- ZALMAN CNPS9500A LED -- 2x2GB TEAM GROUP DDR2 800 -- ATI HD 3650 con ZALMAN VF900 CU-LED -- 2 X SEAGATE 160GB RAID 0 + 1 x MAXTOR 260 GB SATA + 1 x MAXTOR 120 GB SATA
Avatar utente
tonertemplum
Moderatore
Moderatore
 
Messaggi: 6906
Iscritto il: 11 set 2005, 19:11
Località: Roma

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi `knives` il 04 apr 2008, 16:43

non conosco il c++.. ma in c lo farei cosi:

Codice: Seleziona tutto
#include <stdio.h>

unsigned int main ()
{
     int num1=1000, num2=0, num3=1,i,j=1;
 
         do
              {
                  for ( i = 1; i <= j ; i++ )
                     {
                          if (num3<=num1)
                          {
                                     num2=j;
                          num3++;
                          }
         
                      }
                      j++;
               } while(j<=num1);

printf("%d",num2);
}


quello a cui devi stare attento secondo me.. è proprio come dichiari le variabili perchè (almeno in c) int va da -32700 a 32700, quindi 1000000 è fuori dal range.
vogliadidolci.wordpress.com
Avatar utente
`knives`
Moderatore
Moderatore
 
Messaggi: 6246
Iscritto il: 24 mar 2005, 01:57

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi dannyb78 il 04 apr 2008, 17:11

così ha complessità maggiore dell'altro, e mi sembra anche meno leggibile (così a colpo d'occhio)

almeno però è scritto in c++ (o qualcosa che ci somiglia molto). Io non lo uso da almeno 8 anni e lo ho [quasi] completamente dimenticato. MAURIIIIII
CM Cosmos S | CM Pro Real Power 1000W | ASUS P6T6 WS Revolution | intel i7 965 extreme | CM V8 | Corsair DHX 1600C8 6*2GB | ASUS EAH4870X2 | Creative X-Fi Titanium Fatal1ty Champion Series | WD Velociraptor 300 +Seagate 1,5TB | ASUS Bluray BC-08B1ST | NZXT Sentry LX | Panasonic TH-D42PT84

MTB CLUB CECINA - XII GRANFONDO COSTA DEGLI ETRUSCHI - Marina di Bibbona ||| Foto edizione 2009!!!
Avatar utente
dannyb78
Luce delle stelle
Luce delle stelle
 
Messaggi: 2648
Iscritto il: 26 giu 2005, 16:33
Località: Cecina

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi `knives` il 04 apr 2008, 17:26

è meno leggibile xke l ho scritto velocemente... senza badare troppo ad indentare o altro..

per la complessita.. non ho provato il vostro.. cmq il mio risolve la richiesta
vogliadidolci.wordpress.com
Avatar utente
`knives`
Moderatore
Moderatore
 
Messaggi: 6246
Iscritto il: 24 mar 2005, 01:57

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi `knives` il 04 apr 2008, 17:41

l'oputput dei due è diverso.. il mio si ferma alla posizione voluta, il vostro la salta.. diciamo che basterebbe aggiungere al vostro un controllo sulla posizione giusta e fermarlo li oppure salvare la variabile della posizione.
vogliadidolci.wordpress.com
Avatar utente
`knives`
Moderatore
Moderatore
 
Messaggi: 6246
Iscritto il: 24 mar 2005, 01:57

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi Joistick il 04 apr 2008, 18:23

non capisco una cosa.... qual'è il valore assegnato alla variabile i nel tuo programma knives???
    Genova non ha scordato perché è difficile dimenticare,
    c'è traffico, mare e accento danzante e vicoli da camminare.
    La Lanterna impassibile guarda da secoli gli scogli e l'onda.
    Ritorna come sempre, quasi normale, piazza Alimonda
Avatar utente
Joistick
Luce delle stelle
Luce delle stelle
 
Messaggi: 1598
Iscritto il: 12 feb 2007, 17:45
Località: Canzo (Como)

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi diegofio il 04 apr 2008, 18:40

i va da 1 a j l'assegnamento si fa all'interno del for
diegofio
AmdPlanet Guru
AmdPlanet Guru
 
Messaggi: 9270
Iscritto il: 29 lug 2005, 09:55

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi dannyb78 il 04 apr 2008, 18:54

`knives` ha scritto:l'oputput dei due è diverso.. il mio si ferma alla posizione voluta, il vostro la salta.. diciamo che basterebbe aggiungere al vostro un controllo sulla posizione giusta e fermarlo li oppure salvare la variabile della posizione.


il mio si ferma alla posizione voluta uscendo dal while, basta aggiungere l'output della variabile num che è il valore cercato. O forse sono totalmente arrugginito, il che è possibile.
CM Cosmos S | CM Pro Real Power 1000W | ASUS P6T6 WS Revolution | intel i7 965 extreme | CM V8 | Corsair DHX 1600C8 6*2GB | ASUS EAH4870X2 | Creative X-Fi Titanium Fatal1ty Champion Series | WD Velociraptor 300 +Seagate 1,5TB | ASUS Bluray BC-08B1ST | NZXT Sentry LX | Panasonic TH-D42PT84

MTB CLUB CECINA - XII GRANFONDO COSTA DEGLI ETRUSCHI - Marina di Bibbona ||| Foto edizione 2009!!!
Avatar utente
dannyb78
Luce delle stelle
Luce delle stelle
 
Messaggi: 2648
Iscritto il: 26 giu 2005, 16:33
Località: Cecina

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi Joistick il 04 apr 2008, 18:55

diego.fiozzi ha scritto:i va da 1 a j l'assegnamento si fa all'interno del for

capito grazie diego :wink: :wink:

sistemando un po tutto alla fine vieni così
Codice: Seleziona tutto
#include <iostream>


using namespace std;

int main ()
{
   int num1,num2,num3,i,j;
   num1=1000;
   num2=0;
   num3=1;
   j=1;

         do
       {
          for(i=1;i<=j;i++)
                     {
                      if (num3<=num1)
                          {
                          num2=j;
                          num3++;
                          }
         
                      }
                      j++;
               } while(j<=num1);

       cout<<"Il numero in milionesima posizione e':"<<num2<<endl;
      system("PAUSE");
      return 0;
}
    Genova non ha scordato perché è difficile dimenticare,
    c'è traffico, mare e accento danzante e vicoli da camminare.
    La Lanterna impassibile guarda da secoli gli scogli e l'onda.
    Ritorna come sempre, quasi normale, piazza Alimonda
Avatar utente
Joistick
Luce delle stelle
Luce delle stelle
 
Messaggi: 1598
Iscritto il: 12 feb 2007, 17:45
Località: Canzo (Como)

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi `knives` il 04 apr 2008, 19:14

dannyb78 ha scritto:
`knives` ha scritto:l'oputput dei due è diverso.. il mio si ferma alla posizione voluta, il vostro la salta.. diciamo che basterebbe aggiungere al vostro un controllo sulla posizione giusta e fermarlo li oppure salvare la variabile della posizione.


il mio si ferma alla posizione voluta uscendo dal while, basta aggiungere l'output della variabile num che è il valore cercato. O forse sono totalmente arrugginito, il che è possibile.



l ho provato, e dato che somma le varie posizioni non avrai la milionesima.


@joistick : num1 = 1000 del mio è in realta 1000000. non va bene un int.. ma deve essere un long int o un unsigned int, per il discorso che dicevo prima

se il tuo è scritto in c++ ora provo a sistemarlo..
vogliadidolci.wordpress.com
Avatar utente
`knives`
Moderatore
Moderatore
 
Messaggi: 6246
Iscritto il: 24 mar 2005, 01:57

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi Joistick il 04 apr 2008, 19:46

`knives` ha scritto:

@joistick : num1 = 1000 del mio è in realta 1000000. non va bene un int.. ma deve essere un long int o un unsigned int, per il discorso che dicevo prima

se il tuo è scritto in c++ ora provo a sistemarlo..

si ho visto... comunque il mio è scritto in C++ e compila solo che va fino al 1000...
se compilo con un long int non finisce più( e da 5 minuti in esecuzione), adesso provo con unsigned ma non penso cambi e penso sia colpa del milione...
    Genova non ha scordato perché è difficile dimenticare,
    c'è traffico, mare e accento danzante e vicoli da camminare.
    La Lanterna impassibile guarda da secoli gli scogli e l'onda.
    Ritorna come sempre, quasi normale, piazza Alimonda
Avatar utente
Joistick
Luce delle stelle
Luce delle stelle
 
Messaggi: 1598
Iscritto il: 12 feb 2007, 17:45
Località: Canzo (Como)

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi dannyb78 il 04 apr 2008, 20:06

non ricordo la sintassi, per cui il mio non è scritto in c++, anche se conoscendo la sintassi da lì si dovrebbe arrivare velocemente al codice.

il mio programma somma il numero alla posizione e scorre il numero. Chiaramente però fa il controllo sulla posizione. Si ferma quando supera la posizione i_max e restituisce l'intero con il quale ha superato i_max (che deve essere uguale a quello in posizione i_max)
CM Cosmos S | CM Pro Real Power 1000W | ASUS P6T6 WS Revolution | intel i7 965 extreme | CM V8 | Corsair DHX 1600C8 6*2GB | ASUS EAH4870X2 | Creative X-Fi Titanium Fatal1ty Champion Series | WD Velociraptor 300 +Seagate 1,5TB | ASUS Bluray BC-08B1ST | NZXT Sentry LX | Panasonic TH-D42PT84

MTB CLUB CECINA - XII GRANFONDO COSTA DEGLI ETRUSCHI - Marina di Bibbona ||| Foto edizione 2009!!!
Avatar utente
dannyb78
Luce delle stelle
Luce delle stelle
 
Messaggi: 2648
Iscritto il: 26 giu 2005, 16:33
Località: Cecina

Re: Quale numero troviamo nella milionesima posizione?

Messaggiodi MauriAxel il 04 apr 2008, 20:49

ecco ci ho provato anche io a farlo:

Codice: Seleziona tutto
#include <iostream>
using namespace std;

int main ()

{
int cont=0;
int num=0;
do
{
   num=num+1;
   cont=cont+num;
}while(cont<=1000000);

cout<< "L'elemento in milionesima posizione e' il numero "<<num;
cout<<endl;

system("pause");
return 0;
}
Ultima modifica di MauriAxel su 04 apr 2008, 20:54, modificato 1 volte in totale.
Immagine
Avatar utente
MauriAxel
Luce delle stelle
Luce delle stelle
 
Messaggi: 1605
Iscritto il: 11 giu 2005, 20:48
Località: Provincia di Como

 
Prossimo

Torna a Programmare

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron