ΑΕΠΠ για δυνατούς λύτες

Guest 209912 · 12-05-16

Ξεκινάω αυτό το θέμα στο οποίο θα ανεβάζω ασκήσεις στην Ανάπτυξη Εφαρμογών (ή στον Προγραμματισμό για τους φοιτητές). Οι ασκήσεις θα είναι αρκετά δύσκολες και απευθύνονται σε άτομα που τους αρέσουν οι προκλήσεις.

Ξεκινάω λοιπόν.

Να γραφεί αναδρομική συνάρτηση, η οποία θα παράγει και θα εκτυπώνει όλα τα υποσύνολα ενός συνόλου που θα δέχεται. Για παράδειγμα, τα υποσύνολα του συνόλου {a,b,c} είναι τα {} (κενό σύνολο), {a}, {b}, {c}, {a,b}, {a,c}, {b,c} και {a,b,c}. Υποθέστε ότι θα δέχεται το σύνολο σαν ένα πίνακα χαρακτήρων ή αλλιώς string. Π.χ το σύνολο {a,b,c} θα περαστεί στην συνάρτηση ως "abc".

Dreamweaver · 12 Μαΐου 2016

Εμεις οι πληβειοι που ξερουμε μονο vba ειμαστε eligible?

Anyway

Sub ischool()
i = 1
j = 3
l = 0
Cells(2, 1) = ""
If Mid(Cells(1, 1), i + l, 1) = Right(Cells(1, 1), 1) Then
Cells(j, 1) = Mid(Cells(1, 1), i + l, 1)
End If
Do Until Mid(Cells(1, 1), i + l, 1) = Right(Cells(1, 1), 1)
Cells(j, 1) = Mid(Cells(1, 1), i, 1)
k = i - 1
Do Until k = 0
j = j + 1
Cells(j, 1) = Cells(j - 1, 1) & Mid(Cells(1, 1), k, 1)
k = k - 1
Loop
i = i + 1
j = j + 1
If Mid(Cells(1, 1), i + 1, 1) = Right(Cells(1, 1), 1) Then
l = -1
End If
Loop
ActiveSheet.PrintOut
End Sub

Guest 209912 · 12 Μαΐου 2016

Δεν έχω ιδέα από vba και συνεπώς δεν μπορώ να καταλάβω τι ακριβώς κάνεις εδώ. Αυτό που μπορώ να καταλάβω είναι πως δεν χρησιμοποιείς αναδρομή. Επίσης που ακριβώς διαβάζεις το αρχικό σύνολο?

ΥΓ. Johny15 θα την επιχειρήσεις?

Dreamweaver · 12-05-16

Υποτιθεται οτι το συνολο βρισκεται στο κελι A1. Μπορει να ζητηται κατευθειαν απο τον χρηστη, αλλα ειναι πιο γρηγορο να το γραψω ετσι.
Αυτο που κανω ουσιαστικα ειναι να παιρνω τα γραμματα ενα ενα απο το συνολο, να τα βαζω σε ενα κελι και στα επομενα κελια τους συνδιασμους αυτου το γραμματος με ολα τα προηγουμενα μεχρι να φτασω στην αρχη του συνολου και ολο αυτο τελειωνει οταν το τρεχον γραμμα ισουται με το πρωτο γραμμα του συνολου απο τα δεξια.
Αν βαλεις πχ abc στο Α1 θα βγει

a
b
ba
c
cb
cba

Βασικα γι'αυτο ρωτησα αν η vba is cool enough to join the club

Guest 209912 · 12-05-16

Χάνεις όμως το ac, εκτός και αν παρέλειψες να το γράψεις. Αgain που χρησιμοποιείς αναδρομική συνάρτηση όμως? Αναδρομική είναι μία συνάρτηση που καλεί τον εαυτό της. Για παράδειγμα

Code:

Συνάρτηση (χ)
{
              if (χ=0)
              {
                       τύπωσε χ
                       return
          }
              else
              {
                      Τύπωσε χ
                      Συναρτηση(χ-1)
                      return;
              }
}

H παραπάνω συνάρτηση ψευδοκώδικα θα τυπώσει όλους τους αριθμούς από το χ έως το 0 καλώντας συνεχώς τον εαυτό της.

