Jednostavni Algoritam

[ McKnight @ 16.06.2008. 15:32 ] @

Pozdrav ekipa!

Pripremam se za na fakultet pa me muci jedan zadatak iz podrucja algoritama a glasi ovako:

Koji će broj ispisati ovaj algoritam:

Rezultat je broj 512 ali me zanima kako se dodje do tog broja, pa eto ako bi to netko znao pa da napise.
Izvinjavam se unaprijed ako sam topic napisao u pogresnu kategoriju, pregledao sam "Programiranje" pa reko idem napisati ovdje :)
Hvala unaprijed!

[ Aleksandar Ružičić @ 16.06.2008. 15:55 ] @

ako analiziramo algoritam:

- na pocetku su x = 1 i y = 0
- za i = 1: x = x + y => 1, y = x => 1
- za i = 2: x = x + y => 2, y = x => 2
- za i = 3: x = x + y => 4, y = x => 4
- za i = 4: x = x + y => 8, y = x => 8
- za i = 5: x = x + y => 16, y = x => 16
- za i = 6: x = x + y => 32, y = x => 32
- za i = 7: x = x + y => 64, y = x => 64
- za i = 8: x = x + y => 128, y = x => 128
- za i = 9: x = x + y => 256, y = x => 256
- za i = 10: x = x + y => 512, y = x => 512

mislim da bi ovo moderatori trebali da prebace u Art of Programming....

[ McKnight @ 16.06.2008. 18:53 ] @

Totalno mi je jasnije sada. Hvala ti sto si mi to sve tako fino napisao :)
Imam jos jedan malo kompliciraniji za koji se nisam ni trudio da ga rijesim jer nisam znao ovaj pa cu ga napisati sutra u ovaj topic jer knjiga trenutno nije kod mene a sutra ce bit. Zato bi molio moderatore da ne lockaju topic, pa da sutra napisem reply sa tim drugim zadatkom.

[ McKnight @ 19.06.2008. 09:58 ] @

Eto ga i drugi, malo kompliciraniji zadataka. Pa ako bi netko znao rijesiti, bio bih vam zahvalan.

U ovom zadatku, mislim da je rezultat 385.

[ S_3_ka @ 20.06.2008. 14:26 ] @

Malo poduži odgovor, ali nadam se da je jasnije...

Code:

i = 1
        y = 0
                j = 1   y = y + i => y = 1
        x = x + y => x = 1
i = 2
        y = 0
                j = 1   y = y + i => y = 2
                j = 2   y = y + i => y = 4
        x = x + y => x = 5
i = 3
        y = 0
                j = 1   y = y + i => y = 3
                j = 2   y = y + i => y = 6
                j = 3   y = y + i => y = 9
        x = x + y => x = 14
i = 4
        y = 0
                j = 1   y = y + i => y = 4
                j = 2   y = y + i => y = 8
                j = 3   y = y + i => y = 12
                j = 4   y = y + i => y = 16
        x = x + y => x = 30
i = 5
    y = 0
        j = 1    y = y + i => y = 5
        j = 2    y = y + i => y = 10
        j = 3    y = y + i => y = 15
        j = 4    y = y + i => y = 20
        j = 5    y = y + i => y = 25
    x = x + y => x = 55
i = 6
    y = 0
        j = 1    y = y + i => y = 6
        j = 2    y = y + i => y = 12
        j = 3    y = y + i => y = 18
        j = 4    y = y + i => y = 24
        j = 5    y = y + i => y = 30
        j = 6    y = y + i => y = 36
    x = x + y => x = 91
i = 7
    y = 0
        j = 1    y = y + i => y = 7
        j = 2    y = y + i => y = 14
        j = 3    y = y + i => y = 21
        j = 4    y = y + i => y = 28
        j = 5    y = y + i => y = 35
        j = 6    y = y + i => y = 42
        j = 7    y = y + i => y = 49
    x = x + y => x = 140
i = 8
    y = 0
        j = 1    y = y + i => y = 8
        j = 2    y = y + i => y = 16
        j = 3    y = y + i => y = 24
        j = 4    y = y + i => y = 32
        j = 5    y = y + i => y = 40
        j = 6    y = y + i => y = 48
        j = 7    y = y + i => y = 56
        j = 8    y = y + i => y = 64
    x = x + y => x = 204
i = 9
    y = 0
        j = 1    y = y + i => y = 9
        j = 2    y = y + i => y = 18
        j = 3    y = y + i => y = 27
        j = 4    y = y + i => y = 36
        j = 5    y = y + i => y = 45
        j = 6    y = y + i => y = 54
        j = 7    y = y + i => y = 63
        j = 8    y = y + i => y = 72
        j = 9    y = y + i => y = 81
    x = x + y => x = 285
