Algorithm Formule de récurrence

Question

Je lis des algorithmes en C++ par Robert Sedgewick. La récurrence de base a été mentionnée comme Cette récurrence survient pour un programme récursif qui boucle l'entrée pour éliminer un élément Cn = cn-1 + N, pour N> = 2 avec C1 = 1.

Cn est sur Nsquare/2. L'évaluation de la somme 1 + 2 + ... + N est élémentaire. En plus de cette déclaration suivante est mentionné. "Ce résultat - deux fois la valeur recherchée - se compose de N termes, dont chacune des sommes à N + 1

J'ai besoin d'aide pour comprendre ce abouve déclaration sont N termes ici et comment chacun des sommes à N + 1, ASLO qu'est-ce que « deux fois la valeur recherchée » signifie.

Merci pour votre aide

Answer 1

Je pense qu'il fait référence à cette astuce mathématique de base pour calculer cette somme. Même si, il est difficile de conclure quoi que ce soit de ce court passage que vous avez cité.

Supposons N = 100. .g., la somme est 1 + 2 + 3 + .. + 99 + 100.
Maintenant, regroupons les paires d'éléments avec la somme 101: 1 + 100, 2 + 99, 3 + 98, ..., 50 + 51. Cela nous donne 50 (N/2) paires avec la somme 101 (N + 1) dans chaque: ainsi la somme globale est 50*101.

De toute façon, pourriez-vous fournir un peu plus de contexte à cette citation?

Answer 2

La formule de récurrence signifie:

C1 = 1 
C2 = C1 + 2 = 1 + 2 = 3 
C3 = C2 + 3 = 3 + 3 = 6 
C4 = C3 + 4 = 6 + 4 = 10 
C5 = C4 + 5 = 10 + 5 = 15 
etc. 

Mais vous pouvez aussi écrire directement: C5 = 1 + 2 + 3 + 4 + 5 = 15

Et puis utilisez le vieux truc:

1 + 2 + 3 + ... + N 
+ N + N-1 + N-2 + ... + 1 
------------------------- 
(N+1) ...    (N+1) 

= (N + 1) * N

De là, nous obtenons: 1 + 2 + ... N = N * (N + 1)/2

Pour l'anecdote, la formule ci-dessus a été trouvée par le grand mathématicien Carl Friedrich Gauss, quand il était à l'école. De là, nous pouvons déduire un algorithme récursif est O (N carré) et c'est probablement ce que fait Robert Sedgewick.