Srednjoškolski zadaci

[marko_n]

Program koji sam napisao najpre izračunava koliko bi se robota dobilo ako se primeni raspodela iz slučaja 1, a potom isto izračuna ako se primeni raspodela iz slučaja 2. Nakon toga rezultati ta dva slučaja se upoređuju i kao tačan se uzima veći.

Nije sporno to da li kod radli ili ne radi dobro - meni je očigledno da radi dobro, nego je problem to što se algoritam svodi na "probanje". Izračunaš jedno, izračunaš drugo, pa uzmeš veće. Recimo da je potrebno naći formulu po kojoj se pronalazi optimalna raspodela bez "probanja" (to sam ja uradio) i da je pri tom tu formulu moguće matematički dokazati (ovo još nisam uradio).

 

[Speeder]

Nije sporno to da li kod radli ili ne radi dobro - meni je očigledno da radi dobro, nego je problem to što se algoritam svodi na "probanje". Izračunaš jedno, izračunaš drugo, pa uzmeš veće. Recimo da je potrebno naći formulu po kojoj se pronalazi optimalna raspodela bez "probanja" (to sam ja uradio) i da je pri tom tu formulu moguće matematički dokazati (ovo još nisam uradio).

Pa znam ja to, znam i ja po kojoj formuli treba računati, samo ne znam dokaz niti sam pokušavao da ga nađem... zato sam i napravio ovakav kod, kom ne treba ništa da se dokazuje. Mada, bilo bi interesantno naći taj dokaz.

 

[ivan90BG]

Evo finalne verzije mog predloga algoritma prevedene u Pascal. Nadam se da nema grešaka. Dakle pokrivene su sve opcije za ostatak deljenja broja robota sa 5 (0,1,2,3,4). Kada je ostatak 1, 3 ili 4 postoji jedna najproduktivnija raspodela bez obzira na vrednost broja robota, ali kada je ostatak 2 postoje dve najproduktivnije raspodele u zavisnosti da li je broj robota manji ili veći-jednak 12.

program roboti;

var
brojDana,pocetniBrojRobota,brojRobota,jedanDan,dvaDana,triDana,i,ostatak:integer;
kolicnik:float;

begin	

write('Unesite broj dana: ');
readln(brojDana);
write('Unesite pocetni broj robota: ');
readln(triDana);

jedanDan:=0;
dvaDana:=0;

for i:=1 to brojDana do
	begin
	pocetniBrojRobota = jedanDan + dvaDana + triDana;
	
	if pocetniBrojRobota < 3  then
		begin
		writeln('Nema dovoljno robota za razmnožavanje');
		break;
		end
	else
		begin
		kolicnik:= pocetniBrojRobota / 5;
		ostatak:= pocetniBrojRobota mod 5;
		if kolicnik < 1 then
			brojRobota:= pocetniBrojRobota + 5;
		else
			if ostatak = 0 then
				brojRobota:= pocetniBrojRobota + kolicnik*9;
			else
				case ostatak of
					1: brojRobota:= pocetniBrojRobota + trunc(kolicnik)*9 + 1;					
					2: if pocetniBrojRobota >= 12 then
						brojRobota:= pocetniBrojRobota + trunc(kolicnik)*9 + 2;
					   else brojRobota:= pocetniBrojRobota + trunc(kolicnik)*9 + 1;					
					3: brojRobota:= pocetniBrojRobota + trunc(kolicnik)*9 + 5;
					4: brojRobota:= pocetniBrojRobota + trunc(kolicnik)*9 + 6;
				end;
		end;
	jedanDan:= dvaDana;
	dvaDana:= triDana;
	triDana:= brojRobota - pocetniBrojRobota;
	end;

writeln('Posle ',brojDana,' dan/a broj robota je: ',brojRobota);
readln;

end.

 

[Switch]

