[es] - [Zadatak] - jednostavan?!

peromalosutra
Ivan Rajkovic
PHP/MySQL programmer, Ogosense
Banjaluka

Član broj: 54774
Poruke: 432
*.dialup.blic.net.

Jabber: peromalosutra@elitesecurity.org
Sajt: computer-stuff.freehostia..

Profil

[Zadatak] - jednostavan?!

^{13.08.2005. u 21:34}

Procitao sam da je na nekom takmicenju bio sledeci zadatak (papir sam izgubio, a zadatka se ne sjecam tačno..): Iz datoteke se ucitava binarni broj duzine do 8 mjesta. Naci najvecu seriju jedninica u zapisu tog broja, te ispisati njenu duzinu i lokaciju. Na primjer,

ULAZ: 10011101
IZLAZ: 3 4

Ja sam to mislio rijesiti "na silu", dakle gledati da li iza prve jednice u zapisu ima jos jedinica, pa ako ima brojiti koliko, a ako nema preci na sledecu jedinicu, itd. Na kraju se uzima najveca grupa jedinica i u datoteku upisuju podaci vezani za nju.
Postoji li neko elegantnije rjesenje?

Hvala!

ivan@ivan-desktop:~$ ./encrypt.run
*** stack smashing detected ***: ./encrypt.run terminated
Aborted (core dumped)

^{13.08.2005. u 21:34}

Re: [Zadatak] - jednostavan?!

^{14.08.2005. u 00:01}

Sad sam se sjetio jos jednog: pretvorimo ulaznu vrijednost u string, a zatim prvo pretrazujemo da li u tom stringu postoji pod-string od dve jedinice. Zatim trazimo podstirng od 3,4 pa sve do krajnje mogucnosti, tj 8 jedinica. Sve rezultate upisujemo u niz. Kada predjemo svih 8 mogucnosti, u nizu pogledamo koji je najveci skup jedinica, a zatim pomocu procedure pos(pod_niz,niz) odredimo njegovu lokaciju.
Ovo mi se cini kao ljepse rjesenje, ali cuo sam da nekom liku na takmicenju nisu priznali zadatak slican ovome jer je takodje koristio varijablu tipa string za zapis bin. broja (iako nigdje nisu naglasili kojeg tipa mora da bude varijabla).

_{[Ovu poruku je menjao peromalosutra dana 14.08.2005. u 01:02 GMT+1]}

ivan@ivan-desktop:~$ ./encrypt.run
*** stack smashing detected ***: ./encrypt.run terminated
Aborted (core dumped)

^{14.08.2005. u 00:01}

D3adly

Član broj: 43272
Poruke: 35
*.cmu.carnet.hr.

ICQ: 281458481

Profil

Re: [Zadatak] - jednostavan?!

^{14.08.2005. u 09:49}

Napraviš si array int-a. Zatim prolaziš po binarnom broju i u svako polje array-a zapisuješ koliko je jedinica zaredom ispred njega.
Npr. za tvoj slučaj bi taj array izgledao : 1 0 0 1 2 3 0 1

Onda istovremeno traziš maximum, a pozicija je pozicija na kojoj se maximum nalazi minus maximum. ;-) rjesenje je malo cudno , ali je brže.

#include <D3adly.h>

^{14.08.2005. u 09:49}

Re: [Zadatak] - jednostavan?!

^{14.08.2005. u 10:41}

Uradio sam zadatak na ovaj način i radi za sve test-primjere:

Code:

program max_jedinica;
uses wincrt;
var broj,skup:string;
    i,temp_lok,max,lokacija:integer;

function pretvori (n:integer):string;
var i:integer;
    s:string;
begin
s:='';
for i:=1 to n do
    s:=s+'1';
pretvori:=s;
end;

begin
readln (broj);
max:=0;
for i:=1 to length(broj) do
    begin
    skup:=pretvori(i);
    temp_lok:=pos(skup,broj);
    if (temp_lok>0) and (i>max)
       then max:=i;
    end;
lokacija:=pos(pretvori (max),broj);
writeln (lokacija,max:3);
end.

Uradio sam da čita podatke sa tastature, a ne sa diska zbog jednostavnosti, to nije problem. Jedino što tad moram korisiti biblioteku WinCrt (čitaj CRT) koja je valjda zabranjena na takmičenjima, ali to neće biti problem pri učitavanju i snimanju na disk.

Da li je ovo korektno rjesenje?

_{[Ovu poruku je menjao peromalosutra dana 14.08.2005. u 11:42 GMT+1]}

ivan@ivan-desktop:~$ ./encrypt.run
*** stack smashing detected ***: ./encrypt.run terminated
Aborted (core dumped)

^{14.08.2005. u 10:41}

Toyo

