Décomposer un entier en somme

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1115
Enregistré le: 30 Juin 2007, 01:31

Décomposer un entier en somme

par anthony_unac » 09 Mar 2016, 08:35

Bonjour,

Je cherche l'écriture d'un entier N sous la forme d'une somme de termes de la forme ϵ×k×10j où ϵ∈{−1,1}, k∈{1,2,4,8} et j∈N et pour laquelle le nombre de tels termes est minimal.

Exemples :
---------------
139 = 100+20+10+8+1 (réécriture brute en cinq termes)
139 = 100+40-1 (réécriture optimale en trois termes)

157 = 100+40+10+4+2+1 (réécriture brute en six termes)
157 = 200-43 = 200-40-2-1 (réécriture optimale en quatre termes)

87 = 80+4+2+1 (réécriture brute en quatre termes)
87 = 80+8-1 (réécriture optimale en trois termes)

38 = 20+10+8 (réécriture brute en trois termes)
38 = 40-2 (réécriture optimale en deux termes)

Le cas général d'un entier N mettons inférieur à 1 000 000 est il décomposable à la main ou cela nécessite t il l'outil informatique obligatoirement ?

Cordialement
Anthony



Robot

Re: Décomposer un entier en somme

par Robot » 09 Mar 2016, 09:59

Je suppose que c'est 10^j et pas 10j comme tu l'as écrit...

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Décomposer un entier en somme

par nodgim » 09 Mar 2016, 12:21

Pour un nombre de k chiffres, ta décomposition en n termes est telle que:
S'il y a p chiffres 1,2,3 ou 4 et q fois 0, alors n < 2(k-p-q) + p.

ça se fait assez bien à la main. Parfois, tu as 2 choix: prendre les 2 et continuer avec les 2 possibilités. Si tu as à nouveau 2 choix, les 2 te conduiront au même nombre. L'une des options sera alors peut être plus courte.

Exemple:
3737
1737 ou 263
737 ou 63
63 ou 23
il est clair que 737 n'est pas l'option minimale.
Donc
3737
263
63
23
3
1

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Décomposer un entier en somme

par nodgim » 09 Mar 2016, 14:16

On peut affiner n le nombre de décompo en ne retenant comme chiffre particulier que le 6.
Pour un nombre à k chiffres dont p "6" alors n < k + p + 1.
En prenant pour les chiffres:
1: complémentaire à 2 ou non.
3: complémentaire à 4
5 et 9: complémentaire à 10.
7: complémentaire à 8.

Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 21:39

Re: Décomposer un entier en somme

par chan79 » 09 Mar 2016, 14:43

salut
pour 3737, j'arrive à ça:
3737=4000-200-80+8+8+1
pour 999888
999888=1000000-100-10-2=1000000-200+80+8=1000000-100-20+8

SAGE63
Membre Relatif
Messages: 498
Enregistré le: 29 Nov 2014, 13:45

Re: Décomposer un entier en somme

par SAGE63 » 09 Mar 2016, 17:49

Bonjour

Votre problème de rappelle les cours de "mécanographie" que l'on pouvait suivre sur les machines à calculer de L'EPOQUE, la "ARITHMOMETRE d'ODHNER" : pour faire une multiplication, par exemple par 998 :on avait deux possibilités :

a) tourner 8 fois pour les unités, 9 fois pour les dizaine et 9 fois pour les centaines (attention au poignet, même au bout de d'une heure de cours)

b) ou alors 1 fois pour les milliers et 2 fois dans l'autre sens pour les unités.

c) les élèves avaient.............................vite compris le système ...................

Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1115
Enregistré le: 30 Juin 2007, 01:31

Re: Décomposer un entier en somme

par anthony_unac » 09 Mar 2016, 23:43

Robot a écrit:Je suppose que c'est 10^j et pas 10j comme tu l'as écrit...


Exact vous avez vu juste :perv:

Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1115
Enregistré le: 30 Juin 2007, 01:31

Re: Décomposer un entier en somme

par anthony_unac » 09 Mar 2016, 23:48

chan79 a écrit:salut
pour 3737, j'arrive à ça:
3737=4000-200-80+8+8+1
pour 999888
999888=1000000-100-10-2=1000000-200+80+8=1000000-100-20+8


Pour ma part je décomposerai 3737 comme suit :
3737 = 4(-2)(-6)(-3)=4000-200-40-20-2-1 (soit six termes au total)
Je ne fais donc pas mieux que vous qui proposez une décomposition en six termes au total également sauf que je m'affranchie d'aller chercher du 8.10^n :langue:

Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1115
Enregistré le: 30 Juin 2007, 01:31

Re: Décomposer un entier en somme

par anthony_unac » 09 Mar 2016, 23:56

SAGE63 a écrit:Bonjour

Votre problème de rappelle les cours de "mécanographie" que l'on pouvait suivre sur les machines à calculer de L'EPOQUE, la "ARITHMOMETRE d'ODHNER" : pour faire une multiplication,


