Programming Quiz

bokarinho · 16 Ιανουαρίου 2007

Τελευταία έπεσε στα χέρια μου ένα Quiz που έθετε το εξής:

Για πίνακες δυναμικούς με μέγεθος n * n με n > 4 και ξεκινώντας από την θέση (0,0) του πίνακα να γεμίζουμε τον πίνακα μέχρι τέλους με τους αριθμούς απο το 1 μέχρι το n * n με τον εξής τρόπο.

1. Ο αριθμός 1 θα μπαίνει πάντα στην θέση (0,0)

2. Για κάθε κ απο το 1 μεχρι το (n * n) -1 οι αριθμοί κ και κ + 1 θα πρέπει να έχουν τοποθετηθεί στην ίδια γραμμή ή στην ίδια στήλη έχοντας αφήσει 2 κενές θέσεις μεταξύ τους ή στην ίδια διαγώνιο έχοντας αφήσει μία κενή θέση μεταξύ τους.

Για παράδειγμα για έναν αριθμό που έχει τοποθετηθεί σωστά στην θέση (i,j)

η επόμενη δυνατή θέση θα είναι μία από τις 8 ακόλουθες εφόσον υφίστανται μέσα στα όρια του πίνακα. Δηλαδή (i+3,j),(i-3,j),(i,j+3),(i,j-3),(i+2,j+2),(i-2,j+2),(i-2,j+2),(i-2,j-2).

Μία λύση για παράδειγμα είναι αυτή για ν = 5

1 19 16 4 20

14 24 8 11 23

17 5 21 18 6

2 10 15 3 9

13 25 7 12 22

ή για ν = 6 αυτή:

1 28 7 2 25 8

13 18 34 10 15 35

32 3 24 29 6 23

20 27 14 19 26 9

12 17 33 11 16 36

31 4 21 30 5 22

Την γνώμη σας λοιπόν....

george86 · 16 Ιανουαρίου 2007

Να και η εκφωνηση σε pdf αν σας βοηθαει.

http://www.di.uoa.gr/~ip/iphw0607_4.pdf

bokarinho · 16 Ιανουαρίου 2007

Να και η εκφωνηση σε pdf αν σας βοηθαει.

http://www.di.uoa.gr/~ip/iphw0607_4.pdf

Ναι σωστά το έθεσες αλλά δεν πρόκειται για εργασία που αφορά εμένα απλά μου τέθηκε σαν ζήτημα και το θεώρησα ενδιαφέρον να συζητηθεί,δεν αναμένω καμία λύση στο θέμα και ούτε ζητάω από κάποιον να δημιουργήσει το πρόγραμμα για αυτό. Απλά μπορούν να θιχτούν πολλά και ωραία προγραμματιστικά κόλπα όπως η αναδρομή ή η μέθοδος του Backtracking..

paulogiann · 16 Ιανουαρίου 2007

...
Απλά μπορούν να θιχτούν πολλά και ωραία προγραμματιστικά κόλπα όπως η αναδρομή ή η μέθοδος του Backtracking..

Κάτι σαν depth-first search μοιρίζει.. Να αποκλείσουμε όποια straightforward προσέγγιση?

drm · 16 Ιανουαρίου 2007

Μία σχετικά απλή λύση θα ήταν η εξίς:

Έστω πίνακας 'Π' με τους είδη τοποθετημένους αριθμούς, 'Λ' η λίστα με τις διαθέσιμες θέσεις του αριθμού 'κ' στον πίνακα 'Π'. (Προσοχή η λίστα είναι διαφορετική για κάθε πίνακα 'Π' ανάλογα με το ποιες θέσεις είναι άδειες)

