Un challenge algorithmique pour 2013?

[askolein]

Serait ce possible d'avoir un nouveau challenge algorithmique ?

merci !

[csamborski]

Voilà un problème qui m'a l'air intéressant et permet de d'utiliser dans des algorithmes les nombres complexes que l'on est en train d'étudier.

Le problème consiste à vérifier si un point appartient à l'ensemble de Mandelbrot , l'utilisateur entrera les coordonnées.
L'ensemble de Mandelbrot ressemble à ceci : aperçu.
Cette figure est formée de points contenus dans le disque de centre (0;0) et rayon 2.
Elle est intéressante car il s'agit d'un fractale. M Colomban corrigera si besoin, mais il s'agit de figures qui gardent les même motifs quel que soit le niveau de grossissement.
En zoomant et se déplaçant sur la gauche on obtient ceci, voilà une autre animation

Un point M d'affixe z appartient à l'ensemble de Mandelbrot si le module $ |U_n| $ ne tend pas vers l'infini avec la suite (Un) définie comme suit :
$ \begin{cases}
U_0 = 0\\
U_{n+1} = U_n^2 + z
\end{cases} $

Voilà quelques aides :
Il a été démontré que si pour un certain n on a $ |U_n|>2 $ alors (Un) tend vers l'infini.
On peut calculer certains termes pour conclure.
Il peut être plus simple de calculer séparément la partie réelle et la partie imaginaire.

Pour aller plus loin, il est possible d'appliquer l'algorithme à une grille de points pour tracer l'ensemble.


Si certains cherchent d'autres algorithmes, la NASA a lancé un concours récemment : problème des longerons.

[askolein]

Mhh je vais m'y mettre merci

[sc]

Bonsoir,

Ca c'est un excellent challenge ! Et "M" vaut vraiment le coup d'oeil.
Voici un exemple de classe qui permet de dessiner des points sur un plan en java. Il reste à l'adapter pour créer des fractales !

Code: Tout sélectionner


import org.eclipse.swt.graphics.GC;
import org.eclipse.swt.widgets.Display;
import org.eclipse.swt.widgets.Shell;
import org.eclipse.swt.widgets.Button;
import org.eclipse.swt.SWT;
import org.eclipse.swt.widgets.Canvas;
import org.eclipse.swt.events.PaintEvent;
import org.eclipse.swt.events.PaintListener;
import org.eclipse.swt.events.SelectionAdapter;
import org.eclipse.swt.events.SelectionEvent;


public class Dessins_CANVAS {

        protected Shell shell;

       
       
        public static void main(String[] args) {
               
                Display display = new Display();

       
            Shell shell = new Shell(display);
            shell.setSize(751, 476);
            Button button = new Button(shell, SWT.PUSH);
            button.setLocation(50, 38);
           
           
           
           
            Button btnNewButton = new Button(shell, SWT.NONE);
            btnNewButton.setBounds(565, 416, 150, 28);
            btnNewButton.setText("Dessiner");
           
           
            Canvas canvas =  new Canvas(shell,SWT.NONE);
            canvas.setBounds(20, 10, 720, 400);

           
            final GC myGC=new GC(canvas);
           

         
                 
            btnNewButton.addSelectionListener(new SelectionAdapter() {
                @Override
                public void widgetSelected(SelectionEvent e) {
                        dessiner();
                        }
               
         
                private double xx(double X) {
                        double resultat=  4.*(X-720.)/720.+2;
                        return (resultat);
                        }
                 
                  private double yy(double Y) {
                                double ymax=400./720.*2;
                                double resultat= ymax-2.*ymax/400.*Y;
                                return(resultat);
                                }

                 
                  private void dessiner() {
                       
                                myGC.setBackground(Display.getDefault().getSystemColor(SWT.COLOR_CYAN));
                               
                            myGC.setForeground(Display.getDefault().getSystemColor(SWT.COLOR_GREEN));
                                for (int Y=0;Y<400;Y++) {
                                        for (int X=0;X<720;X++) {
                                        if (Math.pow(xx(X),2)+Math.pow(yy(Y),2)<1) {
                                            myGC.drawPoint(X, Y);      
                                        }
                                        }
                                   
                                }
                                myGC.setForeground(Display.getDefault().getSystemColor(SWT.COLOR_RED));
                                for (int Y=0;Y<400;Y++) {
                                        for (int X=0;X<720;X++) {
                                        if (Math.pow(xx(X),2)+Math.pow(yy(Y),2)<1./2.) {
                                            myGC.drawPoint(X, Y);      
                                        }
                                        }
                                   
                                }
                               
                               
                               
                  }
                 
               
               
            });
           
               

           
           
            shell.open();
            while (!shell.isDisposed()) {
              if (!display.readAndDispatch())
                display.sleep();
            }
         
        }
}

 

Pour l'instant cela donne :

img1.jpg (28.15 Kio) Consulté 10478 fois

A vous de le modifier pour obtenir dans un premier temps :

img2.jpg (24.21 Kio) Consulté 10498 fois

Puis dans un deuxième temps (en affectant une couleur égale au nombre d'itérations à effectuer pour que |un|>2):

img3.jpg (38.68 Kio) Consulté 10424 fois

A noter qu'en java, pour générer la couleur du GC, on utilise ce genre de syntaxe :

Code: Tout sélectionner


couleur=new Color(display, r,v,b);    // r,v et b compris entre 0 et 255
myGC.setForeground(couleur);
 

Enfin, dans un troisième temps, il pourrait être intéressant de rajouter un curseur pour paramétrer le nombre de couleurs (car plus il y a de couleurs et plus les calculs sont lents) et la possibilité de zoomer en cliquant sur la fenêtre.

img4.jpg (62.6 Kio) Consulté 10397 fois

A noter qu'un écouteur de clic sur le canvas, se programme ainsi :

Code: Tout sélectionner


 canvas.addMouseListener(new MouseListener() {
              public void mouseDown(MouseEvent e) {
              ...
               }
                public void mouseUp(MouseEvent e) {
               ...
                  }
                public void mouseDoubleClick(MouseEvent e) {
               ...
                }
            });
 

Foncez donc à la découverte de l'ensemble M de Mandelbrot

[askolein]

Je vais le faire ces vacances, parce qu'il faut se poser sur ce challenge




Merci beaucoup pour toutes les précisions !