Jakiś czas temu pracowałem nad problemem programowania (CCC). W poprzednich konkursach natknąłem się na podobne pytania, więc zdecydowałem się zapytać o to. Problem jest w zasadzie taki.Konwersja prostej metody rekursywnej, która powraca w pętli do metody iteratywnej
Dostajesz n ludzi i p kawałki ciasta.
n ludzie stoją z rzędu.
Musisz rozprowadzić między nimi kawałki ciasta. Poszukujesz i każda osoba musi otrzymać co najmniej tyle sztuk, ile osoba przed nimi. Każda osoba musi otrzymać co najmniej jeden kawałek ciasta i nie może pozostać żaden placek.
Należy zwrócić liczbę możliwych sposobów dystrybucji ciasta.
udało się utworzyć następujące rozwiązanie rekurencyjne ale trwa zbyt długo (więcej niż 5 sekund) w następujących źródłach:
120 części 20 osób -> 97.132.873
kawałki 250, 130 osób -> 1844349560
Moje rozwiązanie:
import java.io.*;
public class Main
{
int pieces, people;
int combinations = 0;
public void calculate (int person, int piecesLeft, int prev)
{
if (person == people)
{
if (piecesLeft == 0)
combinations++;
}
else
{
for (int x = prev ; (x * (people - person)) <= piecesLeft ; x++)
{
calculate (person + 1, piecesLeft - x, x);
}
}
}
public static void main (String[] args) throws Exception
{
Main m = new Main();
BufferedReader in = new BufferedReader (new InputStreamReader (System.in));
//m.pieces = Integer.parseInt (in.readLine());
//m.people = Integer.parseInt (in.readLine());
m.pieces=250;
m.people=130;
if (m.people == m.pieces)
System.out.println (1);
else if (m.people == 1)
System.out.println (1);
else
{
m.calculate (0, m.pieces, 1);
System.out.println (m.combinations);
}
}
}
Znalazłem następujące rozwiązanie Pythona z nieoficjalnych rozwiązań, które z tego co under tand, w zasadzie tworzy tablicę już napotkanych wartości.
visited = []
def pi(n,k,min):
if visited [n][k][min] == 0:
if n == k:
visited[n][k][min] = 1
elif k == 1:
visited[n][k][min] = 1
else:
t = 0
for i in range (min, (n/k)+1):
t = t + pi(n-i, k-1, i)
visited[n][k][min] = t
return visited[n][k][min]
file = open("j5.10.in", "r")
n = int(file.readline())
k = int(file.readline())
for i in range(n+1):
x = []
for j in range(k+1):
t = []
for kk in range(n+1):
t.append (0)
x.append(t)
visited.append(x)
print pi(n,k,1)
Co chcę zrobić, to zrobić rozwiązanie z jednego z nich, ale nie jestem pewien, jak to zrobić. Z tego co rozumiem, może nie być dużej różnicy prędkości, ale w jeszcze większych przypadkach pozwoli mi to uniknąć przepełnień stosu.
Proszę wprowadzić wcięcie kodu –
Jak szybkie jest rozwiązanie Python? –
Wierzę, że osoba, która to napisała powiedziała, że zajęło to 3 sekundy na jego komputerze w największej próbie. Mój przejmuje 10. –