» »

[c++] naloge

[c++] naloge

ivana213 ::

Zdravo!

Jaz bi prosla za pomoč pri naslednjih dveh nalogah, če bi kdo znal. Tudi samo kakšna pseudokoda ali ideja bi mi zelo pomagali :)

1. Imamo n učencev in m tem tako da je m manjši ali enak n. Moremo razdelit teme med učence, tako da nobena tema ne ostane. Kake so vse možnosti in koliko jih je?
Primer: n = 3, m =2
1 1 2
1 2 1
1 2 2
2 2 1
2 1 2
2 1 1
Število rešitev je 6.

2. Dana je množice elementov, kjer se lahko elementi ponavljajo. Zato lahko ima množica z elementi tudi manj kot n! permutacija.
Na primer. Vhodni podatek je množica 1, 1, 2, 2. Njene permutacije so
1 1 2 2
1 2 1 2
1 2 2 1
2 1 1 2
2 1 2 1
2 2 1 1
  • spremenila: ivana213 ()

ragezor ::

to se meni zdijo kot naloge iz verjetnosti/statistike

ivana213 ::

pomoje je oboje kot neke permutacije s ponavljanjem... sem gledala na netu pa nimam dovol znanja da bi mi tisto blo kaj v pomoč... kr nikjer ni tak ko bi jaz rabla... druga naloga še mogoče, prva pa ne.

roba87 ::

1. Imamo n učencev in m tem tako da je m manjši ali enak n. Moremo razdelit teme med učence, tako da nobena tema ne ostane. Kake so vse možnosti in koliko jih je?
Primer: n = 3, m =2
1 1 2
1 2 1
1 2 2
2 2 1
2 1 2
2 1 1
Število rešitev je 6.


Nerazumljivo navodilo. 1 1 2 pomeni da sta to 2 učenca in 1 tema ? Torej že tu ne štima, ker v navodilu piše, da nobena tema ne ostane. Tukaj ostane 1 izmed dveh...

Fuks ::

roba87 je izjavil:

1. Imamo n učencev in m tem tako da je m manjši ali enak n. Moremo razdelit teme med učence, tako da nobena tema ne ostane. Kake so vse možnosti in koliko jih je?
Primer: n = 3, m =2
1 1 2
1 2 1
1 2 2
2 2 1
2 1 2
2 1 1
Število rešitev je 6.


Nerazumljivo navodilo. 1 1 2 pomeni da sta to 2 učenca in 1 tema ? Torej že tu ne štima, ker v navodilu piše, da nobena tema ne ostane. Tukaj ostane 1 izmed dveh...


1 1 2 pomeni da ima prvi učenec temo 1, drugi učenec temo 1 in tretji učenec temo 2.

Fuks ::

Ena možnost bi recimo bila, da sestaviš najprej vse možne kombinacije (vrstni red ni pomemben). Npr 112 in 122. Potem pa vsako kombinacijo permutiraš. Permutacije pa lahko narediš tako da narediš vse možne in potem odstraniš duplikate (npr urediš in primerjaš sosednji).

Druga varianta pa je npr da narediš vse možne permutacije iz teh tem (npr. začenši z 111, 112 .... 222) in potem samo odstraniš neveljavne.

roba87 ::

Kar neprijetno za sprogramirat pri večjih številkah n in m....

Randomness ::

Tole je primer rešitve za prvo nalogo. Rešitev mogoče ni optimalna, je pa enostavna.

Zgodovina sprememb…

Randomness ::

Evo še primer rešitve za drugo nalogo.

Spura ::

ivana213 je izjavil:

Zdravo!

Jaz bi prosla za pomoč pri naslednjih dveh nalogah, če bi kdo znal. Tudi samo kakšna pseudokoda ali ideja bi mi zelo pomagali :)

1. Imamo n učencev in m tem tako da je m manjši ali enak n. Moremo razdelit teme med učence, tako da nobena tema ne ostane. Kake so vse možnosti in koliko jih je?
Primer: n = 3, m =2
1 1 2
1 2 1
1 2 2
2 2 1
2 1 2
2 1 1
Število rešitev je 6.

2. Dana je množice elementov, kjer se lahko elementi ponavljajo. Zato lahko ima množica z elementi tudi manj kot n! permutacija.
Na primer. Vhodni podatek je množica 1, 1, 2, 2. Njene permutacije so
1 1 2 2
1 2 1 2
1 2 2 1
2 1 1 2
2 1 2 1
2 2 1 1

