Discussion :

[Sophie_26]

Bonjour.
Les programmes que je veux faire sont la multiplication et la division entière appliquées à des entiers infinis qui sont représentés par des séquences d'entiers à 4chiffres.
Il faut que en applicant mes programmes sur ces séquences d'entiers je retrouve le même résultat que quand je fais l'opération avec les entiers infinis à la main ou à la calculette....
C'est la prise de tête depuis une semaine.... quelqu'un peut-il m'aider ?

[gorgonite]

caml win n'existe pas...

OCaml ou CamlLight ?

ensuite, montres-nous le type qui définit tes entiers infinis, et les fonctions que tu as commencées, et expliques-nous où ça coince

à partir de là, on pourra t'aider

au passage connais-tu le module Num d'OCaml ?

[Sophie_26]

oui, c'est Caml Light 0.74

type int_inf == int list ;;
par exemple l'entier infini 1234567890 sera traité par le programme sous cette forme: [12;3456;7890] et 213000476530067 sous [213;4;7653;67].
La division entière 1234567890/213000476530067 = 5 à la calculette.
Le programme doit me trouver le même résultat en utlisant les séquences d'entiers. pour des séquences du type ([e],[f]) c'est simple c'est e/f... Mais quand y a plusieurs éléments je sais pas comment faire...
idem pour la multiplication.
(c'est clair comme ça ? )

[gorgonite]

je en comprends pas comment tu détermines la représentation des nombres...

pas ailleurs, j'aurais plutot fait une liste contenant les chiffres du nombre à représenté... ensuite, il faut voir les entiers comme des polynomes (1234 = 1*10^4 + 2*10^3 + 3*10^1 + 4*10^0) et appliqué la multiplication de Hörner

enfin je dis cela... mais tu fais comme tu le sens

[Sophie_26]

ben en fait (c'est des consignes pour un devoir) c'est nous qui donnons la séquence...
quand on fait une aplication on écrit Mult([12;3456;7890],[213;4;7653;67]), y a pas de programme pour transformer l'entier en séquence...

j'ai fait déjà l'addition par exemple...

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
let rec (Add : int_inf * int_inf  -> int_inf ) = function
([],[]) -> []
| ([],s) -> s
| (s,[]) -> s
| ([e],[f]) -> if (e+f)>=10000 
		then [1;e+f-10000] 
		else [e+f]
| (s,[f]) -> if (dernier(s)+f)>=10000 
			then ajd(ajd(debut(debut(s)),dernier(debut(s))+1),dernier(s)+f-10000) 
			else ajd(debut(s),dernier(s)+f)
| ([e],s) -> if (dernier(s)+e)>=10000 
			then ajd(ajd(debut(debut(s)),dernier(debut(s))+1),dernier(s)+e-10000) 
			else ajd(debut(s),dernier(s)+e)
| (s1,s2) -> if (dernier(s1)+dernier(s2))>=10000 
				then ajd(Add(ajd(debut(debut(s1)),(dernier(debut(s1))+1)),debut(s2)),(dernier(s1)+dernier(s2)-10000))
				else ajd(Add(debut(s1),debut(s2)),(dernier(s1)+ dernier(s2)));;

et ça donne:

#Add([12;3456;7890],[213;4;7653;67]);;
- : int_inf = [213; 17; 1109; 7957]
#

[gorgonite]

je ne comprends pas la logique d'une telle représentation... je vais donc avoir du mal à t'aider

[Jedai]

Que c'est laid tout ça... On est en fonctionnel que diable, un peu d'élégance !!
Par ailleurs je ne saisis pas la logique de l'ordre de la représentation. Si on l'inversait on pourrait faire les opérations nettement plus logiquement et avoir une récurrence terminale aisément.
Bon, l'addition :

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
let rnr num = 
  if num >= 10000 
  then let rest = num mod 10000
    in ( (num - rest) / 10000, rest )
  else (0, num)
 
let my_add l1 l2 = 
  let rec aux = function
  | ([],[]) -> (0,[])
  | (l,[]) -> (0,l)
  | ([],l) -> (0,l)
  | (h1::q1,h2::q2) -> 
    let (retenue, l) = aux (q1,q2)
    in let (next_retenue, result) = rnr (retenue + h1 + h2)
    in (next_retenue, result::l)
  in let (ret, res) = aux (l1,l2)
  in ret::res

Bon le nom des variables laisse à désirer, néanmoins je pense que tu admettras que l'algorithme employé est nettement plus clair dans cette version ?

La division... Rappelle-toi comment tu poses une division, et mimique le procédé.

EDIT : Il faut que les listes aient la même longueurs pour que cet algo marche... En fait plus j'y pense, plus je trouve bizarre que la représentation ne soit pas dans l'autre sens.

--
Jedaï

[Sophie_26]

c'est laid c'est laid... t'es marrant... je fais avec les moyens que j'ai... j'suis étudiante en maths... j'ai aucune ambition en informatique... j'utilise bêtement ce que les profs nous donnent....
ils nous disent ça:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
type int_inf == int list;;
(*on écrit le bit le plus significatif à droite ainsi 
  sera vu comme la liste 98987687667576 sera vu 
  [98;9876;8766;7576].
 
  0 est codé comme la liste [0] pas la liste vide !
  Un négatif est codé en mettant le digit de poids le plus fort négatif. 
  Par exemple -123456789012 se code par la liste [-1234;5678;9012]
  Attention  [123;0;67;43] se décode en 123000000670043 ne pas oublier les 
  0 intermédiaires car on travaille en base 10000. 
  *)

alors je fais quoi avec les moyens que j'ai (ceux utilisés pour mon Add-qui au passage marche très bien et j'en suis fière...)
J'ai pas compris la multiplication de Hörner...

[gorgonite]

J'ai pas compris la multiplication de Hörner...

si tu veux quelques indications... (c'est au milieu de la page, mais tu peux lire le reste )
http://www.labri.fr/perso/maylis/Alg.../polynome.html


ps:

[Sophie_26]

merci...
ça fait quoi cette balise code ?
dsl si la question est bête

[gorgonite]

merci...
ça fait quoi cette balise code ?
dsl si la question est bête

merci ça encadre le texte...

[Sophie_26]

ok merci.

J'ai compris la multiplication de Hörner. En fait c'est assez simple... enfin mathématiquement...
après j'ai du mal à écrire un programme avec.
Avec ces séquences: [12;3456;7890] et [213;4;7653;67] je devrais trouver, en faisant la multiplication classique: [2629;6354;8878;7193;3774;8630] (je fais ma multiplication 1234567890*213000476530067 puis je fais la séquence d'entiers à 4chiffres).
Mais je trouve pas ça du tout... je suis larguée.

[gorgonite]

hörner marche sur les polynomes... donc ta forme n'est pas correcte

[Sophie_26]

Voilà le programme Horner que j'essaie de faire:

Code :

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

1
2
3
4
5
let(Horner: int*int -> int) = function
(i1,i2) -> let a=int & b=int & c=int & d=int & e=int & f=int & g=int & h=int in
	let i1=a*10^3+b*10^2+c*10+d in 
		let i2=e*10^3+f*10^2+g*10+h in
	(e*a)*10^6+(f*a+e*b)*10^5+(g*a+f*b+e*c)*10^4+(a*h+g*b+f*c+e*d)*10^3+(b*h+g*c+f*a)-10^2+(c*h+g*h)*10+d*h ;;

[gorgonite]

deuxième fois

[Sophie_26]

Code :

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

1
2
3
4
5
let(Horner: int*int -> int) = function
(i1,i2) -> let int=a & int=b & int=c & int=d 
& int=e & int=f & int=g & int=h in 
	(i1=a*10^3+b*10^2+c*10+d & i2=e*10^3+f*10^2+g*10+h)
(e*a)*10^6+(f*a+e*b)*10^5+(g*a+f*b+e*c)*10^4+(a*h+g*b+f*c+e*d)*10^3+(b*h+g*c+f*a)-10^2+(c*h+g*h)*10+d*h ;;

Comment initaliser de nouveaux entiers pour arriver à ce que le programme prenne par exmple 0123 et arrive à le décomposer en 0*10^3+1*10^2+2*10+3 pour faire la multiplication de Hörner ?

[Sophie_26]

j'ai essayé autrement:

Code :

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

1
2
3
4
5
6
7
8
9
10
let(Horner: int list*int list -> int list) = function
(i1,i2) -> let 	( a==dernier(i1)
		& b==dernier(debut(i1))
		& c==premier(fin(i1))
		& d==premier(i1)
		& m==dernier(i2)
		& n==dernier(debut(i2))
		& o==premier(fin(i2))
		& p==premier(i2))
in [(m*a)*10^6+(n*a+m*b)*10^5+(o*a+n*b+m*c)*10^4+(a*p+o*b+n*c+m*d)*10^3+(b*p+o*c+n*a)-10^2+(c*p+o*p)*10+d*p] ;;

Pourquoi il me met ça ? :

Code :

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

1
2
3
4
Toplevel input:
>(i1,i2) -> let 	( a==dernier(i1)
>               	   ^^
Syntax error.

j'ai essayé avec un simple =, il veut pas non plus...
je craque...

[InOCamlWeTrust]

Teuuteuuteuuteuuteuu... bonne ambiance ici ! On est entre nous, il n'y a aucune réprimande !

c'est laid c'est laid... t'es marrant... je fais avec les moyens que j'ai... j'suis étudiante en maths... j'ai aucune ambition en informatique... j'utilise bêtement ce que les profs nous donnent...

Ah oui, mais ça, ça ne marche pas en programmation ! Si tu commences à faire de la programmation bêtement, sans te poser de questions, ça va pas aller... du tout !

La programmation, c'est le genre de truc qui n'est pas du tout scolaire : en clair, ça n'a rien à voir avec les autres enseignements et il faut faire marcher sa tête peut-être plus que d'habitude !

Même si tu ne veux faire que des maths, la programmation est aujourd'hui une étape quasi-incontournable... et faire du code, c'est difficile.

Pose bien ton problème, clairement, tranquilement, essaye de regarder comment faire la chose "avec les doigts" : à cette étape, ne regarde pas le problème d'un point de vue du code, mais uniquement d'un point de vue algorithmique. Transcris-le en termes de code, une fois "résolu".

C'est toujours comme ça que j'ai fait, et c'est ainsi que l'on peut résoudre simplement des problèmes compliqés (peut-être pas de façon optimale, mais résolus tout de même !).

[Sophie_26]

je suis dsl, mais quand on y comprend rien on s'accroche aux trucs donnés par les profs, à leurs exemples à ce qu'on a fait avec eux sur les machines... bref à ce qu'ils nous ont appris... moi j'ai pas assez confiance pour me risquer dans des trucs que je connais pas... ils m'ont donné des outils et une façon de faire, je m'y accroche... ça a parfaitement fonctionné pour l'addition et la soustraction...

Code :

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

1
2
3
4
5
6
7
8
9
10
let(Horner: int list*int list -> int list) = function
(i,j) -> let 	(dernier(i)=a
		&& b=dernier(debut(i))
		&& c=premier(fin(i))
		&& d=premier(i)
		&& m=dernier(j)
		&& n=dernier(debut(j))
		&& o=premier(fin(j))
		&& p=premier(j))
in [(m*a)*10^6+(n*a+m*b)*10^5+(o*a+n*b+m*c)*10^4+(a*p+o*b+n*c+m*d)*10^3+(b*p+o*c+n*a)-10^2+(c*p+o*p)*10+d*p] ;;

là je sais pas quoi faire... il me refuse en fait dernier(i)=a (dernier est "unbound") ou a=dernier(i) (erreur de syntaxe sur = ou ==)... pourtant la fonction (dernier: séquence -> dernier élément de la séquence) a été programmée par le prof et elle marche très bien dans mon addition et ma soustraction...

[InOCamlWeTrust]

je suis dsl, mais quand on y comprend rien on s'accroche aux trucs donnés par les profs, à leurs exemples à ce qu'on a fait avec eux sur les machines... bref à ce qu'ils nous ont appris... moi j'ai pas assez confiance pour me risquer dans des trucs que je connais pas... ils m'ont donné des outils et une façon de faire, je m'y accroche... ça a parfaitement fonctionné pour l'addition et la soustraction...

Mauvais raisonnement.

Ce n'est pas une question de confiance, mais une question de découverte et d'apprentissage : ce n'est pas parce que l'on a eu un cours magistral sur Caml que l'on sait programmer en Caml (moi j'ai mis quatre ans de dûr acharnement avant de maîtriser ce langage !).

Tu dois apprendre ce petit côté curieux qui te fera sortir des sentiers battus du cadre purement scolaire. Comme je le disais, tu n'es ni en cours de mathématiques ni en cours de physique.