J'étais curieux de voir un autre article et je l'ai essayé moi-même. Le problème est
"1000 numéros sont alignés. Prenez 13 numéros consécutifs et considérez le produit de ces 13 nombres. Trouvez la valeur maximale."
quelque chose comme.
Ce serait un obstacle d'avoir 13 multiplications effectuées près de 1000 fois, et si vous y pensez comme une méthode à l'échelle, la division se produirait près de 1000 fois, ce qui n'est pas bon. Utilisons ** logarithmique ** car nous prenons beaucoup de produits. $ \ log_a M $ est appelé le logarithme de $ M $ avec ** $ a $ comme base **, et est défini comme suit.
Nombre réel r,a>0, a\neq1,M>Contre 0\\
a^r=M \iff r= \log_a M
En termes simples, il représente un exposant lorsque vous essayez de représenter un nombre positif $ M $ comme une puissance d'un nombre positif non-un $ a $. Par exemple, $ 2 ^ 3 = 8 $, donc $ \ log_2 8 = 3 $. Pensez également à étendre l'exposant au nombre réel entier. Sur la base de cette idée, il devient $ 2 ^ {\ frac {1} {2}} = \ sqrt {2} $, donc il devient $ \ log_2 \ sqrt {2} = \ frac {1} {2} $.
La loi exponentielle $ a ^ x \ times a ^ y = a ^ {x + y} $ est valable pour l'exposant. Du point de vue que l'indice est à l'origine le nombre de multiplications, il semble naturel de comprendre que ces multiplications sont multipliées par le nombre total de multiplications. Il s'agit d'une expression logarithmique.
a>0, a\neq1,M>0,N>Contre 0\\
\log_a {MN} = \log_a M + \log_a N
En raison de cette propriété, la multiplication ** peut être convertie en addition logarithmique. ** Aussi en logarithme
M>0,N>Réglez sur 0.\\
a>Quand 1, M<N \iff \log_a M < \log_a N
Il a la propriété de. En d'autres termes, lorsque $ a> 1 $, la grandeur du nombre d'origine et la grandeur du nombre logarithmique correspondent. ** En utilisant cela, la multiplication est utilisée comme addition du logarithme, et elle est calculée en recherchant la section où la somme du logarithme est maximisée par la méthode d'échelle.
Cette fois, nous utilisons la méthode de classe Java Math Math.log10 (x) pour prendre la logarithmique. C'est une méthode qui prend l'argument logarithmique avec $ a = 10 $, c'est-à-dire trouve $ \ log_ {10} x $.
(À propos, le logarithme pris comme $ a = 10 $ est appelé ** logarithme régulier **.)
Puisque le logarithme requis n'est que pour chacun des 10 nombres de 0 à 9, calculez-le à l'avance et placez-le dans le tableau. Cependant, la valeur logarithmique de 0 n'est pas définie mathématiquement et la définition de la méthode est «infini négatif», donc si elle est ajoutée par la méthode de mise à l'échelle, elle ne peut pas être restaurée. Par conséquent, -1000 est défini comme valeur logarithmique pour 0 pour plus de commodité. En conséquence, la somme des valeurs logarithmiques sera toujours négative dans la section incluant 0, et elle sera en dehors du maximum candidat, et il sera possible de la restaurer lorsque 0 est sorti.
Une fois l'intervalle maximum connu, le produit est effectivement calculé. En effet, si vous essayez de le trouver à partir de la définition du logarithme, vous risquez de ne pas obtenir une valeur précise en raison du problème d'erreur en virgule flottante.
Le code écrit avec cette idée est le suivant.
import java.util.*;
import java.util.stream.*;
public class Main {
private static final String NUMS
= "73167176531330624919225119674426574742355349194934"
+ "96983520312774506326239578318016984801869478851843"
+ "85861560789112949495459501737958331952853208805511"
+ "12540698747158523863050715693290963295227443043557"
+ "66896648950445244523161731856403098711121722383113"
+ "62229893423380308135336276614282806444486645238749"
+ "30358907296290491560440772390713810515859307960866"
+ "70172427121883998797908792274921901699720888093776"
+ "65727333001053367881220235421809751254540594752243"
+ "52584907711670556013604839586446706324415722155397"
+ "53697817977846174064955149290862569321978468622482"
+ "83972241375657056057490261407972968652414535100474"
+ "82166370484403199890008895243450658541227588666881"
+ "16427171479924442928230863465674813919123162824586"
+ "17866458359124566529476545682848912883142607690042"
+ "24219022671055626321111109370544217506941658960408"
+ "07198403850962455444362981230987879927244284909188"
+ "84580156166097919133875499200524063689912560717606"
+ "05886116467109405077541002256983155200055935729725"
+ "71636269561882670428252483600823257530420752963450";
public static void main(String[] args) {
final int SPAN = 13;
final double[] log10 = IntStream.range(0, 10).mapToDouble(Math::log10).toArray();
log10[0] = -1000;
double logMax = IntStream.range(0, SPAN).mapToDouble(i -> log10[getNum(i)]).sum();
int head = 0;
double partial = logMax;
for (int i = 0, j = SPAN; j < NUMS.length(); i++, j++) {
partial = partial - log10[getNum(i)] + log10[getNum(j)];
if (partial > logMax) {
logMax = partial;
head = i + 1;
}
}
long result = IntStream.range(head, head + SPAN)
.mapToLong(i -> getNum(i))
.reduce(1L, (x, y) -> x * y);
System.out.println(result);
}
private static int getNum(int i) {
return NUMS.charAt(i) - '0';
}
}