Un défi poétique !?

6 septembre 2024 : Avant de passer à toute discussion sur le problème lui-même, voyons l'histoire. Un défi, un défi mathématique ouvert dans un livre.
Un vieux livre de 1984 dans la bibliothèque, dont j'ai oublié le nom mais j'ai eu une image d'un problème très intrigant qu'il présente dans la section "Plus à lire...".
Une, euh, une énigme poétique... Oui, vous avez bien entendu, un problème de mathématiques qui est écrit sous la forme d'un poème en vieil anglais.
Depuis le lycée, je ne suis plus du tout fan des Poèmes, mais celui-ci a retenu mon attention. En le lisant, j'avais l'impression d'avoir compris quelque chose mais je ne l'ai pas complètement compris. Passer plus de six heures à comprendre une énigme issue d'une fable, de dragons et ainsi de suite. Mais une chose m'a coincé, les pierres précieuses. Pour que vous compreniez bien voici le poème :

**Dans les terres infinies et merveilleuses de Zopraria, où les étoiles fredonnent sereinement,

Et d'anciens dragons gardent les cieux, où le temps et les marées ne font qu'un,

Un vieux sage sage vivait tranquillement, dont la connaissance s'étendait sur tous les temps,

Dont les mains pourraient tisser les fils de la magie comme les poètes créent des rimes.

Un jour, depuis les hauteurs du ciel, sur des ailes de feu et d'or,

Un don descendu au sage, comme le racontent les mythes et légendes :

Un vaste trésor de gemmes rayonnantes, comme des fragments d'étoiles,

Pourtant lié à la propre prophétie du destin, avec des règles aussi vieilles que Mars.

Le ciel lui murmura un message doux mais clair :

"Divisez ces pierres précieuses lumineuses en deux, avec un cœur et une oreille prudents.

Laissez vos deux récipients fabriqués supporter un poids si presque partagé,

Cette harmonie entre eux demeure, dans un équilibre brillant et juste.

Mais écoutez-nous, sage, si un match parfait est perdu au-delà de vos connaissances,

Ne désespérez pas dans votre quête, car votre voyage ne se terminera toujours pas.

Car même si l'équilibre penche, le changement peut être léger,

Les cieux te souriront encore et les bénédictions couleront librement. »

Le sage, au cœur à la fois courageux et sage, commença son épreuve sacrée,

Façonner des vaisseaux proches de la même chose et donner le meilleur aux étoiles.

Les dragons tournaient au-dessus, tandis que les anges s'arrêtaient en vol,

Car dans cette tâche d’équilibre se trouve une vérité aussi pure que la lumière.

Les pierres précieuses, comme les secrets du passé, avant que le sage ne se transforme,

À chaque choix, les destins prenaient forme et les cœurs commençaient à brûler.

Même si le travail à venir était intimidant, les stars admiraient toujours

Le sage qui cherchait, d’une main ferme, à équilibrer le feu cosmique.

Et comment l'histoire a atteint sa fin, sous ces cieux sans fin,

N'est connu que de ceux qui cherchent et osent lever les yeux.

Dans les royaumes illimités de Zopraria, où perdurent les contes anciens,

Certains disent que le sage réfléchit encore, son cœur et son esprit aussi purs.

Car dans les cieux silencieux se trouve un équilibre fin et rare,

Une harmonie que seuls ceux qui ont les mains fermes peuvent partager.**

C'est le poème, ça semble bizarre, n'est-ce pas. Et que fait-il dans un livre de mathématiques. Ce n'est pas un nouveau puzzle, un puzzle des années 1600, écrit quelque part dans le Westminster d'aujourd'hui.
Néanmoins, l'IA est notre bonne amie, c'est vrai, je lui ai demandé ce qu'elle a répondu, c'était bizarre, et on dirait même qu'elle ne comprend rien.

Il pensait que je l'avais créé, ce qui n'est pas le cas. Mais qu’en est-il de GPT-4 ? Demandons-lui s'il sait rien. C'est devenu mon professeur d'anglais.

Ok, je dois le décoder moi-même. Essayons.

9 septembre 2024 : « Divisez ces pierres précieuses lumineuses en deux, avec un cœur et une oreille prudents.

Laissez vos deux récipients fabriqués supporter un poids si presque partagé,

Cette harmonie entre eux demeure, dans un équilibre brillant et juste.

Mais écoutez-nous, sage, si un match parfait est perdu au-delà de vos connaissances,

Ne désespérez pas dans votre quête, car votre voyage ne se terminera toujours pas.

Car même si l'équilibre penche, le changement peut être léger,

Les cieux te souriront toujours et les bénédictions couleront librement. "

C'est la partie principale de l'histoire et décodons-la.
Après quelques réflexions, désolé, en me torturant pendant plus de 3 jours d'affilée, j'ai eu un indice.
Les pierres précieuses peuvent être des nombres, comme il est dit « avec un cœur et une oreille attentifs ».
Les vaisseaux sont peut-être des ensembles, mais le concept d'ensembles n'a pas été découvert jusque-là, donc je peux me tromper.
L'extrait ci-dessus peut signifier deux ensembles d'un nombre égal d'éléments, ou la somme des nombres de l'ensemble est égale. Et si les sommes ne sont pas les mêmes, la plus proche peut être affichée.

