Le chat palindrome

[C#] Algorithme de recherche de Palindrome mathématique

J’ai découvert récemment le projet Euler, site proposant de résoudre quelques problèmes mathématiques (environ 400 quand même). Ces problèmes sont à priori à résoudre grâce à quelques lignes de codes.
Le problème numéro 4 consiste à trouver le plus grand palindrome constitué du produit de deux nombres à trois chiffres.
Je vous invite bien sûr à rechercher par vous-même la solution avant d’aller plus loin…


L’énoncé complet du problème est
(en français)

Un nombre palindrome est un nombre qui peut être lu dans les deux sens. Le plus large palindrome constitué du produit de deux nombres à deux chiffres est 9009 = 91 x 99.
Quel est le plus grand palindrome constitué du produit de deux nombres à trois chiffres ?

(en anglais)

Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.
Find the largest palindrome made from the product of two 3-digit numbers.

Carré Sator d'Oppede
Exemple de Palindrome carré latin trouvé à Oppède le Vieux en France (84)

Voici l’algorithme que je vous propose :

        /// <summary>
        /// Compute the largest palindrome made from the product of two 3-digit numbers.
	/// Calcul le plus grand palindrom fabrique à partir du produit de deux nombres à 3 chiffres		
        /// </summary>
        /// <returns></returns>
        public static Palindrome ComputePalindrome()
        {
            Palindrome MyPalindrome = new Palindrome();
 
            for (int i = 999; i > 100; i--)
            {
                for (int j = 999; j > 100; j--)
                {
                    int produit = i * j;
 
                    //If product < Max Product then other product are lower
                    if (produit < MyPalindrome.Product)
                    {
                        break;
                    }
 
                    if (produit.ToString() == Reverse(produit.ToString()))
                    {
                        //Save Max Palindrome
                        if (MyPalindrome.Product < produit)
                        {
                            MyPalindrome.FactorA = i;
                            MyPalindrome.FactorB = j;
                            MyPalindrome.Product = produit;
                        }
                    }
                }
            }
 
            return MyPalindrome;
        }

La classe Palindrome étant juste un objet tout bête contenant les champs suivant :

    public class Palindrome
    {
        #region fields
        private int _FactorA = 0;
        private int _FactorB = 0;
        private int _Product = 0;
        #endregion
}



Bien sûr, ce code est optimisable pour des recherches de produit de grands chiffres. On peut, par exemple, vérifier la condition suivant laquelle les palindromes de chiffres pairs sont divisibles par 11. (Exemple 1221 = 11*111. D’ailleurs en l’occurrence pour cet exemple nous avons un joli palindrome : ‘111 * 11 = 1221 = 11 * 111’).

En l’occurrence la réponse au problème est 906609 = 993 * 913.
Vous pouvez aussi télécharger le programme de calcul : Palindrome.zip (C’est un exe, et il n’y a pas de virus 😉 )

Le chat palindrome mathématique
« Mon nom » est un palindrome. Tandis que mon nom n’en est pas un.

Résoudre cet algorithme est d’ailleurs proposé par la société Rail Concept (basé dans le Vaucluse) comme test de présélection d’embauche. Rail Concept est un bureau d’études ferroviaires,
Voici d’ailleurs quelques conseils pour réussir ce test :

  • Oubliez la pratique, n’utilisez que la théorie que vous avez apprise à l’école.
  • Les variables en CamelCase, ils n’aiment pas les autres types d’écriture de variables.
  • De l’anglais (après tout c’est une boite Française… C’est un autre débat mais je trouve dommage de tout développer en Anglais lorsque l’ensemble des développeurs parlent français ce qui engendre souvent des problèmes d’interprétation ou d’incompréhension du vocabulaire)
  • Du commentaire, mais pas trop. (J’ai cru comprendre que les commentaires pour générateur de chm sont à éviter).
  • Du MVC
  • Du test unitaire
  • De l’objet
  • Ré-instancié vos objets à chaque boucle (bof au niveau optimisation, heureusement que Monsieur Garbage Collector est là…) plutôt que de faire évoluer votre objet dans le temps.
  • Bref, prévoyez quelques heures de développement pour un algorithme qui en lui-même, par sa simplicité, ne mérite pas plus d’un quart d’heure. Mais bon le but est d’épater le recruteur non ? ;).

Voilà, si vous souhaitez travailler à proximité d’Avignon et postuler à un poste de développeur chez eux, sachez qu’ils cherchent quelqu’un en ce moment (septembre 2013). La société à l’air sympa et leurs projets très intéressant au niveau développement. Surtout s’ils arrivent à mettre en pratique ce qu’il demande pour le test de recrutement, ce que j’espère pour eux. En ce qui me concerne, je n’ai malheureusement pas encore rencontré de société dans ce cas…



Et pour aller plus loin je vous propose de lire :


Mots clefs liés à cet article:

  • palindrome

3 commentaires sur « [C#] Algorithme de recherche de Palindrome mathématique »

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.