Figuras de Lichtenberg

Neste arquivo iremos colocar os problemas já resolvidos (não são problemas "mortos" porque a discussão pode continuar a qualquer altura!)

Figuras de Lichtenberg

Mensagempor jap em Domingo Jul 29, 2007 6:23 pm

As figuras de Lichtenberg são estruturas fractais que resultam de descargas eléctricas no interior de materiais isoladores.

Vejam aqui o vídeo: :D

http://www.youtube.com/watch?v=FWOst4VwwEU

O que é giro é que é possível simular computacionalmente estas figuras usando um modelo conhecido como DLA...

Diffusion limitted aggregation

... o que me deu + uma ideia para um problemazito para o pessoal que gosta de programação... :D
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6805
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Mensagempor vbmaster em Domingo Jul 29, 2007 7:11 pm

Weeee!

Venha ele!

Era bom é que mais pessoal do quark se dedicasse à programação, o Ivo tem de começar a treinar...
Avatar do utilizador
vbmaster
up-Quark!
up-Quark!
 
Mensagens: 464
Registado: Quarta Nov 15, 2006 11:49 pm
Localização: Peniche

Mensagempor jap em Domingo Jul 29, 2007 9:19 pm

Bom, o algoritmo é o seguinte.

Considera uma grelha (array) de, digamos, 1000 x 1000.

Coloca uma partícula no centro da grelha (podes utilizar 1 para notar uma posição ocupada, 0 para desocupada).

Repete:

Coloca uma nova partícula numa posição aleatória da grellha. Se a posição já estiver ocupada, tenta de novo gerar uma outra posição aleatória.

Move a partícula aleatoriamente na grelha com um salto de uma unidade (à sorte para cima, baixo, esquerda ou direita). Se ao lado da partícula já existir outra, gera um númerto aleatório entre 0,0 e 1,0; se esse número for superior ap (podes fazer p = 0.75) a partícula fica "agarrada" e o processo recomeça gerando nova partícula. Caso contrário, continua o movimento aleatório até que a partícula fique agarrada ou saia fora da rede.

Este algoritmo repete-se (GOTO repete) um número grande de vezes, digamos 50000.

Vê no final qual a forma da figura das partículas que ficam agarradas à rede! :D
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6805
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Mensagempor vbmaster em Terça Jul 31, 2007 5:42 pm

Bem, este demorou um bocado mais porque ontem apanhei sol a mais na cabeça e não fiquei lá muito bem. :P

Aqui vai o código:

Código: Seleccionar Todos
#include <iostream>
#include <cstdlib>
#include <time.h>
using namespace std;

float grelha[1000][1000];

void preenche ()
{

  //preenche a grelha com 0 e 1 no centro

  for (int a = 0; a < 1000; a++)
    for (int b = 0; b < 1000; b++)
      {
        if ((a == 499) && (b == 499)) grelha[a][b] = 1.0;
        else grelha [a][b] = 0.0;
      }
}

int agarra ()
{
  //obtem-se a posiçao aleatória da partícula
  int px=0, py=0;
  px = rand () % 999;
  py = rand () % 999;

  if (grelha[py][px] >= 1E-6)
    {
      //caso a posiçao esteja ocupada chama-se de novo a agarra ()
      return 1;
    }
  else
    {
      if ((grelha[py+1][px] >= 1E-6) || (grelha[py-1][px] >= 1E-6) || (grelha[py][px-1] >= 1E-6) || (grelha[py][px+1] >= 1E-6))
        {
          //se ao seu lado se encontrar uma particula

          float value;
          value = rand () % 1000001;
          value /= 1000000;

          if (value > 0.75)
            {
              //se o valor aleatorio for superior a 0.75 essa posiçao toma esse valor

              grelha[py][px] = value;
            }
          else
            {

              //caso contrario chama-se de novo a agarra()

              return 1;
            }
        }
      else
        {

          //caso posiçao nao tenha nada ao lado, é chamar de novo

          return 1;
        }
    }
  return 0;
}

void mostra ()
{
  for (int a = 0; a < 1000; a++)
    {
      for (int b = 0; b < 1000; b++)
        {
          cout << grelha[a][b] << " ";
        }
      cout << endl;
    }
}

int main ()
{
  preenche ();
  srand((unsigned)time(NULL));
  for (int a = 0; a < 50000; a++)
    {
      if (agarra () == 1) a--;
    }
  mostra ();
  return 0;
}




E aqui vai um possível resultado:

ftp://ftp.ua.pt/incoming/lol/lol
Avatar do utilizador
vbmaster
up-Quark!
up-Quark!
 
