[Illustration] Recherche de la somme des pièces avec une fonction récursive [Ruby]

introduction

À propos de Probem31 du projet Euler. J'ai essayé de l'expliquer par un débutant de la fonction récursive, faisant référence aux réponses des autres en fonction récursive. J'ai aussi Illustration ci-dessous, alors jetez-y également un œil.

problème

Problème 31 "Somme des pièces" Au Royaume-Uni, il existe des livres £ et des pence p, et huit types de pièces sont en circulation générale. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). Il est possible de gagner 2 £ par la méthode suivante. 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p De combien de façons puis-je gagner 2 £ avec ces pièces?

Version japonaise Version anglaise officielle

politique

Répétez le processus de retrait de n'importe lequel de coins = [1,2,5,10,20,50,100,200] jusqu'à ce qu'il atteigne 200. Ce ne serait pas génial si cela était fait par des mains humaines, mais c'est innombrable, donc dans de tels cas, «" fonction récursive "»!

Qu'est-ce qu'une fonction récursive?

Une fonction qui s'appelle elle-même dans la fonction définie par def ~ end. Si elle est célèbre, la fonction de Fibonacci est souvent traitée comme une introduction aux fonctions récursives. Si vous l'avez entendu pour la première fois, veuillez effectuer une recherche.

Un autre article de commentaire: [Illustration] Fonction récursive hiérarchique [Ruby]

répondre

def coin_count(coins, goal, last = 0)
  if goal == 0
    return 1
  end

  total = 0
  coins.each do |c|
    if c < last
      next
    end
    if goal >= c
      total += coin_count(coins, goal - c, c)
    end
  end

  total
end

coins = [1,2,5,10,20,50,100,200]
puts coin_count(coins,200)

J'avais honte de dire que je ne pouvais pas le résoudre moi-même, alors je l'ai créé sur ici. J'expliquerai cette solution en japonais.

Commentaire

Ce que je veux faire cette fois, c'est le nombre «200». Alors définissez goal = 200 et la valeur d'une pièce

Tout d'abord, l'explication commence à partir de chaque instruction de la fonction.

if c < last
  next
end

Ceci afin d'éviter d'ajouter plus que le dernier ajout le plus récent. «50 + 50 + 100» et «50 + 100 + 50» sont les mêmes dans ce numéro, n'utilisez donc que des modèles qui s'ajoutent par ordre croissant. suivant est le processus qui consiste à sauter le processus après le suivant dans le bloc.

Next est la troisième instruction if dans une fonction qui utilise une fonction récursive.

if goal >= c
  total += coin_count(coins, goal - c, c)
end

Cette fois, «c» vaut «1 <= c» car c'est l'un des éléments de «coins = [1,2,5,10,20,50,100,200]». Ainsi, le but passé comme argument à coin_count (pièces, but, dernier) diminuera vers 0 pour objectif --c.

Si «c = 50 et objectif = 200», ce sera comme suit.

Exemple)
Objectif avec fonction récursive-Lorsque c est répété, l'argument but devient
Première fois: 150     ※coin_count(coins, 150, 50)Appeler avec
Deuxième fois: 100     ※coin_count(coins, 100, 50)
Troisième fois: 50      ※coin_count(coins, 50, 50)
4e: 0       ※coin_count(coins, 0, 50)

La quatrième fois que la fonction est appelée avec coin_count (coins, 0, 50)

if goal == 0
  return 1
end

Ce sera, donc enfin ici,

total += coin_count(coins, goal - c, c)

La fonction coin_count de aura une valeur de retour de 1. À ce stade, il devient finalement «total + = 1», et 1 est ajouté.

--Lorsque objectif> 0 --Lorsque objectif <0

Dans ce cas, «total = 0» reste 0 et est passé à la valeur de retour. Enfin, le nombre total de combinaisons est obtenu comme la valeur du total.

Illustré

J'ai essayé de comprendre cet état où la fonction est appelée à plusieurs reprises.

À la fin

Veuillez me faire savoir s'il y a des points manquants, des points incorrects ou des explications plus claires. Merci pour la lecture.