[Défi] Je vous sers un petit algo ?

[Bisam]

Bon, l'année scolaire est finie ou presque... mais je sens que vous avez encore envie de vous lancer un petit défi.

Voici ce que je vous propose : répondez à la question 9 de ce sujet :

ce sujet

Je vous laisse une totale liberté sur le langage (ou pseudo-langage) utilisé du moment que l'algorithme écrit répond à la question.
Je laisse le sujet en entier car les autres questions peuvent vous aider à comprendre et vous inspirer.

Répondez directement sur le forum en utilisant la balise [code] et éventuellement la balise [spoiler] si vous ne voulez pas influencer les autres.

J'espère que ça vous plaira... bon courage.

PS : N'hésitez pas à mettre un petit mot juste pour dire si vous souhaitez participer... ou non.

[davidElmaleh]

Voila, ma réponse :

Show/Hide spoilerAfficher/Masquer le spoiler

Si j'ai bien compris, on doit carrément déterminer l'écriture de x en base 3 dans ce cas, voila mon code en TI-BASIC

Code: Select all

Define balance2(x)=
Func
Local bin,reste,i
reste:={}
bin:=""
While x≥3
  reste:=augment(reste,{mod(x,3)})
  x:=int(((x)/(3)))
EndWhile
reste:=augment(reste,{mod(x,3)})
For i,0,dim(reste)-1
  bin:=string(reste[i+1])&"*"&string(3^(i))&"+"&bin
EndFor
Return mid(bin,1,dim(bin)-1)
EndFunc


[Bisam]

J'ai bien peur, David, que tu n'aies lu un peu trop en diagonale... mais peut-être y a-t-il quelques éléments un peu compliqués dans l'énoncé.

Clarifions :
1) On appelle développement ternaire classique d'un entier

$mathjax$x$mathjax$

une écriture

$mathjax$x=t_0+t_1\times 3+t_2\times 3^2+\cdots+ t_n\times 3^n$mathjax$

pour laquelle tous les

$mathjax$t_k$mathjax$

sont égaux à 0, 1 ou 2.
2) On appelle développement ternaire balancé d'un entier

$mathjax$x$mathjax$

une écriture

$mathjax$x=b_0+b_1\times 3+b_2\times 3^2+\cdots+ b_n\times 3^n$mathjax$

pour laquelle tous les

$mathjax$b_k$mathjax$

sont égaux à -1, 0 ou 1.

La question 9) demande de trouver la liste des coefficients

$mathjax$(b_k)$mathjax$

d'un entier

$mathjax$x$mathjax$

donné, en suivant l'algorithme décrit un peu plus haut dans l'énoncé. La fonction doit simplement renvoyer une liste d'entiers.

[davidElmaleh]

ah.. je vois

[m@thieu41]

Sympa ça

J'arrive à faire les parties I et II (et la IV ), mais j'ai du mal à comprendre le rapport entre le système ternaire balancé et la partie III...

Je ne suis pas non plus sur de ce que demande la question 9. Tu dis

trouver la liste des coefficients (bk) d'un entier x donné, en suivant l'algorithme décrit un peu plus haut dans l'énoncé.

Mais n'est ce pas ce qui est demandé à la question 5 plutôt?

[Bisam]

