Ich war neugierig auf einen anderen Beitrag und habe es selbst versucht. Das Problem ist
"1000 Zahlen stehen in einer Reihe. Nehmen Sie 13 aufeinanderfolgende Zahlen und betrachten Sie das Produkt dieser 13 Zahlen. Finden Sie den Maximalwert."
etwas wie.
Es wäre hinderlich, 13 Multiplikationen fast 1000-mal durchführen zu lassen, und wenn Sie es als Skalierungsmethode betrachten, würde die Division fast 1000-mal erfolgen, was nicht gut ist. Verwenden wir ** logarithmisch **, weil wir viele Produkte nehmen. $ \ log_a M $ heißt der Logarithmus von $ M $ mit ** $ a $ als Basis ** und ist wie folgt definiert.
Reelle Zahl r,a>0, a\neq1,M>Gegen 0\\
a^r=M \iff r= \log_a M
Einfach ausgedrückt, stellt es einen Exponenten dar, wenn versucht wird, eine positive Zahl $ M $ als Potenz einer nicht einer positiven Zahl $ a $ darzustellen. Zum Beispiel ist $ 2 ^ 3 = 8 $, also $ \ log_2 8 = 3 $. Erwägen Sie auch, den Exponenten auf die gesamte reelle Zahl zu erweitern. Basierend auf dieser Idee wird es zu $ 2 ^ {\ frac {1} {2}} = \ sqrt {2} $, also zu $ \ log_2 \ sqrt {2} = \ frac {1} {2} $.
Für den Exponenten gilt das Exponentialgesetz $ a ^ x \ mal a ^ y = a ^ {x + y} $. Unter dem Gesichtspunkt, dass der Index ursprünglich die Anzahl der Multiplikationen ist, scheint es natürlich zu verstehen, dass diese Multiplikationen mit der Gesamtzahl der Multiplikationen multipliziert werden. Dies ist ein logarithmischer Ausdruck.
a>0, a\neq1,M>0,N>Gegen 0\\
\log_a {MN} = \log_a M + \log_a N
Aufgrund dieser Eigenschaft kann die ** Multiplikation in eine logarithmische Addition umgewandelt werden. ** Auch im Logarithmus
M>0,N>Auf 0 setzen.\\
a>Wenn 1, M.<N \iff \log_a M < \log_a N
Es hat die Eigenschaft von. Mit anderen Worten, wenn $ a> 1 $ ist, stimmen die Größe der ursprünglichen Zahl und die Größe der logarithmischen Zahl überein. ** Hiermit wird die Multiplikation als Addition des Logarithmus verwendet und berechnet, indem nach dem Abschnitt gesucht wird, in dem die Summe des Logarithmus durch die Skalierungsmethode maximiert wird.
Dieses Mal verwenden wir die Java Math-Klassenmethode Math.log10 (x), um den Logarithmus zu verwenden. Es ist eine Methode, die das logarithmische Argument mit $ a = 10 $ verwendet, dh $ \ log_ {10} x $ findet.
(Der als $ a = 10 $ angenommene Logarithmus heißt übrigens ** regulärer Logarithmus **.)
Da der erforderliche Logarithmus nur für jede der 10 Zahlen von 0 bis 9 gilt, berechnen Sie ihn im Voraus und fügen Sie ihn in das Array ein. Der logarithmische Wert für 0 ist jedoch nicht mathematisch definiert, und die Definition der Methode lautet "negative Unendlichkeit". Wenn dies also durch die Skalierungsmethode hinzugefügt wird, kann sie nicht rückgängig gemacht werden. Daher wird der Einfachheit halber -1000 als logarithmischer Wert für 0 festgelegt. Infolgedessen ist die Summe der logarithmischen Werte in dem Abschnitt, der 0 enthält, immer negativ, und sie liegt außerhalb des maximalen Kandidaten, und es ist möglich, sie wiederherzustellen, wenn 0 aus ist.
Sobald das maximale Intervall bekannt ist, wird das Produkt tatsächlich berechnet. Dies liegt daran, dass Sie aufgrund des Problems des Gleitkommafehlers möglicherweise keinen genauen Wert erhalten, wenn Sie versuchen, ihn anhand der logarithmischen Definition zu finden.
Der mit dieser Idee geschriebene Code lautet wie folgt.
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';
}
}