Συνάρτηση Τοποθέτησε(Π) {

Κ = Μέγιστος αριθμός του πίνακα;

Εάν Κ > ν*ν ΕΠΕΣΤΡΕΨΕ ΑΛΗΘΕΣ;

(Χ, Υ) = Η θέση του Κ;

Λ = Η λίστα με τις διαθέσιμες θέσεις;

Εάν Λ = κενό τότε επέστρεψε ΛΑΘΟΣ (Δηλ. εάν δεν υπάρχει διαθέσιμη θέση)

Για κάθε στοιχείο της Λ κάνε

Τοποθέτησε τον Κ+1 στην θέση Λ του Π

επέστρεψε την τιμή της Τοποθέτησε(Π); Προφανός με το νέο στοιχείο.

}

Λογικά θα λειτουργήσει.

Καλή τύχη

bokarinho · 16 Ιανουαρίου 2007

Κάτι σαν depth-first search μοιρίζει.. Να αποκλείσουμε όποια straightforward προσέγγιση?

Μοιρίζει πολύ για DFS δεν νομίζω να παίζει μια straightforward απάντηση.

chiossif · 18 Ιανουαρίου 2007

...και καταθέτω τον ακόλουθο κώδικα:

>
#include <stdio.h>
#include <stdlib.h>

int mat[12][12], n;
void display_mat(void);

int main(int argc, char **argv) {
   if (argc!=2)
       exit(1);
   if ((n=atoi(argv[1]))<4 || n>12)
       exit(2);
   if (sqr(1,0,0))
       display_mat();
   return 0;
}

void display_mat(void) {
   register int i,j;
   for (i=0;i<n;i++) {
       for (j=0;j<n;j++)
           printf(" %3d",mat[i][j]);
       printf("\n");
   }
}

int check(int i, int j) {
   if (i>=0 && i<n && j<n && j>=0)
       return 1;
   else
       return 0;
}

int sqr(int k, int i, int j) {
   int l, o, p;

   if (l=mat[i][j])
       return l;
   else {
       mat[i][j]=k;
       o=i-2;
       p=j+2;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i;
       p=j+3;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i+2;
       p=j+2;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i+3;
       p=j;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i+2;
       p=j-2;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i;
       p=j-3;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i-2;
       p=j-2;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i-3;
       p=j;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
   }
}

Φίλε bokarinho,

τώρα έγινε πραγματικό Programming Quiz.

Πριν ήταν απλά μια δύσκολη άσκηση.

bokarinho · 19 Ιανουαρίου 2007

...και καταθέτω τον ακόλουθο κώδικα:

>
#include <stdio.h>
#include <stdlib.h>

int mat[12][12], n;
void display_mat(void);

int main(int argc, char **argv) {
   if (argc!=2)
       exit(1);
   if ((n=atoi(argv[1]))<4 || n>12)
       exit(2);
   if (sqr(1,0,0))
       display_mat();
   return 0;
}

void display_mat(void) {
   register int i,j;
   for (i=0;i<n;i++) {
       for (j=0;j<n;j++)
           printf(" %3d",mat[i][j]);
       printf("\n");
   }
}

int check(int i, int j) {
   if (i>=0 && i<n && j<n && j>=0)
       return 1;
   else
       return 0;
}

int sqr(int k, int i, int j) {
   int l, o, p;

   if (l=mat[i][j])
       return l;
   else {
       mat[i][j]=k;
       o=i-2;
       p=j+2;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i;
       p=j+3;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i+2;
       p=j+2;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i+3;
       p=j;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i+2;
       p=j-2;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i;
       p=j-3;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i-2;
       p=j-2;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
       o=i-3;
       p=j;
       if (check(o,p))
           if (l=sqr(k+1,o,p))
               return l;
   }
}

Φίλε bokarinho,

τώρα έγινε πραγματικό Programming Quiz.

Πριν ήταν απλά μια δύσκολη άσκηση.