Član broj: 45193
Poruke: 227
*.kovnet.co.yu.

Profil

Re: [Zadatak] - jednostavan?!

^{14.08.2005. u 11:59}

Ne verujem da na takmicenju traze da radis sa pos funkcijom, ali ako je tako...

Code:

var
   i, poz: integer;
   s:string;
begin
     readln(s);
     i := 9;
     repeat
           dec(i);
           poz:=pos(copy('11111111',1,i),s);
     until (i=1) or (poz>0);
     writeln(i:3, poz:3);
end.

i malo bezobraznije bez copy i varijable i....

Code:

var
   s, j:string;
   poz: integer;
begin
     j := '11111111';
     readln(s);
     repeat
          poz:=pos(j,s);
          dec(j[0]);
     until (j[0]=#0) or (poz>0);
     writeln(byte(j[0])+1:3, poz:3);
end.

Mislim da se trazi da sa jednim prelaskom kroz string pronadjes maksimum i poziciju u stringu, a ovo sto sam napisao nije to.

_{[Ovu poruku je menjao Toyo dana 14.08.2005. u 13:19 GMT+1]}

^{14.08.2005. u 11:59}

Re: [Zadatak] - jednostavan?!

^{14.08.2005. u 13:57}

Pa kao sto sam rekao:

Citat:

Ovo mi se cini kao ljepse rjesenje, ali cuo sam da nekom liku na takmicenju nisu priznali zadatak slican ovome jer je takodje koristio varijablu tipa string za zapis bin. broja (iako nigdje nisu naglasili kojeg tipa mora da bude varijabla).

Ali u pravilniku nigdje nisu naglasili na koji način se zadatak radi, samo su rekli da se ne smiju koristiti nikakve dodatne biblioteke, a pos,str, i ostale funkcije/procedure za rad sa stringovima rade bez uključivanja bilo kojih dodatnih bibl. Pošto se broj učitava iz tekstualne datoteke, valjda se može koristiti tip varijable koji učesniku najviše odgovara, jer rekli su da se učitava binarni broj, a ne i u koji tio varijable treba on da se sačuva.

Mislim, glupo je da ti govore - to smiješ, a to ne. U čemu je onda svrha učenja tih naredbi ako ih ne smiješ koristiti.. Po meni bi trebalo da ti daju problem i puste te da ga rješavaš kako hoćeš.

_{[Ovu poruku je menjao peromalosutra dana 14.08.2005. u 15:00 GMT+1]}

ivan@ivan-desktop:~$ ./encrypt.run
*** stack smashing detected ***: ./encrypt.run terminated
Aborted (core dumped)

^{14.08.2005. u 13:57}

Shadowed
.NET developer

SuperModerator
Član broj: 649
Poruke: 9030
*.etf.bg.ac.yu.

Sajt: www.diskusije.net

Profil

Re: [Zadatak] - jednostavan?!

^{14.08.2005. u 21:34}

Citat:

peromalosutra: Sad sam se sjetio jos jednog: pretvorimo ulaznu vrijednost u string, a zatim prvo pretrazujemo da li u tom stringu postoji pod-string od dve jedinice. Zatim trazimo podstirng od 3,4 pa sve do krajnje mogucnosti, tj 8 jedinica. Sve rezultate upisujemo u niz. Kada predjemo svih 8 mogucnosti, u nizu pogledamo koji je najveci skup jedinica, a zatim pomocu procedure pos(pod_niz,niz) odredimo njegovu lokaciju.

Cisto komentar na ovaj algoritam.
Bolje bi bilo proveravati unazad tj. prvo da li ima 8 jedinica, pa 7, 6... Tako ne moras da proveravas sve duzine vec cim naidjes na onu koju trazis to je - to.

^{14.08.2005. u 21:34}

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.pat-pool.nsad.sbb.co.yu.

Profil

Re: [Zadatak] - jednostavan?!

^{14.08.2005. u 22:12}

Ovo sto kaze Shadowed je tacno, ali taj algoritam uopste nema smisla. Ovaj zadatak je skolski i radi se u jednom prolazu kroz niz (keceva i nula). Stalno pamtis pocetak niza jedinica i kad dodjes do prekida niza pogledas da li je duzina veca od trenutne maximalne i ako jeste zapamtis je zajedno sa pocetnim indexom.

Don’t do drugs, sleep deprivation is better.

^{14.08.2005. u 22:12}

Shadowed
.NET developer

SuperModerator
Član broj: 649
Poruke: 9030
*.etf.bg.ac.yu.

Sajt: www.diskusije.net

Profil

Re: [Zadatak] - jednostavan?!

^{14.08.2005. u 22:44}

Naravno, ono je samo bio komentar na taj konkretni algoritam (sto sam i napomenuo).

^{14.08.2005. u 22:44}