Sfide për të gjetur numra të plotë pa progresion aritmetik

[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 .

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:

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

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