[es] - [Zadatak] Precizno otsecanje zice (republicko takmicenje 1999)

Daniel93
Daniel Ferizovic
nope
Bih/USK/Bos.Petrovac

Član broj: 196240
Poruke: 3
92.36.244.*

Profil

[Zadatak] Precizno otsecanje zice (republicko takmicenje 1999)

^{04.10.2008. u 21:38 - pre 189 meseci}

Treba mi pomoc oko ovog zadatka. Pokusao sam rekurzijom , ali pada na vremenu, pa bi bio zahvalan ako mi ko moze reci na koji nacin da uradim.

Zadatak:
Imamo vrlo preciznu mašinu koja može da od žice proizvoljne dužine odsece tacno jednu trecinu. Napisati program kojim se izracunava potreban broj secenja da se od žice pocetne dužine dobije komad dužine najbliže željenoj.

Sa standardnog ulaza se u dva reda ucitava pocetna i željena dužina žice. Oba broja su realni brojevi dvostruke preciznosti iz intervala [1, 10^14] zadati sa jednom decimalom.

Na standardni izlaz u dva reda ispisati potreban broj secenja i dužinu (na 5 decimala) žice najbližu željenoj, koja se dobiva tim brojem secenja.

Primer:

Ulaz:
6000.0
187.7

Izlaz:
5
197.53086

Komentar: Ako je žica duga 6000.0, a željena dužina komada je 187.7, tada treba u drugom secenju seci duži komad (od 4000). U trecem secenju seci duži komad (od 2666.66667). U cetvrtom secenju seci duži komad (od 1777.77778). U petom secenju seci kraci komad (od 592.59259) i izabrati kraci komad (od 197.53086) koji je rešenje

Vremensko ogranicenje: 0.2 s

Hvala unaprijed

Odgovor na temu

StefanJer91
Stefan Jeremic
Beograd

Član broj: 121923
Poruke: 160
*.static.ikomline.net.

Profil

Re: [Zadatak] Precizno otsecanje zice (republicko takmicenje 1999)

^{05.10.2008. u 17:06 - pre 189 meseci}

Evo resio sam pa reci jel odgovara pa cu ti reci kako sam dosao do resenja:

Code:

#include <stdio.h>
#include <math.h>

inline double get_closer(double b1, double b2, double n)
{
    return (fabs(b1-n) < fabs(b2-n) ? b1 : b2);
}

int main()
{
    double n = 6000;
    double b = 187.7;
    double x;
    int i = 1;
    int closest_i = 1;
    double smaller, bigest = n, closest, last_closest = n;
    while (bigest > b)
    {
        x = n/(pow(3,i));
        smaller = x;
        bigest = x*pow(2,i);
        closest = x;
        for (int j = 0; j < i+1; j++)
        {
            if (get_closer(closest, closest*2, b) == closest)
                break;
            else
                closest*=2;
        }
        last_closest = get_closer(closest, last_closest, b);
        if (last_closest == closest) closest_i = i;
        i++;
    }

    printf("%d\n%lf\n",closest_i, last_closest);

    return 0;
}

Lako mozes da podesis da se menjaju brojevi n i b

The earth teaches us more about ourselves than all the books. Because it resists us. Man discovers himself when he measures himself against the obstacle.

Odgovor na temu

Daniel93
Daniel Ferizovic
nope
Bih/USK/Bos.Petrovac

Član broj: 196240
Poruke: 3
92.36.247.*

Profil

Re: [Zadatak] Precizno otsecanje zice (republicko takmicenje 1999)

^{05.10.2008. u 17:23 - pre 189 meseci}

Da, radi zadatak na svim primjerima. Mozes mi samo pojasniti tvoj kod i nacin.

Odgovor na temu

StefanJer91
Stefan Jeremic
Beograd

Član broj: 121923
Poruke: 160
*.static.ikomline.net.

Profil

Re: [Zadatak] Precizno otsecanje zice (republicko takmicenje 1999)

^{05.10.2008. u 18:31 - pre 189 meseci}

Ako pocetni broj oznacimo sa n grananje ce izgledati ovako:

Kao sto mozes da primetis na slici, u svakom sledecem koraku ima za 1 vise mogucih brojeva ako se izuzmu oni koji se ponavljaju (kao sto je slucaj za 2/3*n, 2/27*n ...)
Daljim posmatranjem se vidi da je delilac uvek stepen trojke, dok je mnozilac stepen dvojke. Stepen delioca je onoliki koliki je i trenutni korak, dok je stepen mnozioca od 0 do stepena delioca. To se lepo vidi na slici.

dakle evo sta se desava u svakom koraku:

x = n/3^i (n je broj od koga se pocinje a i je korak)

onda moguce kombinacije brojeva su:

x*2^0 x*2^1 x*2^2 ... x*2^i

Od ovih kombinacija uzimas onu koja je najbliza trazenom broju (oznacen je sa b). To je variabla closest. last_closest je ona koja je bila najbliza za prethodni krug i ona postaje closest u slucaju da je closest blizi nego prethodni. Slican princip je i za closest_i.

smaller variablu sam zaboravio da izbacim, ona ne sluzi nicemu :)

proces se ponavlja sve dok je biggest veci od b jer kada postane manji nema smisla dalje traziti brojeve. bigest je najveca moguca kombinacija odnosno x*2^i.
Nadam se da ces ukapirati, reci ako jos nesto nije jasno ;)

The earth teaches us more about ourselves than all the books. Because it resists us. Man discovers himself when he measures himself against the obstacle.

Odgovor na temu