Jednostavni Algoritam

Jednostavni Algoritam 16.06.2008. u 16:32 · pre 223 meseca #1

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!

Re: Jednostavni Algoritam 16.06.2008. u 16:55 · pre 223 meseca #2

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....

Potpis

rafforum.rs - Forum Računarskog Fakulteta

Re: Jednostavni Algoritam 16.06.2008. u 19:53 · pre 223 meseca #3

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.

Re: Jednostavni Algoritam 19.06.2008. u 10:58 · pre 223 meseca #4

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.

Re: Jednostavni Algoritam 20.06.2008. u 15:26 · pre 223 meseca #5

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

Re: Jednostavni Algoritam 20.06.2008. u 22:26 · pre 223 meseca #6

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!

Re: Jednostavni Algoritam 21.06.2008. u 07:17 · pre 223 meseca #7

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?

Potpis

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

Re: Jednostavni Algoritam 21.06.2008. u 09:25 · pre 223 meseca #8

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.

Re: Jednostavni Algoritam 21.06.2008. u 12:42 · pre 223 meseca #9

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.

Re: Jednostavni Algoritam 21.06.2008. u 13:20 · pre 223 meseca #10

Matematicka jednacin za ovaj zadatak je prosta

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

Potpis

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

equation.jpg4.22k

Re: Jednostavni Algoritam 21.06.2008. u 13:28 · pre 223 meseca #11

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

Re: Jednostavni Algoritam 21.06.2008. u 13:52 · pre 223 meseca #12

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

Potpis

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

equation2.jpg10.67k

Re: Jednostavni Algoritam 21.06.2008. u 15:04 · pre 223 meseca #13

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.

Re: Jednostavni Algoritam 21.06.2008. u 15:28 · pre 223 meseca #14

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

Re: Jednostavni Algoritam 07.07.2008. u 20:51 · pre 223 meseca #15

$\sum_{i=1}^n\sum_{j=1}^ii=\sum_{i=1}^ni\cdot i=\sum_{i=1}^ni^2=\frac{(2n+1)(n+1)n}{6}$ . Za $n=10$ rezultat je $\frac{21\cdot 11\cdot 10}6=7\cdot 11\cdot 5=385$ .

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Jednostavni Algoritam 07.07.2008. u 21:21 · pre 223 meseca #16

Č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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Jednostavni Algoritam 08.07.2008. u 09:03 · pre 222 meseca #17

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

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Jednostavni Algoritam 08.07.2008. u 10:23 · pre 222 meseca #18

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

Potpis

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

eq0.jpg10.19k

Re: Jednostavni Algoritam 08.07.2008. u 12:40 · pre 222 meseca #19

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

Neka je $S_k(n)=\sum_{i=1}^ni^k$ . Izracunajmo $S_k(n)$ .

Lako se dokazuje da je $\sum_{i=1}^n(a_{i+1}-a_i)=a_{n+1}-a_1$ za bilo koji niz $a_i$ . Dokaz se moze izvesti indukcijom po $n$ , a moze se i primetiti da se svi ostali clanovi medjusobno pokrate. Iz tog razloga je

$\sum_{i=1}^n((i+1)^{k+1}-i^{k+1})=(n+1)^{k+1}-1$ , $\sum_{i=1}^n(i^{k+1}-(i-1)^{k+1})=n^{k+1}$ .

Razvijajuci to po binomnoj formuli je

$\sum_{i=1}^n\left({k+1\choose 1}i^k+\cdots+{k+1\choose k+1}i^0)\right)=(n+1)^{k+1}-1$ $\sum_{i=1}^n\left((-1)^0{k+1\choose 1}i^k\cdots+(-1)^{k}{k+1\choose k+1}i^0)\right)=n^{k+1}$ ,

odnosno ${k+1\choose 1}S_k(n)+\cdots+{k+1\choose k+1}S_0(n)=(n+1)^{k+1}-1$ , odnosno $(-1)^0{k+1\choose 1}S_k(n)+\cdots+(-1)^k{k+1\choose k+1}S_0(n)=n^{k+1}$ . Odatle dobijamo rekurentne formule

$S_k(n)=\frac{(n+1)^{k+1}-1-\left({k+1\choose 2}S_{k-1}(n)+\cdots+{k+1\choose k+1}S_0(n)\right)}{k+1}$ , $S_k(n)=\frac{n^{k+1}+\left((-1)^0{k+1\choose 2}S_{k-1}(n)+\cdots+(-1)^{k-1}{k+1\choose k+1}S_0(n)\right)}{k+1}$ .

Obe su ravnopravne. Koja ce se koristiti, stvar je ukusa. Pritom se zna da je $S_0(n)=n$ . Tako je na primer

$S_1(n)=\frac{n^2+{2\choose 2}S_0(n)}{2}=\frac{n(n+1)}{2}$ ,

$S_2(n)=\frac{n^3+{3\choose 2}S_1(n)-{3\choose 3}S_0(n)}{3}=\frac{(2n+1)(n+1)n}{6}$ .

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Jednostavni Algoritam 08.07.2008. u 15:02 · pre 222 meseca #20

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...

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Forum kao aplikacija na telefonu

Srodne teme