Equations de récurrence

Question

Étant donné un problème, comment créer une équation de récurrence?

Par exemple: Soit S être un ensemble de n>0 entiers distincts. Supposons que n est une puissance de 3. Une comparaison ternaire peut comparer trois nombres de l'ensemble S et les classer du plus grand au plus petit.

Décrire un algorithme efficace utilisant le moins possible de comparaisons ternaires pour trouver le plus grand nombre dans l'ensemble S.

C'est l'une des questions de mi-parcours que j'ai eues. Je viens avec

T(n) = 3T(n/3)+1 

et d'autres étudiants viennent avec autre chose.

En général, quoi rechercher en trouvant une récursion pour un problème?

Answer 1

Cela dépend du problème, mais en général, essayez de diviser le problème en un petit problème plus un pas en plus, ou plusieurs petits problèmes, et une étape qui les combine.

Je pense que votre réponse est juste. Comment êtes-vous arrivé à la réponse? Pouvez-vous expliquer le processus que vous avez suivi?

Voilà comment je le ferais:

Vous pouvez diviser le problème en divisant les entiers en trois petits groupes de taille égale. Supposons que vous sachiez trouver le maximum de chaque petit groupe dans T (n/3), puis que vous utilisiez votre opérateur de comparaison ternaire pour trouver le maximum des trois maximums en une étape supplémentaire (donnant le +1). C'est alors le maximum global. Cela donne la relation de récurrence que vous avez décrite. Vous devez également définir le cas de base: T (1) = 0 ou T (3) = 1. Cela ne prouve pas que c'est optimal, mais je pense que vous pouvez prouver qu'il utilise un argument différent.

La plupart des solutions récursives suivent des modèles similaires, mais il n'y a pas de règle stricte que vous pouvez toujours suivre. Pratiquez juste sur beaucoup d'exemples différents jusqu'à ce que vous obteniez le coup de lui.