Χαίρομαι για τον τρόπο που αντιμετώπισες την άσκηση αλλά να σου πω ότι πρέπει να κάνει το πρόγραμμα και backTracking σε περίπτωση που δεν γίνει κάτι σωστά. Δεν νομίζω να υπάρχει μια straightForward συνάρτηση που να λύνει το πρόβλημα,αλλά το θέμα με την αναδρομή είναι ότι λύνει το πρόβλημα χρησιμοποιώντας την στοίβα του υπολογιστή. Προσπάθησα να το τρέξω σε περιβάλλον DevC++ αλλά δεν μου τρέχει πετάει την οθόνη και την σβήνει. Για να το δω και σε Linux. Εγώ το παλεύει με στοίβα δική μου. Το έτρεξα σε Dos με το .exe 12 και σταματάει να βάζει νούμερα στο 10. Δηλαδή δεν βάζει το 11.

pitsis · 31 Ιανουαρίου 2007

παραθέτω ξανά τη δικιά μου προσσέγγιση

στο πρόβλημα.

είχαμε πει παλιότερα, ότι για ν>8 αρχίζει και αργεί χαρακτηριστικά

να δώσει λύση. αυτό γίνεται γιατί το πρόγραμμα είναι "χαζούλι" και

προσπάθεί να δοκιμάσει όλες τις δυνατές λύσεις χωρίς να μπει

