Quiz of the day

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

Quiz of the day

Postby 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

Postby 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: εμφάνιση/απόκρυψη
Memoization

Code: Select all

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)));
    }   
}


Απο εκθετικό σε γραμμικό χρόνο. Μια απο τις καλύτερες τεχνικές που έχω δει (η υλοποίηση σε 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

Postby Eldebryn » Wed May 01, 2013 2:34 pm

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

http://stackoverflow.com/questions/4568645/printing-1-to-1000-without-loop-or-conditionals
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

Postby 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

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

Who is online

Users browsing this forum: No registered users and 1 guest