Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Pristup 3n+1 problemu

[es] :: Art of Programming :: Pristup 3n+1 problemu

Strane: 1 2

[ Pregleda: 6240 | Odgovora: 29 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cc.fer.hr.

ICQ: 170788654


Profil

icon Pristup 3n+1 problemu16.05.2005. u 12:39 - pre 229 meseci
Problem se nalazi na http://acm.uva.es/p/v1/100.html
+dodatak:Zamišljeno je da imam 1s da se dobije rješenje za pojedini interval
Zanima me smijem li ja ovdje primjenjivati grubu silu za rješavanje problema?

Recimo da za nijedan n nisam našao više od 300 koraka dok ne dođe do broja jedan(npr. za broj 999999 ima 258 koraka).Ako uzmem najgori mogući slučaj(interval [1,1000000]) tada,ako uzmem za svaki broj iz tog intervala 300 koraka,sve skupa imam 300 000 000 operacija. Ako je testno računalo cca 800 Mhz(cca 800 000 000 operacija u sekundi),to bi trebalo biti dovoljno,pretpostavljam. Jesu li dosadašnje pretpostavke točne?

Zamislio sam i malo drugačiji pristup,memorijski zahtjevniji. Nekako podsjeća na dinamičko programiranje. Recimo da za svaki n pamtim u poziciji DULJINA[n], broj koraka koji mu trebaju dok ne dođe do 1,a za neki broj m čiji se ciklus nadovezuje na broj n izračunam broj koraka baš pomoću podatka DULJINA[n].Kažem,memorijski je zahtjevniji(10 000 000 * 4 bajta,recimo),ali trebao bi biti brži.

Koji je način bolji,ispravniji, i postoji li još neka druga metoda za rješavanje?
I da,kako da učitavam podatke s tipkovnice(oblik je naveden na već navedenom linku) dok ih ima(while not FEOF(stdin) ne radi)?(pitanje nižeg prioriteta)
 
Odgovor na temu

sklitzz

Član broj: 54393
Poruke: 13
*.net.t-com.hr.



Profil

icon Re: Pristup 3n+1 problemu16.05.2005. u 14:08 - pre 229 meseci
Možeš tako i ubrzat ali to više za vježbu.
Naravno da će ti proći i brute force, pa to je prvi zadatak da svak
ima nešto poslati i viditi jeli mu radi...
 
Odgovor na temu

D3adly

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

ICQ: 281458481


Profil

icon Re: Pristup 3n+1 problemu16.05.2005. u 18:52 - pre 229 meseci
Učitavaj sa

Code:

while (scanf ("%d %d",&a,&b) != EOF)


#include <D3adly.h>
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.bankerinter.net.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Pristup 3n+1 problemu17.05.2005. u 00:24 - pre 229 meseci
Pa, nije 10 000 000 * 4, nego 1 000 000 * 4 bajta, sto je nesto manje od 4 MB, sto je verovatno prihvatljivo.

A sto se tice operacija u sekundi, zavisi sta smatras pod "operacijom". Obicno se to meri u mflops-ima (mega floating point operations per second), ali kad pricamo o operacijama u sekundi za ovakve "art of programming" probleme, ne bi trebalo racunati vise od 30 000 000 operacija u sekundi. Opet, sigurno ce x puta sporije raditi recimo deljenje ili mod, nego bitovsko and ili tako nesto, i sigurno ce mnooogo brze raditi operacije nad intovima nego nad floatima, ali ne treba probiti (po meni) taj plafon od 30M operacija. Cak, za floatove ja uzimam 10M. O 800M da ni ne govorimo ;)

A sto se feof tice, da li mislis da se to kod njih ucitava sa tastature? Naravno da ne, nego se preusmeri u fajl. Zato lepo ti stavi na pocetku 2 reda koda
Code:

FILE *in = stdin;
FILE *in = fopen ("bla.bla", "r");

pa dok radis kuci prvi red ti stoji iskomentarisan (i koristis feof normalno), a kad saljes iskomentarises drugi red, i opet ce feof kod njih lepo raditi.

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cc.fer.hr.

ICQ: 170788654


Profil

icon Re: Pristup 3n+1 problemu17.05.2005. u 08:07 - pre 229 meseci
Uzeo sam 10 000 000 *4 bajta zato što neki brojevi počnu prelaziti milijun(npr. 999 999 --> 2999998,a ne znam točnu granicu.No,priznajem,da,to baš i nije bilo najpametnije.
 
Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cc.fer.hr.

ICQ: 170788654


Profil

icon Re: Pristup 3n+1 problemu17.05.2005. u 08:08 - pre 229 meseci
I kako mogu znati kako se zove file s ulaznim podacima?
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Pristup 3n+1 problemu17.05.2005. u 11:58 - pre 229 meseci
Ma ne moras da pamtis za preko 1000000.... To ti je 2-3 koraka vise mozda za te brojeve koji budu presli 1000000... Bolje 2-3 operacije nego 10x vise memorije ;)

Pa ti i ne znas kako se zove file sa ulaznim podacima. Nego ti kad testiras kod sebe na kompu, koristi neke fileove, a za resenje koje saljes, samo ih preusmeri na stdin i stdout. Npr, pocetak koda koji koristis dok testiras kod sebe bi bio:
Code:

#include <stdio.h>

FILE *in, *out;