Dreamweaver · 12-05-16

Ναι, δεν βγαζει το ac, μου διεφυγε
Δεν χρησιμοποιω αναδρομη, απλα ειναι ο απλοικος τροπος που θα γινοταν στο excel αυτο που ζητας

Guest 209912 · 13-05-16

Αρχική Δημοσίευση από Dreamweaver:
Ναι, δεν βγαζει το ac, μου διεφυγε
Δεν χρησιμοποιω αναδρομη, απλα ειναι ο απλοικος τροπος που θα γινοταν στο excel αυτο που ζητας

Έστω, κάνει όμως scale? Δηλαδή αν βάλω σύνολο 8 στοιχείων θα βγάλει όλα τα υποσύνολα?

unπαικτable · 13-05-16

Αρχική Δημοσίευση από Ξεχασμένος:
Ξεκινάω αυτό το θέμα στο οποίο θα ανεβάζω ασκήσεις στην Ανάπτυξη Εφαρμογών (ή στον Προγραμματισμό για τους φοιτητές). Οι ασκήσεις θα είναι αρκετά δύσκολες και απευθύνονται σε άτομα που τους αρέσουν οι προκλήσεις.

Ξεκινάω λοιπόν.

Να γραφεί αναδρομική συνάρτηση, η οποία θα παράγει και θα εκτυπώνει όλα τα υποσύνολα ενός συνόλου που θα δέχεται. Για παράδειγμα, τα υποσύνολα του συνόλου {a,b,c} είναι τα {} (κενό σύνολο), {a}, {b}, {c}, {a,b}, {a,c}, {b,c} και {a,b,c}. Υποθέστε ότι θα δέχεται το σύνολο σαν ένα πίνακα χαρακτήρων ή αλλιώς string. Π.χ το σύνολο {a,b,c} θα περαστεί στην συνάρτηση ως "abc".

Οτι θα προσπαθουσα να ξαναγραψω κωδικα μετα απο 1 χρονο δεν το περιμενα.

Guest 209912 · 13-05-16

Αρχική Δημοσίευση από unπαικτable:
Οτι θα προσπαθουσα να ξαναγραψω κωδικα μετα απο 1 χρονο δεν το περιμενα.

Είναι καλό mental workout.

Johnny15 · 13-05-16

Αρχική Δημοσίευση από Ξεχασμένος:
ΥΓ. Johny15 θα την επιχειρήσεις?

Ναι θα το κοιτάξω. Θεωρώ ότι το string που εισήχθηκε είναι σε πίνακα;

Guest 209912 · 13-05-16

Αρχική Δημοσίευση από Johnny15:
Ναι θα το κοιτάξω. Θεωρώ ότι το string που εισήχθηκε είναι σε πίνακα;

char α[] = "abc"
char* α = abc
string α = abc

οπως θες.

Dreamweaver · 13-05-16

Αρχική Δημοσίευση από Ξεχασμένος:
Έστω, κάνει όμως scale? Δηλαδή αν βάλω σύνολο 8 στοιχείων θα βγάλει όλα τα υποσύνολα?

Δεν υπαρχει θεμα με τον αριθμο στοιχειων, ομως χανει καποια υποσυνολα, οπως εδειξες με το ac. ειναι λαθος ο αλγοριθμος, θα το ξανακοιταξω το σκ

Vold · 15 Μαΐου 2016

Ωραίο topic Ξεχασμένε, ελπίζω να υπάρξει και η αντίστοιχη ανταπόκριση

Από πλευράς μου θα προσπαθήσω να παρουσιάσω αλγορίθμους για την επίλυση των ασκήσεων ή εναλλακτικά αν αυτό δεν είναι εφικτό(λόγω αυξημένης δυσκολίας - πολυπλοκότητας), έχω χρόνο και διάθεση και μπορώ φυσικά, απευθείας προγράμματα(σε JAVA). (Ελπίζω αυτό να είναι αποδεκτό εκ μέρους σου

)

Για την συγκεκριμένη άσκηση θα παρουσιάσω έναν απλοϊκό αλγόριθμό όπου εύκολα μετατρέπεται σε πρόγραμμα.

