Définissez une fonction ou une méthode qui renvoie un entier supérieur ou égal à 0 sous forme de ** chaîne ** et le reste après l'avoir divisé par 3. Cet article utilise Ruby, c'est donc une méthode.
Cependant, aucune valeur numérique ne sera utilisée. En d'autres termes, n'utilisez pas d'objets numériques au milieu du traitement. Bien entendu, la valeur de retour est également une chaîne de caractères.
Je ne sais pas si la méthode intégrée a créé un objet numérique en interne, je suppose donc que le code que j'ai écrit ne crée pas d'objet numérique au milieu.
Appelons la méthode restder_modulo_3. Je ne sais pas si l'anglais est correct, mais le reste est le reste, et modulo 3 signifie "lorsqu'il est divisé par 3" [^ modulo 3].
[^ modulo3]: modulo 3 est dit "3 en tant que loi" en termes mathématiques formels.
Ça devrait ressembler à ça:
p remainder_modulo_3("0") # => "0"
p remainder_modulo_3("8") # => "2"
p remainder_modulo_3("12") # => "0"
p remainder_modulo_3("22") # => "1"
Avant de penser au programme, comment le faire manuellement.
Par exemple, le reste de 1234567 divisé par 3 peut être vu en un coup d'œil comme 1. hein? Que voulez-vous dire?
Tout d'abord, considérons le reste des 87 plus simples divisé par trois. Vous pouvez faire la division sérieusement, mais il existe un moyen de sauter plus.
\begin{eqnarray}
87 &=& 8 \times 10 + 7 \\
&=& 8 \times (9 + 1) + 7 \\
&=& 8 \times 9 + 8 + 7
\end{eqnarray}
Cependant, $ 8 \ times 9 $ est un multiple de $ 9 $, donc il est divisible par $ 3 $. Par conséquent, vous pouvez exclure 8 $ \ fois 9 $ et trouver le reste de 8 $ + 7 $ divisé par 3 $.
Puisque 8 $ + 7 $ est 15 $, il est divisible par 3 $. Le reste est de 0 $.
Penser de la même manière, même un grand nombre comme 1234567
\begin{eqnarray}
1234567 &=& 1 \times (999999 + 1) + 2 \times (99999 + 1) + 3 \times (9999 + 1) + 4 \times (999 + 1) + 5 \times (99 + 1) + 6 \times (9 + 1) + 7 \\
&=& (Multiple de 9) + 1 + 2 + 3 + 4 + 5 + 6 + 7
\end{eqnarray}
Par conséquent, le reste de 1 $ + 2 + 3 + 4 + 5 + 6 + 7 $ divisé par 3 $ peut être obtenu.
Vous n'avez pas à calculer sérieusement 1 $ + 2 + 3 + 4 + 5 + 6 + 7 $,
(1 + 2) + (3) + (4 + 5) + (6) + 7
Puisque vous pouvez voir des multiples de 3 $, vous pouvez obtenir 1 $ en les excluant et en trouvant le reste de 7 $ divisé par 3 $.
Alors qu'en est-il des nombres comme 78932705 $? Au lieu de ce numéro
7 + 8 + 9 + 3 + 2 + 7 + 0 + 5
Parmi ces nombres, 9 $, 3 $ et 0 $ sont des multiples de 3 $, vous pouvez donc les exclure.
7 + 8 + 2 + 7 + 5
Pensez-y. De plus, en considérant 7 $ = 2 \ fois 3 + 1 $, 7 $ a été remplacé par 1 $, 8 $ a été remplacé par 2 $ et 5 $ a été remplacé par 2 $.
1 + 2 + 2 + 1 + 2
Il suffit d'y penser. (Les nombres qui sortent ne peuvent être que 1 et 2)
Les humains peuvent jeter un coup d'œil à cela et combiner 1 $ avec 2 $ pour faire 3 $ et l'exclure, et le reste est immédiatement apparent à 2 $. Mais comment faire cela par programme?
Après tout, tri
1 + 1 + 2 + 2 + 2
Ensuite, il serait préférable de créer la chaîne de caractères «" 11222 "».
Après cela, il semble que vous deviez supprimer les chaînes de caractères telles que «111», «222» et «12».
J'ai fait ceci:
def remainder_modulo_3(number)
s = number.delete("0369").tr("4578", "1212")
.chars.sort.join
.gsub(/(.)\1\1|1122|12/, "")
{"" => "0", "1" => "1", "11" => "2", "2" => "2", "22" => "1"}[s]
end
Donne un entier supérieur ou égal à 0 sous forme de chaîne de caractères, et renvoie l'un des «0», «1» et «2» sous forme de chaîne de caractères.
Essayons:
1000000.times do |n|
puts n unless (n % 3).to_s == remainder_modulo_3(n.to_s)
end
Comparez celui calculé avec Integer normalement avec celui obtenu avec la méthode restder_modulo_3, et s'ils ne correspondent pas, affichez-le. Quand je l'ai essayé, rien n'était affiché, donc le code semble correspondre.
La chaîne de méthodes est un peu longue, mais ce que nous faisons est simple.
Premier
delete("0369")
Cependant, puisque 0, 3, 6 et 9 sont des multiples de 3, ces nombres sont exclus.
prochain
tr("4578", "1212")
Par exemple, 4 peut être remplacé par 1 car 4 est 3 + 1, et 5 peut être remplacé par 2.
Suivant
chars.sort.join
Commencez par casser la chaîne caractère par caractère, la trie et la connecte à nouveau. Cela donne, par exemple, "" 122 "" à partir de "" 212 "".
La chaîne obtenue à ce stade est "0 ou plus" "1" "suivi de 0 ou plus" "2" "". Il ne peut y avoir d'autre modèle.
Suivant
gsub(/(.)\1\1|1122|12/, "")
Supprime les chaînes de caractères spécifiques dans l'ordre à partir de la gauche, mais l'expression régulière est un peu déroutante.
Le point culminant est la partie (.) \ 1 \ 1. Cela utilise une référence arrière. Cela signifie que deux caractères capturés par (.) Suivez-le, et il correspond à "trois mêmes nombres dans une ligne" dans son ensemble.
Il correspond également aux colonnes «1122» et «12» qui peuvent exister à la limite entre les colonnes «1» «et« 2 »».
Ceux-ci sont supprimés.
Quel type de chaîne de caractères peut-on obtenir après cette conversion? C'est un peu ennuyeux, mais classons par le nombre de "1" `.
Premièrement, puisque «111» «est supprimé en premier (parce que le multiple« 1 »« de 3 est supprimé), si le nombre de «1» «est 0, 1, 2 seulement. Je sais que c'est bon.
Lorsque "" 1 " vaut 0, c'est une chaîne de caractères dans laquelle 0 ou plus `` 2 " sont connectés. Considérant que les multiples de 3 "" 2 "sont supprimés, il peut y en avoir trois," ", " 2 "et" 22 "`.
Ensuite, quand il y a un "1" , s'il y a 0" 2 "` suivants ", c'est" 1 "", et s'il y en a un "2" ", c'est le tout (" "12"). Est supprimé pour devenir "" "", et s'il y a deux "2" ", il devient" "2" ". S'il y a 3 ou plus «2» «s», le «222» «sera supprimé, donc vous n'avez pas à y penser (les possibilités sont épuisées). En d'autres termes, il peut y en avoir trois, "" 1 "", "" "et" "2".
Enfin, quand il y a deux "1" ", s'il y a 0" "2" "suivant, c'est" "11" ", et s'il y en a un" "2" ", le" 12 "" est supprimé. Il devient "" 1 ", et s'il y a deux " 2 ", le tout (" 1122 ") est supprimé et devient une chaîne de caractères vide. S'il y a trois "" 2 "", le "" 1122 "" est supprimé et devient "" 2 "". Vous n'avez pas à penser à quatre ou plus. En d'autres termes, il peut y en avoir quatre, " 11 ", " 1 ", " ", " 2 "`.
Huh, c'était ennuyeux.
Après tout, la chaîne de caractères convertie est
"""1""11""2""22"Il n'y a que cinq possibilités.
Le hachage est trop utilisé pour les guider. c'est tout.
Le reste après la division par 9 peut être fait exactement de la même manière.
Le reste après la division par 2 ou 5 n'a besoin que de voir le dernier chiffre (la place de 1) (car 10 est divisible par 2 ou 5).
Pour le reste divisé par 4, regardez les deux derniers chiffres (car 100 est divisible par 4).
Regardez les 3 derniers chiffres pour le reste divisé par 8 (car 1000 est divisible par 8).
Le reste après avoir divisé par 6 devrait être assez déroutant. Je veux essayer un jour.
Je ne sais pas si le reste après la division par 7 peut être calculé sans créer d'objet numérique.
Même si quelqu'un me demande: "Et alors?" Je l'ai étiqueté comme "théorie des entiers", mais ce n'est pas si grave, ce n'est pas pratique et ce n'est pas très intéressant. J'ai juste réfléchi et essayé.
Recommended Posts