Venus AUEB Forum

Posted: **Mon Apr 29, 2013 9:42 pm**

Ξεκινάω,

public class test
{
	public static void main(String args[])
	{
		int a[] = new int[10];
		for(int i=0;i<a.length;i++)
			a[i]= i ;
		
		int i = 5 ;
		a[i]= ++i;
		System.out.print("a[5] = "+a[5]+" and a[6] = "+a[6]+" \n");
	}
}

Θα μεταγλωττιστεί το πρόγραμμα ;
Αν ναι,τι θα printarei και γιατί ;
Ο κώδικας σε c

Code: Select all

#include <stdio.h>
int main(int argc,char **argv)
{
	int a[10];
	int i ;
	for(i=0;i<10;i++)
		a[i]= i ;
		
	i = 5;
	a[i]= ++i;
	printf("a[5] = %i and a[6] = %i \n",a[5],a[6]);
	return 0;
}

Τι το διαφορετικό έχουν ; Γιατί συμβαίνει αυτό ;

Posted: **Mon Apr 29, 2013 10:29 pm**

Καλή φάση, δεν το είχα σκεφτεί αυτό. Με βάση αυτή την απάντηση η Java κάνει left-most evaluation όταν δεν είναι ξεκάθαρο πιο operation γίνεται πρώτα. Γι' αυτό το a[5] γίνεται 6, ενώ στην C υποθέτω ισχύει το αντίστροφο.
---
Ορίστε και ενα πρόβλημα:

Έχουμε τον εξής κώδικα, που υπολογίζει την σειρά Fibonacci:

Code: Select all

public class test{
    public static int fib(int n){
        if(n < 2) 
            return 0;
        else if(n == 2) 
            return 1;
        else
            return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args){
        System.out.println(fib(45));
    }   
}

Τί πολυπλοκότητα έχει? (Δοκιμάστε να το τρέξετε με όρισμα 50).
Πως μπορούμε να βελτιώσουμε την απόδοση?
Τι πολυπλοκότητα έχει η βελτιωμένη έκδοση?

Απάντηση:

Spoiler: εμφάνιση/απόκρυψη: [url=http://en.wikipedia.org/wiki/Memoization]Memoization[/url] [code] import java.util.*; import java.math.BigInteger; public class test{ private static Map<BigInteger, BigInteger> memory = new HashMap<BigInteger, BigInteger>(); public static BigInteger fib(BigInteger n){ if(n.compareTo(BigInteger.valueOf(2)) < 0) return BigInteger.valueOf(0); else if(n.compareTo(BigInteger.valueOf(2)) == 0) return BigInteger.valueOf(1); else { BigInteger key1 = n.subtract(BigInteger.ONE); BigInteger key2 = n.subtract(BigInteger.valueOf(2)); if (!memory.containsKey(key1)) memory.put(key1, fib(key1)); if (!memory.containsKey(key2)) memory.put(key2, fib(key2)); return memory.get(key1).add(memory.get(key2)); } } public static void main(String[] args){ System.out.println(fib(BigInteger.valueOf(45))); } } [/code] Απο εκθετικό σε γραμμικό χρόνο. Μια απο τις καλύτερες τεχνικές που έχω δει (η υλοποίηση σε Java είναι πανάσχημη).

Posted: **Wed May 01, 2013 2:34 pm**

Ενδιαφέρον ερώτημα με πολλαπλές "απαντήσεις":

http://stackoverflow.com/questions/4568 ... nditionals

Posted: **Thu May 02, 2013 11:11 am**

Πολύ ενδιαφέρον το quiz για το Fibonacci, με όντως άσχημη υλοποίηση σε java

Βέβαια για να είμαστε ακριβείς, το static HashMap που χρησιμοποιούμε μπορεί να μας επιτρέψει να απαντήσουμε ερωτήματα σε O(1) (εφόσον έχουν υπολογιστεί σε προηγούμενες κλήσεις), αλλά το πληρώνουμε αυτό με υπερμεγέθες κόστος σε χωρική πολυπλοκότητα (Ο(MaxNum) θεωρητικά, πρακτικά από ένα σημείο και μετά OutOfMemoryException

)

Ακόμα και αν το HashMap δεν ήταν static state, και το είχαμε ενσωματώσει στο σώμα της μεθόδου (μετατρέποντας τη μέθοδο από αναδρομική σε επαναληπτική, ή εναλλακτικά περνώντας αλυσιδωτά το HashMap ώς παράμετρο στη μέθοδο), παρατηρείστε πως λόγω της αποθήκευσης όλων των ενδιαμέσων τιμών, η πολυπλοκότητα χώρου του αλγορίθμου γίνεται O(n). Μπορούμε να το βελτιώσουμε αυτό, παρατηρώντας πως σε κάθε βήμα του Fibonacci, χρειαζόμαστε μόνο τις 2 προηγούμενες τιμές. Έτσι, μπορούμε να ρίξουμε την πολυπλοκότητα χώρου σε O(1) υπολογίζοντας ως εξής:

Code: Select all

    public static long linearFibonacci(long n)
    {
        long memory[] = {0, 1};
        
        if (n < 2)
            return memory[0];
        else if (n == 2)
            return memory[1];
        
        long fib = 0;
        
        for (long i = 3; i <= n; i++)
        {
            fib = memory[1] + memory[0];
            memory[0] = memory[1];
            memory[1] = fib;
        }
        
        return fib;
    }

H οποία έχει πολυπλοκότητα χρόνου O(n) που είναι και το ζητούμενο εξαρχής, όντας όμως μακράν οικονομικότερη σε χώρο (μνήμη).

Venus AUEB Forum

Quiz of the day

Quiz of the day

Re: Quiz of the day

Re: Quiz of the day

Re: Quiz of the day