Prva naloga je simpl ce te boli za hitrost, pac zgeneriras seznam seznamov stevil od 1 1 1 do 2 2 2 (osem jih je) in vn zmeces vse kjer se vsaj enkrat ne pojavi vsako stevilo (v tem primeru ravno 111 in 222).
Druga naloga, mas eno butasto varianto da lepo znegeniras vse permutacije in potem samo iz rezultatov vn vrzes podvojene, najlazje tako, da prej seznam posortiras. Obstajajo pa tut boljse variante, samo so tezje za izvest.

ivana213 ::

Najlepša hvala! :)

ivana213 ::

randomness še enx hvala kr si se potrudo in napisal programe... prvi rok sem sicer padla :P no zdaj hočem nekak razumet tote naloge, pa mogoče se vam ko obvladate zdi to vse isto ampak mislim da je to programirano v c# ? kr so neke stvari v kodi ko jih še sploh vidla nisem. bi se ti dalo mogoče samo par komentarov napisat?

black ice ::

Napisano je v programskem jeziku go.
Go is an open source programming language that makes it easy to build simple, reliable, and efficient software.


Povej kaj ti ni jasno.

epicVoid ::

Jap. Lahko poveš kaj si imela na izpitu in ti pomagamo oz. razložimo.

ivana213 ::

odlično! :) bom ju3 probala te samo malo zgooglat keri ukazi mi niso bli jasni pa vas pol vprašam. Evo v priponki prilagam izpit, če bote znali 2. ali 3. nalogo ... tudi samo razlaga kak se lotit bi mi ful pomagala.
Pri drugi nalogi je tak da najkrajšo pot znam zračunat in sem misla da je pri najdaljši isto ( Floyd Warshall) ... samo da pač namesto minimuma med potmi iščem maximum ampak očitno ni tak. 3. naloge se sploh lotit nisem znala samo ta ni tak pomembna ker 3. je vedno ful težka in unikatna in nikoli več ni pol kakšne podobne.

http://postimg.org/image/897fnliap/

alexa-lol ::

am pri 3. mi na misel pride sledeča pseudo koda

function cuboid(inserted_cuboids, leftover_cuboids) {
  if(leftover_cuboids.length < 1) {
    return inserted_cuboids;
  } else {
    if(evaluate_inserted_cuboids()) return; // če ne ustreza pogojem
  
    for(cuboid in leftover_cuboids) {
      var permutes = cuboid.permute() // vrne array permutacij
      var new_leftover = leftover_cuboids.without(cuboid);

      for(permute in permutes){
         cuboid(inserted_cuboids.push(permute), new_leftover);
      }
    }
  }
}


upam da se nisem kje zmotil ampak to mi je prvo prišlo na misel...

kaj je tisto z metodo sestopanja?

Spura ::

Ce bi bil dejansko prav napisan, bi to bil algoritem s sestopanjem (backtrackingom) s casovno zahtevnostjo O(2^n).

ivana213 ::

to pomeni da probavaš varjante različne... večjo časovno zahtevnost ima sestopanje... drugače pa se da rešit tudi z dinamičnim programiranjem... sem zdaj ugotovila kak se reši samo še morem sprogramirat. uredimo vse kocke tak da damo od najmanjše do največje stranice v vsako vrstico, pol pa še vrstice uredimo od najmanjše do največje, in potem z dinamičnim programiranjem iščemo najdaljše naraščajoče podzaporedje

sproti seveda vedno preverimo ko iščemo najdaljše podzaporedje... če so vse istoležne stranice manjše od tiste naslednje kocke/kvadrata

Zgodovina sprememb…

  • spremenila: ivana213 ()

Spura ::

import java.util.Arrays;

/**
 *
 * @author Nope
 */
public class Naloga3 {

    public static void main(String[] args) {
        Box[] boxes = {new Box("K1", 3, 12), new Box("K2", 8, 10),
            new Box("K3", 5, 2), new Box("K4", 21, 18), new Box("K5", 9, 11),
            new Box("K6", 8, 6), new Box("K7", 14, 4)};
        Arrays.sort(boxes); // n * log n,  nm * log nm;
        for (int i = 0; i < boxes.length; i++) { // n^2
            for (int j = 0; j < i; j++) {
                boxes[i].considerBox(boxes[j]);
            }
        }
        // find max
        Box max = null;
        for (Box b : boxes) {
            if (max == null || b.getStackSize() > max.getStackSize()) {
                max = b;
            }
        }
        System.out.println(max);
    }

