[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

pl.comp.programming

Pytanie o algorytm

julekmen

12/9/2006 4:03:00 PM

Witam,

Mamy dwie tablice liczb. W obu tablicach liczby s± u³o¿one niemalej±co.
Chcê wygenerowaæ tablicê stanowi±c± "minimaln± sumê" z tych dwóch ci±gów.
Np. mamy 2 ci±gi:
Kod:
0 1 2 3 4 5 6 (to s± indeksy)
0 7 8 8 10 19 19
0 2 7 12 18 27 32


Do wyniku wpisujemy w n - tym elemencie tablicy minimaln± sumê indeksów,
których suma jest równa wynikowemu indeksowi. Tutaj wynik to:

Kod:
0 1 2 3 4 5 6
0 2 7 8 10 12 17 (itd.)


Ma kto¶ pomys³ na algorytm w czasie mniej ni¿ kwadratowym?

Z góry dziêki


3 Answers

Andrzej 'Rudy' Dabrowski

12/9/2006 5:34:00 PM

0

bim_bom narze?bi3(a):

> Witam,
>
> Mamy dwie tablice liczb. W obu tablicach liczby s? u3o?one niemalej?co.
> Chce wygenerowaa tablice stanowi?c? "minimaln? sume" z tych dwóch ci?gów.
> Np. mamy 2 ci?gi:
> Kod:
> 0 1 2 3 4 5 6 (to s? indeksy)
> 0 7 8 8 10 19 19
> 0 2 7 12 18 27 32
>
>
> Do wyniku wpisujemy w n - tym elemencie tablicy minimaln? sume indeksów,
> których suma jest równa wynikowemu indeksowi. Tutaj wynik to:
>
> Kod:
> 0 1 2 3 4 5 6
> 0 2 7 8 10 12 17 (itd.)
>
>
> Ma kto? pomys3 na algorytm w czasie mniej ni? kwadratowym?

Najpierw porównaj pierwsze wyrazy ci?gów. "Od3ó?" ten mniejszy i wywo3aj
procedure rekurencyjnie na tych samych ci?gach (jeden jest zmniejszony o
ten mniejszy element!). Wykonuj to do momentu, a? osi?gniesz wystarczaj?c?
liczbe czynników. Czas O(n).

--
Pozdrawiam, Andrzej

Jakub Lisowski

12/9/2006 6:34:00 PM

0

Dnia Sat, 9 Dec 2006 17:02:47 +0100, bim_bom <julekmen@go2.pl>
w <elemn6$vcs$1@news.onet.pl> napisa3:

> Witam,
>
> Mamy dwie tablice liczb. W obu tablicach liczby s? u3o?one niemalej?co.
> Chce wygenerowaa tablice stanowi?c? "minimaln? sume" z tych dwóch ci?gów.
> Np. mamy 2 ci?gi:
> Kod:
> 0 1 2 3 4 5 6 (to s? indeksy)
> 0 7 8 8 10 19 19
> 0 2 7 12 18 27 32
>
>
> Do wyniku wpisujemy w n - tym elemencie tablicy minimaln? sume indeksów,
> których suma jest równa wynikowemu indeksowi. Tutaj wynik to:
>
> Kod:
> 0 1 2 3 4 5 6
> 0 2 7 8 10 12 17 (itd.)

Niejasne toto.
Móg3by? rozpisaa, sk?d sie wzie3y wyniki dla poszczególnych pozycji
pe3numi zdaniami, opisowo?

ja czyli jakub
--
Z zaparkowanego Forda Fulkersona wysiedli genera3 Grant i porucznik
Revoke.

julekmen

12/10/2006 10:14:00 AM

0


U¿ytkownik "Jakub Lisowski" <jakub@SPAMFILTER.kofeina.net> napisa³ w
wiadomo¶ci news:slrnenm0c9.v4i.jakub@jakub.kofeina.net...
> Dnia Sat, 9 Dec 2006 17:02:47 +0100, bim_bom <julekmen@go2.pl>
> w <elemn6$vcs$1@news.onet.pl> napisa³:
>
>> Witam,
>>
>> Mamy dwie tablice liczb. W obu tablicach liczby s± u³o¿one niemalej±co.
>> Chcê wygenerowaæ tablicê stanowi±c± "minimaln± sumê" z tych dwóch ci±gów.
>> Np. mamy 2 ci±gi:
>> Kod:
>> 0 1 2 3 4 5 6 (to s± indeksy)
>> 0 7 8 8 10 19 19
>> 0 2 7 12 18 27 32
>>
>>
>> Do wyniku wpisujemy w n - tym elemencie tablicy minimaln± sumê indeksów,
>> których suma jest równa wynikowemu indeksowi. Tutaj wynik to:
>>
>> Kod:
>> 0 1 2 3 4 5 6
>> 0 2 7 8 10 12 17 (itd.)

Oznaczaj±c Tab1 (tablica pierwsza), Tab2(tablica druga),TabW(tablica
wynikowa, na dole).
TabWyn[0]=Tab1[0]=Tab2[0]; // bo inaczej nie mo¿na
TabWyn[1]=Tab2[1]; // bo Tab2[1]<Tab1[1]
TabWyn[3]=Tab1[3];
TabWyn[4]=Tab1[4];
TabWyn[5]=Tab1[4]+Tab2[1]; // 4+1= 5, a suma tych akurat elementów jest
najmniejsza
TabWyn[6]=Tab1[4]+Tab2[2];

Warto¶ci w TabWyn s± wybierane jako najmniejsze, jakie mog± byæ, spe³niaj±ce
warunek:
TabWyn[n]=Tab1[k]+Tab2[n-k];

Pozdrawiam!