Griglia infinita di uni e di zeri...

Ecco il codice.

Testo nascosto, fai click qui per vederlo

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>


int nMinX, nMaxX, nMinY, nMaxY;
int **p;
int setcall = 0;

typedef struct { int xl, xr, y, dy; } LINESEGMENT;

#define MAXDEPTH 10000

#define PUSH(XL, XR, Y, DY) \
if( sp < stack+MAXDEPTH && Y+(DY) >= nMinX && Y+(DY) <= nMaxY ) \
{ sp->xl = XL; sp->xr = XR; sp->y = Y; sp->dy = DY; ++sp; }

#define POP(XL, XR, Y, DY) \
{ --sp; XL = sp->xl; XR = sp->xr; Y = sp->y+(DY = sp->dy); }

int GetPixel(int x, int y) {
return p[x][y];
}

void SetPixel(int x, int y, int c) {
p[x][y] = c;
setcall++;
}

// Fill background with given color

void SeedFill_4(int x, int y, int new_color)
{
int left, x1, x2, dy;
int old_color;
LINESEGMENT stack[MAXDEPTH], *sp = stack;

old_color = GetPixel(x, y);
if( old_color == new_color )
return;

if( x < nMinX || x > nMaxX || y < nMinX || y > nMaxY ) {
puts("Border");
return;
}

PUSH(x, x, y, 1); /* needed in some cases */
PUSH(x, x, y+1, -1); /* seed segment (popped 1st) */

while( sp > stack ) {
POP(x1, x2, y, dy);

for( x = x1; x >= nMinX && GetPixel(x, y) == old_color; --x )
SetPixel(x, y, new_color);

if( x >= x1 )
goto SKIP;

left = x+1;
if( left < x1 )
PUSH(y, left, x1-1, -dy); /* leak on left? */

x = x1+1;

do {
for( ; x<=nMaxX && GetPixel(x, y) == old_color; ++x )
SetPixel(x, y, new_color);

PUSH(left, x-1, y, dy);

if( x > x2+1 )
PUSH(x2+1, x-1, y, -dy); /* leak on right? */

SKIP: for( ++x; x <= x2 && GetPixel(x, y) != old_color; ++x ) {;}

left = x;
} while( x<=x2 );
}
}

int main(int argc, char *argv[]) {
// dimensione del reticolo
int d = 1000;
// numero di prove
int iter = 100;
double res[iter];

nMinX = 0;
nMaxX = d-1;
nMinY = 0;
nMaxY = d-1;

p = new int*[d];
for (int i=0; i<d; i++) {
p[i] = new int[d];
}

// inizializza il generatore random
srand(time(0));

double s = 0, ss = 0;

for (int n = 0; n < iter; n++) {
// inizializza il reticolo con dati random fra 0 e 1
for (int i=0; i<d; i++) {
for (int j=0; j<d; j++) {
p[i][j] = rand() % 2;
}
}

setcall = 0;

SeedFill_4(d/2, d/2, 1 - GetPixel(d/2, d/2));

printf("%7d,", setcall);
res[n] = setcall;
s += setcall;
double s2 = setcall;
ss += s2 * s2;
}

double m = s / iter;
double var = (ss - s*s / iter) / (iter - 1);
//printf("\nSomma = %f, Somma quad = %f\n", s, ss);
printf("\nMedia = %f, varianza = %f\n", m, var);
}

Ecco il codice.

Ti è difficile postare un file testo contenente la griglia ( 0, 1 ) delle 100 simulazioni da te effettuate ?

Mi è piu' facile lavorare su una "base dati comune" anzichè verificare il tuo codice.

Ultima modifica di Umby il 03/01/2011, 21:49, modificato 1 volta in totale.

Ehm, si tratta di griglie 1000x1000...

Per quel che può servire, ti posso postare l'output del programma:

181, 1, 4, 9, 3, 5, 2, 734, 2, 97,
128, 58, 2, 43, 4, 943, 1347, 5, 9, 795,
216, 38, 810, 123, 25, 305, 135, 145, 1181, 72,
26, 2, 127, 34, 29, 177, 3, 34, 22, 50758,
157, 25, 2, 8, 878, 18, 115, 5, 89, 67,
3, 47272, 20, 11, 446, 30, 4, 30, 23, 487,
367, 25, 12, 7, 52, 238, 7707, 479, 98905, 14,
11, 119, 52, 48, 10, 123, 16, 5, 13, 7,
1, 50, 3, 21240, 246, 23, 15, 52, 359, 28,
2916, 1, 1, 19, 1947, 136, 8, 37, 4, 15,

Media = 2436.350000, varianza = 146774187.340909

Sono in effetti sospetti i valori molto elevati (>10000); dovrei dare un'occhiata per vedere se ci sono problemi al bordo.

Quei lavori elevati sono effettivamente errati; aumentando la dimensione della griglia (e dunque la probabilità di finire al bordo) tendono a sparire.

Questi i risultati con griglia 2000x2000:

7, 1, 2412, 327, 9, 52, 28, 185, 1, 4,
19, 4291, 44, 56, 3, 15, 145, 1, 89, 8,
12, 20, 9, 8, 12, 3, 7, 20, 1, 1734,
2, 31, 6, 18, 5, 5507, 124, 1126, 15, 22,
1, 28, 58, 74, 12, 25, 2271, 1, 39, 277,
164, 365, 23, 130, 733, 37, 1, 229, 48, 56,
9, 4, 1682, 45, 8, 20, 2, 27, 132, 25,
14, 14, 119, 1, 117, 43, 8, 9, 3, 1,
408, 430, 5, 11, 155, 129, 60, 15, 38, 35,
54, 568, 11, 5, 680, 1, 75, 109, 67, 4,

Media = 260.940000, varianza = 629606.218586

E questi con griglia 3000x3000:

65, 5236, 110, 5, 170, 241, 8, 14, 22, 16,
51, 1, 70, 4, 550, 17, 10, 9, 1, 45,
64, 139, 1067, 1, 74, 82, 129, 30, 82, 10,
8, 1, 65, 7, 1, 79, 20, 6, 116, 1,
14, 4, 9, 3080, 689, 16, 1935, 48, 72, 48,
46, 10639, 335, 61, 22, 14, 1, 3, 30, 1,
581, 235, 8, 36, 5, 446, 12, 2187, 689, 32,
62, 20, 4237, 47, 11, 7, 8, 4, 267, 773,
1002, 73, 650, 7, 78, 1, 30, 3551, 203, 1,
10, 68, 122, 1, 1309, 56, 41, 6, 63, 35,

Media = 426.680000, varianza = 1799858.745051

Mi viene in mente una distribuzione binomiale (di Bernoulli), considerando un cammino di \( \displaystyle n \) passi con probabilità di continuare pari a \( \displaystyle 1/2 \) con infiniti lanci... risulta che il valore atteso di quella area sia \( \displaystyle \infty \) anche perchè il valore atteso della binomiale è un minorante del valore che l'area percorribile.

Non credo sia corretto: la binomiale si può applicare (ed è quello che hai fatto tu) per calcolare il valore atteso del numero di celle dello stesso colore di quella iniziale (che in una matrice infinita è difatti ovviamente illimitato), ma in questo caso conta anche come sono disposte le celle di uno stesso colore e di conseguenze che la cella j sia raggiungibile non dipende solo dal colore della cella stessa e di conseguenza gli eventi "la cella j è raggiungibile" NON sono indipendenti tra loro.

Ehm, si tratta di griglie 1000x1000...

Non importa la grandezza.
Se riesci a generare il file, zippandolo (si tratta di un file testo) ottieni un valore di compressione molto alto

Sono in effetti sospetti i valori molto elevati (>10000); dovrei dare un'occhiata per vedere se ci sono problemi al bordo.

Perchè ritieni sospetti questi valori elavati !!!
Secondo me, è normale che ci siano .... anzi, piu si va avanti più è facile "continuare"

Mi spiego meglio: è più facile che la "catena" si spezzi all'inizio che non dopo.

Secondo me, è normale che ci siano .... anzi, piu si va avanti più è facile "continuare"
Mi spiego meglio: è più facile che la "catena" si spezzi all'inizio che non dopo.

Mi sembra sensato: più aumenta il perimetro della "marea nera" e più è improbabile contenerla

fu^2: l'area "dovrebbe essere" (con elevata probabilità) finita perchè la tua matrice è binaria (consentimi questa accezione
per indicare che è composta solo dai numeri uno e da zero) e random (cioè avente una distribuzione CASUALE degli elementi)

dunque supponi che ogni pixel ha probabilità 0.5 di essere bianco e 0.5 di essere nero. Parlare di distribuzioni ha completamente senso.

In una dimensione l'area è limitata con probabilità uno, in dimensione due secondo me è falso come ho già detto.

In una dimensione l'area è limitata con probabilità uno, in dimensione due secondo me è falso come ho già detto.

Cercavo di definire il problema così (e in questo modo mi muoverei per una eventuale dimostrazione), senza usare matrici predefinite in dimensione:
- la cella iniziale ha 4 adiacenti ognuna con $p=1/2$ di essere dello stesso colore, quindi ha un valore atteso di 2 celle adiacenti dello stesso colore;
- le celle adiacenti a queste sono 8, ma se considero il valore atteso di prima sono 5 (6 a seconda della configurazione), essendo sempre $p=1/2$ ho valore atteso di 2 (3) celle dello stesso colore;
- le celle adiacenti a queste sono 12, già le configurazioni si complicano ma credo si possa calcolare il valore atteso;

e possiamo proseguire, magari cercando una formula ricorsivamente utilizzabile.

Quindi è logico aspettarsi una varianza elevata dell'area, così come (sembra) è logico aspettarsi una area mediamente grande (infinita?). Magari dopo provo a fare un algoritmo.