    public static class Box implements Comparable<Box> {

        private int[] dims;
        private String id;
        private Box childBox;
        private int stackSize = 1;

        public String toString() {
            return (childBox == null ? "" : childBox.toString() + " -> ") + "Box " + id;
        }

        public int getStackSize() {
            return stackSize;
        }

        public Box(String id, int... dims) {
            Arrays.sort(dims);
            this.dims = dims;
            this.id = id;

        }

        public int[] getDims() {
            return dims;
        }

        public void considerBox(Box b) {
            if (b.dims.length != this.dims.length) {
                throw new IllegalStateException("Stevilo dimenzij se ne ujema.");
            }
            for (int i = 0; i < dims.length; i++) {
                if (dims[i] <= b.dims[i]) {
                    return;
                }
            }
            int otherBoxStackSize = b.getStackSize();
            if (childBox == null || otherBoxStackSize >= this.stackSize) {
                childBox = b;
                stackSize = otherBoxStackSize + 1;
            }
        }

        @Override
        public int compareTo(Box t) {
            return dims[0] - t.dims[0];
        }
    }
}

Spura ::

Dynamic programming je drugace eno zelo butasto ime za divide and conquer algoritme.

technolog ::

za prvo nalogo je število razporeditev:

(n binomsko m) * m^(n-m)


Koda je pa taka:

n = 3
m = 2

p (1..n).to_a.combination(m).flat_map { |com|
	(0..m-1).to_a.repeated_permutation(n-m).map { |perm|
		j = -1
		Array.new(n) { |i|
			1 + (com.index(i+1) || perm[j += 1])
		}
	}
}


Output:
[[1, 2, 1], [1, 2, 2], [1, 1, 2], [1, 2, 2], [1, 1, 2], [2, 1, 2]]


Koda od uporabnika @Randomness je slaba, ker v primeru, ko je n = m, je časovna zahtevnost moje kode O(1), njegove pa O(n^n). Podobno slabo za vse primere, ko je m blizu n.

Zgodovina sprememb…

alexa-lol ::

Spura je izjavil:

Ce bi bil dejansko prav napisan, bi to bil algoritem s sestopanjem (backtrackingom) s casovno zahtevnostjo O(2^n).


Kaj sem falil? :P

technolog ::

Spura je izjavil:

Dynamic programming je drugace eno zelo butasto ime za divide and conquer algoritme.


Sploh ne. Dinamično programiranje pa divide and conquer sta dve čisto drugi paradigmi.

Rešitev tretje naloge pa je taka:

Najprej posortiraš vse koordinate po velikosti, to ti omogoči, da v O(n) ugotoviš, če kocka paše ena v drugo. O(k*n*logn)

Potem v O(n*k^2) zgradiš graf, katera kocka pade v katero. Ta graf je jasno usmerjeno drevo.

Nato pa lahko v času O(k^2) ugotoviš premer usmerjenega drevesnega grafa (najdaljšo mogočo pot).

Skupaj: O(n*k*logn + n*k^2)

Zgodovina sprememb…

Spura ::

technolog je izjavil:

Spura je izjavil:

Dynamic programming je drugace eno zelo butasto ime za divide and conquer algoritme.


Sploh ne. Dinamično programiranje pa divide and conquer sta dve čisto drugi paradigmi.
Ubistvu nista, kljub temu da se loceno obravnavata. Vsekakor pa nista cisto drugi kot pravis.

technolog je izjavil:


Rešitev tretje naloge pa je taka:

Najprej posortiraš vse koordinate po velikosti, to ti omogoči, da v O(n) ugotoviš, če kocka paše ena v drugo. O(k*n*logn)

Potem v O(n*k^2) zgradiš graf, katera kocka pade v katero. Ta graf je jasno usmerjeno drevo.

Nato pa lahko v času O(k^2) ugotoviš premer usmerjenega drevesnega grafa (najdaljšo mogočo pot).

Skupaj: O(n*k*logn + n*k^2)

Zakaj bi clovek s k oznacil stevilo stakel in z n stevilo dimenzij? That's just weird.

alexa-lol je izjavil:

Spura je izjavil:

