infoarena

infoarena - concursuri, probleme, evaluator, articole => Teme => Subiect creat de: ics ics din Noiembrie 09, 2007, 17:59:32


Titlul: conway game of life
Scris de: ics ics din Noiembrie 09, 2007, 17:59:32
pornind de la acest "joc" http://en.wikipedia.org/wiki/Conway's_Game_of_Life , am intalnit o problema care suna cam asa :

avand data o matrice (m*n) de cel mult 1000/1000 si o configuratie initiala a acesteia (vezi regulile jocului) cu celule vii, respectiv moarte, sa se afiseze matricea dupa generatia cu nr T (nu si generatiile intermediare).
problema de care m-am lovit este faptul ca acest T este putin cam mare (1.000.000) iar un algoritm de complexitate T*m*n ruleaza cam....mult  :oops:. pe google am dat doar de simulatoare,nu si de o sursa care sa-mi afiseze doar ultima configuratie.
daca s-a mai lovit cineva de pb asta si are o solutie,o sursa sau macar o idee, va rog sa-mi spuneti si mie. multumesc.

Titlul: Răspuns: conway game of life
Scris de: Cosmin Negruseri din Noiembrie 10, 2007, 02:13:43
Poti sa zici sursa problemei?

Proiectul asta http://golly.sourceforge.net/ are algoritmi rapizi de generare a configuratiilor din jocul mentionat de tine.

Este si un articol cu algoritmul in dr dobb's http://www.ddj.com/hpc-high-performance-computing/184406478 e scris de radeye (veteranii pe topcoder il stiu).

Titlul: Răspuns: conway game of life
Scris de: ics ics din Noiembrie 10, 2007, 11:38:37
Uite enuntul original al problemei. (La asta te-ai referit cand ai cerut sursa problemei nu?)

Titlul: Răspuns: conway game of life
Scris de: Cosmin Negruseri din Noiembrie 10, 2007, 11:43:22
Nu, intrebam de la ce concurs e. Sper ca nu e unul in desfasurare ...

Titlul: Răspuns: conway game of life
Scris de: ics ics din Noiembrie 10, 2007, 12:51:35
aa  :)...nu e vorba despre niciun concurs . e una dintre aplicatiile primite la facultate (sunt student in anul 1 la automatica)

Titlul: Răspuns: conway game of life
Scris de: Cosmin Negruseri din Noiembrie 10, 2007, 13:14:12
Misto, deci nu e un concurs e tema :) si eu care credeam ca vrei sa te ajut la ceva pt care trebuie sa te descurci singur :)

Oricum cerinta cu afisat pe ecran si citit de la tastatura pare sa faca limitele impuse putin dubioase :).

Titlul: Răspuns: conway game of life
Scris de: ics ics din Noiembrie 10, 2007, 16:55:50
chestia cu cititu de la tastatura e practic de forma (pentru ca inca nu s-a predat lucrul cu fisiere)..insa datele vor fi citite fortat dintr-un fisier (din command prompt : sursa.exe <fisier.txt ). so, exista vreo idee de la care sa plec pentru o rezolvare eficienta (=cu complexitate mai mica decat t*m*n) ?

Titlul: Răspuns: conway game of life
Scris de: Valentin Stanciu din Noiembrie 30, 2007, 22:23:45
Pana la urma ce algoritm ai implementat?
Dupa ce se corecteaza, sa ne spui si noua, poate ii ajuta si pe altii :)

Titlul: Răspuns: conway game of life
Scris de: Hulub Ionut-Adrian din Ianuarie 21, 2008, 19:52:05
asa ceva se face la facultate... eu am facut-o in clasa a 9-a fara vreo problema majora.....

Cod:
#include <fstream.h>
#include <stdlib.h>
#include <conio.h>

void citeste_fisier(int &, int &, int[20][20], int[20][20]);
void arata(int [20][20], int ,int);
void schimbare(int[20][20], int[20][20], int, int);