15 septembre 2024 : Après une réflexion plus complexe et la publication de nombreux articles complémentaires. Je pense que oui, j’ai peut-être trouvé la meilleure de mes réflexions sur ce poème.
Bien que ce poème soit si ancien, je n’ai trouvé aucune autre solution à ce poème. Mais j’ai formulé les questions de manière à ce que tout le monde puisse comprendre, moi y compris.

Le défi

Du point de vue de CS, oui, je ferais cela sous la forme de CS d'abord, puis de mathématiques plus tard.

On nous donne une liste d'entiers. Notre tâche est de diviser la liste en deux sous-listes de telle sorte que la différence absolue de leurs sommes soit minimisée. S'il existe une séparation parfaite, nous devons renvoyer les deux listes. Sinon, renvoyez les deux listes où la différence de somme est la plus petite possible.

Exemple:

Input: [3, 1, 4, 2, 2]
Output: ([2, 4], [3, 1, 2])

Dans cet exemple, diviser la liste en [3, 4] et [1, 2, 2] donne des sommes de 7 et 5, et la différence absolue est minimisée à 2.

Codage

Alors commençons à coder.
16 septembre 2024 :

from itertools import combinations

def minimize_difference(lst):
    total_sum = sum(lst)
    n = len(lst)

    # Generate all possible subsets
    best_diff = float('inf')
    best_split = ([], [])

    for i in range(1, n//2 + 1):
        for subset in combinations(lst, i):
            subset_sum = sum(subset)
            other_sum = total_sum - subset_sum

            diff = abs(subset_sum - other_sum)

            if diff < best_diff:
                best_diff = diff
                best_split = (list(subset), [x for x in lst if x not in subset])

    return best_split

# Example usage
lst = [3, 1, 4, 2, 2]
result = minimize_difference(lst)
print("Split lists:", result)

Le fait que le code fonctionne mieux que mon cerveau est tout simplement étonnant.

Explication du code

Le problème de diviser une liste en deux sous-listes de telle sorte que la différence absolue entre leurs sommes soit minimisée, découle d'un défi mathématique fascinant. Voyons comment le code Python fourni résout ce problème.

1. Comprendre le problème :
   Le but est de trouver deux sous-listes de la liste donnée telles que leur somme soit la plus proche possible. S'il existe une division parfaite (où les sommes des deux sous-listes sont égales), nous renvoyons les deux sous-listes. Sinon, on renvoie la répartition où la différence entre les deux sommes est la plus petite.

2. Structure du code :

Le cœur du code réside dans la génération de toutes les combinaisons possibles d'éléments de la liste pour former l'une des sous-listes. Une fois qu'une sous-liste est sélectionnée, l'autre sous-liste est automatiquement formée par les éléments restants. Ensuite, nous comparons leurs sommes pour trouver la meilleure répartition possible avec la différence minimale.

1. Fonctions et concepts clés :

• combinations(lst, i) : Ceci génère toutes les combinaisons possibles de longueur i à partir de la liste. Pour chaque sous-ensemble, il simule l'une des sous-listes, tandis que les éléments restants forment l'autre sous-liste.

• total_sum = sum(lst) : Ceci calcule la somme totale de la liste. Il permet de déterminer facilement la somme de l'autre sous-liste en soustrayant la somme du sous-ensemble actuel de la somme totale.

• best_diff = float('inf') : Nous initialisons la variable best_diff avec un grand nombre (infini) pour garder une trace de la plus petite différence trouvée jusqu'à présent. Au fur et à mesure que nous examinons chaque répartition possible, nous mettons à jour cette valeur si nous trouvons une différence plus petite.

• Trouver le meilleur split : Pour chaque sous-ensemble généré, le code calcule la différence entre les sommes des deux sous-listes. Si la différence actuelle est inférieure au best_diff, la répartition est mise à jour.

1. Considérations relatives aux performances :
   Le code utilise la fonction de combinaisons de la bibliothèque itertools pour explorer des sous-ensembles de différentes longueurs. Bien que cette approche fonctionne bien pour des listes relativement petites, elle n’est peut-être pas optimale pour des listes plus grandes en raison de la croissance exponentielle des sous-ensembles possibles. Pour des entrées plus importantes, des algorithmes plus efficaces comme la programmation dynamique pourraient être envisagés.

2. Exemple de sortie :

Dans l'exemple fourni :

   lst = [3, 1, 4, 2, 2]
   result = minimize_difference(lst)
   print("Split lists:", result)

La fonction divise la liste en [2, 4] et [3, 1, 2], ce qui donne des sommes de 6 et 6 respectivement, et une différence minimale de 0, ce qui est la solution optimale dans ce cas.

1. Pourquoi ça marche bien : En explorant tous les sous-ensembles possibles et en calculant leurs différences respectives, l’algorithme garantit que nous trouvons la répartition avec la plus petite différence de somme possible. Cette approche par force brute est intuitive et efficace pour les listes de taille moyenne, offrant une solution claire et simple à cette énigme ancienne.

---

Ce que vous avez vu ci-dessus est un extrait de mon journal, 100% vrai. Mais une version plus « storifiée » est disponible sur sa version storifiée de la même chose

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!