Ce bi bil dejansko prav napisan, bi to bil algoritem s sestopanjem (backtrackingom) s casovno zahtevnostjo O(2^n).


Kaj sem falil? :P

Vrnes le ko najdes resitev, ki uporabi vse skatle.

Zgodovina sprememb…

  • spremenil: Spura ()

technolog ::

Zakaj bi clovek s k oznacil stevilo stakel in z n stevilo dimenzij? That's just weird.


Tako je v nalogi. Kar se mene tiče, je tudi zelo nelogično. N im M bi bili logična izbira.


Razlika med dinamičnim programiranjem in D&C je med drugim v tem, da pri DP memoiziraš podprobleme, ki si jih že rešil.

Zgodovina sprememb…

ivana213 ::

technolog bi mi znal oz. če bi se ti dalo še to nalogo z učenci in testi napisat v c++? ker se dostix ponavljajo take naloge da moreš pol napisat vse permutacije... meni je profesor reko da sta v bistvu ti dve naloge obe ful podobni in da mi je najlažje če grem skozi vse varjante in sproti kličem še funkcijo ki preverja če ustreza ta permutacije pogojem.

alexa-lol ::

Spura je izjavil:


alexa-lol je izjavil:

Spura je izjavil:

Ce bi bil dejansko prav napisan, bi to bil algoritem s sestopanjem (backtrackingom) s casovno zahtevnostjo O(2^n).


Kaj sem falil? :P

Vrnes le ko najdes resitev, ki uporabi vse skatle.


Aja pa res.. sem preveč površno prebral.

technolog ::

Zadeva je dost simpl, edina komplikacija je funkcija, ki računa kombinacije dolžine m na vektorju n elementov. Permutacije s ponavljanjem so pa tako ali tako zelo simpl stvar.

Kodo sem ti pripravil v malo lepši obliki (kot tisti prej), če kaj pomaga. Poskušaj ugotovit, kaj počne, je pa v jeziku Ruby.

Hint: prva vrstica ponavlja blok kode za vsako kombinacijo dolžine m na množici {1,2,3,...n}.

Kodo lahko prilepiš sem: http://www.compileonline.com/execute_ru...

n = 5
m = 3

(1..n).to_a.combination(m).each { |com|
	(1..m).to_a.repeated_permutation(n-m).each { |perm|
		j = -1
		p Array.new(n) { |i|
			if idx = com.index(i+1)
				idx + 1
			else
				j += 1
				perm[j]
			end
		}
	}
}

ivana213 ::

hvala!

Randomness ::

technolog je izjavil:

Koda od uporabnika @Randomness je slaba, ker v primeru, ko je n = m, je časovna zahtevnost moje kode O(1), njegove pa O(n^n). Podobno slabo za vse primere, ko je m blizu n.
Če bi pozorno prebral moj post, bi videl, da sem že sam komentiral, da koda ni optimalna. Vendar je po mojem mnenju za izpit čisto ok, če podaš neoptimalno, a delujočo rešitev. Sploh če jo opremiš s komentarjem, kako bi se dalo kodo izboljšati oz. uporabiti drug, bolj učinkovit algoritem. Po drugi strani pa ti nič ne pomaga, če imaš super hiter algoritem, ki pa da napačen rezultat, kar se zgodi v tvojem primeru.

technolog ::

Res ni delovala čisto pravilno. Je pa tvoja zato slaba, ko je m blizu n, ker moraš vržt stran skoraj vsako rešitev (v asimptotičnem smislu.)

Sem pa opazil, da sta prva in druga naloga v bistvu samo v različen celofan zavita ena in ista naloga. Spodaj je rešitev za obe:

def comp(n: Int, t: Int): Seq[List[Int]] = {
	if (n == 1) Seq(List(t)) else for {
		x <- 1 to t-n+1
		c <- comp(n-1, t-x)
	} yield x :: c
}

def posRec(rem: List[(Int, Int)], cur: List[Int]): Seq[List[(Int, Int)]] = {
	if (rem.isEmpty) Seq(List()) else {
		val (num, p) = rem.head
		for {
			comb <- cur.combinations(num).toSeq
			tail <- posRec(rem.tail, cur diff comb)
		} yield (comb zip Stream.continually(p+1)) ++ tail
	}
}

def pos(rem: List[(Int, Int)], size: Int) = {
	posRec(rem, (0 until size).toList).map(
		_.sorted.map(_._2)
	)
}