Speeder, mislim da je tvoje rešenje najelegantnije. Samo bi umesto množenja sa 8 i sa 14, moglo da se množi sa 5 i 9 i da se onda za d0 uzima odmah vrednost novi, bez ikakvog oduzimanja.
Hvala svima koji ste učestvovali u rešavanju ovog zadatka. Videću da li u knjizi ima nešto zanimljivo, pa ću postavljati nove probleme ako ste raspoloženi za mozganje.

 

[marko_n]

@ivan90BG
Prevideo si da je uslov da bude 8+ robota na početku, dakle možeš samo da proveriš da li ih ima više od 7, a ne da proveravaš da li ih ima menje od 3.

@Speeder
Evo je adaptacija tvog koda na moj način, dakle bez petlji (osim za dana), pa ako te ne mrzi proveri da li nam programi daju iste rezultate. U tvom programu samo Integer promeni u LongInt.

Program Roboti;
Var R, d, d0, d1, d2, d3, i, brrob, x, y, novi: LongInt;
pattern: array[0..4] of Integer = (1, 3, 0, 2, 4);


Begin
     Write('Unesi broj robota: ');
     Readln(R);
     Write('Unesi broj dana: ');
     Readln(d);
     d0:=R;	{roboti stari 0 dana}
     d1:=0;	{roboti stari 1 dan}
     d2:=0;	{roboti stari 2 dana}
     d3:=0;
     For i:=1 to d do	{petlja koja broji dane}
     Begin
          brrob:=d0+d1+d2;	{ukupan broj robota koji pocinju proizvodnju tog dana}
          y:=pattern[(brrob-8) mod 5];
          x:=(brrob-y*3) div 5;
          novi:=x*14+y*8;
	  d3:=d2;
          d2:=d1;		{sada se roboti "stare" za jedan dan, a oni stari 3 dana se automatski odbacuju}
          d1:=d0;
          d0:=novi-brrob;	{ovo su potpuno novi roboti}
     End;
     Writeln('Konacni broj robota je: ',d0+d1+d2+d3);
     Readln;
End.

Što se tiče matematičkog dokaza, radim na tome. :type:

 

[Bahati [SiD]]

ma pusti nove zadatke, javi nam semplove da vidimo sta je od mozganja valjalo! :d

ps. i nesto mi sad deluje glupo da racunamo "mrtvake"... sve zavisi od toga kad semplujemo... tako da pre uzmi onu prethodnu speederovu verziju.

pps. i jos uvek imam feeling da je brute force ono sto se trazi jer jedino tako se sve koristi kako treba, a ne da se podmesta for umesto while, if banane i sl. al mozda te i pohvale zato sto si nasao efikasnije a jednako tacno resenje. :d

 

[Speeder]

Hvala Switch. Evo ovo bi trebalo da je finalna verzija, pošto sam uspeo da matematički dokažem da je najbolja raspodela ta da imamo što više grupa po pet robota, ali uz uslov da su svi roboti uposleni, izbacio sam poređenje raspodela iz koda:

Program Roboti;
Var R, d, d0, d1, d2, d3, i, j, brrob, ost, x, y, z, x1, y1, novi: Integer;
Begin
     Write('Unesi broj robota: ');
     Readln(R);
     Write('Unesi broj dana: ');
     Readln(d);
     d0:=R;
     d1:=0;
     d2:=0;
     d3:=0;
     For i:=1 to d do
     Begin
          brrob:=d0+d1+d2;
          x:=brrob div 5;
          ost:=brrob mod 5;
          y:=ost div 3;
          z:=ost mod 3;
          novi:=x*14+y*8+z;
          For j:=1 to 2 do
          Begin
               If ((z=j) and (x>=j)) then
               Begin
                    x1:=x-j;
                    y1:=y+2*j;
		    novi:=x1*14+y1*8;
               End;
          End;
	  d3:=d2;
          d2:=d1;
          d1:=d0;
          d0:=novi-brrob;
     End;
     Writeln('Konacni broj robota je: ',d0+d1+d2+d3);
     Readln;
End.

