Quiz of the day

Συζητήσεις για γλώσσες προγραμματισμού και θέματα σχετικά με προγραμματισμό.
Post Reply
User avatar
moody
Gbyte level
Gbyte level
Posts: 1082
Joined: Sun Oct 16, 2011 11:38 am
Gender:

Quiz of the day

Post by moody » Mon Apr 29, 2013 9:42 pm

Ξεκινάω,

Code: Select all

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;
}
Τι το διαφορετικό έχουν ; Γιατί συμβαίνει αυτό ;
modie is balanced ¯\_(ツ)_/¯
User avatar
Spongebobu
Mbyte level
Mbyte level
Posts: 702
Joined: Mon Jul 02, 2012 6:54 pm
Academic status: Alumnus/a
Gender:
Location: In yo house

Re: Quiz of the day

Post by Spongebobu » 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 είναι πανάσχημη).
Last edited by Spongebobu on Wed May 01, 2013 9:44 pm, edited 3 times in total.
Every time you make a typo the errorists win.
Fabio 2 - 1 Funk
User avatar
Eldebryn
Venus Former Team Member
Posts: 1116
Joined: Sat Sep 18, 2010 8:43 pm
Academic status: Alumnus/a
Gender:
Location: Somewhere in the Forgotten Realms...

Re: Quiz of the day

Post by Eldebryn » Wed May 01, 2013 2:34 pm

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

http://stackoverflow.com/questions/4568 ... nditionals
Image<-- My profile playlists
User avatar
nachos
Gbyte level
Gbyte level
Posts: 1252
Joined: Mon Aug 21, 2006 4:28 pm
Academic status: Alumnus/a
Gender:
Location: Brachamee City

Re: Quiz of the day

Post by nachos » Thu May 02, 2013 11:11 am

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

Ακόμα και αν το 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) που είναι και το ζητούμενο εξαρχής, όντας όμως μακράν οικονομικότερη σε χώρο (μνήμη). :-D
Nothing is impossible for the man who doesn't have to do it himself
Post Reply

Return to “Προγραμματισμός”