i = 10
    y = 0
        j = 1    y = y + i => y = 10
        j = 2    y = y + i => y = 20
        j = 3    y = y + i => y = 30
        j = 4    y = y + i => y = 40
        j = 5    y = y + i => y = 50
        j = 6    y = y + i => y = 60
        j = 7    y = y + i => y = 70
        j = 8    y = y + i => y = 80
        j = 9    y = y + i => y = 90
        j = 10    y = y + i => y = 100
    x = x + y => x = 385

[ McKnight @ 20.06.2008. 21:26 ] @

Hvala S_3_ka, puno mi je sada jasnije. U biti nije toliko ni komplicirano samo trebas skuziti shemu po kojoj ide.

Idem sad probat sam rijesiti neke takve zadatke. Pozdrav!

[ Predrag Supurovic @ 21.06.2008. 06:17 ] @

Mislim da je kod ovih zadataka poenta ne da izvrsis program nego da "izracunas" rezultat.
Sta bi da u zadatku brojac ne ide do 10 nego do 100 ili 1000?

[ S_3_ka @ 21.06.2008. 08:25 ] @

Citat:

Predrag Supurovic: Mislim da je kod ovih zadataka poenta ne da izvrsis program nego da "izracunas" rezultat.
Sta bi da u zadatku brojac ne ide do 10 nego do 100 ili 1000?

Pa... To je manje više isti zadatak. Da bi izračunao rezultat treba da izvršiš program.

[ McKnight @ 21.06.2008. 11:42 ] @

On vjerovatno misli da bi iz toga trebalo postaviti nekakvu jednadzbu koja bi to izracunala bez obzira koliko "i"-jeva ima. Ako bi bilo od 1 pa do 1000 kao što Predrag kaže, to bi bio opak posao za ispisati, da bi na kraju dobio rezultat. Nemam puno iskustva s takvim zadatcima ali cini mi se da bi se to mozda moglo nekako rijesiti nekom vrstom aritmetickog ili geometrijskog niza.

[ mmix @ 21.06.2008. 12:20 ] @

Matematicka jednacin za ovaj zadatak je prosta

[att_img]

Medjutim, bar koliko ja vidim ne postoji analiticki oblik x(k) za ovu dvostruku sumu. Mora iterativno.

[ McKnight @ 21.06.2008. 12:28 ] @

Oces reci, da za ovaj gore prvi algoritam mozes postaviti jednadzbu a za ovaj drugi, koji ima dvije varijable ne mozes?

[ mmix @ 21.06.2008. 12:52 ] @

Citat:

McKnight: Oces reci, da za ovaj gore prvi algoritam mozes postaviti jednadzbu a za ovaj drugi, koji ima dvije varijable ne mozes?

Ova jednacina je i bila za drugi zadatak, imas dve petlje, dakle dve sume.

Al odmah da demantujem sebe, drugi zadatak moze da se pojednostavi:

[att_img]

Znaci svodi se na sumu kvadrata iteratora. Malo lici na fibonacija, ali nije zato sto se sabiraju kvadrati, a ja bar ne znam za prostu formu konance sume kvadrata. Ako nista, bar smo izbacili jednu petlju

[ S_3_ka @ 21.06.2008. 14:04 ] @

Verovatno se neki deo zadataka može rešiti i izračunavanjem korišćenjem nizova, ali pošto se radi o prijemnom ispitu za fakultet, verovatno su zadaci takvi da se mogu rešiti "izvršavanjem" algoritma i takvom rešavanju su i namenjeni. Tako da sumnjam da će iteratori (ili više nijh) biti u nekom velikom opsegu, jer se gubi smisao zadatka.

[ McKnight @ 21.06.2008. 14:28 ] @

Ma da, i jos su odgovori ponudjeni ispod, a i nema negativnih bodova. Treba samo malo razmislit.

[ Nedeljko @ 07.07.2008. 19:51 ] @

. Za

rezultat je

[ Nedeljko @ 07.07.2008. 20:21 ] @

Čik da neko izračuna formulu za ovo (pod pretpostavkom da tip int nema ograničenja, to jest, da može da predstavi svaki ceo broj)

Code:

#include <iostream>

using namespace std;

