Thread View: pl.comp.lang.funkcyjne
5 messages
5 total messages
Started by Czarek
Sat, 17 Oct 2009 12:43
zupki
Author: Czarek
Date: Sat, 17 Oct 2009 12:43
Date: Sat, 17 Oct 2009 12:43
123 lines
3794 bytes
3794 bytes
Witam.
Kolega zbiera saszetki z promocyjnych zupek, zadanie jest takie:
W każdej saszetce jest kwota, trzeba znaleźć okrągłą sumę tych kwot nie
większą niż 10000, czyli może być 1000, 2000, 3000 ...9000,10000 .
Na razie robię to tak:
Wybieram wszystkie możliwe kombinacje ze zbioru danych i sumuję wybrane
liczby i sprawdzam czy sumy są podzielne przez 1000. Niestety tych liczb
jest już ponad 30 i czas zaczyna być długi.
Do tej pory zoptymalizowałem trochę w taki sposób, że liczenie sumy jest
przerywane przy przekroczeniu 10000. Ale to niewiele dało.
Wpadłem na taki pomysł, że można wyliczyć ile najmniejszych liczb ze
zbioru danych daje sumę większą niż załozona. Można by w taki sposób
wybierać zestawy liczące np nie więcej niż 7 liczb. Co o tym sądzicie?
Jak prosto to zaprogramować? Niby można za pomocą 6 zagnieżdżonych
pętli, ale przy dopisaniu liczby może zajść konieczność modyfikacji
tekstu programu i ponownej kompilacji.
Poniżej działający program w pascalu (jeszcze dla wszystkich możliwych
zestawów):
--------------------------------------------
program zupki;
{$mode objfpc}{$H+}
uses
{$IFDEF UNIX}{$IFDEF UseCThreads}
cthreads,
{$ENDIF}{$ENDIF}
Classes
{ you can add units after this };
type dane =record
liczba : array[1..100] of integer;
flaga : array[1..101] of boolean;
ilosc : byte;
end;
const
suma_max=10000;
var
liczby : dane;
procedure wczytaj(var liczby : dane);
var
plik : text;
s:integer;
begin
liczby.ilosc :=0;
assign(plik,'');
reset(plik);
while not eof(plik) do
begin
inc(liczby.ilosc);
readln(plik,s);
liczby.liczba[liczby.ilosc] := s;
liczby.flaga[liczby.ilosc] := false;
end;
writeln;
write('wczytano ');
writeln(liczby.ilosc,' liczb');
writeln;
close(plik);
end;
function zwieksz(var liczby : dane) : boolean;
var
pozycja : byte;
przeniesienie : boolean;
begin
pozycja := 1;
while liczby.flaga[pozycja] = true do
begin
liczby.flaga[pozycja] := false;
inc (pozycja);
end;
liczby.flaga[pozycja] := true;
if pozycja > liczby.ilosc then
zwieksz :=false
else
zwieksz := true;
end;
procedure suma(liczby : dane);
var
suma : longint;
k : byte;
begin
suma:=0;
for k:= 1 to liczby.ilosc do
begin
if liczby.flaga[k] then suma := suma + liczby.liczba[k];
if suma >suma_max then break; {przyspiesza prawie 1,5 raza }
end;
if ((suma mod 1000) = 0) and (suma <= suma_max) and (suma >0) then
begin
for k:=1 to liczby.ilosc do
if liczby.flaga[k] then write ('+',liczby.liczba[k]);
writeln('=',suma);
end;
end;
begin
wczytaj(liczby);
repeat
suma(liczby);
until not zwieksz(liczby);
end.
--
Cezary Grądys
czarekgr@wa.onet.pl
Re: zupki
Author: Czarek
Date: Sat, 17 Oct 2009 12:53
Date: Sat, 17 Oct 2009 12:53
22 lines
1527 bytes
1527 bytes
Czarek pisze:
> Jak prosto to zaprogramować? Niby można za pomocą 6 zagnieżdżonych
> pętli, ale przy dopisaniu liczby może zajść konieczność modyfikacji
> tekstu programu i ponownej kompilacji.
Miałem na myśli, że trzeba użyć 2,3,4,5 i 6 pętli, żeby wybierać
zestawy liczące 2,3 .. 6 liczb. Coś w stylu
for a := 1 to ilosc - 1 do
for b := a + 1 to ilosc do
begin
sumowanie;
end;
dla sumowania zestawu 2 liczb. Dla 3 - 3 pętle itp.
Może ktoś ma bardziej elegancki pomysł, aby nie rekurencyjnie, maszynka
nie podoła.
--
Cezary Grądys
czarekgr@wa.onet.pl
Re: zupki
Author: Czarek
Date: Sun, 18 Oct 2009 11:50
Date: Sun, 18 Oct 2009 11:50
43 lines
2327 bytes
2327 bytes
Czarek pisze:
> Czarek pisze:
>
>> Jak prosto to zaprogramować? Niby można za pomocą 6 zagnieżdżonych
>> pętli, ale przy dopisaniu liczby może zajść konieczność modyfikacji
>> tekstu programu i ponownej kompilacji.
>
> Miałem na myśli, że trzeba użyć 2,3,4,5 i 6 pętli, żeby wybierać
> zestawy liczące 2,3 .. 6 liczb. Coś w stylu
> for a := 1 to ilosc - 1 do
> for b := a + 1 to ilosc do
> begin
> sumowanie;
> end;
>
> dla sumowania zestawu 2 liczb. Dla 3 - 3 pętle itp.
>
> Może ktoś ma bardziej elegancki pomysł, aby nie rekurencyjnie, maszynka
> nie podoła.
>
Już sobie z tym poradziłem.
Sortuje dane wejściowe, sumuje po kolei od najmniejszej do przekroczenia
załozonej sumy i już wiem ile maksymalnie danych trzeba wybrać ze zbioru
wejściowego.
Potem już tylko w pętli
for k :=1 to mk do
kombinacje(n,k);
Czas wykonania spadł 50..60 razy (dla 35 liczb).
Na razie do przyjęcia, ale mam kolejny pomysł. Jeśli wybieram zbiory 2
elementowe i suma najmniejszej i najwiekszej liczby jest za duża, to
mogę śmiało wywalić z danych wejściowych największą liczbę. Jesli 3
elementowe sprawdzam sumę 2 najmniejszych i największą. Myślę, że to
może też znacznie przyspieszyć.
Czy tu ktoś zagląda?
Pozdrawiam
--
Cezary Grądys
czarekgr@wa.onet.pl
Re: zupki
Author: luckboy
Date: Tue, 20 Oct 2009 09:55
Date: Tue, 20 Oct 2009 09:55
42 lines
2371 bytes
2371 bytes
Czarek pisze: > Czarek pisze: >> Czarek pisze: >> >>> Jak prosto to zaprogramować? Niby można za pomocą 6 zagnieżdżonych >>> pętli, ale przy dopisaniu liczby może zajść konieczność modyfikacji >>> tekstu programu i ponownej kompilacji. >> >> Miałem na myśli, że trzeba użyć 2,3,4,5 i 6 pętli, żeby wybierać >> zestawy liczące 2,3 .. 6 liczb. Coś w stylu >> for a := 1 to ilosc - 1 do >> for b := a + 1 to ilosc do >> begin >> sumowanie; >> end; >> >> dla sumowania zestawu 2 liczb. Dla 3 - 3 pętle itp. >> >> Może ktoś ma bardziej elegancki pomysł, aby nie rekurencyjnie, >> maszynka nie podoła. >> > > Już sobie z tym poradziłem. > Sortuje dane wejściowe, sumuje po kolei od najmniejszej do przekroczenia > załozonej sumy i już wiem ile maksymalnie danych trzeba wybrać ze zbioru > wejściowego. > Potem już tylko w pętli > > for k :=1 to mk do > kombinacje(n,k); > > Czas wykonania spadł 50..60 razy (dla 35 liczb). > Na razie do przyjęcia, ale mam kolejny pomysł. Jeśli wybieram zbiory 2 > elementowe i suma najmniejszej i najwiekszej liczby jest za duża, to > mogę śmiało wywalić z danych wejściowych największą liczbę. Jesli 3 > elementowe sprawdzam sumę 2 najmniejszych i największą. Myślę, że to > może też znacznie przyspieszyć. > Czy tu ktoś zagląda? > > Pozdrawiam > A może programowanie dynamiczne?
Re: zupki
Author: Czarek
Date: Tue, 20 Oct 2009 20:30
Date: Tue, 20 Oct 2009 20:30
17 lines
1533 bytes
1533 bytes
luckboy pisze: > A może programowanie dynamiczne? Dzięki za sugestię, faktycznie to podobny problem do problemu plecakowego. W wolnych chwilach sobie poczytam. Ale już mi się nie chce dalej optymalizować. Robię to dla zabawy, mogę trochę poczekać, aby nie był to czas liczony w dobach:) Na razie czas jest rzędu sekund przy ok 40 liczbach. Zastosowałem ostatni pomysł z usuwaniem największych liczb ze zbioru danych, to zmniejszyło czas do ok 1/3 pierwotnego. -- Cezary Grądys czarekgr@wa.onet.pl
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads