Discussion :

[Twice22]

Bonsoir à tous

Voilà, j'aimerais créer un programme qui prend en argument a et b deux entiers et qui me renvoie un tableau remplit de b fois le nombre 1 et de a fois le nombre 0

Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
#proba 3 7;;
- : int list = [0; 1; 1; 1; 0; 0; 1; 1; 1; 1]

Alors j'ai réussi à créer une telle fonction mais elle est en O((a+b)²) en terme de complexité. La voici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let prob ng mh = (* n-gauche m-haut *)
	let t = make_vect (ng+mh+1) 0 in
		for i = ng to (ng+mh) do
			t.(i) <- 1
		done;
		for i = 1 to (ng-1) do
			t.(i) <- 0
		done;
t.(random__int (mh+ng));;
 
let proba ng mh =
	let v = make_vect (ng+mh) 0 in
	let rng = ref ng and rmh = ref mh in
		for i = 0 to (ng+mh-1) do
		if (prob (!rng) (!rmh)) = 1 then 
				(v.(i) <-1;
				rmh:=(!rmh - 1))
		else (v.(i) <-0;
			 rng:=(!rng - 1))
		done;
v;;

Je pense qu'une complexité en O(a+b) est impossible... Donc via la méthode diviser pour régner je souhaite obtenir une complexité en O((a+b)log(a+b)).

J'ai déjà créé une fonction qui renvoie un tableau de longueur n avec les (n-1) premiers entiers naturels dans le désordre via cette méthode, mais j'arrive pas à adapter le code pour avoir une fonction prenant 2 arguments et faisant ce que je souhaite.

Voilà la fonction que j'ai créé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#open "random";;
let hasard n =
	int n;;
 