Možeš da množiš sa 5 i 9, ali opet ćeš negde morati da izračunaš ukupan broj robota, znači izbeći ćeš ono oduzimanje, ali ćeš negde morati da sabiraš, pa ti je svejedno...

 

[marko_n]

pošto sam uspeo da matematički dokažem da je najbolja raspodela ta da imamo što više grupa po pet robota, ali uz uslov da su svi roboti uposleni

:rtfm:

 

[ivan90BG]

Ko je rekao da je uslov 8+?

 

[marko_n]

Ko je rekao da je uslov 8+?

Ok, ljudi hvala vam na odgovorima. Ovako, problem je podeliti te robote na grupe tako da one potom daju maksimalan broj novih robota. Uzima se broj obavezno veći od 7.

Switch je rekao.

 

[Speeder]

@marko_n
Evo, nije me mrzelo...
Dokaz
:rtfm:

 

[marko_n]

@marko_n
Evo, nije me mrzelo...
Dokaz
:rtfm:

Atačment ne postoji. Ukoliko ste kliknuli na inače ispravan link, kontaktirajte administratora.

:whip:

 

[Speeder]

Da probam opet...

Edit:
Evo i link ka sendpace-u... za svaki slučaj
http://www.sendspace.com/file/m0zy15

 

[WebWolf]

Super . Porazgovarao sam sa nekim ko zna matematiku mnogo bolje od mene (u principu mnogo dobro zna ), i cinjenica da je ovakav greedy algoritam ok. Ali treba uzeti u obzir algoritam koji bi mozda danas zrtvovao nekog robota, da ne radi, ali da bi kroz dan, dva ili tri dobio takav broj da bi ih tako rasporedio da nadoknadi taj gubitak i napravi jos vise robota . Cisto treba uzeti u obzir da mozda postoji tako nesto. E sad... u pitanju je zadatak za srednju skolu. Cisto sumnjam da bu uzeli tako napredne i komplikovane algoritme u obzir...

 

[Speeder]

Mislim da to baš i nema smisla, poenta je danas napraviti što više robota, jer što ih više imaš danas, sutra ćeš imati više radne snage. A posebno zato što roboti žive samo tri dana.

 

[ivan90BG]

To žrtvovanje jednog danas nema smisla jer je jedini slučaj kada se mora žrtvovati jedan robot u raspodeli najveće produktivnosti slučaj kada ima 7 robota, a uslova je da ih ima više od sedam. Za bilo koji drugi broj najveća produktivnost će biti kada se raspodele svi u što više grupa po 5, a što manje po 3. Tako da se moj algoritam svodi na proveru da li je broj robota veći od 7 i 5 slučajeva za 5 ostataka deljenja sa 5.

if pocetniBrojRobota < 8  then
		begin
		writeln('Nema dovoljno robota za razmnožavanje');
		break;
		end
	else
		begin
		kolicnik:= pocetniBrojRobota / 5;
		ostatak:= pocetniBrojRobota mod 5;
		case ostatak of
			0: brojRobota:= pocetniBrojRobota + kolicnik*9;
			1: brojRobota:= pocetniBrojRobota + trunc(kolicnik)*9 + 1;
			2: brojRobota:= pocetniBrojRobota + trunc(kolicnik)*9 + 2;
			3: brojRobota:= pocetniBrojRobota + trunc(kolicnik)*9 + 5;
			4: brojRobota:= pocetniBrojRobota + trunc(kolicnik)*9 + 6;
		end;
	end;

 

[WebWolf]

Rekao sam da moze da postoji mogucnost, ne i da postoji . Tj. u ovom slucaju se moze desiti i da nema, ali da je u pitanju neka drugacija raspodela ili da roboti zive duze ili da postoji jos neka grupa robota moglo bi se desiti. Samo hocu da kazem da se ne treba uvek slepo hvatati za ovakav algoritam. Medjutim za izdradu ovog drugog, dinamickog, treba mnogo iskustva...

 

[Switch]