int main ()
{
  in = fopen ("3nplus1.in", "r"); out = fopen ("3nplus1.out", "w");
//  in = stdin; out = stdout;
...

pa kad treba da ga posaljes:
Code:

#include <stdio.h>

FILE *in, *out;

int main ()
{
//  in = fopen ("3nplus1.in", "r"); out = fopen ("3nplus1.out", "w");
  in = stdin; out = stdout;
...


I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cc.fer.hr.

ICQ: 170788654


Profil

icon Re: Pristup 3n+1 problemu18.05.2005. u 10:28 - pre 229 meseci
Ovo je nevjerojatno!Sada program i radi kako treba,a na ACMovim stranicama mi stalno javlja Compile Error.Užas.
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Pristup 3n+1 problemu18.05.2005. u 12:18 - pre 229 meseci
posalji kod
I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249



+96 Profil

icon Re: Pristup 3n+1 problemu18.05.2005. u 13:28 - pre 229 meseci
Pascal i Turbo Pascal se razlikuju u par detalja...
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Pristup 3n+1 problemu18.05.2005. u 14:54 - pre 229 meseci
A sta je samo "pascal" ?

Na tim graderima uglavnom koriste free pascal.
I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cc.fer.hr.

ICQ: 170788654


Profil

icon Re: Pristup 3n+1 problemu18.05.2005. u 15:14 - pre 229 meseci
Program je napisan u C-u.Prvo je kompajliran u VC6,radio,a zatim kompajliran u VS.Net 2003 i radi.Stavit ću source za koji dan,posudio sam disk nekome.
Dobro,skužio sam jednu malu manu kad je radio,tj. nije radio uopće za brojeve veće od 200 000.Mislim da odabir rekurzije nije bila greška(nema velik broj poziva),izgledala je otprilike

int cikl(int n){
if (n==1) return 1;
if (n%2) return (cikl(n*3+1)+1);
else return(cikl(n/2)+1);
}

I kao takva baš nije mogla prepuniti memorijski stog.
No dobro,kad uploadam source,vidjet ćete kako to izgleda.
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Pristup 3n+1 problemu18.05.2005. u 15:32 - pre 229 meseci
Paaaa, ogranicenje za stek je dosta manje nego za heap, sto ce reci da za rekurziju verovatno nemas bas previse memorije :(

A stvarno mislim da bi bilo bolje da radis onako, da pamtis za svaki broj koliko ti koraka treba do 1....

Uostalom, pricacemo kad posaljes kod :)

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249



+96 Profil

icon Re: Pristup 3n+1 problemu18.05.2005. u 16:02 - pre 229 meseci
Evo jednog interesantnog koda koji se lepo kompajlira i u Turbo Pascalu i u Standard Pascalu, samo što daje različite rezultate. Dva Pascala različito tretiraju ugnježdene komentare:

Code:

{----------------------------------------------------------------------}
program Comments (output);
const
    (* { }
    STANDARD = TRUE;
    FOO = '*) STANDARD = FALSE; (*';
    BAR = '*) BAZ = '''(*' { };
begin
    writeln ('The assertion that this Pascal is standard is ',
        STANDARD, '.')
end.
{----------------------------------------------------------------------}


Ako svi koriste free pascal onda ga koristite i vi. Ako koristite različite kompajlere onda ćete stalno nailaziti na ovakve probleme.

Ovo nema toliko veze sa "umetnošću programiranja", više sa korišćenjem pravog alata. Neka je i tako, nema umetnika bez majstora
 
Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr.

ICQ: 170788654


Profil

icon Re: Pristup 3n+1 problemu21.05.2005. u 21:27 - pre 229 meseci
Evo i sourcea,komentirajte,je li samo katastrofa ili je totalni užas.
Prikačeni fajlovi
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Pristup 3n+1 problemu22.05.2005. u 00:57 - pre 229 meseci
Hehe, pa sta moze biti tolika katastrofa u kodu od 15 reda ;)

Btw, i dalje tvrdim da je bolje da pamtis duzinu za sve brojeve....

A inace, ako vec radis ovako, ne vidim nista lose u kodu, osim sto (nema veze sa samim problemom) bi trebao da imas naviku da ti main vraca int, a ne void.

Poz

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr.

ICQ: 170788654


Profil

icon Re: Pristup 3n+1 problemu22.05.2005. u 08:20 - pre 229 meseci
Pa koliko se često ispituje da'l je program završio svoj posao ili ne?
Modificirat ću kod,ovo je otprije par dana. Možda će ako napravim 100% promjenu prestati javljati Compile Error na ACM-u.
 
Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.net.t-com.hr.

ICQ: 281458481


Profil

icon Re: Pristup 3n+1 problemu22.05.2005. u 11:40 - pre 229 meseci
1.) Compile Error ti javlja zbog

Code:

void main(){

}


to zamjeni sa
Code:

int main(void){

}



2.) Ako tako izmjeniš kod javljat će ti WA (Wrong Answer). Gledaj zašto:
input:
Code:

10 1


output mora biti:
Code:

10 1 20


Dakle, u zadatku nije navedeno da prvi broj može biti veći od drugog.

Ako to sve središ dobit ćeš Accepted! ;-)
#include <D3adly.h>
 
Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr.

ICQ: 170788654


Profil

icon Re: Pristup 3n+1 problemu22.05.2005. u 14:01 - pre 229 meseci
Napravio sam kako si rekao,no još uvijek javlja isti tip greške.A ništa,vraćam se ja Pascalu,što će mi C,C++ i te gluposti :-)
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Pristup 3n+1 problemu22.05.2005. u 14:13 - pre 229 meseci
Posalji kao C++, ne kao C (provereno radi, slao sam tvoj kod ;))
I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

[es] :: Art of Programming :: Pristup 3n+1 problemu

Strane: 1 2

[ Pregleda: 6240 | Odgovora: 29 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.