Sfidë për të gjetur kufizat natyrore të një shume

[edspace]

Është me vënd përmirësimi që ke përmendur dhe programi funksionon si më parë.

Nuk është e nevojshme të kontrollojmë kombinacione ku kufiza më e vogël është më e madhe se gjysma sepse shuma e dy kufizave më të mëdha se gjysma është më e madhe se shuma e dhënë nga përdoruesi. Për shembull, nëse n=5, nuk është e nevojshme të kontrollojmë nënbashkësitë [3 3], [3 4], [3 5], [4 4], [4 5], [5 5] sepse shuma e tyre është gjithnjë më e madhe se 5.

Argumentuar ndryshe, mund të themi se nëse një kufizë është më e madhe se n/2, kufizat e tjera duhet të jenë më të vogla se n/2. Për të gjetur kufizat më të vogla se kufiza fillestare, funksioni rekursiv duhet të zvogëlojë argumentin nisje. Kjo nuk ndodh në funksionin rekursiv, kështu që kemi vërtetuar se kufizat e tjera do jenë gjithnjë më të mëdha se n/2 dhe shuma e tyre më e madhe se n. Pra, është e kotë të thërasim funksionin rekursiv ku argumenti i nisjes është më i madh se n/2.

Programi im më lart i kryen këto thirrje të kota të funksionit rekursiv por nuk vazhdon të thërasë vetveten sepse (n/2) + (n/2 + 1) > shuma. Pra, edhe pse bëhen n/2 thirrje të kota të funksionit rekursiv, ato nuk kanë ndikim në rritjen e algoritmit.

Për të shmangur edhe n thirrje të tjera, mund të fillojmë rekursionin me kufizën 2, sepse kufiza 1 është zgjidhje vetëm për shumën 1.

Si përmbledhje, nëse e nisim kërkimin me kufizën 2 dhe e ndalojmë kur kufiza më e vogël është n/2, kursejmë n + n/2 thirrje. Për të shfrytëzuar këto optimizime, funksioni zbertheShumen(uint shuma) duhet të ndryshohet si më poshtë:

void zbertheShumen(uint shuma) {
  if (shuma == 1) {
    return 1;
  }

  Thyese<uint> zero(0 ndaj 1);
  list<uint> kufizat;

  uint fund = shuma / 2;
  for (int i = 2; i <= fund; i++) {
    zbertheShumen(i, i, shuma, zero, kufizat);
  }
} 

Borix, a mund të na tregosh hapat që ndjek algoritmi yt? Vura re se është më i ngadaltë, por nuk e di cili është faktori kryesor i ngadalësisë. Si autori i programit, ti mund t'ia bësh më mirë analizën.

[Borix]

Edspace pershendetje,

Algoritmin tim (iterativ) e kam ndertuar per nje profesor matematike, i cili vertetoi problemen e Nash me ane te metodes "induksion me blloqe." Per kete arsye, mora nje loop "for" per numrat nga 1 deri ne 76, sepse aq mjaftonin per hapat induktive. Pa marre kete gje parasysh (e cila e ngadaleson programin), me lejoni te shpjegoj hapat iterative te algoritmit tim.

1. Kufizat fillestare

Kam deklaruar nje vektor v, i cili do te ruaje kufizat e mundshme per nje shume te dhene n. Per cdo n, vektori inicializohet me n/2 dysha, dhe jo me n njesha (pse?).

2. Loop-i while

Ky loop ndalon se iteruari kur variabli boolean done merr vleren TRUE (do ta shpjegoj me poshte se si). Variabli s kontrollon shumen e kufizave te pranishme tek vektori v.

Per cdo iteracion, nese shuma aktuale e kufizave e kalon ose eshte me e vogel se numri i dhene n, atehere snippet-i i mëposhtem korrigjon elementin e fundit te vektorit:

 			
// elementi i fundit += [shuma - numrin e dhene]:
	if (sn) {
		v[i-1]-=s-n;
	}