La question 9) propose une autre façon de faire... (et la question 5 n'est pas guidée, de toute façon).

[m@thieu41]

Voici ma proposition (en python):

Show/Hide spoilerAfficher/Masquer le spoiler

Code: Select all

#On retourne la somme de la liste
def somme(l):
    s = 0
    for nb in l:
        s += nb
    return s

#la somme cumulée
def somCum(l):
    s = 0
    i = 1
    cum = [0]
    for nb in l :
        s += nb
        cum.append(s)
    return cum

#rajoute les poids pour que la balance bascule ou s'équilibre
def equilibre(cote, objectif):
    while somme(cote) < objectif:
        poidsCum = somCum(poids)
        i = n
        while poidsCum[i] + somme(cote) >= objectif and i > 0:
            i -= 1
        cote.append(poids[i])
        poids[i] = 0
       

def balance2(x):
    #on récupère les poids possibles
    global n
    n = 5
    i = 0

    global poids
    poids = []
   
    while i <= 5 :
        poids.append(3**i)
        i += 1

    #on équilibre chaque côté l'un après l'autre
    cote1 = [x]
    cote2 = []

    while somme(cote1) != somme(cote2):
        equilibre(cote2, somme(cote1))
        equilibre(cote1, somme(cote2))

    #on récupère la liste des bk
    cote1[0] = 0
    b = []
    i = 0
    while i <= n:
        if 3**i in cote1:
            b.append(-1)
        elif 3**i in cote2:
            b.append(1)
        else:
            b.append(0)
        i+=1

    print(b)


[davidElmaleh]

Voila donc ma réponse :

Show/Hide spoilerAfficher/Masquer le spoiler

Code: Select all

Define balance2(x)=
Func
:Local puis,lstbk,lstpuis,i,bk,j
:puis:=round(log(x,3),0)
:lstbk:={}
:lstpuis:={puis}
:bk:={}
:j:=1
:While x≠0
:  If x>0 Then
:    x:=x-3^(puis)
:    lstbk:=augment({1},lstbk)
:  ElseIf x<0 Then
:    x:=x+3^(puis)
:    lstbk:=augment({−1},lstbk)
:  EndIf
:  If x≠0 Then
:    puis:=round(log(abs(x),3),0)
:    lstpuis:=augment({puis},lstpuis)
:  EndIf
:EndWhile
:For i,0,lstpuis[dim(lstpuis)]
:  bk:=augment(bk,{when(i=lstpuis[j],lstbk[j],0)})
:  If bk[dim(bk)]≠0 Then
:    j:=j+1
:  EndIf
:EndFor
:Return bk
:EndFunc


[Bisam]

@David : il manque une valeur absolue dans ton premier calcul de logarithme... et il y aura une erreur si x est nul au départ.
Par ailleurs, si x est trop grand au départ, il peut y avoir une erreur dans le calcul du logarithme en base 3... et du coup tout l'algorithme est faussé. Il vaut mieux toujours travailler avec des entiers.
À part ça, ça a l'air de marcher.

@mathieu : En Python, il existe une fonction "sum" qui fait ce que fait ta fonction "somme"... Par ailleurs, tu n'aurais pas dû te limiter à n=5... vois ce que tu peux faire pour modifier cela.
Ceci étant, tu sembles doué pour écrire des algorithmes compréhensibles ! Bravo !

[m@thieu41]

Merci !

Voici mes algos q2/5/9:

Show/Hide spoilerAfficher/Masquer le spoiler

Code: Select all

#la suite u(n)
def u(n):
    return (3**(n+1) - 1) / 2


#q2
def ternaire(x, n = -1):
    #on cherche n si besoin
    if n == -1:
        n = 0
        while 2 * u(n) < x:
            n += 1

    #on écrit x en base 3
    t = []
    i = 0
    while i <= n:
        t.append(x % 3)
        x //= 3
        i+=1
    return t


#q5
def balance(x, n = -1):
    #on cherche n
    if n == -1:
        n = 0
        while -u(n) > x or x > u(n):
            n += 1

    #on écrit en ternaire balancé
    b = []
    for tk in ternaire(x + u(n), n) :
        b.append(int(tk - 1))

    return b


#q9

#la somme cumulée
def somCum(l):
    s = 0
    i = 1
    cum = [0]
    for nb in l :
        s += nb
        cum.append(s)
    return cum

#rajoute les poids pour que la balance bascule ou s'équilibre
def equilibre(cote, objectif):
    while sum(cote) < objectif:
        poidsCum = somCum(poids)
        i = len(poids) - 1
        while poidsCum[i] + sum(cote) >= objectif and i > 0:
            i -= 1
        cote.append(poids[i])
        poids[i] = 0
       

def balance2(x, n = -1):
    #On cherche n au besoin
    if n == -1:
        n = 0
        while -u(n) > x or x > u(n):
            n += 1
   
    #on récupère les poids possibles
    global poids
    poids = []
    i = 0
   
    while i <= n :
        poids.append(3**i)
        i += 1

    #on équilibre chaque côté l'un après l'autre
    cote1 = [x]
    cote2 = []

    while sum(cote1) != sum(cote2):
        equilibre(cote2, sum(cote1))
        equilibre(cote1, sum(cote2))
       
    #on récupère la liste des bk
    cote1[0] = 0
    b = []
    i = 0
    while i <= n:
        if 3**i in cote1:
            b.append(-1)
        elif 3**i in cote2:
            b.append(1)
        else:
            b.append(0)
        i+=1

    return b