int main()
{
      int M[20][20], MOD[20][20];char x='n';
      register int c = 0;
      int i, y, n, m;
      citeste_fisier(n, m, M, MOD);
      arata(M, n, m);
      cout<<"Iesiti? (d/n) ";
      x = getche();
      cout<<'\n'<<'\n'<<'\n'<<'\n';
      if(x == 'd')
           return 0;
      while(x != 'd') {
              schimbare(M, MOD, n, m);
              arata(M, n, m);
              cout<<"Iesiti? (d/n) ";
              x = getche(); cout<<'\n';
              for(int lol = 0; lol < 3; lol++)
              cout<<'\n';
      }


      return 0;
}
void citeste_fisier(int & a, int & b, int M[20][20], int MOD[20][20]) {
     fstream f("start.in", ios::in);
     f>>a>>b;
     for (int i = 0; i < a; i++)
         for(int y = 0; y < b; y++) {
                 f>>M[i][y]; MOD[i][y] = M[i][y];
         }
     }

void arata(int M[20][20], int n, int m) {
     char x;
     static int contor = 0;

     cout<<"Pasul t + "<<contor<<"."<<'\n';
     for(int i = 0; i < n; i++) {
             for(int y = 0; y < m; y++)
                     cout<<M[i][y];
             cout<<'\n';
     }
     contor++;
     }

void schimbare(int M[20][20], int MOD[20][20], int n, int m) {
     int nr = 0;
     for(int i = 0; i < n; i++)
             for( int y = 0; y < m; y++) {
                  if(M[i-1][y-1] == 1)
                                 nr++;
                  if(M[i-1][y] == 1)
                                 nr++;
                  if(M[i-1][y+1] == 1)
                                 nr++;
                  if(M[i][y-1] == 1)
                                 nr++;
                  if(M[i][y+1] == 1)
                                 nr++;
                  if(M[i+1][y-1] == 1)
                                 nr++;
                  if(M[i+1][y] == 1)
                                 nr++;
                  if(M[i+1][y+1] == 1)
                                 nr++;
                  if(M[i][y] == 1) {
                             if (nr<2 || nr >3)
                                MOD[i][y] = 0; }
                  if (M[i][y] == 0)
                     if (nr==3)
                        MOD[i][y] = 1;
                  nr = 0;
               }

     for(int i = 0; i < n; i++)
             for(int y = 0; y < m; y++)
                     M[i][y] = MOD[i][y];
     }

afiseaza ceva de genul:
pasul t + x;
aici este matricea.
Doriti sa continuati? (d/n)

samd.

Titlul: Răspuns: conway game of life
Scris de: Savin Tiberiu din Ianuarie 21, 2008, 22:46:17
da pai algoritmul tau are complexitate o(N*M*T) ceea ce e prea mare ptr restrictiile problemei.

Titlul: Răspuns: conway game of life
Scris de: Hulub Ionut-Adrian din Ianuarie 21, 2008, 23:22:12

dar avand in vedere ca e spre a fi citit in consola la fiecare pas nu e nici o problema :D

Titlul: Răspuns: conway game of life
Scris de: HighScore din Ianuarie 22, 2008, 14:04:07
nu chiar ca si la acm citesti date din consola si asta nu afecteaza timpul de rulare...

Titlul: Răspuns: conway game of life
Scris de: Bogdan-Cristian Tataroiu din Ianuarie 22, 2008, 17:27:18
chiar daca citesti de la consola se pot redirectiona fisiere in stdin
Cod:
./program < fisier.in > fisier.out

sau se pot folosi pipe-uri
Cod:
cat fisier.in | ./program

Titlul: Răspuns: conway game of life
Scris de: Hulub Ionut-Adrian din Ianuarie 22, 2008, 19:54:17
ceea ce vreoiam sa zic este ca oamenii nu percep diferente in timpul re rulare de ordinul milisecundelor asa ca nu conteaza care este complexitatea.

Titlul: Răspuns: conway game of life
Scris de: Adrian Diaconu din Ianuarie 22, 2008, 20:11:05
Iar ce incercau Bogdan si Razvan sa zica era ca se pot sesiza aceste diferente cu ajutorul calculatorului.

Cod:
time ./program < fisier.in > fisier.out

Titlul: Răspuns: conway game of life
Scris de: Savin Tiberiu din Ianuarie 22, 2008, 21:25:47
si un program cu o complexitate aprox de 1000*1000*1000000 poate dura destul de mult, ore intregi (daca nu si mai mult).


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines