Pomoc oko c++ programa - Izumitelj igre sah

[ dinamozagreb @ 14.09.2005. 15:26 ] @

Molim vas pomoć.

Trebao bi napisati program o izumitelju saha.

Ako niste culi pricu evo ukratko: sahovska ploca ima 8x8 polja, i sad u prvo polje se stavi 1 zrno zita, u drugo duplo vise znaci 2, u trece 4, u peto 8.....

i sad treba to sve zbrojiti i ispisati ukupni broj zrna...

ako ko ima kakve ideje nek se javi ;)

[ NeznamTkoSam @ 14.09.2005. 16:01 ] @

Code:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
  int zbroj = 0;
  for (int i=1; i<65; i++) zbroj += pow(2, i);
  cout << zbroj << endl;
  char z; cin >> z;
  return 0;
}

[ japan @ 14.09.2005. 16:35 ] @

to može na papiru, inače se dobija prekoračenje i netačan rezultat...

po meni je, kad se radi sa velikim brojevima, pogotovo stepenima dvojke, najlogičnije predstavljati brojeve kao stringove, i to njihovu binarnu reprezentaciju. npr 2 = '10', 13 = '1101', itd, i implementirati funkcije za aritmetičke operacije sa ovakvim reprezentacijama brojeva...

mada ovo može da se uradi i primenom brze furijeove transformacije, ali je algoritam prilično komplikovan za implementaciju, i mislim da u ovom slučaju nije baš isplativo...

_{[Ovu poruku je menjao japan dana 14.09.2005. u 17:37 GMT+1]}

[ vladab @ 14.09.2005. 16:42 ] @

Imas i klase za rad sa velikim brojevima, mada mozes da napravis i svoju klasu koja ca da odradi taj posao. :O)

[ dinamozagreb @ 14.09.2005. 19:18 ] @

Probao sam program od NeznamTkoSam i nije radilo. U programu samo crni ekran.
Onda sam ja to malo promjenio..i..opet nista...evo kak sam ja to zamislio

#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <iostream.h>
using namespace std;
void main()
{
long int zbroj = 0;
for (int i=1; i<65; i++) zbroj += pow(2, i);
cout << "Zbroj zrna je: " << zbroj;
}

[ Buffy @ 14.09.2005. 19:31 ] @

Koristi "Infinite Integer class"(rad sa velikim brojevima) koju je NrmMyth napravio i ne davno objavio na ovom forumu.
http://www.elitesecurity.org/tema/134491-Infinite-Integer-Class
Pozdrav

_{[Ovu poruku je menjao Buffy dana 14.09.2005. u 20:32 GMT+1]}

[ dinamozagreb @ 23.09.2005. 19:30 ] @

Evo code za program, ali nije jos finalna verzija,trebam pomoc.

Code:

#include <math.h>
#include <iostream.h>
void main()
{
  double brojac=1;
  for (int i=1; i<64; i++) brojac+=pow(2,i);
  cout << "Broj zrna je: " << brojac;
}

Program ispise broj zrna ali u ovom obliku 1.84467e+19
Ali meni treba cijeli broj bez decimala, kako to izvesti ???

Znam 100% da se to moze izvesti i bez "Infinite Integer class", ali pitanje je kako ??

Pls Help!

[ igac @ 23.09.2005. 19:52 ] @

pa u toj prici kaze car "zar samo to... trazi nesto drugo sta god hoces blabla..." a ovaj hoce "samo" to... i onda kada su carevi ljudi preracunali koliko je to zita, skontali su da cijelo carstvo nema toliko zita... i ti hoces taj broj zrna da predstavis u decimalnom obliku bez Inf. int class :)

[ NrmMyth @ 23.09.2005. 20:18 ] @

2^64 je 18,446,744,073,709,551,616, a max 64-bitni int je 9,223,372,036,854,775,807.
Zakljucak je da ne postoji ugradjeni tip u koji mozes spremiti trazeni broj. :)

[ danio @ 24.09.2005. 01:50 ] @

Tocan odgovor je 2^64-1.

Double nema problema sa pohranjivanjem toga broja:

