Inaugurazione con tartarughe...

Programmazione, algoritmica, teoria dell'informazione, ...
MindFlyer

Messaggio da MindFlyer » 11 mar 2005, 00:26

Sì!

Pyv
Messaggi: 11
Iscritto il: 01 gen 1970, 01:00
Località: Latina

Messaggio da Pyv » 12 mar 2005, 00:30

Vi ricordo comunque che c'e' il forum delle Olimpiadi Italiane di Informatica appena nato su cui potete postare i vostri dubbi e vedere nuovi problemi:

http://81.208.32.83:8889/ioi-site/pn/ht ... file=index

Tra l'altro la' io sono il moderatore :) Sciocchezze a parte, visto che quel forum verra' utilizzato dai Probabili Olimpici informatici, e' possibile confrontarsi con quelli che saranno gli olimpionici del 2005.

Almeno fateci una visitina, in cambio di questo codice :) Non garantisco che sia giusto, ma dovrebbe... Se e' toppato non fatene uno scandalo, capita a tutti di sbagliare!

Codice: Seleziona tutto

#include	<iostream>
#include	<algorithm>

using namespace std;

#define	MAXTARTA	6000

int		T;
int		peso[MAXTARTA], forza[MAXTARTA];
int		pesomin[2][MAXTARTA+1];

int		L;

void leggi()
{
	int		p, f;

	while (cin >> p >> f)
	{
		peso[T] = p;
		forza[T] = f;
		T++;
	}
}

void risolvi()
{
	int		t, l, p;

	fill(*pesomin, *pesomin+2*(MAXTARTA+1), -1);
	pesomin[0][0] = 0;

	for (t=T-1; t>=0; t--)
	{
		for (l=0; l<=T-t; l++)
		{
			if (pesomin[0][l] == -1)	continue;
			p = pesomin[0][l] + peso[t];

			if (forza[t] >= p)
				if ((pesomin[1][l+1] == -1) || (p < pesomin[1][l+1]))		pesomin[1][l+1] = p;
		}

		copy( pesomin[1], pesomin[1]+MAXTARTA+1, pesomin[0]);
	}

	L = T;
	while (pesomin[0][L] == -1)	L--;
}

inline void scrivi()
{
	cout << L << endl;
}

int main()
{
	leggi();
	risolvi();
	scrivi();

	return 0;
}

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 12 mar 2005, 14:28

Pyv ha scritto:Ciao e scusate l'intromissione, il forum matematica non e' posto che mi spetterebbe
Pyv ha scritto:Almeno fateci una visitina, in cambio di questo codice :) Non garantisco che sia giusto, ma dovrebbe... Se e' toppato non fatene uno scandalo, capita a tutti di sbagliare!
Ciao Pyv. Anche da parte mia, benvenuto. Non ti preoccupare, siamo abituati a vedere sbagli di ogni tipo e non ci scandalizziamo facilmente...

E non ti fare scrupolo a tornare: come vedi, non è affatto vero, che questo Forum non "ti spetterebbe". E perché mai?

Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

manub
Messaggi: 9
Iscritto il: 01 gen 1970, 01:00
Località: Napoli
Contatta:

Messaggio da manub » 13 mar 2005, 12:33

l'unico "consiglio" che mi sento di proporre è quello di scrivere algoritmi in pseudo-codice, restando lontani dalle differenze implementative dei vari linguaggi di programmazione. cosa ne dite?

MindFlyer

Messaggio da MindFlyer » 13 mar 2005, 18:54

Dipende dal contesto.
Forse in questo caso era meglio lo pseudo-codice.

Avatar utente
bh3u4m
Messaggi: 547
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da bh3u4m » 13 mar 2005, 19:15

Nel codice manca l'inizializzazione di T se non sbaglio... meglio metterla che alcuni compilatori non inizializzano da soli le variabili.

Avatar utente
bh3u4m
Messaggi: 547
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da bh3u4m » 13 mar 2005, 19:33

Bene, ho verificato il programma... è l'algoritmo che avevo in mente all'inizio.
E' difficile capire se sia giusto, però sembra esserlo, ho provato a fare una verifica manuale con 4 tartarughe e non sembrava avere problemi.