let recol t u =
	let n1 = vect_length t in
	let n2 = vect_length u in
	let v = make_vect (n1 + n2) 0 in
	let pos_u = ref 0 and pos_t = ref 0 in	
	for i = 0 to (n1 + n2 - 1) do
		if (!pos_t < n1) then (* s'il reste des élts dans t*)
			begin
				if (!pos_u < n2) then (* s'il reste des élts dans u*)
				begin
				if (hasard 2)=0 then
					begin
						v.(i) <- t.(!pos_t); 
						pos_t:= !pos_t + 1;
					end
				else 
					begin
					v.(i) <- (u.(!pos_u) + n1); 
					pos_u:= !pos_u + 1;
					end
				end
				else (*s'il n'y a plus d'élt dans u*)
					begin
						v.(i) <- t.(!pos_t);
						pos_t := !pos_t + 1;
					end
			end
			else (* s'il n'y a plus d'élts dans t*)
				begin
				v.(i) <- (u.(!pos_u) + n1);
				pos_u := !pos_u + 1;
				end
	done;
	v;;
 
let rec permut_final n =
		if (n <2) then [|0|] else
			begin
				let m = n/2 in
				let t = permut_final m in
				let u = permut_final (n-m) in
				recol t u
			end;;

Si vous pouviez m'aider, je vous en remercie par avance.

[gasche]

C'est trop compliqué.

Crée ton tableau avec tous les 0 d'abord, puis tous les 1 ensuite, et après applique une fonction qui mélange uniformément les éléments d'un tableau. Ça s'écrit en temps linéaire (il y a des versions plus lentes et fausses); c'est très simple mais un peu subtil, c'est normal si tu ne connais pas l'algorithme. Je te conseille de chercher un peu, puis de demander si tu ne trouves pas.

Mon conseil pour les algorithmes utilisant le hasard et espérant avoir une distribution uniforme en sortie (en supposant que les fonctions random__int de la bibliothèque standard le sont): soit il est évident qu'elles sont bien uniformes, soit il faut considérer qu'elles sont fausses. Tous les "trucs bizarres" auxquels on pense en premier ont tendance à ne pas marcher.

[Twice22]

Merci à vous d'avoir répondu. Je m'excuse de mon premier post, je me suis rendu compte de ma bêtise une fois l'ayant posté, car un tableau remplit de 0 et de 1 aléatoirement m'est totalement inutilissable.

En effet il faut se replacer dans le contexte. J'ai déjà posté une question pour mon T.I.P.E : mouvement de foule. J'ai pas mal d'algorithmes, tout à l'air de fonctionner plus ou moins bien sauf que le programme est trop lent, il faut donc que je simplifie la complexité de certains sous-algorithmes.

Ainsi, j'ai créer une matrice dans laquelle il y a une sortie (par exemple de coordonnés (a,b)) et il y a un point aux coordonnées (x,y) représentant un personnages dans cette matrice. Le but étant de se déplacer le plus droit possible de (x,y) à (a,b) dans la matrice.

Ainsi j'avais pensé à créer un tableau rempli de 1 et de 0, à la lecture d'un 0 du tableau on se déplacerait suivant l'horizontal, à la lecture d'un 1 dans la matrice, on se déplacerait suivant la verticale. C'est pourquoi les algorithme prob et proba donnaient dans mon premier message permettaient de réaliser plus ou moins bien cette droite cependant il est en coût quadratique et même en O(n^3) puisque proba réutilise prob donc Proba est en O(n^2) et ensuite il faut encore lire les n cases du tableaux (O(n^3)).

Voici les algortihmes pour tester chez vous l'affichage graphique (on peut voir que cela fonctionne pas si mal...)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#open "graphics";;
let room = make_matrix 600 800 0;;
 
let dim room =
 let n = vect_length room in
  	if n = 0 then (0, 0) 
	else (n, vect_length room.(0));;
 
let prob ng mh =
	let t = make_vect (ng+mh+1) 0 in
		for i = ng to (ng+mh) do
			t.(i) <- 1
		done;
		for i = 1 to (ng-1) do
			t.(i) <- 0
		done;
t.(random__int (mh+ng));;
 
let proba ng mh =
	let v = make_vect (ng+mh) 0 in
	let rng = ref ng and rmh = ref mh in
		for i = 0 to (ng+mh-1) do
		if (prob (!rng) (!rmh)) = 1 then 
				(v.(i) <-1;
				rmh:=(!rmh - 1))
		else (v.(i) <-0;
			 rng:=(!rng - 1))
		done;
v;;
 
let fix_outline room =
	let (l,h) = dim room in
	for j = 0 to (l-1) do
		room.(j).(0) <- 2;
		room.(j).(h-1) <- 2;
	done;
	for i = 0 to (h-1) do
		room.(0).(i) <- 2;
		room.(l-1).(i) <- 2;
	done;
	for j = 280 to 320 do
		room.(j).(h-1) <- 0;
	done;
	for i = 28 to 45 do
		room.(l-1).(i) <- 0;
	done;
	for j = 80 to 140 do
		room.(j).(h-1) <- 0;
	done;
	for i = 700 to 750 do
		room.(l-1).(i) <- 0;
	done;
	for i = 0 to (h-1) do
		room.(200).(i) <- 2;
	done;
room;;
 
let room1 = fix_outline room;;
 
let translate_into_graph room (x,y) (a,b) = 	
open_graph " ";		
let mh = abs(y-b) in		
let ng = abs(x-a) in		
let xc = ref x in		
let yc = ref y in		
let t = proba ng mh in
	let u = vect_length t in	
let (n,p) = dim room in
	for i = 0 to (n-1) do	
    for j = 0 to (p-1) do		
	if (room.(i).(j) = 2) 		
	then begin 			
	set_color red;			
	plot j (n-i);		
	end		
	else if (room.(i).(j) = 2) 		
	then begin			
	set_color black;			
	plot j (n-i);		
	end	
    done;	
done;	
for i = 0 to (u-1) do	
	if t.(i)=1 then  begin	
	if (y > b) then (decr yc)
 else (incr yc);		
	set_color red;	
	plot (!xc) (n - !yc)	
		end		
	else if t.(i)=0 	
		then begin
	if (x > a) then (decr xc)		
	else (incr xc);		
		set_color black;	
		plot (!xc) (n - !yc);	
		end	
done;	
read_key();	
close_graph();;
 
translate_into_graph room1 (50,550) (799,300);;

Pour tracer le plus fidèlement cette droite de (x,y) à (a,b) j'avais pensé à faire ng = abs(a-x); mh = abs(b-y) qui donne le nombre de cases horizontales et verticales pour arriver au bout.
Si le pgcd(nh,mg) = 1 alors on ajoute +-1 à nh, mg de manière à ce que le nouveau pgcd =< 2 puis réitérer cela... jusqu'à obtenir par exemple : on se déplace de 3 cases selon l'horizontale et de 1 selon la verticale,
et de rajouter les +-1 manquants en déroulant l'algorithme dans l'autre sens. je pense que c'est un peu trop compliqué...

Si Vous pouviez me donner une piste pour créer un tel algorithme en O(n) au lieu de O(n^3) ce serait formidable. Merci par avance et excusez-moi si cela ne ressemble plus à la première question posée