Mensagens: 464
Registado: Quarta Nov 15, 2006 11:49 pm
Localização: Peniche

Mensagempor jap em Terça Jul 31, 2007 10:13 pm

Obrigado, Miguel pela tua resposta rápida ao meu desafio! :D


Numa leitura rápida do código, acho que há um pequeno problema: onde está codificado o passo em que a partícula, quando não fica agarrada, dá um passo aleatório para a esquerda, direita, cima ou baixo? Isto não foi codificado, pois não? Basta tirar um número à sorte entre 0 e 3 e associar 0- esquerda, 1 - direita, etc...

Só depois de a partícula ficar agarrada ou sair fora do array é que se gera uma nova partícula numa posição à sorte!

Abraço,
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6805
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Mensagempor vbmaster em Terça Jul 31, 2007 10:58 pm

Ah, pela minha leitura do problema não era isso que tinha percebido.

Realmente não é isto que se pretende, vou corrigir.
Avatar do utilizador
vbmaster
up-Quark!
up-Quark!
 
Mensagens: 464
Registado: Quarta Nov 15, 2006 11:49 pm
Localização: Peniche

Mensagempor vbmaster em Quarta Ago 01, 2007 1:33 pm

Bem, este foi um dos problemas mais tricky de codar... tive de andar para aqui a fazer fluxogramas que já estava a atrofiar (sim, não quis usar goto's :P). Cheguei ontem a postar uma solução e após 40 minutos na cama vir cá remover por ter visto que estava mal. :P

Aqui vai o código (demora uns 10 minutos a processar):

Código: Seleccionar Todos
#include <iostream>
#include <cstdlib>
#include <time.h>
using namespace std;

float grelha[1002][1002];
int px=0, py=0,gap=0;

void preenche ()
{

  //preenche a grelha com 0 e 1 no centro

  for (int a = 1; a < 1001; a++)
    for (int b = 1; b < 1001; b++)
      {
        if ((a == 500) && (b == 500)) grelha[a][b] = 1.0;
        else grelha [a][b] = 0.0;
      }
}

int agarra ()
{
  if ((px > 1000) || (py > 1000) || (px < 1) || (py < 1))
    {
      return 0;
    }
  else
    {
      if (grelha[py][px] >= 1E-6)
        {
          //se a posicao actual ja estiver ocupada gera de novo posicao
          return 2;
        }
      else
        {
          if ((grelha[py+1][px] >= 1E-6) || (grelha[py-1][px] >= 1E-6) || (grelha[py][px-1] >= 1E-6) || (grelha[py][px+1] >= 1E-6))
            {

              //se a casa ao lado estiver ocupada

              float value;
              value = rand() % 1000001;
              value /= 1000000;

              if (value >= 0.75)
                {
                  //se o valor gerado for superior a 0.75
                  grelha[py][px] = value;
                  return 0;
                }
              else
                {
                  //caso contrario sorteia um salto espacial e corre de novo
                  gap = rand () % 4 + 1;

                  switch (gap)
                    {
                    case 1: px++; break;
                    case 2: px--; break;
                    case 3: py++; break;
                    case 4: py--; break;
                    }
                  return 1;
                }
            }
          else
            {
              //caso contrario sorteia um salto especial e corre de novo
              gap = rand () % 4 + 1;

              switch (gap)
                {
                case 1: px++; break;
                case 2: px--; break;
                case 3: py++; break;
                case 4: py--; break;
                }
              return 1;
            }
        }
    }
}

void mostra ()
{
  for (int a = 1; a < 1001; a++)
    {
      for (int b = 1; b < 1001; b++)
        {
          cout << grelha[a][b] << " ";
        }
      cout << endl;
    }
}

int main ()
{
  bool test = true;
  preenche ();
  srand((unsigned)time(NULL));
  for (int a = 0; a < 50000; a++)
    {
      if (test == true)
        {
          px = rand() % 999;
          py = rand () % 999;
        }
      switch (agarra())
        {
        case 0: test = true;break;
        case 1: a--; test = false; break;
        case 2: a--; test = true; break;
        }
    }
  mostra ();
  return 0;
}



Há ali código repetido, podia usar uma função, mas acho que não interessa...


Possível resultado:

ftp://ftp.ua.pt/incoming/lol/lol
Avatar do utilizador
vbmaster
up-Quark!
up-Quark!
 
Mensagens: 464
Registado: Quarta Nov 15, 2006 11:49 pm
Localização: Peniche

Mensagempor jap em Quarta Ago 01, 2007 9:49 pm

Miguel,

Obrigado, mais uma vez, pelo teu empenho no programa! :hands:

Infelizmente, não consigo aceder ao output que colocaste no servidor de FTP. :?
Mas não te preocupes, eu sacarei o código fonte e compilarei aqui o programa. :D Mas não sei se terei tempo de analisar o teu programa hoje, uma vez que ainda tenho de ultimar a minha viagem de amanhã. Assim, se não disser nada hoje, fica combinado que voltarei ao assunto logo que regressar de férias. Pode ser?

Abraço,
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6805
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Mensagempor vbmaster em Quarta Ago 01, 2007 10:35 pm

Na boa.

Por acaso nunca me tinham eliminado algo do ftp tão cedo...

Anyway, cá está de novo:

ftp://ftp.ua.pt/incoming/lol/lol
Avatar do utilizador
vbmaster
up-Quark!
up-Quark!
 
Mensagens: 464
Registado: Quarta Nov 15, 2006 11:49 pm
Localização: Peniche

Mensagempor hexphreak em Quarta Jan 09, 2008 11:00 pm

Não resisti a ressuscitar uma thread com um problema de simulação :D São os meus problemas preferidos, passo a vida metido nos arquivos da ACM à procura deles... Anyway, o meu código demorou 13 minutos, mais coisa menos coisa, num PIII (onde eu tenho o Linux). Suponho que neste M740 demoraria 8-10 minutos :)