Code:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    double a=1;

    a=pow(2.0,64.0)-1.0;

    cout<<a<<endl;

    system("PAUSE");

    return 0;
}

_{[Ovu poruku je menjao danio dana 24.09.2005. u 02:51 GMT+1]}

[ danio @ 24.09.2005. 01:55 ] @

Vopce mi nije jasno. Kakve veze ima ta prica sa izumom saha. Bas nikakve...

[ japan @ 24.09.2005. 03:24 ] @

naravno da ima... sah je navodno nastao tako sto je covek za nagradu trazio od cara onoliko zita koliko ima zrna kad se na 64 polja stavi zrna: 1 na prvo, a na svako sledece duplo toliko...

skolski zadatak... kao i proizvoljno veliki fibonacci niz...

[ NeznamTkoSam @ 24.09.2005. 06:53 ] @

Ma ono sam ja napiso napamet

Evo rjesenja:
Rezultat je 3.68935e+19

Code:
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
  long double zbroj = 1.;
  for (double i=2; i<65; i++) zbroj += pow(2, i);
  cout << zbroj << endl;
  char z; cin >> z;
  return 0;
}

[ danio @ 24.09.2005. 08:45 ] @

Nemoj ga slusati, odgovor je 18446744073709551615.

Evo vam link sa cijelom pricom.

I kao sto vidite ta prica nema nikakve veze sa izumom saha. Sah je izumljen u Indiji ili Kini jako davno. Zapravo tako davno da nitko nezna sigurno kad je izumljen, a pogotovo ko ga je izumio. Njavjerojatnije neki seljak koji se dosadjivao. Bas me zanima tko je izvrnuo tu legendu zato sto prvi put cujem da se radi o izumu saha...

Sto se tice odogovora, to nije nista drugo nego suma geometrijskog niza:

Code:

       63
      ---                63+1
      \     k      1 - 2     64
  S = /   2   = ---------- = 2  -1
     ---           1 - 2
     k=0

_{[Ovu poruku je menjao danio dana 24.09.2005. u 09:46 GMT+1]}

_{[Ovu poruku je menjao danio dana 24.09.2005. u 09:46 GMT+1]}

_{[Ovu poruku je menjao danio dana 24.09.2005. u 09:46 GMT+1]}

_{[Ovu poruku je menjao danio dana 24.09.2005. u 09:47 GMT+1]}

_{[Ovu poruku je menjao danio dana 24.09.2005. u 09:47 GMT+1]}

_{[Ovu poruku je menjao danio dana 24.09.2005. u 09:47 GMT+1]}

_{[Ovu poruku je menjao danio dana 24.09.2005. u 09:48 GMT+1]}

[ random @ 24.09.2005. 19:33 ] @

Danio, es podržava pisanje matematike na lakši način.

[ danio @ 24.09.2005. 19:49 ] @

Hvala, ubuduce cu to koristiti.

[ dinamozagreb @ 25.09.2005. 19:10 ] @

Citat:

danio: Tocan odgovor je 2^64-1.

Double nema problema sa pohranjivanjem toga broja:

Code:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    double a=1;

    a=pow(2.0,64.0)-1.0;

    cout<<a<<endl;

    system("PAUSE");

    return 0;
}

_{[Ovu poruku je menjao danio dana 24.09.2005. u 02:51 GMT+1]}

Lijepo izgleda rjesenje, samo meni compiler kaze: "a" is assigned a value that is never used in function main ()

[ danio @ 25.09.2005. 19:48 ] @

A sitnica. Radio sam neke druge eksperimente, pa mi je ostalo od prije.

Code:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    double a;

    a=pow(2.0,64.0)-1.0;

    cout<<a<<endl;

    system("PAUSE");

    return 0;
}

[ dinamozagreb @ 26.09.2005. 07:43 ] @

Citat:

danio: A sitnica. Radio sam neke druge eksperimente, pa mi je ostalo od prije.

Code:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    double a;

    a=pow(2.0,64.0)-1.0;

    cout<<a<<endl;

    system("PAUSE");

    return 0;
}

