Diviser et conquérir la stratégie

Question

J'essaie d'apprendre le concept de la stratégie de Diviser pour régner.Comment j'écrirais un pseudo-code pour déterminer si tous les éléments dans le tableau donné sont égaux en utilisant l'approche de diviser pour régner. Je veux commencer par un appel initial, allEqual (a, 0, a.length-1).

Answer 1

vous pouvez le faire comme:

1. start=0, end = a.length-1, middle= (start+end)/2
2. maintenant vous appelez récursive comme:
   i) allEqual(a, start, middle)
   ii) allEqual(a, middle+1, end)
3. vous vérifiez dans Base case

Answer 2

Je trouve qu'il est préférable de penser divide et conq uer comme ceci:

1. Pour de très petits problèmes (1 ou 2 éléments), comment pourrais-je résoudre le problème sur papier?

   Évidemment pour votre problème: si vous avez un élément, renvoyez cet élément. Je divise mon grand problème en deux moitiés égales. Je résous les deux moitiés (je me fous de savoir comment maintenant). Comment cela m'aide-t-il à résoudre mon problème d'origine?

   Les deux solutions aux deux moitiés retourneront un élément. Vérifiez si les deux éléments retournés sont égaux: si oui, le tableau entier contient la même valeur. Sinon, ce n'est pas le cas. Est-ce que j'ai trop simplifié quelque chose et comment puis-je en prendre soin dans la pratique?

   Nous retournons la valeur à cette position pour les sous-matrices avec un élément, mais que retournons-nous si les résultats de la résolution des deux sous-problèmes sont différents?

   Dans ce cas, vous pouvez renvoyer une valeur qui ne fera pas partie de votre entrée (peut-être -1?), Ou définir un indicateur global qui vous indique si cela s'est produit, auquel cas la réponse finale sera no, not all are equal., peu importe ce qui se passe pour d'autres appels récursifs.