Suite de nombres

[Anonyme77]

Bonjour,

Je viens vers vous avec un petit challenge (qui est en fait également une question).
Je m'explique :

J'ai pris part à un concours de programmation dont l'énoncé était le suivant :
Soit X un nombre fixé par l'utilisateur, vous devez trouver le chemin le plus court démarrant 2 et allant vers ce nombre donné. Les opérations permises sont les suivantes : +2, -2, /2, *2.

J'ai fait ma propre méthode de résolution, mais je me demandais si, d'après vous, cette méthode est celle donnant le chemin (le nombre d'opérations à effectuer) le plus court.

La voici (pour ceux qui veulent tenter de résoudre le challenge évitez de lire ma résolution ) en C# :

static void Main(string[] args)
        {
            int x = 37;

            List<string> liste = new List<string>();

            if (x % 2 == 1)
            {
                x *= 2;
                liste.Add("*");
            }

            int y = 0;
            while (Math.Pow(2, y) < x) y++;

            int dist1 = (int)Math.Pow(2, y) - x;
            int dist2 = x - (int)Math.Pow(2, (y - 1));

            if (dist1 < dist2)
            {
                while (x < Math.Pow(2, y))
                {
                    x = x + 2;
                    liste.Add("+");
                }
            }
            else
            {
                while (x > Math.Pow(2, (y-1)))
                {
                    x = x - 2;
                    liste.Add("-");
                }
            }

            while (x != 2)
            {
                x /= 2;
                liste.Add("/");
            }

            for (int i = (liste.Count - 1); i >= 0; i--)
            {
                switch (liste[i])
                {
                    case "-":
                        Console.WriteLine("+");
                        break;
                    case "+":
                        Console.WriteLine("-");
                        break;
                    case "*":
                        Console.WriteLine("/");
                        break;
                    case "/":
                        Console.WriteLine("*");
                        break;
                }
            }
            Console.ReadLine();
        }

Veuillez m'excuser si le code n'est pas optimal, je l'ai écrit rapidement.
Dans cet exemple, le chiffre à atteindre (désigné par la variable x) n'est par exemple pas demandé à l'utilisateur mais bien fixé dans le code.

Pensez vous que cette méthode de résolution donne le résultat le plus court ?
Quelle est votre méthode pour ce problème ?

Merci beaucoup pour vos réactions.

[fred]

Bonsoir,

Pensez vous que cette méthode de résolution donne le résultat le plus court ?

Je ne sais pas, marche-t-elle dans tous les cas de figure ?

[Anonyme77]

Je pense que oui (même si je n'ai pas eu énormément de temps pour le tester) mais je ne suis pas certain que le résultat soit le plus court possible. Même si je dois bien avouer qu'en générale, je ne vois pas spécifiquement d'autres méthode que celle trouvée par l'algo.

As tu d'autres idées pour résoudre ce problème que de se référer à 2^x (méthode que j'utilise en fait) ?

[fred]

Je n'en ai absolument aucune idée, connais-tu le nom d'un algorithme pour faire ce genre de chose ?

Sinon, problème qui peut se passer, avec x=0 ?

[int80h]

Je pense qu'il faudra implémenter un algorithme de pathfinding pour que ce soit plus "académique".

Regardes du coté du A* par exemple.

Sinon en l'état ça me semble correct pour certains cas, mais ça ne donnera pas toujours le chemin le plus court pour tous.

[Anonyme77]

Que veux tu dire par un algo de pathfinding ?
Un algo récursif ?

Je dirais que le problème du récursif dans ce cas est celui du nombre de possibilités à tester.

Pourquoi penses tu que le chemin ne seras pas toujours le plus court par contre ?

[reader117]

B
Soit X un nombre fixé par l'utilisateur, vous devez trouver le chemin le plus court démarrant 2 et allant vers ce nombre donné. Les opérations permises sont les suivantes : +2, -2, /2, *2.

            if (x % 2 == 1)

            while (Math.Pow(2, y) < x) y++;

C'est pas un peu de la triche si tu utilise d'autres opérations que celles précisées dans les règles dans tes conditions ? Le challenge est intéressant en tout cas, j'y jetterai un oeil

[Anonyme77]

J'utilises d'autres opérations pour le bien de mes calculs mais les opérations utilisées pour se rendre d'un nombre à l'autre sont bien des opérations de +2, -2, *2 et /2.