Η είσοδος του αλγορίθμου είναι ένα string με n χαρακτήρες.
Η αναδρομική συνάρτηση θα κληθεί n φορές, με είσοδο από το 1 έως το n.
Η είσοδος αντικατοπτρίζει το πλήθος των χαρακτήρων/στοιχείων του εκάστοτε συνόλου.
Η αφετηρία των νέων συνόλων είναι αυτή που ξεκινάει με το πρώτο στοιχείο του αρχικού συνόλου και κάθε επόμενο είναι το επόμενο του προηγούμενου. (π.χ για είσοδο cdefg, με είσοδο της αναδρ. συνάρτησης τον αριθμό 3, τα νέα σύνολα ξεκινάνε από το cde.)
Κατόπιν, κάθε χαρακτήρας/στοιχείο του συνόλου αυτού αλλάζει, ξεκινώντας από τον τελευταίο, έως ότου πάρει τον τελευταίο του επιτρεπτό χαρακτήρα/στοιχείο. cdefg: cde -> cdf ->cdg.
Όταν ο χαρακτήρας που αλλάζει δεν είναι ο τελευταίος τότε οι επόμενοι του αλλάζουν κι αυτοί και ξεκινούν από τον επόμενο χαρακτήρα εκείνου που άλλαξε τελευταίος. cde -> ... -> cdg-> cef.
Όλοι οι χαρακτήρες αλλάζουν τις ίδιες φορές κι εξαρτάται από την είσοδο. Συγκεκριμένα αλλάζουν κατά n - input.
Προσθέτουμε το κενό σύνολο ή εναλλακτικά καλούμε την αναδρομική συνάρτηση μια παραπάνω φορές προσθέτοντας κατάλληλη συνθήκη ελέγχου.
Tip: To πλήθος των δυνατών υποσυνόλων ενός συνόλου είναι ίσο με το δυναμοσύνολο του, δηλαδή 2 εις το πλήθος των στοιχείων της εισόδου - του αρχικού συνόλου.

Παράδειγμα: Για το σύνολο abcd, 4ων χαρακτήρων, έχουμε την εξής διαδικασία-έξοδο.

Κλήση αναδρομικής συνάρτησης με είσοδο 1:
a
b
c
d
(4 αλλαγές σε όλα - εδώ είναι μόνο ένα στοιχείο)

Κλήση αναδρομικής συνάρτησης με είσοδο 2:
ab
ac
ad
bc
bd
cd
(3 αλλαγές σε όλα)

Κλήση αναδρομικής συνάρτησης με είσοδο 3:
abc
abd
acd
bcd
(2 αλλαγές σε όλα)

Κλήση αναδρομικής συνάρτησης με είσοδο 4:
abcd
(1 αλλαγή σε όλα)

Προσθήκη κενού συνόλου - Συνολικά:
{ }
a
b
c
d
ab
ac
ad
bc
bd
cd
abc
abd
acd
bcd
abcd

Guest 209912 · 15-05-16

Vold πολύ ωραίος ο αλγόριθμός σου. +1 και για την παρουσίαση, έχεις μέλλον. Κάνε και μια υλοποίηση σε Java αν δε βαριέσαι, για να μπορούμε να το τρέξουμε και να δούμε ότι όντως λειτουργεί.

Αφού πέρασαν μερικές μέρες παραθέτω κι εγώ τη δική μου λύση. Είναι γραμμένη σε C++. Όποιος θέλει να το τρέχει μπορεί απλά να το κάνει copy paste σε ένα σημειωματάριο και μετά compile με το g++.

Code:

#include <iostream>
#include <cstdlib>
#include <string.h>
using namespace std;


char* subString(char* str,int index,int strlength);
int subSet(char* Set,int length);

/*
    Για να κρατήσω τον κώδικα όσο πιο απλό γίνεται, ώστε να είναι εύκολα κατανοητός το παρακάτω
    πρόγραμμα δεν είναι το βέλτιστο. Ναι μεν θα παράγει όλα τα δυνατά υποσύνολα, αλλά θα παράγει
    μερικά πάνω από μία φορά. Το να μειώσουμε την παραγωγή αυτή είναι σχετικά εύκολο καθώς απλά
    θα πρέπει να περνάμε τα παραχθέντα υποσύνολα σε ένα πίνακα στοιχείων και προτού εισάγουμε ένα
    νέο να ελέγχουμε αν ήδη υπάρχει. Αν και εύκολο στην σύλληψη η υλοποίηση έχει πολλές γραμμές
    κώδικα και τεχνικές λεπτομέρειες της C++ γι'αυτό και θα την παραλείψω.

*/
int main()
{
    char str[] = "abc";
    subSet(str,3);
    return 0;
}


/*
    Η subSet είναι η αναδρομική συνάρτηση που θα παράγει όλα τα υποσύνολα. Ως παραμέτρους
    δέχεται έναν πίνακα χαρακτήρων Set όπου περιέχεται το αρχικό σύνολο, καθώς και μία 
    μεταβλητή int όπου περιέχεται των πλήθος των διαφορετικών στοιχείων του συνόλου.
    Για παράδειγμα αν Set = "αβγ" και length = 3 έχουμε το σύνολο {α,β,γ}.

*/
int subSet(char* Set,int length){

    /*
        Επειδή η συνάρτηση είναι αναδρομική, καλεί δηλαδή τον εαυτό της, για να μην έχουμε
        μια ατέρμονη επανάληψη χρειαζόμαστε ένα if τερματισμού, όπως το παρακάτω. Στην 
        περίπτωση που η παράμετρος length είναι 0 τότε σημαίνει πως ως είσοδος μας δόθηκε
        το κενό σύνολο, συνεπώς το βάζουμε σε μια προσωρινή μεταβλητή temp και του τυπώνουμε,
        ενώ στην συνέχεια η αναδρομική συνάρτηση τερματίζει.
    */
    if(length == 0)
    {
        char* temp = (char*)malloc(3);
        temp[0] = '{';
        temp[1] = '}';
        temp[2] = '\0';

        cout << temp << endl;
        free(temp);
        return 0;
    }
    /*
        Αντιθέτως, αν το length είναι μεγαλύτερο του 0, τότε το αρχικό μας σύνολο δεν είναι το
        κενό και επομένως πρέπει να παράγουμε υποσύνολα. Θα ξεκινήσουμε παράγοντας υποσύνολα τα 
        οποία έχουν βαθμό μικρότερο κατά 1 του αρχικού συνόλου. Δηλαδή αν το αρχικό μας σύνολο
        είναι "αβγ" βαθμού 3 καθώς περιέχει 3 στοιχεία, τα πρώτα υποσύνολα που θα παράγουμε θα
        είναι τα "αβ","αγ" και "βγ", όλα βαθμού 2.
    
    */
    else
    {
        cout << Set << endl; // Πρώτα τυπώνουμε το παρόν σύνολο, δηλαδή το "αβγ".

        /*
            Η παρακάτω for υλοποιεί την αναδρομή που θα παράγει όλα τα υποσύνολα. Κάθε σύνολο βαθμού
            Ν έχει Ν άμεσα υποσύνολα. Για παράδειγμα το σύνολο "αβγ" βαθμού 3 έχει 3 άμεσα υποσύνολα
            βαθμού 2. Συνεπώς με την παρακάτω for, καλούμε 3 φορές την συνάρτηση  subSet. Ως παραμέτρους
            τώρα θα της περάσουμε ένα σύνολο χαρακτήρων και ένα μήκος ή βαθμό συνόλου. Ο βαθμός του 
            επόμενου συνόλου θα είναι προφανώς κατά 1 μικρότερος από τον τωρινό βαθμό άρα length-1.
            Η συνάρτηση subString δέχεται τρεις παραμέτρους. Ένα σύνολο, ένα δείκτη και το μήκος του
            συνόλου (ή βαθμό). Αυτό που θα επιστρέψει θα είναι ένα υποσύνολο του συνόλου που δέχθηκε
            μικρότερο κατά 1 βαθμό και δίχως το στοιχείο στο οποίο δείχνει ο δείκτης i. Για παράδειγμα 
            αν περάσουμε τις παραμέτρους "αβγ",1,3 θα μας επιστραφεί το σύνολο "αγ" καθώς θα αφαιρεθεί
            το στοιχείο του "αβγ" που βρίσκεται στη θέση 1 δηλαδή το "β". (Στην C++ οι πίνακες αρχίζουν
            από το 0, άρα η δεύτερη θέση του πίνακα έχει τον δείκτη 1.)

            Επόμένως η παρακάτω for θα τροφοδοτήσει την συνάρτη με τα σύνολα "αβ","αγ" και "βγ" και θα
            ξεκινήσει έτσι μια νέα αναδρομή.
        */
        for (int i=0;i<length;i++)
        {
          subSet(subString(Set,i,length),length-1);
        }
    }
    return 0;
}