int main()
{
    int i,j,k,n,s,s0;

    cout << "Unesi prirodan broj " << flush;
    cin >> n;
    s = 0;
    s0 = 0;

    for (i=1; i<=n ; i=i+1)
    {
        s = s + n;
        s0 = s0 + n;

        for (j=1; j<=s0; j=j+1)
        {
            s = s + n*j;

            for (k=1; k<=(i+j)*s0; k=k+1)
            {
                s = s + k + s0;
            }
        }
    }

    cout << "Rezultat je " << s << endl;

    return 0;
}

Priznaje se i ako neko da postupak kojim se može naći formula.

_{[Ovu poruku je menjao Nedeljko dana 08.07.2008. u 17:28 GMT+1]}

[ Nedeljko @ 08.07.2008. 08:03 ] @

Ako bude zainteresovanih, objavicu resenje. Ko ovo resi (ili bar razume resenje), moze da resi svaki zadatak ovog tipa.

[ mmix @ 08.07.2008. 09:23 ] @

Ajd okaci (daj i postupak), ja sam dobio nesto sasvim suludo, ali definitivno sume imaju rekurzivne parametre, i nisam bas siguran kako dalje

[att_img]

[ Nedeljko @ 08.07.2008. 11:40 ] @

Sada nemam mnogo vremena, pa cu okaciti samo jedan deo, a nastavak cu drugi put.

Neka je

. Izracunajmo

.

Lako se dokazuje da je

za bilo koji niz

. Dokaz se moze izvesti indukcijom po

, a moze se i primetiti da se svi ostali clanovi medjusobno pokrate. Iz tog razloga je

.

Razvijajuci to po binomnoj formuli je

,

odnosno

, odnosno

. Odatle dobijamo rekurentne formule

.

Obe su ravnopravne. Koja ce se koristiti, stvar je ukusa. Pritom se zna da je

. Tako je na primer

[ Nedeljko @ 08.07.2008. 14:02 ] @

Sad treba ici od unutra ka spolja. Petlja

Code:

for (k=1; k<=(i+j)*s0; k=k+1)
{
s = s + k + s0;
}

je ekvivalentna kodu

Code:

u = (i+j)*s0
for (k=1; k<=u; k=k+1)
{
s = s + k + s0;
}

gde je u neka nova promenljiva, jer se vrednost izraza koji opisuje gornju granicu indeksa ne menja unutar petlje. Petlja

Code:

for (k=1; k<=u; k=k+1)
{
s = s + k + s0;
}

Je ekvivalentna sa

Code:

s = s+u*s0;
for (k=1; k<=u; k=k+1)
{
s = s + k;
}

odnosno sa

Code:

s = s+u*s0;
s = s+u*(u+1)/2;

Dakle, celu petlju sa pocetka mozemo sabiti u jednu liniju

Code:

s = s+(i+j)*s0*s0+(i+j)*s0*((i+j)*s0+1)/2;

pa je nas program ekvivalentan sa

Code:

#include <iostream>

using namespace std;

int main()
{
    int i,j,k,n,s,s0;

    cout << "Unesi prirodan broj " << flush;
    cin >> n;
    s = 0;
    s0 = 0;

    for (i=1; i<=n ; i=i+1)
    {
        s = s + n;
        s0 = s0 + n;

        for (j=1; j<=s0; j=j+1)
        {
            s = s + n*j;
            s = s+(i+j)*s0*s0+(i+j)*s0*((i+j)*s0+1)/2;
        }
    }

    cout << "Rezultat je " << s << endl;

    return 0;
}

odnosno sa

Code:

#include <iostream>

using namespace std;

int main()
{
    int i,j,k,n,s,s0;

    cout << "Unesi prirodan broj " << flush;
    cin >> n;
    s = 0;
    s0 = 0;

    for (i=1; i<=n ; i=i+1)
    {
        s = s + n;
        s0 = s0 + n;

        for (j=1; j<=s0; j=j+1)
        {
            s = s+n*j+(i+j)*s0*s0+(i+j)*s0*((i+j)*s0+1)/2;
        }
    }

    cout << "Rezultat je " << s << endl;

    return 0;
}

To be continued...

_{[Ovu poruku je menjao Nedeljko dana 08.07.2008. u 17:30 GMT+1]}

[ Nedeljko @ 08.07.2008. 16:48 ] @

Zaboravih da napomenem da znak "/" označava uobičajeno delenje realnih brojeva. Prethodni zadatak razmotrimo u realnoj aritmetici da ne bi došlo do C-ovskog celobrojnog delenja, što je nešto drugo.

Šta nam omogućavaju izračunati polinomi

? Ako je

bilo koji polinom, onda možemo izračunati