def prva(n: Int, m: Int) = {
	require(m <= n, "Število študentov mora biti manj kot nalog.")
	comp(m, n).flatMap(x => pos(x.zipWithIndex, n))
}

def druga(nums: Int*) = {
	val frequency = nums.groupBy(identity).toList.map { case (n, all) =>
		all.size -> (n-1)
	}
	pos(frequency, nums.size).toVector
}

println(prva(3,2))
println(druga(1,1,2,2,3))

Zgodovina sprememb…

technolog ::

Še boljše:

// kombinatorične kompozicije dolžine n
def comp(n: Int, t: Int): Seq[List[Int]] = {
	if (n == 1) Seq(List(t)) else for {
		x <- 1 to t-n+1
		c <- comp(n-1, t-x)
	} yield x :: c
}

// permutacije z ekvivalenčnimi skupinami
def pos(rem: List[(Int, Int)]) = {
	def posRec(rem: List[(Int, Int)], cur: List[Int]): Seq[List[(Int, Int)]] = {
		if (rem.isEmpty) Seq(List()) else {
			val (num, p) = rem.head
			for {
				comb <- cur.combinations(num).toSeq
				tail <- posRec(rem.tail, cur diff comb)
			} yield (comb zip Stream.continually(p+1)) ++ tail
		}
	}

	val size = rem.map(_._1).sum
	posRec(rem, (0 until size).toList).map(
		_.sorted.map(_._2)
	)
}


def prva(n: Int, m: Int) = {
	require(m <= n, "Število študentov mora biti manj kot nalog.")
	comp(m, n).flatMap(x => pos(x.zipWithIndex))
}

def druga(nums: Int*) = {
	pos(nums.groupBy(identity).toList.map { case (n, all) =>
		all.size -> (n-1)
	}).toVector
}

println(prva(3,2))
println(druga(1,1,2,2,3))

Randomness ::

Ker scale ne poznam preveč dobro, bi te prosil, da malo pokomentiraš, kako je s prostorsko učinkovitostjo zgornje kode. Opazil sem namreč, da implementacija ni preveč učinkovita. Program sem poskusil pognati za primer m=7 in n=9, pa sem po približno 12-ih minutah dobil OutOfMemoryError, medtem ko moj program uspešno zaključi v manj kot 20-ih sekundah.

Spura ::

import java.util.Arrays;

/**
 *
 * @author
*/

public class Naloga1 {
    public static void main(String[] args) {
        long t = System.nanoTime();
        print(3,5);
        System.out.println(System.nanoTime() - t);
    }
    
    
    private static void print(int numOfTopics, int numOfPeople) {
        int[] handedOut = new int[numOfTopics];
        int[] assigments = new int[numOfPeople];
        print(handedOut, assigments, 0, numOfTopics);
    }
    
    private static void print(int[] handedOut, int[] assigments, int idx, int zeroes) {
        for (int i = 0;i < handedOut.length;i++) {
            assigments[idx] = i + 1;
            if (handedOut[i]++ == 0) {
                zeroes-- ;
            }
            if (zeroes == 0) {
                enumerate(assigments, idx + 1, handedOut.length);
            } else if (zeroes < assigments.length - idx) {
                print(handedOut, assigments, idx+1, zeroes);
            } 
            if (handedOut[i]-- == 1) {
                zeroes++;
            }
        }
    }
    
    private static void enumerate(int[] assigments, int idx, int maxElem) {
        if (idx == assigments.length) {         
            System.out.println(Arrays.toString(assigments));
        } else {
            for (int i = 1;i <= maxElem;i++) {
                assigments[idx] = i;
                enumerate(assigments, idx + 1, maxElem);
            }
        }
    }
}
Nigga plz.
Prakticno nicelna poraba rama in 4.5ms za 3,5 parametere (50 us ce fuknem vn izpis) in 100 ms za 7,9 parametre ce vn vrzem izpisovanje v konzolo.

technolog ::

Randomness, sorazmerno s številom rešitev. Žal rešitev ni streaming, tako da je treba imet dovolj rama, da shraniš ceoten seznam rezultatov in ga šele nato izpišeš. Scala ma po defaultu dokaj nizke omejitve.

Spodaj je verzija, ki rešitve sproti izpisuje, tako kot je naredil Spura. To je vedno bolj performant opcija.