Sad radi, ali opet ispisuje rezultat u obliku 1.84467e+19

Ja bi htio da se rezultat ispise u cjelosti, znaci, 18446744073709551615.

[ tosa @ 26.09.2005. 08:55 ] @

Rezultat ne samo da nije tacan, nego i ne moze da se zapise u celosti u double.
Double kao i float, koristi priblizne vrednosti za zapis brojeva, mada je dosta precizniji
od float-a, nikada nece biti dovoljno precizan za ovakve racune.

[ danio @ 26.09.2005. 11:19 ] @

Rezultat je tocan, ali reprezentacija mozda nije onakva da bi zadovoljila svakoga.
Ako ti se to ne svidja probaj ovo:

Code:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    unsigned long long a=0;

    a--;

    cout<<a<<endl;

    system("PAUSE");

    return 0;
}

Rezultat je tocan.

[ NrmMyth @ 26.09.2005. 20:41 ] @

E pa nema tu lijeka, ni 64-bitni int ne moze spremiti taj broj u cijelosti, pa zato potrazi alternativni razred za rad sa velikim brojevima.

[ dinamozagreb @ 26.09.2005. 20:54 ] @

Citat:

NrmMyth: E pa nema tu lijeka, ni 64-bitni int ne moze spremiti taj broj u cijelosti, pa zato potrazi alternativni razred za rad sa velikim brojevima.

Nema lijeka ??

Evo vam rjesenja:

Code:

#include<stdio.h>
#include<math.h>
int main(){
double brojac=1;
for (int i=1; i<64; i++) brojac+=pow(2,i);
printf("\n Broj zrna je: %.0f",brojac);
return 0;
}

Program ispise rezultat 18446744073709551620, ( a pravo rjesenje je 18446744073709551615), sto mislim da je vrlo tocno za razliku od 1.84467e+19

[ danio @ 26.09.2005. 21:54 ] @

Zasto ne pogledate ovaj program koji sam gore napisao?! On ispisuje tocan rezultat! long long jest 64-bita. Ako napises sizeof(long long) dobit ces odgovor 8 bajta iliti 64 bita. Nazalost moj kompilator ne moze ici dalje i iskompilirati np. long long long, ali 64 bita je dovoljno, zato sto je odgovor na ovaj zadatak tocno najveca brojka koja stane u 64 bita. Naravno radi se o brojkama unsigned.

[ idb @ 27.09.2005. 09:57 ] @

Evo kako ja vidim resenje problema:

Code:

// Ivan Bulic, Dev-Cpp 4.9.9.1, Windows 2000
#include <iostream>
using namespace std;
int main(){
    unsigned long long suma = 1, p = 1;
    for (int i=0;i<64;i++){
        if (i>0){
            p *= 2;
            suma += p;
        }
        cout.width(3);    cout << i+1  <<"\t";
        cout.width(20);   cout << p    << "\t";
        cout.width(20);   cout << suma <<endl;
    }
    system("PAUSE");
    return 0;
}

Propusti dosadasnjih resenja su koriscenje tipa double i funkcije pow.
Tip double omogucava tacnost do nekih 15 cifara u rezultatu.
Znaci, bez obzira sto tip double moze da prikaze jos vece brojeve, neces moci da postignes tacan rezultat.
Cak i ako se uzme da je long double a; nece se dobiti dobar rezultat jer su argumenti funkcije pow tipa double.

Gornji primer daje na konzoli tezultat:

Code:

  1                        1                       1
  2                        2                       3
  3                        4                       7
  4                        8                      15
  5                       16                      31
  6                       32                      63
  7                       64                     127
  8                      128                     255
  9                      256                     511
10                      512                    1023
11                     1024                    2047
  .
  .
  .
56        36028797018963968       72057594037927935
57        72057594037927936      144115188075855871
58       144115188075855872      288230376151711743
59       288230376151711744      576460752303423487
60       576460752303423488     1152921504606846975
61      1152921504606846976     2305843009213693951
62      2305843009213693952     4611686018427387903
63      4611686018427387904     9223372036854775807
64      9223372036854775808    18446744073709551615
Press any key to continue . . .