Vous ne croyez pas si bien dire, c'est exactement de cela dont il s'agit à peine déguisé derrière tout ça : s'exercer à multiplier deux nombres sans utiliser les tables de multiplication.

Voici un petit exemple pour illustrer la chose :
Image

Vos machines de l'époque ainsi que votre enseignement (que certains qualifieront de rétrograde) me plaisent beaucoup et je suis frustré (moi le gamin de 1981 qui n'est connu que la casio fx92 collège) de ne pas avoir pu goûter un peu à cette douce époque (il faut dire que je suis un peu fâché avec l'époque actuelle).
Modifié en dernier par anthony_unac le 10 Mar 2016, 11:23, modifié 1 fois.

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Décomposer un entier en somme

par nodgim » 10 Mar 2016, 10:53

@ anthoni_unac: j'ai perdu par inadvertance ton MP avant de le lire. Si tu peux le réécrire. Désolé.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Décomposer un entier en somme

par fatal_error » 10 Mar 2016, 14:03

decomp.js
Code: Tout sélectionner
function nearest(n, arr){
    var d = n*n;
    var val = 0;
    for(var i = 0; i<arr.length; ++i){
        var dist = Math.abs(arr[i]-n);
        if(dist < d){
            d = dist;
            val = arr[i];
        }
    }
    return val;
}
/**
 * [decomp description]
 * @param  {Number} n      [description]
 * @param  {[Number]} digits [description]
 * @param  {[Number]} ops    [description]
 */
function decomp(n, digits, ops){
    ops = ops||[];
    n = ''+n;
    var first = n[0];
    var eligibles = digits.map(function(x){
        return x*Math.pow(10, n.length-1-(n<0));
    })

    var value = nearest(n, eligibles);
    ops.push(value);
    var left = n-value;
    if(left == 0){
        return ops;
    }
    return decomp(left, digits, ops);
}

var ops = decomp(process.argv.splice(2)[0], [-8,-4,-2,-1,1,2,4,8]);
console.log(ops)



node decomp.js 3737
[ 4000, -200, -80, 20, -4, 1 ]


idée:
pour 3737, je prends 3 (chiffre à gauche)
je prends le multiple de 1000 (le plus proche de 3000, parmi -8000,...8000)
ici, 4000.
je prends ce qu'il reste : 263
le plus proche est 200, etc
la vie est une fête :)

SAGE63
Membre Relatif
Messages: 498
Enregistré le: 29 Nov 2014, 13:45

Re: Décomposer un entier en somme

par SAGE63 » 10 Mar 2016, 14:37

Cette méthode de calcul était étudiée (dans "l'ancien" temps) en comptabilité pour calculer les intérêts.
Ces méthodes portaient le nom de :
* méthode des parties aliquotes du temps
* méthode des parties aliquotes du capital
* méthode des parties aliquotes des intérêts

MAIS……
On pouvait aussi transposer cette méthode pour calculer les prix du pain……..ou des croissants……………………..

Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1115
Enregistré le: 30 Juin 2007, 01:31

Re: Décomposer un entier en somme

par anthony_unac » 10 Mar 2016, 15:12

fatal_error a écrit:decomp.js

idée:
pour 3737, je prends 3 (chiffre à gauche)
je prends le multiple de 1000 (le plus proche de 3000, parmi -8000,...8000)
ici, 4000.
je prends ce qu'il reste : 263
le plus proche est 200, etc


Pourquoi pas, j'ignore si cette façon de faire nous donne systématiquement la décomposition "optimale" (celle qui minimise le nombre de termes), par contre le plus proche de 6 peut être aussi bien 8 que 4. Vous avez opté pour 8 pourquoi ?
Au final, vous aboutissez (vous aussi) à une décomposition de 3737 en six termes également. Je vais finir par croire que 3737 n'est pas décomposable en moins de six termes.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Décomposer un entier en somme

par fatal_error » 10 Mar 2016, 17:23

Vous avez opté pour 8 pourquoi ?

ben pour le coup entre 40 et 80, 63 est plus proche de 80.
maintenant si on avait eu 60, j'aurais choisi 40 (parce que dans le code on a un inférieur strict et que la distance mini aurait du coup été 20 et 80-60 n'est pas strictement inférieure à 20).
ca n'aurait rien changé quant au nombre de termes nécessaires.
la vie est une fête :)

Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1115
Enregistré le: 30 Juin 2007, 01:31

Re: Décomposer un entier en somme

par anthony_unac » 10 Mar 2016, 19:35

Si j'ai bien compris votre programme, il décomposerai l'entier 14159 sous la forme :
14159=10000+4000+100+80-20-1 (soit 6 termes)

alors qu'il est décomposable en cinq termes ainsi :
14159=142(-4)(-1)=10000+4000+200-40-1

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Décomposer un entier en somme

par nodgim » 10 Mar 2016, 20:38

On peut théoriser un minimum sur ce sujet.
Avec les chiffres 1,2,4 et 8, il est clair qu'on ôte un chiffre au nombre, et que le reste est inchangé.
159-100=59
Avec le 1, on a la possiblité en plus de changer le reste en faisant:
200-159=41.
41 est plus sympa que 59, car 41 se décompose en 2 termes 40 + 1, et pas 59.