http://hexquark.pastebin.com/d16f41548 (as tags de código portam-se mal :? )

Bem sei que é o meu próprio código, mas acho que ficou bastante bem. Podia ter ficado ligeiramente mais elegante com numeração sequencial da grelha, mas depois não podíamos verificar se tinha saído. A imagem é linda (e espero que correcta), gostava de vos mostrar mas até conseguir acordar um dos idlers no IRC para me emprestar o servidor vão mesmo ter de o correr :P


P.S.: A macro é só porque programo sempre em linhas de 75 caracteres, que é a resolução do tty sem X.
Avatar do utilizador
hexphreak
top-Quark!
top-Quark!
 
Mensagens: 1959
Registado: Segunda Nov 05, 2007 8:52 pm
Localização: Maia/Porto

Mensagempor vbmaster em Quarta Jan 09, 2008 11:12 pm

Por aqui deu SegFault.

Deve ser do Mac OS X.
Avatar do utilizador
vbmaster
up-Quark!
up-Quark!
 
Mensagens: 464
Registado: Quarta Nov 15, 2006 11:49 pm
Localização: Peniche

Mensagempor hexphreak em Quarta Jan 09, 2008 11:15 pm

Oh diabos :roll: Estás a usar o gcc? A mim também me dá segfault na primeira compilação, mas compilando outra vez já funciona, é bastante esquisito :? Também não consigo descobrir onde estará o bug, consegues ver algum out-of-bounds nos índices?
Avatar do utilizador
hexphreak
top-Quark!
top-Quark!
 
Mensagens: 1959
Registado: Segunda Nov 05, 2007 8:52 pm
Localização: Maia/Porto

Mensagempor jap em Quarta Jan 09, 2008 11:16 pm

vbmaster Escreveu:Por aqui deu SegFault.

Deve ser do Mac OS X.


A mim também deu, no Linux. Viva o C e as violações de memória! :D
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6805
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Mensagempor jap em Quarta Jan 09, 2008 11:18 pm

hexphreak Escreveu:Oh diabos :roll: Estás a usar o gcc? A mim também me dá segfault na primeira compilação, mas compilando outra vez já funciona, é bastante esquisito :? Também não consigo descobrir onde estará o bug, consegues ver algum out-of-bounds nos índices?


:shock: .

A mim dá-me sempre o mesmo erro na primeira, segunda, ..., compilações, como deveria ser, aliás . Bem, não necessariamente, com ponteiros marados... :roll: é de esperar tudo. :P
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6805
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Mensagempor hexphreak em Quarta Jan 09, 2008 11:45 pm

Ok experimentem esta versão. Parece que de vez em quando o array fica em zonas sensíveis, tive de criar uma margem de segurança à volta :) Funcionou de todas as vezes aqui, espero que aí também! (Agora vou dormir que véspera de aulas não é altura para arranjar código)
Avatar do utilizador
hexphreak
top-Quark!
top-Quark!
 
Mensagens: 1959
Registado: Segunda Nov 05, 2007 8:52 pm
Localização: Maia/Porto

Próximo

Voltar para Problemas resolvidos

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 1 visitante

cron