E ja sad imam problem oko izvršavanja koda, odnosno imam Windows 7 i kad otvorim turbo pascal radna površina je veoma mala, praktično se ni ne vidi, a kada otvorim delphi prijavljuje mi grešku da ne može da dodeli neku ekstenziju, a freepascal ne može ni da se pokrene.

Edit: Speeder, svaka čast na strpljenju.

 

[alfaunits]

U Delphi-u sacuvaj kod kao .dpr i samo tako ga pokreni.
Dodaj:
{$APPTYPE CONSOLE}
posle Program ImeProga;

 

[Switch]

Problem je što ni ne mogu da otvorim prostor za kucanje koda, u Delphiju ne mogu da otvorim konzolnu aplikaciju, prijavljuje mi neku grešku.

 

[ivan90BG]

^WebWolf

Pa normalno da je ovakav algoritam veoma ograničen na ovaj jedan slučaj, ali samo to se tražilo u zadatku. Za promenljive veličine grupe je potreban složeniji i prolagodljiviji. (za promenljiv broj tipova grupa bi možda moralo da se ide na objektno orijentosano programiranje)

 

[Speeder]

Evo i grafika razlike 10@10 - 9@10

Vidi se koliko smanjenje stvori odsustvo samo jednog robota. Pretpostavljam da bi i za većinu drugačijih raspodela važilo isto, tako da je cilj da danas napravimo što više robota.

Video sam još mesta za poboljšanje mog koda (samo su izbačene promenljive x1 i x2, koje su bile nepotrebne, posle onog dokaza).

I ipak sam se vratio na ono prethodno da na kraju poslednjeg dana ne računam robote koji su odradili svoja 3 dana... logičnije mi je da ''crknu'' čim završe proizvodnju.

Program Roboti;
Var R, d, d0, d1, d2, d3, i, j, brrob, ost, x, y, z, novi: LongInt;
Begin
     Write('Unesi broj robota: ');
     Readln(R);
     Write('Unesi broj dana: ');
     Readln(d);
     d0:=R;
     d1:=0;
     d2:=0;
     For i:=1 to d do
     Begin
          brrob:=d0+d1+d2;
          x:=brrob div 5;
          ost:=brrob mod 5;
          y:=ost div 3;
          z:=ost mod 3;
          novi:=x*14+y*8+z;
          For j:=1 to 2 do
          Begin
               If ((z=j) and (x>=j)) then
               Begin
                    x:=x-j;
                    y:=y+2*j;
		    novi:=x*14+y*8;
               End;
          End;
          d2:=d1;
          d1:=d0;
          d0:=novi-brrob;
     End;
     Writeln('Konacni broj robota je: ',d0+d1+d2);
     Readln;
End.

Edit:

Ja sam sa neta skinuo Turbo Pascal 7.0 (samo da bih uradio ovaj zadatak ). Ako ga skineš i ti, u folderu BIN pokreni TPX.EXE i trebalo bi da ti otvori fullscreen, meni jeste (isto Win7).

 

[Switch]

Uspeo sam da otvorim preko Delphija ali je problem što je dos prozor koji otvori veoma mali.

 

[Speeder]

Iz ovog poslednjeg koda koji sam dao, iz var izbaci d3, jer se ne koristi.

 

[alfaunits]

Uspeo sam da otvorim preko Delphija ali je problem što je dos prozor koji otvori veoma mali.

A to je vec drugo...
Ako ti je ogromna rezolucija neces bash puno moci. J***ni W7 i Vista ne dozvoljavaju vishe full-screen text mode.

Kad uradis prvi Readln, klikni na prozorov menu (iz aplikacije) i na Properties postavi fontove na max. Ako ti i to ne pomaze, smanji rezoluciju.

 

[Bahati [SiD]]

evo i ultra brzog algoritma koji svasta podrazumeva (vidi ispod):