Snippet-i i meposhtem kontroll nese shuma e thyesave eshte 1.0, >1.0 ose <1.0:

	sum=0.0; // LLOGARIT SHUMEN
	for (i=0;i=0.9999999999 && sum<=1.0000000001 && v[k-1]>=v[k-2]){
		fprintf(fout,"   ");
		for (i=0;i

Nese shuma eshte 1.0, atehere rezultati printohet ne skedarin “result.txt”.

Kaq per llogaritjet elementare. Me poshte vijon shpjegimi i algoritmit ne baze te programit.

3. Algoritmi

Kemi vektorin v[]=2|2|...|2| (pra n/2 dysha). Sic mund ta kesh vene re, variablet l dhe k merren me indeksimin e kufizave. Fillimisht ato kane vlerat

	l=0; 
	k=1;

Brenda loopit, variabli l merr vleren:

	l=k-2; // indeksi per el. e parafundit te zones se testimit aktual

Pra keto dy variabla percaktojne hapsiren aktuale te kërkimit. Nese l==-1, atehere hapësira duhet zgjeruar. Kjo behet me ane te kodit:

	// zgjero hapesiren e kerkimit:
	if (l==-1){
		++k; l=0;
		while (l

Cdo te thote? Vektori fillimisht ka nje hapesire te vogel: v[]=2, pra l=0 dhe k=1. Brenda loopit, vlera e variablit s eshte s=2. Nese numri i dhene [b]n[/n] eshte me i madh se 2, atehere vlera e fundit e vektorit behet n-s+v[k]. Pra nese n=6, atehere elementi i fundit behet 6-2+2=6, dhe vektori do te jete ne gjendjen: v[]=6. Testohet nese shuma e thyesave eshte 1.0 (qe ne rastin tone nuk eshte e tille), dhe l=k-2. (Kontrollo per rastin n=1).

Megjithate, sic e ke përmendur dhe ti me siper, testimi duhet te ndaloje atehere kur elementet e vektorit ne baze indeksi (pra nga indeksi me vlere zero ne indeksin me vlere n/2) jane me te mëdhenj ne fillim se sa ne fund. Pra, nuk duhen testuar vlera te tilla si: 4|3|3 sepse algoritmi na siguron qe do te kete testuar njehere me pare vlerat 3|3|4. Per kete arsye, snippet-i i meposhtem kontrollon kete kusht:

	++v[l]; // Elementi me indeks l inkrementohet, per te testuar vlera te reja.

	/* nese elementi i parafundit (dhe para inkrementimit)
	 eshte me i madh ose baraz me elementin e fundit
	 atehere mbaron kerkimi ne ate pike. 
	*/
	if (v[l]-1>=v[l+1]) {
		l=k-2;
		while (v[l]>=v[k-1]){
			--l;
		}
			
		if (l>=0 && v[l]+1<=v[l+1]) ++v[l];
			
	}

Pra, vereni kushtin e if, dhe loop-in while. Per sa kohe qe elementet e vektorit me indeks me te vogel jane me te medha se elementi me indeksin k-1 (i cili eshte elementi i fundit i hapesires aktuale), dekrementoje indeksin l per te arritur tek ai element i cili eshte me i vogel se v[k-1]. Nese ai element gjendet, atehere indeksi l eshte >=0 dhe rritet me 1 (++v[l]) per te testuar kufizen tjeter. Tani, te gjithe elementet ndermjet indeksit l dhe k-1 do te marrin vleren e elementit v[l], sepse per deri sa ato elemente jane me te mëdhenj, testimi nuk ia vlen, pasi harxhon kohe. Kodi i meposhtem e realizon kete gje:

	s=0;
	for (i=0;iif (i>=l)
			v[i]=v[l];
		s+=v[i];
	}

Pra, llogaritet shuma e kufizave, por nese indeksi i eshte me i madh ose baraz me indeksin l, atehere vektori do te marre vleren v[l], pasi nese shumon vlerat v[i], algoritmi do te humbase testimin per kombinacionin e ri. SHIHNI SHEMBULLIN E MEPOSHTEM, DO TE JETE ME I QARTE.

Nese loop-i while nuk ekzekutohet, atehere l=k-2 do te mbaje vleren -1 dhe sipas pjeses se fundit te programit, nese l==-1, zgjerohet hapësira e kërkimit.

SHEMBULL

Marrim n=9. Pra, n/2=4.5 dhe rrumbullakoset ne 4. Pra, vektori v do te inicializohet me 4 dysha: v[]=2|2|2|2 (kjo nuk eshte e domosdoshme, por ka qendruar ne program pa arsye).

Fillimisht kemi vlerat l=0 dhe k=1. Pra hapësira aktuale e kërkimit eshte tek elementi: v[]=2.
Loop-i i pare do te llogarise shumen s, qe eshte s=2. If-i i pare do te gjeje qe shuma eshte me e vogel se n=9, prandaj elementi i fundit i vektorit kthehet ne 9 dhe: v[]=9. Indeksi l merr vleren k-2. Ne kete rast, ka vleren l=-1. Shuma e thyesave sum, eshte me vogel se 1.0. ++v[l] rrit elementin me indeks l, per te testuar kufize tjeter. Megjithate, l==-1, prandaj gjuha C e konsideron v[-1] nje dummy value. If-i i dyte nuk do te ekzekutohet. Por if-i i fundit (pra, if (l==-1)) ekzekutohet, dhe rrit vleren k. Pra, k=2, dhe ri-inicializon vektorin.

Loop-i while fillon perseri me vlerat vektoriale: v[]=2|2 (sepse l=0 dhe k=2). Shuma e kufizave, 2+2=4, eshte me e vogel se numri n=9, prandaj vektori kthehet ne gjendjen v[]=2|7. Llogaritet shuma e thyesave, qe nuk eshte 1.0, dhe l=k-2==0. Inkrementohet vlera v[l], pra nga 2 behet 3 dhe rifillon loop-i while me vlerat v[]=3|6. Pastaj vazhdon me vlerat v[]=4|5, pastaj vazhdon me v[]=5|4. POR, ketu ndalon testimi, sepse vlera 5|4 eshte testuar ne rastin 4|5. Per kete arsye, brenda if-it te dyte, loop-i whilee con indeksin l ne -1, dhe hapësira zgjerohet ne 2|2|2.

Ne pergjithesi testimi vazhdon ne kete menyre:

2|2|5
2|3|4
2|4|3 -STOP
3|3|3 -gjeti nje rast
3|4|3 –STOP
4|4|4 – STOP, shuma eshte 12, dhe variabli boolean done merr vleren TRUE, sepse shuma aktuale eshte 12, pra 12>n+2, pra 12>11 dhe programi ndalon, sepse cdo testim tjeter eshte i kote. (KETE GJE REALIZON DHE REKURSIONI I MODIFIKUAR I edspace).


Shembull tjeter per n=11: nga hapësira me e vogel (l=0,k=1) deri ne maksimumin qe arrin:

Hapësira = 1
V[]=11 – STOP

Hapësira = 2
V[]=2|9
3|8
4|7
5|6
6|5 – STOP

Hapsira = 3
V[]=2|2|7
2|3|6 – U GJET NJE VLERE
2|4|5
2|5|4 – STOP

V[]=3|3|5
3|4|4 – STOP

V[]=4|4|4 – STOP

Hapësira = 4
V[]=2|2|2|5
2|2|3|4
2|2|4|3 – STOP

V[]=2|3|3|3 – STOP (3==3)

V[]=3|3|3|2 – STOP (3>2)

V[] = 4|4|4|4 – PROGRAMI NDALON KETU, sepse 16>11+2.

--

Shpresoj te kem qene i qarte ne diskutimin e funksionimit te programit. Megjithate, kur teston nje vlere vete, atehere e kupton me mire.


Algoritmin qe paraqita me siper e kam modifikuar ne daten e dhene, sepse i pari qe bera testonte me shume kombinacione se sa duhej. Nevoje per permiresime ka, si psh ne koken e algoritmit, ku vektori v incializohet. Por keto nuk ndikojne ne kohe, vetem ne hapesire. Kam bere nje analize te kohes, por ky eshte nje algoritem i tipit kombinatorik: Po paraqes rezultate te analizes:

Number n: 84, Seconds: 1.000000

Number n: 85, Seconds: 1.000000

Number n: 86, Seconds: 1.000000

Number n: 87, Seconds: 1.000000

Number n: 88, Seconds: 1.000000

Number n: 89, Seconds: 2.000000

Number n: 90, Seconds: 2.000000

Number n: 91, Seconds: 2.000000

Number n: 92, Seconds: 3.000000

Number n: 93, Seconds: 4.000000

Number n: 94, Seconds: 4.000000

Number n: 95, Seconds: 5.000000

Number n: 96, Seconds: 5.000000

Number n: 97, Seconds: 6.000000

Number n: 98, Seconds: 7.000000

Number n: 99, Seconds: 8.000000

Number n: 100, Seconds: 9.000000

Number n: 101, Seconds: 10.000000

Number n: 102, Seconds: 11.000000

Per me teper, ekzistojne disa teorema ne Teorine e Serive te Fundme, te cilat mund te shtojne permiresimin e kohes te këtij algoritmi. Megjithate, pas nje diskutimi me kete prof. tim te Matematikes, algoritmi behet me kompleks per t’u implementuar. Nje permiresim i mundshem qe kam gjetur eshte përdorimi i mesatares aritmetike te kufizave per te llogaritur vlerat prospektive deri ne nje shkalle thellësia 2-3 nyje, ne menyre qe loop-i while te mos vazhdoje ekzekutimin e kote, por te ndaloje para kohe.

Duhet te kesh parasysh edhe implementimin time ne C. Nuk perdor ndonje data strukture, sic e sheh, dhe asnjë modulim, por vetem tipe te thjeshta. Kam menduar te perdore peme (i kam gjetur me praktike se listat) ne C++. Nje here u mendova rreth 40 sekonda per kete transformim dhe nxora përfundimin qe ishte me e leverdisshme te gjeja dicka tjeter per te bere...

[Borix]

Pra, algortimi i pergjithshem kombinatorik, permban analizen ne postimin e mesiperm, ndersa algoritmi i modifikuar permban kete analize.

Me nje analize diskrete kombinatorike, mund te llogarisim numrin e hapave te testimit, i cili jepet me shumen

1 + n/2 + n/3 + ... + n/(n/2) = 1 + SHUMA_(k=1 -> n/2)[n/k], ku k eshte hapesira (nga 1 ne n/2)

Pra, per hapesire k=1, algoritmi teston vetem nje here, per k = 2 algoritmi teston floor(n/2) e vlerave, e keshtu me rradhe.

Kam mendimin se hapat do te uleshin nese perdoren struktura te dhenash...

[edspace]

Faleminderit për shpjegimet e algoritmit. Falë shëmbujve që kishe dhënë arrita të kuptoja pak a shumë rrugën që ndjek algoritmi yt.

Të dy algoritmet tona ndjekin të njëjtën rrugë duke provuar të gjithë kombinacionet me radhë, rruga që do ndiqte një njeri nëse do i duhej të bënte llogaritë me dorë. Ndryshimi është se algoritmi im i përcjell shumat e kufizave nga një kombinacion në tjetrin, ndërsa algoritmi yt i mbledh të gjitha kufizat nga e para për çdo kombinacion. Këtu besoj vjen dhe ngadalësia.

E kam provuar programin tënd me vlera të ndryshme të n-së por nuk kam arritur të nxjerr rezultatet që ke shkruar ti më lart. Në kompjuterin që e kam testuar (Athlon 1.3 Ghz) algoritmit tënd i duheshin disa minuta vetëm për n=9. Nuk e di nëse ke kompjuter të shpejtë, apo ke modifikuar algoritmin për të nxjerrë rezultatet me sekonda. Rezultatet që ke hedhur u afrohen rezultateve të algoritmit rekursiv.

Lista që kam përdorur unë është e ngjashme me matricën v[] që ke përdorur ti. Unë i shtoj dhe i heq kufizat nga lista, ndërsa ti mbush dhe zbraz matricën.

Nuk e di si mund të hyjë në punë pema për këtë algoritëm. Veprimet e listës (shto/hiq nga fundi) kryhen në kohë konstante ndërsa veprimet e pemës kryhen në kohë log(n).

Jam kurioz të shoh kodin për algoritmin e ri që ta krahasoj me të vjetrin.

[Borix]

Kodin e kam kompiluar ne MS VC++. Cuditem per faktin qe programit i duhen "disa minuta" per n=9. Te them te drejten, e kam ekzekutuar kete program ne nje Celeron edhe ka ecur sipas kohes se dhene... Nuk e di pse ty te ecen ngadale...

Pasi kam shkruar kete algoritem, po germoja per te gjetur ndonje teoreme ne serite e fundme. Ndertova edhe nje menyre e cila perdorte peme, por te them te drejten nuk e mbaj mend fare... Kam nje ves qe i gris gjerat qe shkruaj pas ca kohesh...

Edspace, zgjidhja jote ishte elegante dhe e sakte mbi te gjitha. Besoj se kesaj teme i erdhi fundi.

[edspace]

Është për t'u çuditur. E provova kodin tënd në Visual Studio 2003 dhe në gjendjen "debug" punon shpejt por nxjerr mesazhin "Run-Time Check Failure #2 - Stack around the variable 'v' was corrupted.". Në gjendjen "release" punon shumë ngadalë. Më parë e kisha provuar vetëm në gcc 3.4.2 dhe punonte gjithnjë ngadalë.

[Borix]

Edspace, nese e kompilon programin ne MS Visual Studio 6.0, ky gabim nuk shfaqet. Ky gabim del ne .NET, zakonisht kur kompiluesi mundohet te shkruaje ne nje zone memorie te gabuar (invalid). Po te vesh re programin tim, kur variabli l behet -1, atehere v[-1] eshte e paidentifikuar. Megjithate, po te mos kontrollohej nga nje nga if-et e programit, atehere C do te kthente nje vlere "dummy" te v[-1] (dhe mundesisht do te shfaqte nje gabim fatal). Sigurisht, programi mund te modifikohet ne kete menyre: te shtohet nje dhome me teper ne vektorin v. Ky nuk ka qene dhe aq synim kryesor ndaj synimit tim te zgjidhjes.

Si perfundim, ky gabim ndodh gjithnje kur nje vektor/liste eshte i painicializuar dhe kerkohet te aksesohet nga programi, ose kur indeksi del jashte kufijve te paracaktuar (ne rastin e vektorit).

[gimi_sky]

Implementimi im n'java jep per n=51 kto resultate:
2 4 7 16 22
2 4 7 17 21
2 4 9 10 26
3 3 5 10 30
3 4 6 9 13 16
3 4 6 9 14 15
3 4 6 10 11 17
3 5 6 6 13 18
4 4 4 9 12 18
4 4 5 6 12 20
4 4 5 7 9 22
5 6 7 7 8 9 9
6 6 6 6 9 9 9

[gimi_sky]

Zgjidhja ime n'java:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/**
 * @author Agim Rama
 */
public class Boundaries
{
    private int n;
    private Stack stack;

    private int sum;
    private double div;

    /**
     * @param number
     */
    public Boundaries(int number)
    {
        n = number;
        stack = new Stack();
        sum = 0;
        solve();
    }

    /**
     *
     */
    private void solve ()
    {
        int start = stack.isEmpty()?1:stack.peek();
        for (int i = start; i <= (n-sum); i++)
        {
            add(i);
            remove();
        }
    }

    private void add(int i)
    {
        sum += i;
        div += 1/(double)i;
        stack.push(i);
        if (sum == n && isOne())
        {
           for (int nr : stack)
           {
               System.out.print(nr + " ");
           }
           System.out.println("");
        }
        else if (sum < n && isLessThenOne())
        {
            solve();
        }
    }

    private void remove()
    {
        int i = stack.pop();
        sum -= i;
        div -= 1/(double)i;
    }


    private boolean isLessThenOne()
    {
        return (1-div) > 0.001;
    }

    private boolean isOne()
    {
        return Math.abs(1-div) < 0.001;
    }
    /**
     * @param args
     * @throws IOException
     */
    public static void main (String[] args) throws IOException
    {
        String prompt = "Type a number:";

        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

        System.out.print(prompt);
        String input = r.readLine().trim();

        while (input.length() > 0)
        {
            try
            {
                int number = Integer.valueOf(input);
                if (number==0)
                {
                    return;
                }

                new Boundaries(number);
            }
            catch (NumberFormatException nfe)
            {
                System.err.println(input + " is not a number");
            }
            System.out.print(prompt);
            input = r.readLine().trim();
        }
    }
}

[Borix]

Agim,

Programi juaj ka nje gabim, qe rrubullakos ne 1 vlerat te cilat nuk jane "ekzaktesisht" 1.0. Me nje sy te shpejt, them se gabimin e ke tek kodi:

    private boolean isOne()
    {
        return Math.abs(1-div) < 0.001;
    }

Per kete arsye, programi juaj nxjerr me shume vlera. Per shembull, une bera nje test te thjesht ne Excel per vlerat 2 4 7 16 22, dhe shuma e reciprokeve eshte 1.0008, e cila e kenaq funksionin tend IsOne, sepse |1-1.0008| = 0.0008 < 0.001. Per vlerat 2 4 7 16 22, shuma e reciprokeve nuk te del 1.0, por 0.9993, e per te tjerat me rradhe, te cilat jane ndryshe nga ato qe kam une ose edspace.

Nisur nga kjo, une sugjeroj ose te adaptosh zgjidhjen e edspace duke perdorur algoritmin euklidian ne perfaqesimin thyesor (dhe jo te drejtperdrejte) te pjesetimit, ose duke pershtatur ate qe kam perdorur une (e cila me duket nje "escape way", por funksionon).

    private boolean isOne()
    {
        return (div >= 0.99999999 && div <=1.00000001);
    }

Ne kete rast, funksioni isOne do te jete me strikt ne kthimin e vleres se sakte. (Meqenese funksionon ne C/C++, po supozoj se e njejta teknike do te funksionoje edhe ne Java).

Edhe dicka tjeter, tek kodi:

int start = stack.isEmpty()?1:stack.peek();

dhe

for (int i = start; i <= (n-sum); i++)

variabli start mund te filloje me mire nga 2, jo nga 1, sepse sic e kemi diskutuar me siper, programi do te testoje vlera pa rezultat. prandaj, permiresimi do te ishte: int start = stack.isEmpty() ? 2 : stack.peek(). Gjithashtu, tek kodi i dyte, tek pjesa e kushtit, nje permiresim mund te jete: i<=n/2, sepse per cdo vlere me te madhe se n/2 programi do te ri-testoje vektore vlerash qe ka testuar me pare (operatori i shumes ka veti asociative)...