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

c++ zadaci [zabava za sve] :D

[es] :: C/C++ programiranje :: c++ zadaci [zabava za sve] :D

Strane: 1 2 3

[ Pregleda: 10834 | Odgovora: 40 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D02.12.2010. u 08:58 - pre 162 meseci
Onaj rekurzivan algoritam računa Fibonačijeve brojeve u eksponencijalnom vremenu. Ovaj to radi u linearnom.

Code:
int fib(int n) {
    if (n < 3) {
        return 1;
    }

    int n2 = n >> 1;
    int a = fib(n2);
    int b = fib(n2 + 1);

    if ((n & 1) == 0) {
        return a*(2*b - a);
    }

    return a*a + b*b;
}


a može još brže - u vremenu .
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

itf
Zagreb

Član broj: 59794
Poruke: 993
161.53.237.*



+9 Profil

icon Re: c++ zadaci [zabava za sve] :D02.12.2010. u 14:33 - pre 162 meseci
Hm.. kad smo već kod rekurzije.. Bio je jedan zadatak koji traži da program ispiše koliko puta se može pozvati rekurzivna funkcija void f(); prije nego što se dogodi stack overflow. Jasno, program se ne smije srušiti, već mora ispisati tu informaciju i normalno završiti s izvođenjem.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D02.12.2010. u 15:55 - pre 162 meseci
Rešenje se može naći na stack overflow-u. Ime sajta lepo kaže šta se na njemu može naći.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D03.12.2010. u 10:34 - pre 162 meseci
Evo, kako bi mogao da izgleda efikasan algoritam za Fibonačija:

Code:
#include <iostream>
#include <cstdlib>
#include <map>

using namespace std;

class Fibonachi {
    static map<int, long long int> cache;

public:
    static long long int value(int n) {
        if (n < 3) {
            return 1;
        }

        map<int, long long int>::const_iterator i = cache.find(n);

        if (i != cache.end()) {
            return (*i).second;
        }

        int n2 = n >> 1;
        long long int a = value(n2);
        long long int b = value(n2 + 1);
        long long int val = (n & 1) == 0 ? a*((b << 1) - a) : a*a + b*b;

        cache.insert(pair<int, long long int>(n, val));

        return val;
    }

    static void clear() {
        cache.clear();
    }
};

map<int, long long int> Fibonachi::cache;

int main() {
    cout << "Zdravo" << endl;
    for (int i = 1; i <= 10; ++i) {
        Fibonachi::clear();
        cout << Fibonachi::value(i) << endl;
    }

    system("pause");
    return EXIT_SUCCESS;
}


Uzgred, kako da mi ES ofarba kod u skaldu sa C++ sintaksom?
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.mts.telekom.rs.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D04.12.2010. u 19:00 - pre 162 meseci
Napisati program kome se unosi ispravna šahovska pozicija u kojoj je beli na potezu, od figura su na tabli samo kraljevi, beli konj i beli lovac i koji kao beli matira crnog kojim upravlja korisnik u ne više od 50 poteza.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.mts.telekom.rs.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D04.12.2010. u 22:31 - pre 162 meseci
Samo da napomenem da za rešenje nije potrebno nikakvo poznavanje šahovske teorije osim pravila šahovske igre. Dakle, ne traži se implementacija postojećih algoritama za žive igrače. Zadatak se može rešiti i tako, ali se problem može rešiti programski daleko jednostavnije.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

mihojla

Član broj: 120688
Poruke: 188
free-123-236.mediaworksit.net.

Sajt: keramicar.sekon.net/akciz..


+34 Profil

icon Re: c++ zadaci [zabava za sve] :D06.12.2010. u 17:12 - pre 162 meseci
Taj zadatak bi pre išao u forum matematika-topologija a ne c++
Kap vode...
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.mts.telekom.rs.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D06.12.2010. u 22:13 - pre 162 meseci
Rešenje nema nikakve veze sa matematikom, pa ni sa njenom granom topologijom (sa kojom tek nema veze).
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.mts.telekom.rs.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D06.12.2010. u 22:19 - pre 162 meseci
Da si rekao da je za forum "Art of Programming", bilo bi na mestu, jer problem nema veze sa izborom programskog jezika. Sa matematikom ima veze onaj zadatak koji si ti postavio

Citat:
mihojla: Program koji ce upisati brojeve od 1-125 u kocku 5x5x5 tako da zbir u svakoj koloni i svakom redu bude jednak.


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

mihojla

Član broj: 120688
Poruke: 188
free-123-236.mediaworksit.net.

Sajt: keramicar.sekon.net/akciz..


+34 Profil

icon Re: c++ zadaci [zabava za sve] :D07.12.2010. u 10:43 - pre 162 meseci
Citat:
Nedeljko: beli konj i beli lovac i koji kao beli matira
Mislim da poslednji potez se igra lovcem tako da je potrebno saterati kralja u beli ćošak. Boga mi nije ni malo jednostavno u 50 poteza.
Kap vode...
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D07.12.2010. u 11:06 - pre 162 meseci
Ti razmišljaš o rešenju primenom šahovske teorije za koju sam napisao da nije potrebna. Postoji jednostavnije rešenje ako treba da ga izvršava računar, a ne čovek.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D07.12.2010. u 14:27 - pre 162 meseci
Pa, evo, da dam ideju.

Poziciju cine raspored figura na tabli i informacija o tome ko je na potezu. Može se predstaviti sa 25 bitova. Dakle, ceo broj koji odgovara nekoj poziciji zvacemo njenim kodom. Naravno, neće svi brojevi u opsegu od 0 do 225-1 biti kodovi legalnih pozicija. Vrednošću pozicije smatracemo broj poteza potreban da crni bude matiran uz optimalnu igru oba igraca. Prvo treba izracunati niz v takav da je vi vrednost pozicije sa kodom i.

Najpre u petlji gde i ide od 0 do 225-1 ispitajmo da li je i kod legalne pozicije, pa ako jeste, onda u vi upišimo 0 ako je u njoj crni na potezu i matiran. 51 ako je pat pozicija (crni je na potezu i ne može da igra, a nije u šahu), kao i pozicije u kojima je crni na potezu i može odmah da pojede konja ili lovca, odnosno -1 u ostalim slucajevima. Ako i nije kod legalne pozicije, onda neka je vi jednako 51.

Zatim formirajmo petlju u kojoj k ide od 0 do 50 u kojoj radimo sledece:

U petlji gde i takode ide od 0 do 225-1 ispitajmo da li je vi=-1 i pritom je u odgovarajucoj poziciji beli na potezu, pa ako jeste, da li može odmah da pređe u poziciju sa kodom j tako da je vj=k. Ako može, onda izvršimo dodelu vrednosti k promenljivoj vi.

Potom u petlji gde i takode ide od 0 do 225-1 ispitajmo da li je vi=-1 i u odgovarajucoj poziciji je crni na potezu, pa ako jeste, da li bar jednim svojim legalnim potezom prelazi u poziciju sa kodom j tako da je vj=51. Ako je tako, onda dodelimo vrednost 51 promenljivojvi, a u suprotnom izvršimo dodelu vrednosti m promenljivoj vi, gde je m najveća od vrednosti vj takvih da crni mo\e odmah da pre]e u poziciju sa kodom j.