def comp(n: Int, t: Int): Seq[List[Int]] = {
    if (n == 1) Seq(List(t)) else for {
        x <- 1 to t-n+1
        c <- comp(n-1, t-x)
    } yield x :: c
}

def pos(rem: List[(Int, Int)]) {
    def posRec(rem: List[(Int, Int)], cur: List[Int]): Seq[List[(Int, Int)]] = {
        if (rem.isEmpty) Seq(List()) else {
            val (num, p) = rem.head
            for {
                comb <- cur.combinations(num).toSeq
                tail <- posRec(rem.tail, cur diff comb)
            } yield (comb zip Stream.continually(p+1)) ++ tail
        }
    }

    val size = rem.map(_._1).sum
    posRec(rem, (0 until size).toList).foreach( x =>
        println( x.sorted.map(_._2) )
    )
}


def prva(n: Int, m: Int) {
    require(m <= n, "Število študentov mora biti največ toliko kot nalog.")
    comp(m, n).par.foreach(x => pos(x.zipWithIndex))
}

def druga(nums: Int*) {
    pos(nums.groupBy(identity).toList.map { case (n, all) =>
        all.size -> (n-1)
    })
}

prva(9,7)
druga(1,1,2,2)


Je pa prednost rešitve ta, da se zelo lepo skalira na več jeder out of the box, ker uporablja immutable data strukture. Samo en .par() je potrebno dodat v klic, kot je primer zgoraj. Če maš 8 jeder, ni problem.

+ Krajša je, glede na to, da združuje rešitev obeh nalog.

p.s.: Na mojem dvojedrniku moja rešitev za (8,6) vzame cirka 6,7s, spurina pa 3,6s. Seveda njegova koristi samo eno jedro. Output se redirecta v file, nič se ne printa na zaslon.

Zgodovina sprememb…

Spura ::

A to si meril cajt izvajanja procesa? Start JVMja in pa izpisovanje vzame 99.9% cajta mojga programa. To je nekak tako kot bi primerjal kateri program hitrej kopira 1GB fajl.

technolog ::

No, si le pogruntal.

Generacija podatkov vzame zanemarljivo časa v primerjavi s tistim, kar potem z njimi potem počneš (pa čeprav je to samo izpis v datoteko.)

Zgodovina sprememb…

Randomness ::

No, da še jaz objavim svoj izboljšan algoritem. Bistvena lastnost algoritma je, da ne uporablja rekurzije in je pomnilniško zelo učinkovit.
package main

import _ "fmt"

func main() {
	razdeli(7, 11)
}

func reverse(a []int) {
	for i := 0; i < len(a)/2; i++ {
		a[i], a[len(a)-i-1] = a[len(a)-i-1], a[i]
	}
}

func permNext(a []int) bool {
	for i := len(a) - 2; i >= 0; i-- {
		if a[i] < a[i+1] {
			for j := len(a) - 1; j > i; j-- {
				if a[i] < a[j] {
					a[i], a[j] = a[j], a[i]
					break
				}
			}
			reverse(a[i+1 : len(a)])
			return true
		}
	}
	return false
}

func gen(a, p []int, m int) {
	for i, j, k := 1, 0, 0; i <= m; i++ {
		for ; j < len(p) && p[j] <= i; j++ {
			a[k] = p[j]
			k++
		}
		a[k] = i
		k++
	}

	//fmt.Println(a)
	for permNext(a) == true {
		//fmt.Println(a)
	}
}

func permIncreasingNext(p []int, m int) bool {
	if p[0] == m && p[len(p)-1] == m {
		return false
	}

	i := len(p) - 1
	for ; p[i] == m; i-- {

	}

	v := p[i] + 1
	p[i] = v
	for i = i + 1; i < len(p); i++ {
		p[i] = v
	}

	return true
}

func razdeli(m, n int) {
	a := make([]int, n)
	if n > m {
		p := make([]int, n-m)

		for i := 0; i < len(p)-1; i++ {
			p[i] = 1
		}
		p[len(p)-1] = 0

		for permIncreasingNext(p, m) == true {
			gen(a, p, m)
		}
	} else {
		gen(a, []int{}, m)
	}
}
Če odstranim izpise v konzolo, program za m=7 in n=11 porabi približno 6.4 sekunde, kar je malo slabše od Spurine verzije, ki potrebuje približno 5.7 sekund (skupaj z zagonom JVM-ja). Če pa svojo verzijo predelam v C, ugotovim, da le-ta sedaj potrebuje zgolj 3.2 sekunde, kar je 2-kratna pohitritev glede na go verzijo. Zanimivo, če predelam svojo verzijo v Javo, le ta potrebuje zgolj 2.7 sekunde (skupaj z zagonom JVM-ja), kar je znatno bolje tako od C-jevske verzije kot tudi od Spurine implementacije.

