Πρόβλημα #1

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Πρόβλημα #1

Δημοσίευση από feedWARd »

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

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

Δημοσίευση από chris »

Ένας δείκτης i στην αρχή του πίνακα, ένας δείκτης j στο τέλος του. Αν το άθροιμσα των στοιχείων που δείχνουν είναι μεγαλύτερο του N μειώνουμε το j, αλλιώς αυξάνουμε το i μέχρι να βρούμε την λύση. Πολυπλοκότητα μνήμης n, πολυπλοκότητα χρόνου Ν στην χειρότερη περίπτωση. ΧΑ.
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

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

Δημοσίευση από pman »

Κώδικας: Επιλογή όλων

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

thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

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

Δημοσίευση από thetrojan01 »

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

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


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

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

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

Δημοσίευση από feedWARd »

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

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

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

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

Δημοσίευση από thetrojan01 »

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.
Απάντηση