[es] - Jednostavni Algoritam

McKnight
Gordon Cindrić
Vinkovci

Član broj: 94745
Poruke: 39
*.adsl.net.t-com.hr.

Sajt: www.knowledge-reactor.com

Profil

Jednostavni Algoritam

^{16.06.2008. u 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!

^{16.06.2008. u 15:32}

Aleksandar Ružičić
Software Developer, Joker Games d.o.o.
Beograd

SuperModerator
Član broj: 26939
Poruke: 2850
*.dynamic.adsl.itsisp.net.

Jabber: krckoorascic@gmail.com
Sajt: krcko.net

Profil

Re: Jednostavni Algoritam

^{16.06.2008. u 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....

W3 Schools - An Intervention
rafforum.rs - Forum Računarskog Fakulteta

^{16.06.2008. u 15:55}

McKnight
Gordon Cindrić
Vinkovci

Član broj: 94745
Poruke: 39
*.adsl.net.t-com.hr.

Sajt: www.knowledge-reactor.com

Profil

Re: Jednostavni Algoritam

^{16.06.2008. u 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.

^{16.06.2008. u 18:53}

McKnight
Gordon Cindrić
Vinkovci

Član broj: 94745
Poruke: 39
*.adsl.net.t-com.hr.

Sajt: www.knowledge-reactor.com

Profil

Re: Jednostavni Algoritam

^{19.06.2008. u 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.

^{19.06.2008. u 09:58}

S_3_ka

Član broj: 48863
Poruke: 22
*.static.sbb.rs.

Profil

Re: Jednostavni Algoritam

^{20.06.2008. u 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

^{20.06.2008. u 14:26}

McKnight
Gordon Cindrić
Vinkovci

Član broj: 94745
Poruke: 39
*.adsl.net.t-com.hr.

Sajt: www.knowledge-reactor.com

Profil

Re: Jednostavni Algoritam

^{20.06.2008. u 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!

^{20.06.2008. u 21:26}

Predrag Supurovic
Predrag Supurović Broker
Užice

Član broj: 157129
Poruke: 3189
77.46.253.*

Sajt: pedja.supurovic.net

Profil

Re: Jednostavni Algoritam

^{21.06.2008. u 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?

http://pedja.supurovic.net - http://wireless.uzice.net - Besplatni .RS domeni - Mikrotik uputstva

^{21.06.2008. u 06:17}

S_3_ka

Član broj: 48863
Poruke: 22
*.dynamic.sbb.rs.

Profil

Re: Jednostavni Algoritam

^{21.06.2008. u 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.

^{21.06.2008. u 08:25}

McKnight
Gordon Cindrić
Vinkovci

Član broj: 94745
Poruke: 39
*.adsl.net.t-com.hr.

Sajt: www.knowledge-reactor.com

Profil

Re: Jednostavni Algoritam

^{21.06.2008. u 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.

^{21.06.2008. u 11:42}

mmix
Miljan Mitrović
Software Architect
Pančevo, Srbija

SuperModerator
Član broj: 17944
Poruke: 4196
*.eunet.yu.

Sajt: blog.mitrovic.rs

Profil

Re: Jednostavni Algoritam

^{21.06.2008. u 12:20}

Matematicka jednacin za ovaj zadatak je prosta

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

▪ When the only tool you know how to use is a hammer every problem begins to look like a nail
▪ "Gladni stolećima, kupujemo više hleba nego što nam je potrebno. A, onda ga bacamo. Hleb u đubretu nije dobar prizor. On sluti na zlo. I zlo dolazi" - Momo Kapor
▪ "Opportunity is missed by most because it is dressed in overalls and looks like work" - Thomas Edison

Prikačeni fajlovi

equation.jpg - 4.22k

^{21.06.2008. u 12:20}

McKnight
Gordon Cindrić
Vinkovci

Član broj: 94745
Poruke: 39
*.adsl.net.t-com.hr.

Sajt: www.knowledge-reactor.com

Profil

Re: Jednostavni Algoritam

^{21.06.2008. u 12:28}

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

^{21.06.2008. u 12:28}

mmix
Miljan Mitrović
Software Architect
Pančevo, Srbija

SuperModerator
Član broj: 17944
Poruke: 4196
*.eunet.yu.

Sajt: blog.mitrovic.rs

Profil

Re: Jednostavni Algoritam

^{21.06.2008. u 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:

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

Prikačeni fajlovi

equation2.jpg - 10.67k

^{21.06.2008. u 12:52}

S_3_ka

Član broj: 48863
Poruke: 22
89.216.113.*

Profil

Re: Jednostavni Algoritam

^{21.06.2008. u 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.

^{21.06.2008. u 14:04}

McKnight
Gordon Cindrić
Vinkovci

Član broj: 94745
Poruke: 39
*.adsl.net.t-com.hr.

Sajt: www.knowledge-reactor.com

Profil

Re: Jednostavni Algoritam

^{21.06.2008. u 14:28}

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

^{21.06.2008. u 14:28}

Nedeljko
Nedeljko Stefanović
Beograd

Član broj: 314
Poruke: 5628
195.222.97.*

Profil

Re: Jednostavni Algoritam

^{07.07.2008. u 19:51}

. Za

rezultat je

Pishi kao shto govorish, a chitaj kao shto je napisano.

^{07.07.2008. u 19:51}

Nedeljko
Nedeljko Stefanović
Beograd

Član broj: 314
Poruke: 5628
195.222.97.*

Profil

Re: Jednostavni Algoritam

^{07.07.2008. u 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]}

Pishi kao shto govorish, a chitaj kao shto je napisano.

^{07.07.2008. u 20:21}

Nedeljko
Nedeljko Stefanović
Beograd

Član broj: 314
Poruke: 5628
*.dynamic.sbb.rs.

Profil

Re: Jednostavni Algoritam

^{08.07.2008. u 08:03}

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

Pishi kao shto govorish, a chitaj kao shto je napisano.

^{08.07.2008. u 08:03}

mmix
Miljan Mitrović
Software Architect
Pančevo, Srbija

SuperModerator
Član broj: 17944
Poruke: 4196
*.eunet.yu.

Sajt: blog.mitrovic.rs

Profil

Re: Jednostavni Algoritam

^{08.07.2008. u 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

Prikačeni fajlovi

eq0.jpg - 10.19k

^{08.07.2008. u 09:23}

Nedeljko
Nedeljko Stefanović
Beograd

Član broj: 314
Poruke: 5628
*.dynamic.sbb.rs.

Profil

Re: Jednostavni Algoritam

^{08.07.2008. u 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

Pishi kao shto govorish, a chitaj kao shto je napisano.

^{08.07.2008. u 11:40}

Nedeljko
Nedeljko Stefanović
Beograd

Član broj: 314
Poruke: 5628
*.dynamic.sbb.rs.

Profil

Re: Jednostavni Algoritam

^{08.07.2008. u 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]}

Pishi kao shto govorish, a chitaj kao shto je napisano.

^{08.07.2008. u 14:02}