Algorithme pour diviser une barre de chocolat à parts égales

Question

Une pensée au hasard a sauté dans ma tête (quand je partageais une barre de chocolat bien sûr!). Je me demandais s'il y avait un algorithme générique pour résoudre ce problème.

Le problème va comme ceci:

Infos

1. Vous avez une barre de chocolat avec de petits carrés disposés dans une matrice rectangulaire
2. Il y a n personnes dans la salle

Le problème

Écrire un algorithme qui génère la configuration optimale (pxq) où la barre peut être partagée également entre n, n-1, n-2...., 2, 1 personnes soumises aux restrictions suivantes:

1. Un petit carré (le carré de l'unité) ne peut pas être coupé en plus petits morceaux
2. Toutes les ruptures doivent être faites complètement le long d'un axe
3. Le nombre total de ruptures ne peut pas être plus que n (c'est pour décourager les solutions inefficaces comme essayer de diviser la barre entière en petits morceaux et diviser les petits morceaux)
4. p ou q ne peut pas être égal à 1. yx a souligné dans l'une des réponses que le problème est facilement soluble si un côté a 1 barre. Ceci est cependant pas une bonne solution pour des situations réelles - ce qui était l'intention de résoudre ce problème :)

Exemple

Pour n = 4, la configuration optimale est de 4 x 3.

~~~~ ~~~~ ~~~~ ~~~~ 
| | | | | 
~~~~ ~~~~ ~~~~ ~~~~ 
| | | | | 
~~~~ ~~~~ ~~~~ ~~~~ 
| | | | | 
~~~~ ~~~~ ~~~~ ~~~~ 

Cette configuration peut être répartie entre:

4 personnes en 3 pauses le long des axes verticaux
3 personnes avec 2 pauses le long des axes horizontaux
2 personnes 1 pause juste au milieu

d'autres solutions empiriques sont (n, p, q) = (1, 1, 1); (2, 2, 1); (3, 3, 2); (4, 4, 3); (5, 5, 12); (6, 6, 10) OR (6, 5, 12)

Clarifications
Une rupture est définie comme une coupe le long d'un axe pour le sous-ensemble de la barre, le cas échéant. Pour mieux illustrer cela, que vous avez un 2 x 2 barre de chocolat comme ceci:

~~~~ ~~~~ 
| | | 
~~~~ ~~~~ 
| | | 
~~~~ ~~~~ 

La sagesse conventionnelle indique que vous devez faire 2 pauses (les axes perpendiculaires au milieu - vers le bas et à travers) pour diviser cette barre en 4 pièces. Cependant, dans le monde réel (s'il s'agissait d'une barre de chocolat), vous devez d'abord la casser en deux puis la casser à nouveau séparément. Cela fait un total de 3 pauses - 1 pause sur la barre entière et 2 pauses sur 2 sous-ensembles différents de la barre.

Je ne pouvais pas trouver de solution n'importe où sur Internet - si quelqu'un pense que ce n'est pas une question de programmation ou une solution existe déjà, n'hésitez pas à fermer la question =)

Answer 1

Il me semble que vous cherchez des nombres divisibles de façon égale par tous les nombres compris entre 1 et n inclus. C'est ce qu'on appelle le multiple le moins commun de 1, ..., n. Un carré contenant le plus petit multiple commun de 1, ..., n carrés serait par définition divisible en morceaux de taille 1, ..., n. Vous recherchez un maximum de n divisions, ce qui ajoute une complexité supplémentaire au problème, qui peut ou non être possible. Votre exemple pour n = 4 est le LCM (4,3,2,1) qui est de 12. LCM (5,4,3,2,1) est de 60. LCM (6,5,4,3 , 2,1) est également 60.

Ils peuvent toujours être disposés en rectangles 1xLCM (n, ..., 1), et peuvent toujours être divisés en 1, ..., n pairs en n-1 ou moins de divisions.

Par exemple, lorsque n = 4, LCM (4,3,2,1) = 12. Le rectangle est

############ 

Et peut être divisé comme suit:

1: ############  // 0 cuts 
2: ###### ###### // 1 cut 
3: #### #### #### // 2 cuts 
4: ### ### ### ### // 3 cuts (3 being n-1) 

Answer 2

Une bonne façon de répondre à cette question serait utiliser un algorithme de recherche en largeur. L'algorithme essayera chaque rupture possible de la barre de chocolat entière. Ensuite, pour chacun de ces états possibles du problème, essayez toutes les ruptures possibles, et cela continuera tout en gardant la trace de la régularité des pièces.

Je voudrais ajouter que les règles imposent que les cassures de la barre de chocolat soient légales et que les états possibles qui ne sont pas légaux soient éliminés de l'algorithme.

Answer 3

Peut-être vous pouvez utiliser un langage comme prologue pour résoudre ce genre de choses

Answer 4

Puisque vous ne pouvez pas couper plusieurs pièces à la fois, pour n'importe quel nombre de pièces que vous voulez où m est dans l'ensemble (1..n), vous aura toujours besoin de coupes m-1. Chaque coupe crée une pièce de plus, vous commencez avec une pièce.

bâtiment sur la solution précédente, je pense que vous cherchez intuitivement l'algorithme suivant:

A = LCM(n) 
p = greatest divisor of A <= sqrt(A) 
q = A/p 

Les algorithmes pour ce qui devrait être trivial, (par exemple, commencer par p = étage (sqrt (A)) et compte à rebours jusqu'à mod (A, p) == 0).

La raison pour laquelle vous voulez sqrt est de limiter la quantité de chiffres que vous vérifiez. Après tout, vous aurez toujours un diviseur < = sqrt (A) et un> = sqrt (A)