Avec les chiffres 3 et 7, on ôte également 1 chiffre au nombre:
321=400-79
721=800-79
avec "retournement" du reste.

Avec le chiffre 5, on ne peut ôter un chiffre. 5 coûte donc non pas 1 terme, mais 2 termes.
Attention: suite à retournement, 5 devient 4, et vice versa. Un 4 peut donc coûter 2 termes le cas échéant. ça dépendra du nombre de retournements effectués.

Avec le chiffre 6, ce sera pareil (complémentaire: 3)

Le chiffre 0 ne côute rien, sauf si retournement, car son complémentaire 9 côute un terme. Pour des zéros consécutifs, seul le premier comptera pour un terme, même si retournement en 9.

Donc l'optimisation est à rechercher sur les options retournement qu'offrent les 1.

Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1115
Enregistré le: 30 Juin 2007, 01:31

Re: Décomposer un entier en somme

par anthony_unac » 10 Mar 2016, 22:42

nodgim a écrit:
Donc l'optimisation est à rechercher sur les options retournement qu'offrent les 1.


Et oui c'est exactement là que je voulais en venir et c'est ce qui rend la chose vraiment difficile. Au premier abord ça ressemble à un petit jeu mais au final derrière y a du lourd.
Je suis incapable à mon niveau de théoriser ça et je ne sais même pas si ça l'est réellement.
Si ça ne l'est pas, la décomposition d'entier grand (mettons supérieur à 10^10) risque d'être impossible à faire à la main.

Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 21:39

Re: Décomposer un entier en somme

par chan79 » 10 Mar 2016, 23:50

anthony_unac a écrit:
157 = 100+40+10+4+2+1 (réécriture brute en six termes)
157 = 200-43 = 200-40-2-1 (réécriture optimale en quatre termes)


Souvent plusieurs solutions
157=80+80+1-4

SAGE63
Membre Relatif
Messages: 498
Enregistré le: 29 Nov 2014, 13:45

Re: Décomposer un entier en somme

par SAGE63 » 11 Mar 2016, 00:44

Calculs des intérêts : METHODE DES PARTIES ALIQUOTES DU TEMPS


Exemple :

Calculez d'intérêt de 10 845 € en 83 jours au taux de 4 % l'an.

SOLUTION de l'AN 2016 :

10845 * 4 % * 83/360 = 100,015

(le temps passé "x" secondes.

SOLUTION (la date même sous la torture je ne dirais rien) de l'an 196., et à cette époque
on disposait uniquement :
* d'une feuille de papier
* d'un crayon
* d'une gomme
* et exceptionnellement une heure par semaine d'un calculatrice à manivelle...mais pas pour résoudre
les problèmes de mathématiques financières



Pendant un nombre de jours égal à la "base" de 90 jours,
le capital rapporte 1 % soit 108,45

Décomposons 83 j en parties aliquotes de 90 j, à chaque fraction de 90 j correspond,
en intérêts, la même fraction de 108,45

Nombre xxxxx Fraction xxxxx intérêts xxxxx Montant
de jours xxxxx xxxxx xxxxx calculs xxxxx intérets

45 xxxxx 1/2 xxxxx 108,45*1/2 = xxxxx 54,225
30 xxxxx 1/3 xxxxx 108,45 *1/3 = xxxxx 36,150
5 xxxxx 1/6 de 1/3 xxxxx 36,15*1/6 = xxxxx 6,025
3 xxxxx 1/10 de 1/3 xxxxx 36,15*1/10 = xxxxx 3,615
83 xxxxx xxxxx xxxxx xxxxx xxxxx 100,015

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

Re: Décomposer un entier en somme

par Doraki » 11 Mar 2016, 00:55

D'après mon programme il y aurait une stratégie optimale super simple, qui décide de quelles unités (1,2,4,8) on prend en regardant n mod 20 (une fois qu'on a décidé quelles unités on prenait, on divise le reste par 10 et on recommence)

La table :

0 mod 10 -> 0
1 mod 10 -> 1
02 mod 20 -> 2
12 mod 20 -> -8
03 mod 20 -> 3 (1+2)
13 mod 20 -> -7 (1-8)
4 mod 10 -> 4
05 mod 20 -> 5 (1+4)
15 mod 20 -> -5 (-1-4)
6 mod 10 -> -4
07 mod 20 -> 7 (8-1)
17 mod 20 -> -3 (-1-2)
08 mod 20 -> 8
18 mod 20 -> -2
9 mod 10 -> -1

Si je lis bien, ça revient à aller au multiple de 10 le plus proche, et si il y a égalité, aller à celui qui est un multiple de 20.

(il y a d'autres stratégies, il y a souvent plusieurs choix possibles mais ça risque vite de devenir compliqué si on veut la liste complète des décompositions optimales : par exemple je suis presque sûr (pas vérifié) qu'il n'y a pas de limite sur le nombre de chiffres à regarder pour obtenir les différents choix d'unités possibles)

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 46 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite