Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 12-11-2010 12:41:03

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Arithméique et informatique 2

Toujours sur le même thème, voici quelques questions un peu différentes.
Petite définition pour ceux qui ne connaissent pas tout ça:
une fonction informatique est une liste d'instructions qui prend un ou plusieurs paramètres en entrée, et renvoie un résultat. Un peu comme en math: f(a,b,c,d)=e

1) Je souhaite écrire une fonction informatique pour savoir si un nombre est premier. Quelle instruction rapide pourrais-je écrire au début de ma fonction pour pouvoir traiter la moitié des cas très rapidement ?

2.1) Je souhaite écrire une fonction informatique pour savoir si un nombre est un carré parfait. Quelle instruction rapide pourrais-je écrire au début de ma fonction pour pouvoir traiter la moitié des cas très rapidement ?
2.2) Quelle autre instruction me permettrait d'éliminer encore plus de cas après la précédente ?

3) Je peux faire des boucles (répéter une série d'instructions plusieurs fois). Je n'ai pas le droit de faire de multiplication, comment calculer m*n ?

4) Pareil, je souhaite faire m/n (division euclidienne).



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 12-11-2010 14:04:35

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

arithmétique et infprmatique 2

1) on élimine les pairs
x & 1 = 0 : pas un premier

2.1) 00^2 = 10^2 = 00 et 01^2 = 11^2 = 01
On élimine les cas où le deuxieme bit de poid faible est nul
x & 2 = 1 : pas un carré
2.2)Pas d'idée


3) On fait la somme des 2^i*n pour les bits i de l'ecriture de m
1:  s = 0
2:  si m = 0 goto 8
3:  si m & 1 = 0 goto 5
4:  s = s + n
5:  n = n << 1
6:  m = m >> 1
7:  goto 2
8: suite

4) faire des soustractions de n a m jusqu'a atteindre 0
ça semble aussi trop trivial pour être la solution attendue

 #3 - 12-11-2010 19:10:25

gabrielduflot
Expert de Prise2Tete
Enigmes résolues : 34
Messages : 609

Arithmétique ett informatique 2

1) si a est pair et a différent de 2 alors a n'est pas premier
2) si le chiffre des unités est 2;3;7;8 alors ce nombres n'est pas un carré parfait
    si le chiffre des unités est 5 et que le chiffre des dizaines est différent de 2 alors ce nombre n'est pas un carré parfait
    si le chiffre des unités est 0 et que le chiffre des dizaines est différent de 0 alors ce nombre n'est pas un carré parfait
3) on fait une boucle m fois en rajoutant n a chaque fois m*n=n+n+.....+n
4) q:=0
tant que  m>n
faire m:= m-n et q:=q+1
m/n le quotient sera q et le reste sera le dernier m de la boucle

 #4 - 13-11-2010 00:45:12

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Arithmétique et informatiique 2

1) Je souhaite écrire une fonction informatique pour savoir si un nombre est premier. Quelle instruction rapide pourrais-je écrire au début de ma fonction pour pouvoir traiter la moitié des cas très rapidement ?

int prime( unsigned n)
{
  if (n==2) return(1);
  if ((n&1)==0) return(0);
  /* continuer avec  les nombres impairs */
}

2.1) Je souhaite écrire une fonction informatique pour savoir si un nombre est un carré parfait. Quelle instruction rapide pourrais-je écrire au début de ma fonction pour pouvoir traiter la moitié des cas très rapidement ?
2.2) Quelle autre instruction me permettrait d'éliminer encore plus de cas après la précédente ?

en hexadecimal tous les carrés se terminent par 0, 1, 4 ou 9. donc on peut commencer par tester la presence de 2, puis la presence de 12.
int issquare(int n)
{
  if (n&2) return 0;  /* elimine 8/16 */
  if ((n&12)==12) return 0; /* elimine 2/16 */
... continue a tester...
}
/* ou encore: */
int issquare(int n)
{
  if (n&2) return 0; /* elimine 8/16 */
  if ((n&5)==5) return 0; /* elimine 2/16 */
  if ((n&9)==8) return 0; /* elimine 2/16 */
... continue a tester...
}


3) Je peux faire des boucles (répéter une série d'instructions plusieurs fois). Je n'ai pas le droit de faire de multiplication, comment calculer m*n ?

union { long l; int x,y; } t;
long res;
char a;
long mul( int m, int n)
{
long res;
  res=0;
  t.x=n; t.y=0;
  for (a=0; a<16; ++a)
  {
    t.l<<=1;
    res<<=1;
    if (t.x&1) res+=m;
  }
  return(res);
}

4) Pareil, je souhaite faire m/n (division euclidienne).

union { long l; int x,y; } t;
char a;
int div( int m, int n)
{
  t.x=m; t.y=(m<0) ? -1 : 0;
  for (a=0; a<16; ++a)
  {
    t.l<<=1;
    if (t.y>=n) { t.y-=n; ++t.x; }
  }
  return (t.x);
}


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #5 - 13-11-2010 12:41:57

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

arithmétisue et informatique 2

Salut scarta,

Merci pour cette série.

1) La chose à plus rapide à éliminer ce sont les nombres pairs (sauf 2). Ce "sauf 2" m'ennuie: cela veut dire qu'il faut faire un test supplémentaire. Mais bon on élimine tout de même la moitié des cas. Pour tester les nombres pairs il suffit de tester le bit de poids faible du nombre. J'écrirais quelque chose du genre:

Code:

if ((n & 1) == 0 && n != 2) return;

Ce qui veut dire: si n est pair mais ne vaut pas 2 on ne continue pas l'évaluation. Il vaut mieux tester la parité en premier plutôt que l'égalité à 2, celle-ci ayant la plus forte probabilité.

2.1) On utiliser le résultat sur la congruence modulo 4 des carrés. Un carré ne peut être congru qu'à 0 ou 1 modulo 4 (0->0, 1->1, 2->0, 3->1, n+4->n). Si on considère donc les 2 derniers bits, il ne peuvent être que 00 ou 01. Le bit 1 vaut toujours 0.
Il suffit donc de rajouter un test comme celui-ci au début pour éliminer la moitié des cas (nombres congrus à 2 ou 3 modulo 4):

Code:

if ((n & 2) != 0) return;

(Le != 0 est facultatif mais c'est une bonne pratique de l'écrire)

2.2) Regardons les carrés modulo 8: 0, 1, 4, 1, 0, 1, 4, 1
Le test précédent a permis d'éliminer les congruences à 2, 3, 6 et 7 modulo 8 .
On voit qu'un carré n'est jamais congru à 5 modulo 8. On peut donc aussi éliminer ces cas:

Code:

if ((n & 7) == 5) return;

Est-ce à ça que tu pensais?

3) On se base sur l'écriture en base 2 (naturelle pour l'ordinateur) du multiplicateur.
On écrit: [latex]m=\sum{a_k2^k}[/latex] donc [latex]m.n=\sum{a_k(n.2^k)}[/latex]
Chaque ak est un chiffre en base 2 donc 0 ou 1.
On procède par "accumulation". On part de n. Si a0 vaut 1, on ajoute n à l'accumulation. On mutiplie n par 2 et on regarde a1 cette fois. Si a1 vaut 1 on ajoute 2n à l'accumulation et on multiplie n par 2 et on continue jusqu'à avoir épuisé les ak. On a donc calculé exactement: [latex]\sum{a_k(n.2^k)}[/latex] c'est-à-dire m.n.
La multiplication par 2 à chaque étape se fait par décalage à gauche d'un bit (opération élémentaire).
On choisit le plus grand nombre pour faire l'accumulation et on teste les bits du plus petit, cela permet de réduire encore le nombre de passes dans la boucle. Ici on a décomposé m, la complexité maximale est donc de l'ordre de log2(m) additions et décalages. Il faut faire attention à éviter le "débordement", c'est-à-dire un résultat trop grand pour être stocké dans un entier "informatique".
Voici un petit exemple de comment le faire. Pour des raisons de simplicité, je ne gère ni les signes, ni le débordement mais ce n'est pas difficile.

Code:

int mult(int m, int n)
{
  int r;
  if (m > n) // On échange m et n si nécessaire pour travailler sur le plus petit
  {
    int tmp;
    tmp=m; m=n; n = tmp;
  }
  r = 0; // On met l'accumulateur à 0
  while (m != 0)
  {
    if (m & 1) // Si le bit en cours d'analyse est non nul on ajoute n.2^k à l'accumulateur
      r += n;
    m >> =1; // On regarde le bit suivant de m (en fait décale m à chaque tour et on regarde toujours le bit 0)
    n <<= 1; // On multiple n.2^k par 2 pour passer a n.2^(k+1)
  }
  return r;
}

4) On utilise la aussi la décomposition en base 2. Mais cette fois-ci du quotient avant de le connaître. smile
On peut aussi dire que l'on fait exactement comme lorsque l'on pose la division de façon habituelle mais on le fait en base 2, pas 10 (ce qui oblige à bien comprendre ce que l'on fait quand on pose une division smile).
En fait on multiplie n par 2 jusqu'à ce que ça ne soit plus possible (jusqu'à ce que le multiple suivant soit plus grand que m).
C'était la phase d'initialisation. A partir de là on entre dans un boucle:

Si on peut soustraire n.2^k à m (n.2^k est <= m), on le fait, on obtient une nouvelle valeur de m et on écrit un chiffre 1 au quotient, sinon on écrit un chiffre 0 au quotient.
Dans les 2 cas, si k n'était pas déjà revenu à 0, on divise n.2^k par 2 (décalage à droite), on diminue k (pour savoir lorsqu'on doit arrêter, on peut aussi ne pas avoir besoin de k en tester n.2^k jusqu'à ce qu'il vaille le n initial)
J'ecrirai l'algo en C un peu plus tard, je dois partir...

 #6 - 13-11-2010 15:01:02

FifiCalin
Amateur de Prise2Tete
Enigmes résolues : 5
Messages : 5

Arithmétiuqe et informatique 2

if X mod 2 = 0 then NombrePremier=False

dim RacineCarré
RacineCarré=sqr(X)
if RacineCarré=int(RacineCarré) then CarréParfait=True

Function Multiplication (Valeur, Nfois)
dim i,Total
for i=1 to Nfois
    Total=Total+Valeur
next i
Multiplication = Total
end function

 #7 - 13-11-2010 21:56:17

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

arithmétique et ibformatique 2

Pour le moment, un seul carton plein (rivas, bravo à lui)

Pour les autres: je me vois mal faire m*n en ajoutant m à lui-même n fois... Je sais pas vous, mais moi si je dois faire par exemple 107894 * 3412512 sans calculatrice, j'ai un moyen super simple avec un papier et un stylo !
Et sinon, je ne l'ai pas précisé mais si la multiplication n'est pas autorisée, alors la division ne l'est pas non plus (et la racine carrée encore moins tongue)

 #8 - 13-11-2010 22:20:20

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Arithmétique et nformatique 2

c'est vrai que j'avais pas fait tres fort sur ce coup la.... je l'ai refait avec des shifts..
Evidement, pour la multiplication et la division, on suppose qu'un int a 16 bits et un long a 32 bits.
sinon, on peut transposer avec des longs a 32 bits et des long longs a 64 bits...
ou encore avec n'importe quelle taillede nombre, en ajustant les variables et le compteur.


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #9 - 15-11-2010 10:42:21

Yannek
Passionné de Prise2Tete
Enigmes résolues : 10
Messages : 60

Arithmétique et ifnormatique 2

(1) on renvoie si (n mod 2=0)  on renvoie faux si (n<>2) et vrai sinon.
(2.1) on renvoie faux si (n mod 4=2) ou (n mod 4=3)
(2.2) ??
(3)  somme=m, pour i=1 a n-1 faire somme=somme+m
(4) q=0, tant que (q*n<m) faire q=q+1.

 #10 - 15-11-2010 12:42:59

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Arithmétique et informtique 2

Bravo aux participants, et double bravo aux participants qui ont donné une ou des bonnes réponses smile Voici les miennes

1) SI (N&1 == 0) RENVOIE N==2
Explications:
Si un nombre est pair, alors il est premier s'il vaut 2.

2.1) SI (N&2 == 2) RENVOIE FAUX
Explications:
Soit un nombre n quelconque,
- si n est congru à 0 modulo 4, son carré aussi
- si n est congru à 1 modulo 4, son carré aussi
- si n est congru à 2 modulo 4, son carré est congru à 0 modulo 4
- si n est congru à 3 modulo 4, son carré est congru à 1 modulo 4
Conclusion: aucun carré n'est congru à 2 ou 3 modulo 4.
En base deux, un carré peut être congru à 00 ou 01 modulo 4 mais pas 10 ou 11.
Autrement dit, le deuxième bit en partant de la droite doit être nul, sinon ça n'est pas un carré

2.2) SI (N&7 == 5) RENVOIE FAUX
Explications:
On peut faire la même analyse que ci-dessus, pour remarquer que modulo 8, on n'autorise que 3 valeurs en base 2: 000, 001 et 100
N&7: N%8 en binaire.  Les différentes valeurs binaires modulo 8 sont
000 (ok),
001 (ok),
010 (éliminé au cas précédent),
011 (pareil),
100 (ok)
101 (éliminé car =5),
110 (éliminé au cas précédent),
111 (pareil)

3)Les x: correspondent à l'instruction n°x
1: resultat = 0
2: SI (m&1 <> 0) alors résultat += n
3: n <<= 1
4: m =>> 1
5: SI (m <> 0) alors retourner en 2

