Wątek przeniesiony 2020-09-14 07:55 z Off-Topic przez Adam Boduch.
Jak napisać program, który wyszuka i wypisze mi inne liczby, które po dodaniu i po mnożeniu mają identyczną sumę i iloczyn? Liczby wykorzystane w mnożeniu i dodawaniu, mogą mieć co najwyżej dwa miejsca po przecinku.
Na przykład dla liczby 7.11 z czterema liczbami i 20.25 z trzema liczbami
7.11 = 3.16 + 1.25 + 1.50 + 1.20 = 3.16 * 1.25 * 1.50 * 1.20
20.25 = 0,75 + 1,50 + 18,00 = 0,75 * 1,50 * 18,00
Czemu off topic? Na ile faktorów liczby mają się rozbijać, jak duże mogą być?
Temat bardziej do algorytmów i struktur danych.
A tak w ogóle są jakieś inne kryteria jeszcze?
Najlepiej dodać do programu opcję z ilu liczb mają się rozbijać, oraz dodać do programu możliwość wyboru z jakiej największej liczby ma to być wyszukiwane. Tak jak w programie który wyszukuje liczby pierwsze, wpisujesz powiedzmy 10 000 i on z tej liczby wyszukuje i wypisuje wszystkie liczby pierwsze, a inne pomija.
Poniżej takie rozwiązanie brute force i z brzydkim ręcznym rozpisaniem pętli, ale za to z prymitywną wielowątkowością.
Uwaga na przekręcenie się longów, to działa z niewielkim zapasem.
Dosyć oczywistą obserwacją jest że dla niewielkich liczb pewnie nie ma żadnych reguł, ale jeżeli masz już co najmniej jedną dużą liczbę, to jedna z liczb musi być bardzo mała.
Można poszlifować program w tym kierunku, aby dla pewnego zakresu przetwarzał wszystkie liczby, a od pewnego momentu ograniczał kolejne liczby (np. dla >500 i >1 trzecia liczba musi być bliska zera).
Wydaje mi się, że te punkty w przestrzeni N-wymiarowej są bardzo rzadkie i brute-force tutaj ma krótkie nóżki, można spróbować napisać to w kierunku np. algorytmu genetycznego lub podobnych metod przeszukiwania ogromnych przestrzeni poszukiwań.
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.IntStream;
public class SumProduct {
private static final Set<List<Long>> results = new HashSet<>();
public static void main(String[] args) {
int divisor = Runtime.getRuntime().availableProcessors();
int length = divisor * 16_000;
IntStream.rangeClosed(0, -1 + divisor).asLongStream().parallel().forEach(threadNumber -> {
long rangeS = (length / divisor) * threadNumber;
long rangeE = (length / divisor) * (threadNumber + 1);
long x1, x2, x3;
log("wątek[" + threadNumber + "]: rangeS " + rangeS + ", rangeE " + rangeE);
for (x1 = rangeS; x1 < rangeE; x1++) {
if (x1 % 100 == 0) {
// log("wątek[" + threadNumber + "]: progress " + (1.0 * (x1 - rangeS) / (rangeE - rangeS)));
}
for (x2 = 0; x2 < 2400; x2++) {
for (x3 = 0; x3 < 150; x3++) {
if ((x1 + x2 + x3) * (100 * 100) == x1 * x2 * x3) {
List<Long> res = Arrays.asList(x1, x2, x3);
Collections.sort(res);
if (!results.contains(res)) {
results.add(res);
log(Arrays.asList(toStr(x1), toStr(x2), toStr(x3)));
}
}
}
}
}
});
log("total results==" + results.size());
}
private static void log(Object o) {
System.out.println(o);
}
private static String toStr(long x1) {
String s = "" + x1;
if (s.length() == 1) {
s = "0.0" + x1;
} else if (s.length() == 2) {
s = "0." + x1;
} else {
s = s.substring(0, s.length() - 2) + "." + s.substring(s.length() - 2);
}
return s;
}
}
OP się od tygodnia nie logował, więc nikomu rozwiązanie nie jest potrzebne, ale pobawić się można.
Ja bym pomnożył liczbę wejściową razy 100 na każdy czynnik (czyli razy 100 milionów w przypadku czterech) i sfaktoryzował. Dla takich małych liczb powinno być łatwo.
Potem jak zacząłem szacować to mi wyszło, że sprawdzając wszystkie kombinacje w najgorszym wypadku czynników pierwsszych może być 33 czyli byśmy musieli sprawdzić 4^33 przypadków. To nie przejdzie.
Ale czy na pewno? Rozważmy dwa przypadki, najbardziej złożona liczba to 2^33 czyli jak to sprytnie zakodzimy to trzeba sprawdzić jakieś pół miliona przypadków, więc to chwila. Natomiast najbardziej złożona liczba z różnymi czynnikami to 13! (6 miliardów według Wolframa), a więc wtedy mamy do rozpatrzenia jedynie 4^13 przypadków, to jest około 32 milionów, a więc coś, co współczesny komputer jest w stanie rozpykać w sekundę, może kilka.
Kodu nie chce mi się pisać, ale zapraszam :)
Do takich wielkości faktoryzacja jest spoko; tutaj:
https://github.com/lion137/Competitive-Helper
Można spokojnie faktoryzować do 10^18, (wchodzimy mniej więcej w zakres longa), jakby podkręcić na wstępie to sito do 100000000.
Moim zdaniem nie potrzeba algorytmów brute force, czyli dobieraniem każdej liczby z każdą wywołaną np. przez randomize. Czas takiego doboru może byc bardzo długi jeśli nie wyznaczy się w algorytmie poszukiwań. Myślę, że grafy szybciej by załatwiły sprawę.
Nie wiem na ile autor postu chce operować na dziesiętnych, ale:
1,00, 1,25, 1,50 , 1,75 powinno załatwić sprawę.
{1,33}, 1,67} to bleee.
Mariusz Bruniewski napisał(a):
Moim zdaniem nie potrzeba algorytmów brute force, czyli dobieraniem każdej liczby z każdą wywołaną np. przez
randomize.Czas takiego doboru może byc bardzo długi jeśli nie wyznaczy się w algorytmie poszukiwań. Myślę, że grafy szybciej by załatwiły sprawę.
Mówisz o moim rozwiązaniu? Skąd pomysł, że chcę użyć randomize? Rekurencja starczy.
Ja bym to wrzucił do ILP i po problemie. Dla podanych przykładów liczy się to w 1.84s na jakimś i5 sprzed pięciu lat, więc na luziku. Kod ma 20 linii z użyciem CPLEX i tej biblioteczki https://github.com/afish/CplexMilpSolver
public static void Start() {
var solver = new CplexMilpSolver(23);
var result = solver.FromConstant(711000000);
IVariable[] numbers = Enumerable.Range(0, 4).Select(w => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray();
numbers.Aggregate(solver.FromConstant(0), (a, b) => a.Operation(OperationType.Addition, b)).Operation(OperationType.Multiplication, solver.FromConstant(100*100*100)).Set(ConstraintType.Equal, result);
numbers.Aggregate(solver.FromConstant(1), (a, b) => a.Operation(OperationType.Multiplication, b)).Set(ConstraintType.Equal, result);
var goal = solver.FromConstant(0);
solver.AddGoal("Goal", goal.Operation(OperationType.Negation));
solver.Solve();
foreach(var c in numbers) {
Console.WriteLine(solver.GetValue(c));
}
}
PS Jestem autorem tej biblioteczki, więc jest to na swój sposób autopromocja, ale użycie jej nie jest niezbędne.