babaorhum a écrit :En attendant j'ai fais tourner le basic-cgh sur mon Panasonic HHC de 1983 qui trouve fièrement les 6 valeurs en 12s et balaye les 1000 en 16,5s ... pas mal le papi-pocket !
As-tu essaye avec des variables entieres ? Il y a une syntaxe pour n'utiliser que des variables entieres en utilisant % apres le nom. Ainsi U devient U%. Avec mon algo, nous avons que des entiers compris entre 1000 et 9^3*3 soit 2187 donc dans la plage entiere des -32768..32767. Je pense qu'avec les variables entieres, on devrait aller un peu plus vite...
10 FOR C%=0 TO 9
20 FOR D%=0 TO 9
30 FOR U%=0 TO 9
40 T%=C%*100+D%*10+U%
50 Z%=C%*C%*C%+D%*D%*D%+U%*U%*U%
60 IF T%=Z% THEN PRINT "Nombre: ";T
70 NEXT U%
80 NEXT D%
90 NEXT C%
Toutes les machines a base de MS Basic ont des variables entieres HHC+MS BASIC, X-07,...
Il y a ceux qui voient les choses telles qu'elles sont et se demandent pourquoi, et il y a ceux qui imaginent les choses telles qu'elles pourraient être et se disent... pourquoi pas? - George Bernard Shaw J'adore parler de rien, c'est le seul domaine où j'ai de vagues connaissances ! - Oscar Wilde Ce n'est pas parce que les choses sont difficiles que nous n'osons pas. C'est parce que nous n'osons pas que les choses sont difficiles. - Sénèque
Comme je travaillais hier, j'ai pris un peu de retard. L'avantage est que je vais pouvoir m'inspirer de vos productions. Et comme il faut que quelques secondes à certaines machines pour afficher les résultats, je vais tenter de le faire en moins de 13 min sur mon pauvre et vieux matériel !
L'idée d'imbriquer trois ou quatre boucles me plait bien.
Mais par contre, il faut alors faire attention à ne pas refaire sans cesse les mêmes calculs, surtout dans la boucle principale.
Outre le fait que les valeurs p=i^3 peuvent être pré-calculées pour les nombre de 0 à 9 (surtout sur certaines machines lentes qui estime les puissances entière avec une expression du type p=exp(3.ln(i)) ou je ne sais quoi de transcendant.
Il y a aussi à tenir compte que pour un nombre N à, 4 chiffres a b c et d, calculer N=1000*a+100*b+10*c+d et S=a^3+b^3+c^3+d^3 revient à faire bien trop de calculs inutiles.
En effet, dans la boucle la plus interne parcourant par exemple d, les expressions 1000*a+100*b+10*c et a^3+b^3+c^3 sont en réalité des constantes.
Ensuite le test d'affichage d'un résultat valable revient à comparer deux sommes dont les termes sont positifs et parcourus de façon croissante. Il s'agit donc de comparer deux fonctions croissantes.
Il doit donc y avoir le moyen de simplifier le test (tout au moins de faire en sorte qu'il nécessite moins de calculs)
Utiliser les taux d'accroissement plutôt que les valeurs absolues.
Et surtout de ne pas parcourir toutes les quatre boucles imbriquées quand les taux d'accroissement (l'un est linéaire et l'autre cubique) vont rendre vaine toutes chances d'aboutir ;
Par exemple rien ne sert de tenter de trouver une solution pour a=4. En effet avec a=4, les entiers N sont dans l'intervalle [ 4000 5000 [ et les cubes des trois autres chiffres ne pourront totaliser plus de 3*9^3 = 729 c'est à dire que les valeurs S seront comprises dans l'intervalle [ 64 793 ].
Donc rien ne sert d'aller au-delà de a=3
Afin la boucle parcourant le dernier chiffre, est-elle bien nécessaire ?
Ne peut-on pas trouver la ou les valeurs de d qui conviennent à partir des valeurs N et S déduite du parcourt de la boucle du chiffre c ?
Car pour a,b et c fixés, le chiffre d doit être solution de l'équation N + d == S + d^3 où N et S sont les valeurs pour abc0
Ce qui revient à N-S == d.(d^2 - 1)
Les valeurs prises par d.(d^2 - 1) pour d variant de 0 à 9 sont 0, 0, 6, 24, 60, 120, 210, 336, 504 et 720
Donc, si N-S==0 lorsque l'on choisi le chiffre c, alors on sait que seront solutions les nombres abc0 et abc1 obtenus avec d=0 et d=1.
Sinon, rien sert de chercher un potentiel dernier chiffre si lorsque l'on a choisi le chiffre c, la différence N-S n'est pas un multiple de 6.
Vous l'aurez compris, je me réveille et je suis en pleine cogitation MPOesque
Modifié en dernier par C.Ret le 02 déc. 2015 18:13, modifié 1 fois.
Keeper a écrit :Hello
1 min 30 sur ma fx-8500G avec le code suivant (qui peut peut-être être optimisé en utilisant la fonction Isz, j'ai pas testé)[/code]
Sympa et original ce style !
Il manque quand même l'initialisation de C, D et U pour pouvoir lancer le programme.
Bizarre C D U ? On s'attendait à C D E ou autre A B C / X Y Z...
La 8500 est "rapide" comparée à mon pauvre PB-700...
<<
{ }
0 9 FOR I
I 100 * I 3 ^ -> A B <<
0 9 FOR J
A J 10 * + B J 3 ^ + -> A B <<
0 9 FOR K
A K +
B K 3 ^ +
IF OVER == THEN + ELSE DROP END
NEXT >>
NEXT >>
NEXT
>>
Je n'ai pas pu la tester sur une vraie hp48, par contre en émulation "authentic speed", la première version tourne en 81 secondes, la seconde version est deux fois plus rapide avec un temps d'exécution de 40,5 secondes.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Keeper a écrit :Hello
1 min 30 sur ma fx-8500G avec le code suivant (qui peut peut-être être optimisé en utilisant la fonction Isz, j'ai pas testé)[/code]
Sympa et original ce style !
Il manque quand même l'initialisation de C, D et U pour pouvoir lancer le programme.
Bizarre C D U ? On s'attendait à C D E ou autre A B C / X Y Z...
La 8500 est "rapide" comparée à mon pauvre PB-700...
Oui C D U comme Centaines Dizaines et Unités.
J'initialise les variables à 0 avec Mcl au lieu de faire 0->C, 0->D et 0->U
J'en suis à la mise au point d'un pgm pour HP-19c sans algorithme particulier - donc, pas très intelligent ni très vif. Le temps d'attente d'un quelconque résultat est très long ! Mais bon, c'est dimanche.
Ben c'est comme réaliser ce type de programme sur un SHARP PC-1211
Il faut pas être pressé.
Ma machine la plus véloce met 12.3s pour tester tous les entiers entre 0 et 3000.
Le même engin met 10.7s pour tester jusqu'à seulement 900.
Le dernier des entiers qui égale à la somme des cubes de ses chiffres, est trouvé dans les deux cas au bout de seulement 4.7s
10 DIM n%(4),d%(4),p%(9):FOR i=1 TO 9:p%(i)=i^3:NEXT:e%=1000:i=3: REM *** Initialisation et pré-calcul des cubes
20 n%(i)=n%(i+1)+e%*d%(i):s%(i)=s%(i+1)+p%(d%(i)):m=(n%(i)-d%(i))/6:
IF i>0 AND 6*m>i*p%(9) THEN 80 REM *** Calcul N S et sixième de la différence
30 IF i=1 THEN BEGIN REM *** Avant-dernier chiffre - solution possible?
40 IF m<0 OR m<>INT(m) THEN 70:ELSE d%(0)=.516685+SQRT(m):BEND REM *** si oui donner une première estimation
50 IF i>0 THEN e%=e%/10 : i=i-1 : GOTO 20 REM *** Boucle détermine tous les autres chiffres
60 if m<0 THEN 80 : ELSE IF m=0 THEN PRINT n%(0), REM *** Arrêt dernier chiffre ou affichage solution
70 d%(i)=d%(i)+1:IF d%(i)<=9 THEN 20 REM *** chiffre suivant sans dépasser 9
80 d%(i%)=0:e%=10*e%:i=i+1: if i<4 THEN 70 REM *** sinon remonter au précèdent
90 PRINT "." : END REM *** dernière ligne
C'est un bel exemple de BASIC en spaghettis !
Il s'agit de la version recherchant les entier jusqu'à 3000 (exclu)
Modifié en dernier par C.Ret le 31 oct. 2017 09:13, modifié 3 fois.
Bon, j'ai un peu triché en commençant sous 1000, mais à l'heure où j'écris, ça fait près d'une demi-heure que la 29c mouline - elle a tout de même trouvé 4 solutions. J'ai lancé la 19c environ 10 minutes après... je ferai un comparatif des temps respectifs demain, avec PAUSE sur la 29c, ça peut être intéressant.
Le programme, balourd bien sûr, comme l'algorithme :
9
9
9
STO 0
LBL 0
1
0
/
ENTER
FRAC
1
0
x
ENTER
ENTER
x
x
STO 1
Rd
INT
x=0?
GTO 9
1
0
/
ENTER
FRAC
1
0
x
ENTER
ENTER
x
x
STO+1
Rd
INT
x=0?
GTO 9
ENTER
ENTER
x
x
STO+1
LBL 9
RCL 0
RCL 1
x=y?
R/S (29c) PRx (19c)
DSZ
GTO 0
RTN
53 pas, 2 mémoires, soit 67 octets.
Ne me faites pas rougir en essayant de l'améliorer (mince, raté), c'est du brut.
La 19c semble plus lente... mais ça tient dans les trente-quarante minutes. (!) Ce sont tout de même des machines des années 70 !
zpalm a écrit :Sur HP Prime, moins de 3 dixièmes de seconde pour parcourir les nombres de 0 à 1000
Tellement rapide, que ça ne vaut même plus le coup de chercher à optimiser
N'empêche que j'ai aussi rapide qu'une HP Prime sur mon SHARP PC-1211 !
Sauf si j'allume l'imprimante, il me faut alors 3 secondes de plus qu'une HP Prime