Explications (a+=b signifie a = a+b, a<<=b signifie a = a<<b et a>>=b signifie a = a>>b):
Comment pose-t'on une multiplication en base 10 ?

Code:

        abcde
      x  fghi
----------------
    (abcde*i)
 + (abcde*h)0
+ (abcde*g)00
....

En base 2, on peut faire pareil, mais c'est beaucoup plus simple: en effet, chaque chiffre vaut 0 (dans ce cas, n*0 = 0) ou 1 (dans ce cas, n*1=n)
Donc,
- on part d'un résultat nul
- si le chiffre considéré est 1, on ajoute n avec un certains nombres de zéros derrière (autant que d'étapes)
- on passe au chiffre suivant et on recommence tant qu'il en reste
Ici, "si le chiffre considéré est 1" correspond à "SI (m&1 <> 0)", et "n avec un certains nombres de zéros derrière (autant que d'étapes)" correspond à "n<<=1", autrement dit on ajoute 1 zéro à n à chaque étape (même si ça ne sert à rien pour ce coup-ci), ça nous évite d'avoir à le faire ensuite. Enfin, "on passe au chiffre suivant" correspond à "m>>=1" (en vrai, on supprime le dernier chiffre de m et on décale les autres vers la droite)
Pour des nombres sur 16 bits, faire m+m+m+m... n fois représente jusqu'à 65536 additions, ici 16 additions au maximum.

4) on veut faite n/m
1: resultat =0, m'=m
2: m' <<=1
3: SI (m'<n), alors retourner en 2
4: resultat <<=1
5: SI (m'>n), alors aller en 8
6: n -=m'
7: resultat |= 1
8: m'>>=1
9: SI (m' >= m), alors retourner en 4
(accessoirement, le reste de la division est n)
Explications:
Quand on pose une division en base 10, on regarde si on peut ôter le diviseur au dividende sur les premiers chiffres du nombres, et si oui combien de fois, puis on calcule le reste et on "descend" le chiffres suivant. Plus formellement, on regarde le plus grand n et le plus grand k tels que dividende > diviseur* k * 10^n, puis on calcule un nouveau dividende en lui otant "diviseur* k * 10^n", on écrit k pour le quotient (ou à la fin du quotient déjà trouvé), et on passe à 10^(n-1), on cherche le k suivant, etc...
Ici, c'est tout pareil, en base 2. Je rajoute plein de 0 derrière m jusqu'à avoir m>n. A ce moment là, je suis un cran trop loin mais c'est pas bien grave, on ajoutera juste 0 au résultat, donc ça change rien.
Ensuite, l'avantage de la base 2, c'est que notre k n'a que 2 valeurs possibles: 0 ou 1. Si c'est 0, alors m>n, donc on ajoute un 0 au résultat et on en barre un au diviseur (resultat <<=1 et m' >>=1). Si par contre c'est 1, alors m<n, donc je retranche m à n, j'ajoute un 1 au quotient et j'ôte le dernier chiffre du diviseur ( n-=m, resultat <<=1 et resultat |= 1  qui signifient "ajouter 1 au résultat" et m'>>=1)
Pour des nombres sur 16 bits, faire n-m-m-m-m-m q fois représente q soustractions (soit jusqu'à 65536, pour 65536 / 1) , ici 16 soustractions au maximum.

 #11 - 15-11-2010 12:52:45

RL
Visiteur

arirhmétique et informatique 2

1) passer n si n est pair (i.e. n/2=n\2 ou E(n/2)=n/2).

2.1) passer n si son dernier chiffre est 2, 3, 7 ou 8.

2.2) aucune idée d'instruction simple.

3) fonction (m*n) :
p:=0
de i=1 à n {
p:=p+m
}

4) fonction (m\n) :
d:=0
si m<n alors stop
si m=n alors d:=1 : stop
x:=0
boucle :
si x+n>m alors stop
d:=d+1
x:=x+n
fin de boucle

 #12 - 15-11-2010 13:21:46

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

arithmétique et informatiqur 2

Quel festival de langages...
On voit du Basic, du C, du Pascal et du pseudo-code...
enfin je crois...


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #13 - 16-11-2010 11:37:13

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

Arithmétiqu eet informatique 2

@scarta:

Merci pour cette rédaction.
Dans la division, si on inverse 6 et 7, on peut ajouter un optimisation en 6.5 en utilisant directement le bit de résultat à zéro de la soustraction pour arrêter dans ce cas...

A bientôt pour la suite? smile

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete