program ternes;

{Epreuve informatique de l'Ecole Polytechnique ............... 94.290 


Les Tritons n'ont que trois doigts, c'est pourquoi ils n'utilisent que
trois chiffres {0,1,2} pour représenter les nombres, comme nous mais en 
base 3. Ainsi, pour eux, tout réel x*[0,1[ admet un développement 
"ternaire" :
                                                          k   
x = 0. u  u  u  u  ... u    u  u     ...  ==> x=SIGMA[u /3 ]           
        1  2  3  4      k-1  k  k+1                    k    
                                      *
avec u   in {0,1,2 }  quel que soit  k in N
      k


Exemple :   notre expression usuelle  pi/4 = 0.78539816....  
se traduit par                   pi/11 = 0.210012112... en langage triton

1  	Ecrire un programme Pascal capable de calculer le nombre x à 
        partir de la suite uk et réciproquement. 
        Le développement ternaire de x est-il toujours unique ?

        Application numérique : calcul et vérification des développements
        ternaires de   x=pi/4,  x=1/3,  x=Log(2),   x=1/8


2  	Les jeunes Tritons étudient à l'école l'opérateur ^ , tel que :

	0^0=0    0^1=2    0^2=1 
        1^0=2    1^1=1    1^2=0  
        2^0=1    2^1=0    2^2=2

        Programmer cette opération * dans l'ensemble {0,1,2}. 
        Est-elle commutative ? associative ? distributive par rapport à 
        l'addition modulo 3 ? ou l'inverse ?


3 	Les militaires Tritons utilisent pour coder leurs messages 
        secrets une fonction Y(x) définie sur l'intervalle [0,1[ de la 
        manière suivante :

	Soit v0 le développement ternaire de x. On définit par récurrence 
        la suite de développements ternaires v   où v   se calcule à partir
                                              j       j+1
        de v  de la manière suivante, en désignant par v   le k-ième 
            j                                           j,k

        élément du développement ternaire de vj  :

   		v     =v     ^ v        
   		 j+1,k  j,k     j,k+1        

	enfin Y(x) se calcule à l'aide du premier terme de chaque vj  par  
                      oo           j
		Y(x)=SIGMA[v   ,1/3 ]
                     j=1    j,1

	Exemple :   quand x= pi/4 , on obtient la suite vj suivante :

  	v0= 0.210012112...
        v1= 0.02020010...
	v2= 0.1111022...
	v3= 0.111212...
	v4= 0.11000...
    	...     
	
	où le résultat se lit en deuxième colonne de haut en bas :               

	Y(pi/4)= 0.20111...


	Ecrire un programme Pascal qui calcule Y(x) et trace son graphe. 
	N'est-il pas étonnant ?

4  	Montrer que lorsque p/q  est une fraction rationnelle,  Y(p/q) est 
	aussi une fraction rationnelle. 
	Calculer Y(p/q) pour de petites valeurs entières p<q.  

                                            -1 
5  	Quelle est la fonction de décodage Y  (x) ? 
	Est-elle partout définie sur [0,1[ ?


+------------------------------------------------------------+
¦              Imprimer tous les résultats                   ¦
¦     en indiquant chaque fois à quoi ils correspondent      ¦
+------------------------------------------------------------+

=====================================================================
}


uses modubase,crt;

const
     maxn=30;
type
    terne= byte;
    suite=array[0..maxn] of terne;

var
   u:suite;
   ternion:string;


function ternimal(u:suite):string;
var
   k:integer;
   s:string;
begin
     s:='0.';
     for k:=1 to maxn do
         s:=s+ternion[1+u[k]];
     ternimal:=s;
end;

procedure develop(x:real;var u:suite);
var
   k:integer;
begin
     for k:=0 to maxn do
      begin
         u[k]:=trunc(x);
         x:=(x-u[k])*3;
      end;
end;

function evaluer(u:suite):real;
var
   k:integer;
   x,k3:real;
begin
     x:=0;
     k3:=1;
     for k:=1 to maxn do
      begin
           k3:=k3/3;
           x:=x+u[k]*k3;
      end;
      evaluer:=x;
end;

function t(x,y:integer):integer;
begin
     if x=y then
        t:=x
     else
         t:=3-x-y;
end;


function f(x:real):real;
var
   k,j:integer;
   u,vj:suite;
begin
     develop(x,vj);
     for j:=1 to maxn do
      begin
           u[j]:=vj[1];
           for k:=1 to maxn-1 do
               vj[k]:=t(vj[k],vj[k+1]);
      end;
      f:=evaluer(u);
end;

procedure graphe;
const
     pas=0.0001;

var
   x:real;
   n:integer;
   k3:real;
   c:integer;
begin
     Efface;

     ModeGraphique;
     Couleur(vert);
     Isofenetre(-0.2,1.3,-0.05);
     x_axe(0,0,1);
     y_axe(0,0,1);
     Couleur(Jaune);
     For n:=0 to 9 do
         begin
              Deplace(0,n/9);Trace(1,n/9);
              Deplace(n/9,0);Trace(n/9,1);
         end;
     c:=0;
      k3:=1;
     repeat
      inc(c);
     Couleur(c);
     Couleur(Brillant);
     for n:=0 to 1000 do
       begin
            x:=n/1000;
           point(x,f(x/k3)*k3);
       end;
     k3:=k3*3;
 until false;
end;

begin
     InitGraphique;
     Graphe;
     Pause;
end.