. Zaista, za ma koje brojeve

važi

.

U petlji

Code:

for (j=1; j<=s0; j=j+1)
{
s = s+n*j+(i+j)*s0*s0+(i+j)*s0*((i+j)*s0+1)/2;
}

izraz (s0) koji predstavlja granicu indeksa se ne menja. Pošto je n*j+(i+j)*s0*s0+(i+j)*s0*((i+j)*s0+1)/2=(s0*s0/2)*j*j+(n+s0*s0+i*s0+s0/2)*j+(i*s0*s0+(i*i*s0*s0+i*s0)/2), prethodna petlja je ekvivalentna petlji

Code:

for (j=1; j<=s0; j=j+1)
{
s = s+(s0*s0/2)*j*j+(n+s0*s0+i*s0+s0/2)*j+(i*s0*s0+(i*i*s0*s0+i*s0)/2);
}

Posto se u petlji vrednosti promenljivih s0,n,i ne menjaju, ovaj kod će biti ekvivalentan naredbi

Code:

s = s+(s0*s0/2)*(2*s0+1)*(s0+1)*s0/6+(n+s0*s0+i*s0+s0/2)*(s0+1)*s0/2+(i*s0*s0+(i*i*s0*s0+i*s0)/2)*s0;

Dakle, program je ekvivalentan sa

Code:

#include <iostream>

using namespace std;

int main()
{
    int i,j,k,n,s,s0;

    cout << "Unesi prirodan broj " << flush;
    cin >> n;
    s = 0;
    s0 = 0;

    for (i=1; i<=n ; i=i+1)
    {
        s = s + n;
        s0 = s0 + n;
        s = s+(s0*s0/2)*(2*s0+1)*(s0+1)*s0/6+(n+s0*s0+i*s0+s0/2)*(s0+1)*s0/2+(i*s0*s0+(i*i*s0*s0+i*s0)/2)*s0;
    }

    cout << "Rezultat je " << s << endl;

    return 0;
}

odnosno sa

Code:

#include <iostream>

using namespace std;

int main()
{
    int i,j,k,n,s,s0;

    cout << "Unesi prirodan broj " << flush;
    cin >> n;
    s = 0;
    s0 = 0;

    for (i=1; i<=n ; i=i+1)
    {
        s0 = s0 + n;
        s = s+n+(s0*s0/2)*(2*s0+1)*(s0+1)*s0/6+(n+s0*s0+i*s0+s0/2)*(s0+1)*s0/2+(i*s0*s0+(i*i*s0*s0+i*s0)/2)*s0;
    }

    cout << "Rezultat je " << s << endl;

    return 0;
}

U originalnom programu je bila štamparska greška. Pisalo je s0 = s + n umesto s0 = s0 + n. Sada je to ispravljeno.
Primetimo da izračunavanje s0 nije zavisno od izračunavanja s. Odatle se lako zaključuje da je zapravo s0=i*n. Stoga je program ekvivalentan programu

Code:

#include <iostream>

using namespace std;

int main()
{
    int i,j,k,n,s,s0;

    cout << "Unesi prirodan broj " << flush;
    cin >> n;
    s = 0;
    s0 = 0;

    for (i=1; i<=n ; i=i+1)
    {
        s = s+n+(i*n*i*n/2)*(2*i*n+1)*(i*n+1)*i*n/6+(n+i*n*i*n+i*i*n+i*n/2)*(i*n+1)*i*n/2+(i*i*n*i*n+(i*i*i*n*i*n+i*i*n)/2)*i*n;
    }

    cout << "Rezultat je " << s << endl;

    return 0;
}

Pošto je n+(i*n*i*n/2)*(2*i*n+1)*(i*n+1)*i*n/6+(n+i*n*i*n+i*i*n+s0/2)*(s0+1)*s0/2+(i*i*n*i*n+(i*i*i*n*i*n+i*i*n)/2)*i*n polinom po i, a pritom je dat i postupak za svođenje ovakvog zadatka na

funkcije, za koje je dat postupak računanja, mogao bi neko da dokusuri ovaj zadatak.

[ Nedeljko @ 08.07.2008. 16:54 ] @

Prethodni polinom po i je stepena 5, pa je konačan rezultat polinom po n stepena 6. Ako neko želi da ga računa pomoću nekog gotovog matematičkog softvera, može ga izračunati tako što će odrediti vrednost funkcije (neposrednim računanjem) u 7 tačaka, pa onda provući interpolacioni polinom (ako ima softver sa podrškom za interpolacione polinome).