Na izlasku iz petlje sa brojačkom promenljivom k na sva mesta niza v čija je vrednost jednaka -1 upišimo 51.

Niz v je izračunat. Tačno značenje mu je sledeće: Ako je vi=51, onda je pozicija nelegalna ili crni može da se odbrani. Ako je beli na potezu u legalnoj poziciji sa kodom i, onda mu je uz najbolju odbranu crnog potrebno vi+1 poteza da ga matira. Ako je crni na potezu u legalnoj poziciji sa kodom i, onda crni može da se vadi vi poteza uz najbolju igru belog.

Napokon, evo najbolje strategije za oba igraca, nakon što je niz v izračunat.

Ako je beli na potezu u legalnoj poziciji sa kodom i, onda treba da igra potez koji ga prevodi u poziciju sa kodom j takvu da je vj=vi. Ako je crni na potezu u legalnoj poziciji sa kodom i, onda mu je najbolje da odigra potez koji ga prevodi u poziciju sa kodom j takvim da je vj=vi-1.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D07.12.2010. u 14:32 - pre 162 meseci
Ima li nekoga zainteresovanog za implementaciju?
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D17.12.2010. u 15:30 - pre 161 meseci
Evo rešenja.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Prikačeni fajlovi
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D17.12.2010. u 16:30 - pre 161 meseci
Prilikom prvog pokretanja program izračunava potrebnu tabelu za šta mu je potrebno određeno vreme koje zavisi od brzine računara. Nakon nekog vremena od ispisa "Stage 33 white" se tabela snima na disk. Prilikom svakog sledećeg pokretanja tabela se učitava sa diska, pa nema čekanja na izračunavanje.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Sini82

Član broj: 234605
Poruke: 479
62.101.141.*

Jabber: Sini82@elitesecurity.org


+33 Profil

icon Re: c++ zadaci [zabava za sve] :D18.12.2010. u 11:02 - pre 161 meseci
$ ./main
KnightAndBishop

Copyright (c) 2010 by Nedeljko Stefanovic, [email protected].

You are free to use, copy, modify and distribute it under the terms
of either version 2 or version 3 of the GNU General Public License
as published by the Free Software Foundation.


Data not present. Initialization

Stage 0 white


Svaka čast na zadatku i rješenju, program si stavio pod licencu.

U kom obliku se unose podaci? Možeš li navesti primjer unosa?



Da li je neko riješio ovaj problem (po meni ne bi trebalo da se ide dalje sa postavljanjem zadataka dok se on ne riješi):

Citat:
mihojla:
Program koji ce upisati brojeve od 1-125 u kocku 5x5x5 tako da zbir u svakoj koloni i svakom redu bude jednak.
?
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.ptt.rs.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D18.12.2010. u 12:06 - pre 161 meseci
Evo primera ulaza

KnightAndBishop

Copyright (c) 2010 by Nedeljko Stefanovic, [email protected].

You are free to use, copy, modify and distribute it under the terms
of either version 2 or version 3 of the GNU General Public License
as published by the Free Software Foundation.


Data not present. Initialization

Stage 33 white

Saving data
Data saved


Enter the positions of the pieces

White king a8
White knight h2
White bishop e8
Black king c8
Turn (black or white) black

1. ... Kc7
2. Ka7 Kd8
3. Bc6 Kc7
4. Be4 K


Problem sa 5x5x5 kockom sam pokušavao da rešim i nisam uspeo, ali ako se zadaci ne budu postavljali i rešavali zbog toga, neće biti ništa od teme.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

atelago

Član broj: 265415
Poruke: 776
*.dynamic.sbb.rs.



+53 Profil

icon Re: c++ zadaci [zabava za sve] :D19.12.2010. u 10:41 - pre 161 meseci
Ja imam jedan zadatak za vas, ali ne znam da li da ga postavim. Smislio sam igru
(ne „igricu“) koja može da se postavlja u bezbroj varijanti i da se traži rešenje.
Nazvao sam je „Promenljivi lavirint“. Principijelno je vrlo jednostavna – ima svoje
mogućnosti i ograničenja tako da je naizgled jednostavna, ali stvarno ipak nije.
Mogu se postavljati određeni problemi ili mogu se postavljati krajnji ciljevi do kojih
treba da dođu dva suprotstavljena protivnika i t. d. i t. d.
Onaj što je izmislio šah trebalo je da kao nagradu dobije nekoliko godišnjih žetava
žita, a i ja bih hteo da dobijem bar neku kintu.
Kako?
Ako pokažem princip, stvar je za mene odmah propala što se tiče te kinte. Ima li
kakva mogućnost da nešto zaradim? Ne bi bilo nepošteno.
S druge strane i ovde se govori o nekom zajedničkom vlasništvu autora i ovog
foruma, ali ne znam kako to da protumačim. Postoji li u tom smislu neka zaštita?

Igru nije moguće napraviti od stvarnih elemenata poput šaha jer postoje određene
tehničke poteškoće, mada bi one mogle biti prevaziđene upotrebom elektromagneta
Najbolje i najlakše bi je bilo isprogramirati (a u tu drvenariju se uopšte ne razumem)
Naravno, radi se samo o programiranju mogućih poteza s obzirom na ograničenja
koja logički slede iz same fizičke konstrukcije.
Imate li neki savet?
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249



+96 Profil

icon Re: c++ zadaci [zabava za sve] :D19.12.2010. u 12:18 - pre 161 meseci
Moj savet ti je da istražiš na internetu da nije slučajno već izmišljeno to što si otkrio. Stvaranje promenljivih lavirinata ne postoji od juče. Slučajno baš naletih na knjigu u kojoj ima raznih glavolomki pa pretpostavljam i promenljivih lavirinata: http://www.amazon.com/Zen-Laby...azes-Connoisseur/dp/1402759878 . Na autorovom sajtu http://davephillipspuzzlemaze.com/ imaš jedan lavirint u kome miš treba da pojede sve sireve i izađe iz lavirinta, ali kako prolazi kroz lavirint kapije menjaju konfiguraciju lavirinta.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.



+2789 Profil

icon Re: c++ zadaci [zabava za sve] :D20.12.2010. u 10:37 - pre 161 meseci
Citat:
atelago: Onaj što je izmislio šah trebalo je da kao nagradu dobije nekoliko godišnjih žetava
žita


Mnogo više od nekoliko godišnjih žetava žita. Pitanje je da li je do dan-danas proizvedeno toliko žita u svetu.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

[es] :: C/C++ programiranje :: c++ zadaci [zabava za sve] :D

Strane: 1 2 3

[ Pregleda: 10834 | Odgovora: 40 ] > FB > Twit

Postavi temu Odgovori

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