# Shkenca > Informatikë dhe Internet > Arti i programimit >  Sfide për të gjetur numra të plotë pa progresion aritmetik

## freshness

Vargu i numrave te plote: a(0), a(1),  a(2), a(3), ..., a(n) eshte i tille qe a(0)=0, a(1)=1 dhe a(n) eshte numri me i vogel i plote i tille qe a(n) > a(n-1) dhe ne  vargun a(0), a(1),  a(2), a(3), ..., a(n) te mos gjendet asnje treshe numrash qe te formojne progresion aritmetik. ( pra kufizat e para te vargut do te jene 0, 1, 3, 4, 9, 10, 12 ...)
Kerkohet te shkruhet nje program qe merr si input nga console numrin *n* dhe printon ne ekran vleren e *a(n)*  (Psh nqs merr si input 4, do te printoje ne ekran 9)

----------


## qoska

Me shume se programim kjo eshte matematike per mendimin tim :P

----------


## freshness

> Me shume se programim kjo eshte matematike per mendimin tim :P


Ajo qe doje te thoshe besoj eshte qe problemi kerkon me shume njohuri nga algoritmat se njohuri mbi sintaksen e gjuheve...  

Nqs te ngaterrojne simbolet dhe shprehjet matematikore po jap nje formulim tjeter te problemit (qe nga veshtiresia eshte totalisht ekuivalent me kerkesen e dhene me pare)


N persona vendosen *ne vije te drejte*, secili ka largesi te njejte me personin qe ka ne te majte dhe me personin qe ka ne te djathte _(pervec te parit, i cili nuk ka person ne te majte, dhe te fundit, i cili nuk ka person ne te djathte)_. Cili eshte numri me i madh i personave qe mund te ngrene doren njekohesisht ne menyre te tille qe *te mos ekzistoje* nje person i cili ta kete doren ngritur dhe te kete largesi te njejte nga dy persona te tjere qe e kane doren ngritur?

Programi do te marre si input vleren e N dhe do te printoje numrin e kerkuar.

*Me falni qe nuk bera specifilimin qe ne fillim kur thashe sfide per te gjithe.  Kjo eshte sfide vetem per mjeshtrat ne algoritma...*

----------


## xfiles

> Vargu i numrave te plote: a(0), a(1),  a(2), a(3), ..., a(n) eshte i tille qe a(0)=0, a(1)=1 dhe a(n) eshte numri me i vogel i plote i tille qe a(n) > a(n-1) dhe ne  vargun a(0), a(1),  a(2), a(3), ..., a(n) te mos gjendet asnje treshe numrash qe te formojne progresion aritmetik. ( pra kufizat e para te vargut do te jene 0, 1, 3, 4, 9, 10, 12 ...)
> Kerkohet te shkruhet nje program qe merr si input nga console numrin *n* dhe printon ne ekran vleren e *a(n)*  (Psh nqs merr si input 4, do te printoje ne ekran 9)


ca eshte progresioni aritmetik?

----------


## programuesi

sikur ta sqarosh pak me mire do te ishte me e lehte per ne te aktivizoheshim ne kete sfide.

----------


## xfiles

> *Me falni qe nuk bera specifilimin qe ne fillim kur thashe sfide per te gjithe.  Kjo eshte sfide vetem per mjeshtrat ne algoritma...*


Nje algoritem krijohet atehere kur njihet problemi ne te gjitha detajet.
Kur ne nuk dime se ca eshte progresioni aritmetik nuk mund te modelojme problemin e dhene, 
na fal po nuk jane te gjithe matematicien.

----------


## che_guevara86

Mesa mbaj mend une nga gjimnazi progresioni aritmetik eshte nje varg numrash qe kane nje rritje te caktuar numrash. Pak a shume. Progresion aritmeitk eshte renditja e numrave tek ose cift . Per te gjetur progresionin aritemitk dmth numrin me te cilin ndryshojne numrat zbresim numrit perpara numrin mbarapa. psh  
 1,3.5,7.....  progresion aritmetik dhe si i tille per te gjetur ndryshoren   ose numrin qe keta numra rrisin vleren e tyre :  7-5=2      5-3=2    3-1=2   dmth  ky varg numrash eshte nje progresion aritemtik ne rritje me ndryshore 2. Besoj se eshte kjo dhe isha i qarte  :P  :ngerdheshje:

----------


## GinoTheGodFather

Progresion aritmetik quhet kur ne nje varg te dhene numrash, ndryshesa e nje kufize me kufizen paraardhese eshte e njejte dhe shenohet me d. Ndersa progresioni gjeometrik eshte kur ne nje varg numrash, heresi i nje kufize me kufizen paraardhese eshte i njejte dhe shenohet me q. Por me sa po shof une problemi qe ka ngritur freshness nuk ka te beje fare me progresionet por me n!

----------


## thetracker

HI

eshte akoma e vlefshme ajo sfida me ata qe ngrinin duart?

nese po, ne veshtrim te pare me duket se zgjidhja eshte 

(N div 2) +1

ku N div 2 eshte pjestimi i plote p.sh. 7 div 2 = 3  ,   9 div 2 =4 .

"Algoritmikisht" mund te behet me programim dinamik(mbase) por nese se provoj dot barazimin e mesiperm do shkruaj 1 program per kte prob se qeka i lezetshem.

