W jaki sposób możemy opracować dynamiczny algorytm programowania, który oblicza minimalną liczbę różnych liczb pierwszych, które się sumują x?
Załóżmy, że programowanie dynamiczne oblicza minimalną liczbę różnych liczb pierwszych, spośród których jest największa p za każdą parę x i p. Czy ktoś może pomóc?
Odpowiedzi:
7 dla odpowiedzi № 1Jeśli założymy Hipoteza Goldbacha jest prawdą, wtedy każda parzysta liczba całkowita> 2 jest sumą dwóch liczb pierwszych.
Znamy więc odpowiedź, jeśli x jest parzyste (1 jeśli x == 2 lub 2 inaczej).
Jeśli x jest nieparzyste, to są 3 przypadki:
- x jest pierwsze (odpowiedź to 1)
- x-2 jest liczbą pierwszą (odpowiedź to 2)
- w przeciwnym razie x-3 jest liczbą parzystą większą niż 2 (odpowiedź to 3)
1 dla odpowiedzi nr 2
Przede wszystkim potrzebujesz listy liczb pierwszych do x. Nazwijmy tę tablicę liczb całkowitych.
Teraz chcemy zapełnić odpowiedź tablicową [x] [p], gdzie x jest sumą liczb pierwszych, a p jest maksymalną dla każdej liczby głównej w zbiorze (ewentualnie włączając, ale niekoniecznie włączając p).
Po wszystkich obliczeniach istnieją 3 możliwości odpowiedzi [x] [p]:
1) jeśli p = x i p jest liczbą pierwszą => odpowiedź [x] [p] zawiera 1
2) jeśli nie można rozwiązać problemu dla podanego x, p => odpowiedź [x] [p] zawiera -1
3) jeśli możliwe jest rozwiązanie problemu dla podanego x, p => odpowiedź [x] [p] zawiera liczbę liczb pierwszych
Podczas obliczeń jest jeszcze jedna możliwa wartość odpowiedzi [x] [p]:
4) nie rozwiązaliśmy jeszcze problemu z podanym x, p => odpowiedź [x] [p] zawiera 0
Jest całkiem oczywiste, że 0 nie jest odpowiedzią na nic poza x = 0, więc jesteśmy bezpieczni inicjalizując tablicę z 0 (i robiąc specjalną obróbkę dla x = 0).
Aby obliczyć odpowiedź [x] [p] możemy iterować (niech qjest wartością podstawową, którą sprawdzamy) przez wszystkie liczby pierwsze do (włącznie) p i znaleźć minimum powyżej 1 odpowiedzi [xq] [q-1] (nie rozważaj całej odpowiedzi [xq] [q-1] = - 1 przypadki chociaż). Tutaj 1 przychodzi dla q, a odpowiedź [x-q] [q-1] powinna być obliczona w rekursywnym wywołaniu lub przed obliczeniami.
Teraz mała optymalizacja: iteruj liczby pierwsze od wyższego do niższego, a jeśli x / q jest większe od bieżącej odpowiedzi, możemy zatrzymać, ponieważ aby uzyskać sumę x, potrzebujemy co najmniej x / q liczb pierwszych. Na przykład, nie weźmiemy pod uwagę q = 2 dla x = 10, ponieważ mamy już odpowiedź = 3 (faktycznie, zawiera ona 2 jako jedną z 3 liczb pierwszych - 2 + 3 + 5, ale już to mamy poprzez rekursywną odpowiedź wywołania (10-5, 4)), ponieważ 10/2 = 5, to znaczy, że otrzymamy 5 jako odpowiedź w najlepszym przypadku (w rzeczywistości nie istnieje dla q = 2).
package ru.tieto.test;
import java.util.ArrayList;
public class Primers {
static final int MAX_P = 10;
static final int MAX_X = 10;
public ArrayList<Integer> primes= new ArrayList<>();
public int answer[][] = new int[MAX_X+1][MAX_P+1];
public int answer(int x, int p) {
if (x < 0)
return -1;
if (x == 0)
return 0;
if (answer[x][p] != 0)
return answer[x][p];
int max_prime_idx = -1;
for (int i = 0;
i < primes.size() && primes.get(i) <= p && primes.get(i) <= x;
i++)
max_prime_idx = i;
if (max_prime_idx < 0) {
answer[x][p] = -1;
return -1;
}
int cur_answer = x+1;
for (int i = max_prime_idx; i >= 0; i--) {
int q = primes.get(i);
if (x / q >= cur_answer)
break;
if (x == q) {
cur_answer = 1;
break;
}
int candidate = answer(x-q, q-1);
if (candidate == -1)
continue;
if (candidate+1 < cur_answer)
cur_answer = candidate+1;
}
if (cur_answer > x)
answer[x][p] = -1;
else
answer[x][p] = cur_answer;
return answer[x][p];
}
private void make_primes() {
primes.add(2);
for (int p = 3; p <= MAX_P; p=p+2) {
boolean isPrime = true;
for (Integer q : primes) {
if (q*q > p)
break;
if (p % q == 0) {
isPrime = false;
break;
}
}
if (isPrime)
primes.add(p);
}
// for (Integer q : primes)
// System.out.print(q+",");
// System.out.println("<<");
}
private void init() {
make_primes();
for (int p = 0; p <= MAX_P; p++) {
answer[0][p] = 0;
answer[1][p] = -1;
}
for (int x = 2; x <= MAX_X; x++) {
for (int p = 0; p <= MAX_P; p++)
answer[x][p] = 0;
}
for (Integer p: primes)
answer[p][p] = 1;
}
void run() {
init();
for (int x = 0; x <= MAX_X; x++)
for (int p = 0; p <= MAX_P; p++)
answer(x, p);
}
public static void main(String[] args) {
Primers me = new Primers();
me.run();
// for (int x = 0; x <= MAX_X; x++) {
// System.out.print("x="+x+": {");
// for (int p = 0; p <= MAX_P; p++) {
// System.out.print(String.format("%2d=%-3d,",p, me.answer[x][p]));
// }
// System.out.println("}");
// }
}
}
0 dla odpowiedzi № 3
Zacznij od listy wszystkich liczb pierwszych niż x. Weź największy. Teraz musimy rozwiązać problem (x - pmax). Na tym etapie będzie to łatwe, x - pmax będzie niskie. Zaznacz wszystkie liczby pierwsze jako "używane" i przechowuj rozwiązanie 1. Teraz weź największą z liczb wciąż leżącą na liście i powtarzaj, aż wszystkie liczby pierwsze zostaną użyte lub odrzucone. Jeśli (x - pmax) jest wysoki, problem staje się bardziej złożony.
To jest twój pierwszy przebieg, algorytm brutalnej siły. Zacznij to najpierw, zanim zastanowisz się, jak przyspieszyć działanie.
0 dla odpowiedzi nr 4
Zakładając, że nie używasz hipotez Goldbacha, w przeciwnym razie patrz doskonała odpowiedź Petera de Rivaza:
dynamiczne programowanie zazwyczaj wykorzystuje nakładające się podproblemy. Zwykle przechodzisz z góry do dołu, ale w tym przypadku oddolne może być prostsze
Sugeruję, że sumujesz różne kombinacje liczb pierwszych.
lookup = {}
for r in range(1, 3):
for primes in combinations_with_replacement(all_primes, r):
s = sum(primes)
lookup[s] = lookup.get(s, r) //r is increasing, so only set it if it"s not already there
zacznie się bardzo wolno, jeśli tymiej dużą liczbę liczb pierwszych, w tym przypadku zmień maks. r na coś takiego jak 1 lub 2, bez względu na to, co maksimum jest wystarczająco szybkie dla ciebie, a wtedy pozostanie ci kilka liczb, które nie zostaną znalezione, aby rozwiązać liczba, która nie ma rozwiązania w wyszukiwaniu, spróbuj podzielić tę liczbę na sumy liczb, które znajdują się w odnośniku (być może trzeba będzie zapisać kombinacje pierwszorzędne w odnośniku i odrzucić te kombinacje).