Cara itu terkenal dengan nama Dynamic Programming. Kalo tertarik bikin code2 menarik, itu ladangnya ada di Programming Contest.
Ini ada problem yang lebih menantang: Diberikan array of integer A (0-based index). Saya ingin mencari bilangan integer terkecil di array A dengan index antara [i, j] (inclusive). Jawabannya harus dalam O ( log N ) Jelas kalo looping dari i sampai j itu gak boleh karena itu O ( N ). Ada yang bisa? Kalau tertarik soal2 seperti itu, anda harusnya masuk Programming Contest. FYI, Google suka orang2 yang tahu banyak algorithms ;) Makanya Google ngadain "Google Code Jam" tiap tahun. Milis yang membahas Programming Contest di indo itu: http://groups.yahoo.com/group/indo-algo Tapi sepi nih... disini malah seru :D, bener2 aneh... Felix Halim On Fri, Jun 6, 2008 at 4:57 PM, Jecki Sumargo <[EMAIL PROTECTED]> wrote: > On Fri, Jun 6, 2008 at 3:16 PM, naray citra <[EMAIL PROTECTED]> wrote: >> Gw dapet cuplikan kode menarik neh, untuk share aja, sapa tau ada yang butuh >> :D >> sumber : http://linkmingle.com/details/865 >> >> There is an array A[N+1] of N integers. You have to compose an array >> Output[N+1] such that Output[i] will be equal to the productof all the >> elements of A[] except A[i]. >> Example: >> INPUT:[4, 3, 2, 1, 2] >> OUTPUT:[12, 16, 24, 48, 24] >> >> Solve it without division operator and in O(n) with out using division >> >> import java.util.Arrays; >> >> public class PArray { >> >> public int[] PSub(int[] inp){ >> int[] out = new int[inp.length]; >> out[0]=1;out[1]=inp[0]; >> for (int i = 2; i <inp.length ; i++) >> out[i] = inp[i-1]*out[i-1]; >> int P = 1; >> for(int i=inp.length-2;i>=0;i--){ >> P*=inp[i+1]; >> out[i]=out[i]*P; >> } >> return out; >> } >> public static void main(String[] args) { >> PArray pArray = new PArray(); >> int in[] = new int[]{4,3,2,1,2}; >> System.out.println("INPUT:"+ >> Arrays.toString(in)); >> System.out.println("OUTPUT:"+ >> Arrays.toString(pArray.PSub(in))); >> } >> } >> > > Wah ini hasilnya O(n) ato ga ya? Dilihat2 sepertinya ini O(n^2) > soalnya ada inner loop yg jumlahnya mendekati n. CMIIW. > > Seru juga. Masih blom ketemu caranya nih :) > > ------------------------------------ > > Kalau mau keluar dari mailing list ini, caranya kirim sebuah email ke [EMAIL > PROTECTED] > > Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id > > Yahoo! Groups Links > > > >