ate te parin me a(0) se mora vesh hic.

tung

----------


## prometeo

```
import java.util.HashSet;
import java.util.Iterator;



public class NoProgress {
	
	private void getNext(HashSet teMarre, int n, int i, int sol){
		
		if (i==n) {
			Iterator it = teMarre.iterator();
			while (it.hasNext()) {
				Integer el = (Integer) it.next();
				System.out.print(el.toString() + ", ");
			}
			
			System.out.println("\nRisposta: " + sol);
			System.exit(0);
		}
		Iterator it = teMarre.iterator();
		boolean exists = false;
		while (it.hasNext()) {
			int paraArdhsi1 = ((Integer) it.next()).intValue();
			Integer thisDiff=new Integer(paraArdhsi1 -(i - paraArdhsi1));
			if (teMarre.contains(thisDiff)) {
				exists = true;
				 break;
			}
		}
		
		if (exists) {
			getNext(teMarre, n,  i+1, sol);
		}
		else{
			
			teMarre.add(new Integer(i));
			getNext(teMarre, n, i +1, sol+ 1);
		}
		
	}

	public static void main(String[] args) {
		NoProgress nP = new NoProgress();
		HashSet hs = new HashSet();
		hs.add(new Integer(0));
		nP.getNext(hs, 15,  0, 1);
	}
}
```

Eshte pak lemsh, po eshte zgjidhja e pare,
ndoshta neser dicka me elegante...

----------


## prometeo

Rradhit pergjigjen...



```

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;



public class NoProgress {
	
	private void getNext(HashSet teMarre, int n, int i, int sol){
		
		if (i==n) {
			
			Object[] o = teMarre.toArray();
			Arrays.sort(o);
			for (int j = 0; j < o.length; j++) {
				System.out.print(o[j] + ", ");
			}
			
			
			System.out.println("\nPergjigja: " + sol);
			System.exit(0);
		}
		Iterator it = teMarre.iterator();
		boolean exists = false;
		while (it.hasNext()) {
			int paraArdhsi1 = ((Integer) it.next()).intValue();
			Integer thisDiff=new Integer(paraArdhsi1 -(i - paraArdhsi1));
			if (teMarre.contains(thisDiff)) {
				exists = true;
				 break;
			}
		}
		
		if (exists) {
			getNext(teMarre, n,  i+1, sol);
		}
		else{
			
			teMarre.add(new Integer(i));
			getNext(teMarre, n, i +1, sol+ 1);
		}
		
	}

	public static void main(String[] args) {
		NoProgress nP = new NoProgress();
		HashSet hs = new HashSet();
		hs.add(new Integer(0));
		nP.getNext(hs, 35,  0, 1);
	}
}
```

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31

Pergjigja: 12

----------


## xfiles

sa shume qe perdor HashSet dhe Iterator mo burr i dheut, kur aty mjafton vetem int[], aq me keq perdor objekte Integer per te memorizuar vlera te thjeshta te plota..... thjesht nje keshille kjo, mos ma merr per keq  :buzeqeshje: .

sa i perket problemit une per vete e rishikova rregullin se si perkufizohet a(n) po prap se mora vesh hiç.

----------


## prometeo

S'e marr fare per keq... E rendesishme eshte korrektesia e zgjidhjes...
Perdorimi i objekteve ne vend te tipave primitive eshte nje best practise e keshilluar nga te gjihte. Per me teper nje keshille do ishte wrap your objects, ose

psh:
   mos perdor java.util.Date por objekte te tipit MyDate qe permbajne java.util.Date

pastaj ajo qe bie ne sy eshte zgjidhja me rast te keq O(n2) qe pak a shume eshte zgjidhja e pare qe te vjen ne mendje. 

ciklet for mbi array interesh nuk ndrrojn asgje. Hashset dhe Iterator jan struktura mjaft te shpejta.

Sfide: gjej nje zgjidhje O(n log n)  

befsh qejf!

----------


## prometeo

per ke nuk kupton problemin:

algoritmi duhet te gjeje nje zgjidhje brenda se ciles te mos ekzistoje nje nenvarg  me 3  elemente ( jo detyrimisht te njepasnjeshem ) te tipit


   {x, y, 2y - x} |  x, y, z numura te plote

zgjidhja me n = 100:

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, 84, 85, 90, 91, 93, 94.

24 elemente.

po te marrim cdo tre numra nga zgjidhja, nje here qe fiksojm te parin dhe te dytin,
p.sh a, b, numuri c = 2b - a perjashtohet automatikisht nga zgjidhja

----------


## xfiles

> Sfide: gjej nje zgjidhje O(n log n)  
> 
> befsh qejf!


me gjithe qejf, mbasi te di si te bej ate me O(n*n) :P

----------


## xfiles

> per ke nuk kupton problemin:
> 
> algoritmi duhet te gjeje nje zgjidhje brenda se ciles te mos ekzistoje nje nenvarg  me 3  elemente ( jo detyrimisht te njepasnjeshem ) te tipit
> 
> 
>    {x, y, 2y - x} |  x, y, z numura te plote
> 
> zgjidhja me n = 100:
> 
> ...


prap se kuptova, eshte e kote, nuk arrij ta kuptoj.
megjithate do mundohem

----------