Credo che si possa evitare di usare due vettori per il pesomin servendosi di una variabile che memorizza l'elemento del vettore che dev'essere sostituito per un successivo uso, così si evita di dover chiamare la funzione copy che rallenta l'esecuzione del programma.
Ultima modifica di bh3u4m il 13 mar 2005, 19:37, modificato 1 volta in totale.

MindFlyer

Messaggio da MindFlyer » 13 mar 2005, 19:36

Ok, ho letto il programma, e mi sembra toppato in almeno 2 punti (la T non inizializzata non è un problema, perché si considera inizializzata a 0).
Nessuno scandalo, ma pregherei Pyv di correggerlo quando passa di qua, perché non sono riuscito a capire cosa dovrebbe fare l'algoritmo.

MindFlyer

Messaggio da MindFlyer » 13 mar 2005, 19:42

bheuam, se hai capito l'algoritmo, mi fai la cortesia di provarlo su questa configurazione?

Pesi: 0, 0, 1, 2
Capacità: 1, 1, 2, 0

(ho elencato pesi e capacità dalla tartaruga più "in basso" a quella più "in alto")

MindFlyer

Messaggio da MindFlyer » 13 mar 2005, 20:14

Ah, finalmente ho capito cosa deve fare l'algoritmo!
Però la versione di Pyv va cambiata in vari punti...
In pratica, scorre le tartarughe dalla più in alto alla più in basso, tenendosi il peso minimo delle pile di ogni lunghezza, e questo funziona!!
Ottimo lavoro. :D

manub
Messaggi: 9
Iscritto il: 01 gen 1970, 01:00
Località: Napoli
Contatta:

Messaggio da manub » 13 mar 2005, 23:32

MindFlyer ha scritto:Ah, finalmente ho capito cosa deve fare l'algoritmo!
Però la versione di Pyv va cambiata in vari punti...
In pratica, scorre le tartarughe dalla più in alto alla più in basso, tenendosi il peso minimo delle pile di ogni lunghezza, e questo funziona!!
Ottimo lavoro. :D
un po' come lo zaino ;)

scusate la domanda... ma questo è un problema NP-completo? sono un po' ignorante in materia, ma dato che anche in altri post lo si paragona allo zaino (0/1, ovviamente, se fosse frazionario non sarebbe NP-completo)...

Avatar utente
bh3u4m
Messaggi: 547
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da bh3u4m » 13 mar 2005, 23:55

E' comunque un algoritmo $ O (N^2) $, se non mi sbaglio (ma due cicli for uno dentro l'altro lo dovrebbero essere). :)

manub
Messaggi: 9
Iscritto il: 01 gen 1970, 01:00
Località: Napoli
Contatta:

Messaggio da manub » 14 mar 2005, 00:01

bh3u4m ha scritto:E' comunque un algoritmo $ O (N^2) $, se non mi sbaglio (ma due cicli for uno dentro l'altro lo dovrebbero essere). :)
riguardando l'algoritmo sembra anche a me così. quindi lo zaino non c'entra nulla...

Pyv
Messaggi: 11
Iscritto il: 01 gen 1970, 01:00
Località: Latina

Messaggio da Pyv » 14 mar 2005, 00:25

Anzitutto: la mancata inizializzazione di T non e' un errore, perche' tutte le variabili globali vengono inizializzate a 0. O almeno questo e' quello che dice il C/C++ standard, se poi usate un compilatore scadente che non lo rispetta io non posso farci niente :)

Lo so comunque che il copy rallenta il programma, sarebbe stato meglio (ma meno chiaro) usare i due vettori circolarmente (cioe' usando qualcosa del tipo pesomin[t%2] e pesomin[1-(t%2)]). L'ho fatto per farvi capire meglio le cose.

Gradirei che mi diceste i punti esatti in cui pensate il programma sia sbagliato... se mi dite solo "e' sbagliato in 2 punti" non so cosa intendete.

Avatar utente
bh3u4m
Messaggi: 547
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da bh3u4m » 15 mar 2005, 15:49

La teoria dice però che si tratta di un algoritmo $ O (N \log N ) $ nella normalità, con caso peggiore $ O ( N^2 ) $, infatti non è necessario tenersi un vettore lungo quanto le tartarughe, è sufficiente incrementare il vettore quando si offre la possibilità di una pila con una tartaruga in più del solito, il secondo ciclo for (quello annidato) perciò sarà chiamato un numero molto minore di volte rispetto al primo.

Rispondi