int daythree = 0;
int daytwo = 0;
int dayone = int::Parse(textBox1->Text);
int numofdays = int::Parse(textBox2->Text);
int current,fives,threes;
for(int i=0; i<numofdays; i++) {
	current = dayone+daytwo+daythree; //svi roboti
	[COLOR="Red"]threes = ((current%5)*2)%5; //prvo se grupisu po tri
	fives = (current-3*threes)/5; //ostatak se grupise po pet[/COLOR]
	//starenje
	daythree = daytwo;
	daytwo = dayone;
	dayone = 9*fives + 5*threes; //novi roboti
}
textBox3->Text = (dayone+daytwo+daythree).ToString();

podrazumevano:
1) za svako n koje pripada N0 postoji funkcija n = 5a+3b-8; takva da a i b pripadaju N0
2) optimalna raspodela je takva da ne postoje negrupisani roboti
3) na isteku n-tog dana postoje samo roboti kojima je n-ti dan bio prvi ili drugi dan zivota i roboti proizvedeni n-tog dana, tj. roboti kojima je n-ti dan bio treci su nestali jer je n-ti dan prosao.
4) niko ne trazi matematicki dokaz za 1) i 2) :d

u sustini se nalazi odnos izmedju ostatka deljenja sa 5 i broja grupa od tri, kao sto je neko vec uradio uz pomoc nizova.
ostaci: 0,1,2,3,4 znace 0,2,4,1,3 grupa po tri, tim redom.

moj konacni odgovor: 11@11 = 648629; 8@4 = 434 :d

evo i modifikovanog Speeder-ovog koda:

Program Roboti;
Var R, d, d0, d1, d2, brrob, x, y, i : LongInt;
Begin
     Write('Unesi broj robota: ');
     Readln(R);
     Write('Unesi broj dana: ');
     Readln(d);
     d0:=R;
     d1:=0;
     d2:=0;
     For i:=1 to d do
     Begin
          brrob:=d0+d1+d2;
          y:= ((brrob mod 5) * 2) mod 5;
          x:= (brrob - 3 * y) div 5;
          d2:=d1;
          d1:=d0;
          d0:=9*x + 5*y;
     End;
     Writeln('Konacni broj robota je: ',d0+d1+d2);
     Readln;
End.

samo treba videti oko tipova, da ne bude overflowa, nemam pojma pascal...

 

[Speeder]

samo treba videti oko tipova, da ne bude overflowa, nemam pojma pascal...

Tip je LongInt (što si zaboravio da dodaš), i promenljiva i ti nije definisana.

Var R, d, d0, d1, d2, brrob, x, y, i : LongInt;

U suštini, upropastio si moj kod tako što si ga popravio :d

 

[Bahati [SiD]]

e jes, to su bas krupne greske. :d

elem, poenta je da sada ima formulu po kojoj racuna raspodelu, nikakvi for-ovi, while-ovi, if-ovi i nizovi...

 

[Speeder]

Samo mi objasni kako si došao do ove formule: y:= ((brrob mod 5) * 2) mod 5 ?
Mislim, ok je ona, očigledno, nego kako si odnos između ostatka i broj grupa po 3 uspeo da pretočiš u ovu formulu? Ima li neka logika, koju ja ne vidim, ili ti se prosto javilo

Edit:

Skroz mi je interesantno ovo kako je ''timski rad'' i unapređivanje predstavljenih rešenja dovelo do toga da od koda koji se izvršava 10ak sekundi, dođemo do ultra-jednostavnog i efikasnog koda.

 

[Switch]

Ja sam oduševljen odzivom i tolikom zalaganju da se dođe jednostavnog i efikasnog koda, zaista za svaku pohvalu. Kada sam postavljao temu očekivao sam komentare tipa 'Aj mali malo se potrudi, ne možeš dobiti sve na gotovo' , a zaista je lepo što postoje ljudi koji toliko truda i vremena potroše da pomognu u rešavanja jednog ovakvog zadatka. Zato sam i pre nekoliko postova napisao da ću postavljati slične zadatke ako ste zaintresovani, a to mi je i bila početna ideja i zato je naslov thread-a takav.
Da, i mene intresuje kako se došlo do te formule.