σε διαδικασία επιλογής της βέλτιστης, (με ποια κριτήρια

έτσι στο #define βλέπετε την σειρά με την οποία δοκιμάζει

τις διευθύνσεις προσσέγισης στο πρόβλημα.

υπάρχει καμιά σκέψη;

tip: αν αλλάξει κάποιος την σειρά στο #define π.χ.

#define VD 2

#define DRD 3

#define HR 4

#define DRU 5

#define VU 6

#define DLU 7

#define HL 8

#define DLD 1

έχει "γρήγορη" λύση μέχρι ν==11.

μπορεί κάποιος να κάνει άλλες δοκιμές

>
#include <stdio.h>
#include <stdlib.h>


/*
Eight directions

1=VD=Vertical_Down
2=DRD=Diagonal_Right_Down
3=HR=Horizontal_Right
etc...
*/
#define VD 1
#define DRD 2
#define HR 3
#define DRU 4
#define VU 5
#define DLU 6
#define HL 7
#define DLD 8

int **lookup; /*lookup table*/

struct node {
       int number; /*number from 1 to n^2*/
       int direction; /*direction of the next number*/
       int row; /*line*/
       int col; /*column*/
       struct node *next; /*pointer to next number node. last's number is NULL*/
       struct node *previous; /*pointer to previous number node. 1 is NULL*/
};

/*num, row, col is for the created node. dir is for ther previous*/
void add_node(/*int num, int row, int col, */int dir, struct node *pre){

       struct node *A;
       int ccol, rrow;

       ccol=rrow=0;

       if ((A=malloc(sizeof(struct node)))==NULL){
               fprintf(stderr, "Error. Not enough memory\n");
               exit(3);
       }

       A->number=(pre->number)+1;
       A->direction=0;
       A->next=NULL;
       A->previous=pre;

       pre->direction=dir;
       pre->next=A;

       switch (dir){

               case VD:
                   rrow=pre->row+3;
                   ccol=pre->col;
                   break;
               case DRD:
                   rrow=pre->row+2;
                   ccol=pre->col+2;
                   break;
               case HR:
                   rrow=pre->row;
                   ccol=pre->col+3;
                   break;
               case DRU:
                   rrow=pre->row-2;
                   ccol=pre->col+2;
                   break;
               case VU:
                   rrow=pre->row-3;
                   ccol=pre->col;
                   break;
               case DLU:
                   rrow=pre->row-2;
                   ccol=pre->col-2;
                   break;
               case HL:
                   rrow=pre->row;
                   ccol=pre->col-3;
                   break;
               case DLD:
                   rrow=pre->row+2;
                   ccol=pre->col-2;
                   break;

       }

       A->row=rrow;
       A->col=ccol;
       lookup[rrow][ccol]=1;
}

/*sets the previous of the deleted node, next=NULL. free current memory*/
void del_node(struct node *A){

       A->previous->next=NULL;
       A->previous->direction=0;

       lookup[A->row][A->col]=0;

       free(A);
}


void print_tree_dir(struct node *A){

       while (A){
               printf("%d ", A->direction);
               A=A->next;
       }

}
void print_tree(struct node *A, int n){

       int **Matrix;
       int i, j;

       if ((Matrix=malloc(sizeof(int *)*n))==NULL){
           fprintf(stderr, "Error: Not enough memory\n");
           exit(4);
       }

       for (i=0; i<n; i++)
           if ((Matrix[i]=malloc(n*sizeof(int)))==NULL){
               fprintf(stderr, "Error: Not enough memory\n");
               exit(4);
           }

       while (A){
               Matrix[A->row][A->col]=A->number;
               A=A->next;
       }

       for (i=0; i<n; i++){
           for (j=0; j<n; j++)
               printf("%3d", Matrix[i][j]);
           printf("\n");
       }
}

int check_dir(struct node *A, int dir, int n){

       int rrow, ccol;

       switch (dir){

               case VD:
                   rrow=A->row+3;
                   ccol=A->col;
                   break;
               case DRD:
                   rrow=A->row+2;
                   ccol=A->col+2;
                   break;
               case HR:
                   rrow=A->row;
                   ccol=A->col+3;
                   break;
               case DRU:
                   rrow=A->row-2;
                   ccol=A->col+2;
                   break;
               case VU:
                   rrow=A->row-3;
                   ccol=A->col;
                   break;
               case DLU:
                   rrow=A->row-2;
                   ccol=A->col-2;
                   break;
               case HL:
                   rrow=A->row;
                   ccol=A->col-3;
                   break;
               case DLD:
                   rrow=A->row+2;
                   ccol=A->col-2;
                   break;
       }

   if (rrow<0 || rrow>=n || ccol<0 || ccol>=n || lookup[rrow][ccol])
       return 0;

   return 1;
}

int main(int argc, char *argv[]){

   struct node Start;
   struct node *NODE, *temp;

   int n, i, j, n2;
   int ddir=1;

if (argc!=2) {
	fprintf(stderr, "Only 1 argument\n");
	exit(1);
}

n=atoi(argv[1]);

if (n<5){
       fprintf(stderr, "Number <5\n");
	exit(1);
}


   if ((lookup=malloc(sizeof(int *)*n))==NULL) {
       fprintf(stderr, "Error: Not enough memory\n");
       exit(1);
   }
   for (i=0; i<n; i++)
       if ((lookup[i]=malloc(n*sizeof(int)))==NULL) {
           fprintf(stderr, "Error: Not enough memory\n");
           exit(1);
       }
   for (i=0; i<n; i++)
       for (j=0; j<n; j++)
           lookup[i][j]=0;

n2=n*n;

   /*Start node*/
   Start.number=1;
   Start.direction=0;
   Start.row=0;
   Start.col=0;
   Start.next=NULL;
   Start.previous=NULL;

   lookup[0][0]=1;

   NODE=&Start;

   for (i=1; i<n2; i++){

           while (!check_dir(NODE, ddir, n) && ddir<9){
               ddir++;
           }
           if (ddir>8){
			temp=NODE->previous;
			ddir=NODE->previous->direction+1;
               del_node(NODE);
			i-=2;
			NODE=temp;
			temp=NULL;
           }
           else {
               add_node(ddir, NODE);
			NODE=NODE->next;
               ddir=1;
           }
   }

   print_tree(&Start, n);
   //print_tree_dir(&Start);


   return 0;
}

pitsis · 31 Ιανουαρίου 2007

http://en.wikipedia.org/wiki/Heuristic_%28computer_science%29

εγώ λέω να αρχίσουμε από εδώ το ψάξιμο...

Σύνδεση

Programming Quiz

Προτεινόμενες αναρτήσεις

bokarinho

george86

bokarinho

paulogiann

drm

bokarinho

chiossif

bokarinho

pitsis

pitsis

Αρχειοθετημένο

Σύνδεση