/*
    Αυτή είναι η συνάρτηση που "κόβει" το σύνολο που δέχεται ανάλογα με τον δείκτη.
    Δεν θα την εξηγήσω περαιτέρω καθώς είναι απλά τεχνική υλοποίηση και δεν έχει
    άμεση σχέση με την λογική του αλγορίθμου.
*/
char* subString(char* str, int index, int strlength) {

    char* temp;
    int j = 0;
    if (strlength == 1)
    {
        temp = (char*)malloc(3);
        temp[0] = '\0';
        return temp;
    }
    temp = (char*)malloc(strlength);
    for (int i = 0; i<strlength; i++)
    {
        if (i != index)
        {
            temp[j] = str[i];
            j++;
        }
    }
    temp[j] = '\0';
    return temp;
}

Vold · 15 Μαΐου 2016

Έτοιμο και το πρόγραμμα, μου πήρε λίγο παραπάνω απ' όσο περίμενα αλλά χαλάλι. Φαίνεται πως η θεωρία απέχει αρκετά από την πράξη, ορισμένες φορές.
Ακολουθώ τον αλγόριθμο που παρέθεσα προηγουμένως εκτός από την προσθήκη των μονό-συνόλων όπου και τα προσθέτω ξεχωριστά για λόγους διευκόλυνσης.
Η αναδρομική συνάρτηση είναι κάπως πολύπλοκη αλλά αν κατάλαβες το σκεπτικό μου, τότε μπορείς να το καταλάβεις και στο πρόγραμμα πολύ εύκολα.

Code:

public class Subsets {
    static String[] Subsets;
    static String   string;
    static int[]    Elems;
    static int      counter = 1;
    static int      inputSize;
    static int      i, j;
    
    public static void main(String[] args) {
        string = args[0];
        inputSize = args[0].length();
        Subsets = new String[(int)Math.pow(2, inputSize)];
       
        // Empty Subsets
        for(i = 0; i < Subsets.length; i++) {
            Subsets[i] = "";
        }
        
        // Initialize the one-element Subsets
        for(i = 0; i < string.length(); i++) {
            Subsets[counter] += string.charAt(i);
            counter++;
        }
        findSubsets(2);
        
        // Print Subsets
        for(i = 0; i < Subsets.length; i++) {
             System.out.print('{');
             for(j = 0; j < Subsets[i].length(); j++) {
                 System.out.print(Subsets[i].charAt(j) + (j<Subsets[i].length() - 1?",":""));
             }
             System.out.println('}');  
        }

    }

    public static void findSubsets(int sz) {
        if(sz > inputSize) return;
        Elems = new int[sz];

        for(i = 0; i < sz; i++) {
            Elems[i] = i;
        }
        
        for(j = sz - 1; j > 0; j--) {
            while(Elems[sz - 1] < inputSize) {
                for(int k = 0; k < sz; k++) {
                    Subsets[counter] += string.charAt(Elems[k]);
                }
                counter++;
                Elems[sz - 1]++;
            }
            if(Elems[j - 1] != inputSize - sz + j - 1) {
                Elems[j - 1]++;
                for(i = j; i < sz; i++) {
                    Elems[i] = Elems[i - 1] + 1;
                }
                j = sz;
            }
        }
        findSubsets(++sz);
    }
}

vassilis498 · 16-05-16

2 λύσεις κι από μένα με άλλη προσέγγιση σε python:

Code:

#! /usr/bin/python

import sys

def subset_rec(s): 
    """
    Concatenates the first letter ( or not ) with the rest of the subset
    """

    if len(s) == 1:
        return [s[0]]

    else:
        head, *tail = s
        subsets = subset_rec(tail)
        return [head] + subsets + [head + x for x in subsets]


def subset_nonrec(s):
    """
    Iterate over a number and convert it to a bitstring representing
    the presence or not, of each symbol
    """

    # Convert an integer to a bistring of fixed size
    def number_to_bitstring(s, size): return bin(s)[2:].zfill(size)

    # Convert bitstring representation to the equivalent string according to base string
    def bitstring_to_str(bs, base):
        acc = ""
        for index, bit in enumerate(bs):
            if bit == '1':
                acc += base[index]

        return acc

    strSize = len(s)

    # Number of subsets
    iterations = 2 ** strSize - 1

    return [bitstring_to_str(number_to_bitstring(num, strSize), s) for num in range(1, iterations + 1)]



if __name__ == "__main__":
    if len(sys.argv) != 2:
        sys.exit(1)

    baseStr = sys.argv[1]
    
    # Recursive solution
    print('Testing recursive solution: {}'.format(subset_rec(baseStr)))

    # Non recursive solution
    print('Testing non recursive solution: {}'.format(subset_nonrec(baseStr)))

chmod +x subset.py
./subset.py abcd
Testing recursive solution: ['a', 'b', 'c', 'd', 'cd', 'bc', 'bd', 'bcd', 'ab', 'ac', 'ad', 'acd', 'abc', 'abd', 'abcd']
Testing non recursive solution: ['d', 'c', 'cd', 'b', 'bd', 'bc', 'bcd', 'a', 'ad', 'ac', 'acd', 'ab', 'abd', 'abc', 'abcd']

Vold · 16-05-16

2η -και τελευταία- απόπειρα
Δυστυχώς κάπου έχω κάνει κάποιο λάθος οπότε και αναγκάστηκα να το "καλύψω" με ένα trick.
Μέσω του οποίου διαπίστωσα πως ακόμη πιο εύκολα μπορεί να λυθεί η άσκηση απλά καλύπτοντας όλες τις δυνατές περιπτώσεις και "ξεφορτώνοντας" τις μη-έγκυρες.

Code:

public class Subsets {
    
    public static void main(String[] args) {
        System.out.println("{}");
        // Call the recursive function with different size of the subsets
        for( int i = 0; i < args[0].length(); i++) {
            findSubsets(args[0], args[0].toCharArray(), i + 1, 0);
        }
    }

    public static void findSubsets(String firstStr, char[] string, int sz, int elem) {
        if(elem == sz) {
            // Get off the illigal subsets
            for(int k = 1; k < sz; k++) {
                if(findIndex(firstStr, string[k]) <= findIndex(firstStr, string[k - 1])) return;
            }

            // Print the next subset
            System.out.print("{");
            for(int k = 0; k < sz; k++) {
                System.out.print(string[k] + (k < sz - 1?",":"}\n"));
            }
            return;
        }

        // Find the next subsets
        for(int i = 0; i < string.length - sz + 1; i++) {
            string[elem] = firstStr.charAt(elem + i);
            for(int k = elem + 1; k < sz; k++) {
                string[k] = firstStr.charAt(findIndex(firstStr, string[k - 1]) + 1);
            }
            findSubsets(firstStr, string, sz, elem + 1);
        }
    }

    // Find the index of a char to the original string
    public static int findIndex(String str, char c) {
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i)== c) return i;
        }
        return -1;
    }
}

ΑΕΠΠ για δυνατούς λύτες

Guest 209912

Επισκέπτης

Dreamweaver

Πολύ δραστήριο μέλος

Guest 209912

Επισκέπτης

Dreamweaver

Πολύ δραστήριο μέλος

Guest 209912

Επισκέπτης

Dreamweaver

Πολύ δραστήριο μέλος

Guest 209912

Επισκέπτης

unπαικτable

Πολύ δραστήριο μέλος

Guest 209912

Επισκέπτης

Johnny15

Επιφανές μέλος

Guest 209912

Επισκέπτης

Dreamweaver

Πολύ δραστήριο μέλος

Vold

Πολύ δραστήριο μέλος

Guest 209912

Επισκέπτης

Vold

Πολύ δραστήριο μέλος

vassilis498

Διακεκριμένο μέλος

Vold

Πολύ δραστήριο μέλος

Χρήστες Βρείτε παρόμοια

Λοιπές Σελίδες