Spura ::

Sm tut jst razmisljal o nerekurzivnem algoritmu, sam pol se mi je zdel prevec kompliciran za razumet. Drugace pa primerjaj razumljivost resitev. Funkcijsko programiranje je tak lol, da konec.

ragezor ::

nevem ce so tvoji skillsi v vseh jezikih enaki

Randomness ::

ragezor je izjavil:

nevem ce so tvoji skillsi v vseh jezikih enaki
Seveda niso. Vendar so si C, Go in Java tako zelo podobni med seboj, da gre v tem primeru v bistvu za 1:1 preslikavo. Drugače je seveda v primeru funkcijskih jezikov, ki zaradi drugačne paradigme zahtevajo popolnoma drugačen mindset. Tukaj bi se strinjal s Spuro - tudi meni se ponavadi zdijo imperativne rešitve bolj enostavne in lažje za razumeti od funkcijskih rešitev. Poleg tega pa imperativne rešitve IMHO omogočajo lažjo analizo delovanja algoritma s stališča prostorske zahtevnosti. Seveda dopuščam možnost, da se najde kje kaka pristašica lambda računa, ki bo temu oporekala.

Randomness ::

Še en popravek glede časa izvajanja C-jevskega programa. Prej sem objavil, da Cejevska verzija porabi 3.2 sekunde, kar je slabše od Javanskega programa, ki je porabil le 2.7 sekund. Sedaj sem Cjevsko verzijo prevedel še enkrat z -O3 (prej z -O2; obakrat prevajalnik gcc 4.9.0) in po ponovni meritvi se je vse postavilo na svoje mesto, tako kot mora biti - Cjevski program je porabil 1.7 sekunde. Clang 3.4.2 prevajalnik da nekoliko počasnejšo kodo (2.3 sekunde tako pri -O2 kot pri -O3), ki pa je še vedno hitrejša od Javanske. Vse je bilo izmerjeno na procu Intel Core i7 860 @ 2.80GHz.

technolog ::

Spura je izjavil:

Funkcijsko programiranje je tak lol, da konec.


Ni lol. Koda pride res kratka (30 vrstic za obe nalogi), se bolj drži matematičnih paradigem (kot recimo to, da se podatkovne strukture ne spreminjajo tekom programa), zato je o njih lažje razmišljat.

Zgodovina sprememb…

ivana213 ::

Hvala še enkrat za vso pomoč, v 2. roku mi je le ratalo naret :)Prilagam vam še ta izpit če koga zanima :)

http://postimg.org/image/3rebh1s5p/

ivana213 ::

http://postimg.org/image/d8skb9rrn/

Bi znal kdo odgovorit pri 1. nalogi, dokaži da velja... ?

Randomness ::

Rešiti moraš rekurenčno relacijo. Bo šlo?

Spura ::

technolog je izjavil:

Spura je izjavil:

Funkcijsko programiranje je tak lol, da konec.


Ni lol. Koda pride res kratka (30 vrstic za obe nalogi), se bolj drži matematičnih paradigem (kot recimo to, da se podatkovne strukture ne spreminjajo tekom programa), zato je o njih lažje razmišljat.

Jst bi tezko z resno faco reku, da je tvoja resitev razumljivejsa od moje.

technolog ::

Seveda je. Samo nisi navajen na ta način razmišljat in take kode brat. Pa še ni se mi je dalo z lepo poimenovanimi spremenljivkami pisat.

Sploh pa 30 vrstic za obe nalogi bi pri tebi prišlo najbrž 150 vrstic.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[Java-matematika] Računanje relativnega horizontalnega in vertikalnega kota v 3D

Oddelek: Programiranje
5911 (747) zavtom
»

Kombinatorika

Oddelek: Šola
191856 (1197) 2f4u
»

pomoč matematika - kombinatorika!

Oddelek: Šola
101155 (819) technolog
»

urejanje - python

Oddelek: Programiranje
51264 (1041) ktka
»

cene permutacij help please

Oddelek: Programiranje
261920 (1527) Sergio

Več podobnih tem