Πρόβλημα #1

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.

Πρόβλημα #1

Δημοσίευσηαπό feedWARd » Παρ Ιούλ 30, 2010 7:30 pm

Σας δίνεται ένας πίνακας Α με n ακεραίους ταξινομημένους σε αύξουσα σειρά και ένας ακέραιος c. Βρείτε αλγόριθμο που να ελέγχει αν υπάρχoυν i, j διαφορετικά μεταξύ τους, ωστέ να ισχυεί Α[i] + A[j] = c (δηλαδή αν υπάρχουν δύο στοιχεία του πίνακα που να δίνουν άθροισμα c). Γράψτε time και memory complexity.
feedWARd
 
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Πρόβλημα #1

Δημοσίευσηαπό chris » Παρ Ιούλ 30, 2010 8:38 pm

Ένας δείκτης i στην αρχή του πίνακα, ένας δείκτης j στο τέλος του. Αν το άθροιμσα των στοιχείων που δείχνουν είναι μεγαλύτερο του N μειώνουμε το j, αλλιώς αυξάνουμε το i μέχρι να βρούμε την λύση. Πολυπλοκότητα μνήμης n, πολυπλοκότητα χρόνου Ν στην χειρότερη περίπτωση. ΧΑ.
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
chris
 
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Πρόβλημα #1

Δημοσίευσηαπό sotiris » Παρ Ιούλ 30, 2010 10:48 pm

Κώδικας: Επιλογή όλων
#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

int i , j , N , findu;
int a[MAX];

int main(){
FILE*fin;
FILE*fout;
fin = fopen("input.in","r");
fout = fopen("output.out","w");
fscanf(fin,"%d %d",&N,&findu);
for(i=0;i<N;++i)
fscanf(fin,"%d",&a[i]);
fclose(fin);

for(i=0;i<N;++i){ if(a[i] > findu){break;}
for(j=i+1;j<N;++j){                 
if( a[i] + a[j] == findu){
fprintf(fout,"%d %d\n",i+1,j+1);   
}
}}

fclose(fout);

return 0;   
}

Εικόνα
sotiris
 
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Πρόβλημα #1

Δημοσίευσηαπό thetrojan01 » Σάβ Ιούλ 31, 2010 11:08 pm

πφφφ με προλάβανε.

Όντως, μου φαίνεται Θ(n) για χρόνο και O(1) ή Ο(n) για μνήμη, εξαρτάται με την υλοποίηση του προγράμματος όσον αφορά τον πίνακα. Ο αλγόριθμος από μόνος του είναι Ο(1).
---------------
Επειδή βαριέμαι, παραθέτω τον ψευδοκώδικα του αλγορίθμου:
Κώδικας: Επιλογή όλων
// Looks if there are two elements of the array A, i and j,
// so that A[i] + A[j] = T; if found, returns true, else it returns false.

SUMCHECK(A, T)
    i <-- 1 
    j 
<-- A.length
    
    while
(< j)
        sum <-- A[i] + A[j]
        if(sum == T)
            return true
        elseif
(sum > T)
            j = j - 1
        elseif
(sum < T)
            i = i + 1
    return false


Απόδειξη ορθότητας του αλγορίθμου:
Αμετάβλητο βρόγχου: Στην αρχή κάθε επανάληψης του βρόγχου while θα έχουμε
A[k]+A[l] != T για κάθε k < i και l > j.

Initialization: Πριν την πρώτη επανάληψη το αμετάβλητο ισχύει, διότι δεν θα υπάρχει A[k] ή A[j] με k < i και l > j.
Maintenance: Το αμετάβλητο του βρόγχου διατηρείται σε κάθε επανάληψη, διότι διαφορετικά σε κάποια Ν-οστή επανάληψη θα υπήρχαν κάποια k < i και l > j έτσι ώστε A[k]+A[l]=T. Ωστόσο αν συνέβαινε αυτό, ο βρόγχος στην Μ < Ν επανάληψή του θα έδινε κάποια i και j έτσι ώστε A[i]+A[j]=T, θα τερμάτιζε και το SUMCHECK θα επέστρεφε 'true'. Έτσι, δε θα υπήρχε N-οστή (μεταγενέστερη μιας M-οστής) επανάληψη του βρόγχου. Άτοπο.
--Όσο δε βρίσκονται i και j που να ικανοποιούν αυτό που ψάχνουμε, ο βρόγχος if, εφόσον ο πίνακας είναι ταξινομημένος, θα μας εγγυηθεί ότι θα προσεγγιστεί η λύση αφού:
------Αν το άθροισμα είναι μεγαλύτερο απ' αυτό που ψάχνουμε θα πρέπει ο μεγαλύτερος προσθετέος να μειωθεί. Άρα να μειωθεί το j.
------Αν το άθροισμα είναι μικρότερο απ' αυτό που ψάχνουμε θα πρέπει ο μικρότερος προσθετέος να αυξηθεί. Άρα να αυξηθεί το i.
Termination: Όταν ο βρόγχος while τερματίσει, θα υπάρχουν δύο περιπτώσεις:
  1. Ότι τερμάτησε με i < j και επιστρέφει true. Ο βρόγχος if διαβεβαιώνει ότι θα έχουν βρεθεί i και j ώστε A[i] + A[j] = T.
  2. Ότι το i ταυτίστηκε με το j. Άρα δεν υπάρχουν i και j με i != j έτσι ώστε A[i]+A[j]=T, μιας και έχουν ελεγχθεί όλα τα πιθανά k < i και l > j (βλ Maintenance)

Πρώτη φορά που αποδεικνύω αλγόριθμο... Αξιολογήστε την απόδειξή μου!

Τώρα για επίσημη απόδειξη πολυπλοκότητας μέσης περίπτωσης... δε θα το ψάξω καθόλου :lol:
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
Άβαταρ μέλους
thetrojan01
 
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Τοποθεσία: Ρόδος

Re: Πρόβλημα #1

Δημοσίευσηαπό feedWARd » Κυρ Αύγ 01, 2010 4:50 am

@chris, @thetrojan01: Yeap, σωστοί και οι δύο. Αυτή είναι η καλύτερη λύση.

Την απόδειξη δεν την διάβασα, αλλά :o . Το CLRS είναι κακή επιρροή μερικές φορές :P

@sotiris: Επίσης σωστό, αλλά πιο αργό ( Ο(n^2) ).
feedWARd
 
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Πρόβλημα #1

Δημοσίευσηαπό thetrojan01 » Κυρ Αύγ 01, 2010 12:31 pm

feedWARd έγραψε:@chris, @thetrojan01: Yeap, σωστοί και οι δύο. Αυτή είναι η καλύτερη λύση.

Την απόδειξη δεν την διάβασα, αλλά :o . Το CLRS είναι κακή επιρροή μερικές φορές :P

@sotiris: Επίσης σωστό, αλλά πιο αργό ( Ο(n^2) ).

για μας του ΠΔΠ ναι, είναι κακή επιρροή... αλλά είναι τόσο ωραίο! :lol:

Λοιπόν, μόλις ξύπνησα είπα:

στο αμετάβλητο έπρεπε να λέω:
Αμετάβλητο βρόγχου: Στην αρχή κάθε επανάληψης του βρόγχου while θα έχουμε
A[k]+A[l] != T για κάθε k < i και l > j.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
Άβαταρ μέλους
thetrojan01
 
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Τοποθεσία: Ρόδος


Επιστροφή στο Εξάσκηση και προετοιμασία

Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες

cron