ασκηση στην c

[vaggos_ece]

Μια απλοποίηση στην δικια μου προσέγγιση :

ο μικροτερος αριθμος μπορει να ειναι μονο στην πρωτη ή τελευταία θεση

ο  δευτερος μικροτερος αριθμος μπορει να ειναι μονο στην πρωτη ή τελευταία θεση απο τον πινακα που απομενει 

κλπ

 

κώδικας σε C#  (πατα execute)

 

http://goo.gl/BdzG5R

φίλε σε ευχαριστω πολυ για την βοήθεια αλλα δυστηχος το 50% δεν το καταλαβαίνω (Console.Write(arr + " "); ,int[] copyArr1 = new int[arr.Length]; ,  Generate(copyArr1, start + 1, end); .Θα κάνω ποστ(γιατι δεν δέχεται zip) τον κώδικα που έχω κάνει να δεις το επιπεδο και το πως γράφω.

ΕΚΔΟΣΗ 5.9.2

 

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <time.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

 

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

    srand(time(NULL));

    int i,pin[15],j;

    for(i=0;i<15;i++){

        pin=rand()%101;

    }

    swap(&pin);

    for(i=0;i<14;i++){

        printf("%d\n", (pin-pin[i+1]));

    //    printf("%d\n",pin);

    }

    return 0;

}

 

 

void swap(int *pin){

    int i,j,pindiaf[15][15],p[15],p2[15],k,x,y,r,t,m;

    m=0;

    t=0;

    p[0]=200;

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

        p=p[i-1]+1;

    }

    for(i=0;i<15;i++){

        for(j=0;j<15;j++){

            pindiaf[j]=pin-pin[j];

        }

    }

    for(i=0;i<15;i++){

        for(j=0;j<15;j++){

            x=i;

            y=j;

            r=0;

            p[r]=j;

            if(i!=j){

                for(k=0;k<15;k++){

                    if(r%2==1 && k!=y && pindiaf[x][y]<=pindiaf[k][y] && f(&p,k)==0 && p[r+1]!=y){

                        r=r+1;

                        m=0;

                        t=0;

                        p[r]=k;

                        x=k;

                        k=-1;

                        printf("%d\n",r);

                    }

                    else if(r%2==0 && k!=x && pindiaf[x][y]<=pindiaf[x][k] && f(&p,k)==0 && p[r+1]!=x) {

                        r=r+1;

                        t=0;

                        p[r]=k;

                        y=k;

                        k=-1;

                        printf("%d\n",r);

                    }

                    else{

                        t=t+1;

                    }

                    if(t==15){

                        if(r>0){

                            if(r%2==1){

                                x=p[r];

                            }

                            else{

                                y=p[r];

                            }

                            r=r-1;

                            t=k;

                            if(k==14){

                                t=0;

                                k=-1;

                            }

                        }

                        else if(r==0){

                            k=15;

                            t=0;

                        }

                    }

                    if(r==14){

                        k=15;

                        i=15;

                        j=15;

                    }

                }

            }

        }

    }

    for(i=0;i<15;i++){

        p2=pin;

    }

    for(i=0;i<15;i++){

        pin=p2[p];

    }

    return;

}

int thesh(int r,int x,int y,int s){

    static int pina[15][1],i,j;

    for(i=0;i<15;i++){

        for(j=0;j<2;j++){

            pina[j]=-1;

        }

    }

    if(s==0){

        pina[r][0]=x;

        pina[r][1]=y;

        return 2;

    }

    else{

        if(x=pina[r][0]==x && y==pina[r][1]){

            return 1;

        }

        else{

            return 0;

        }

    }

}

 

int f(int *p,int k){

    int i;

    for(i=0;i<15;i++){

        if(p==k){

            return 1;

        }

    }

    return 0;

}

[albNik]

H Console.Write() ειναι το αντίστοιχο της printf().

 

int[] copyArr1 = new int[arr.Length]; 

αυτο δημιουργεί εναν πινακα μήκους=arr.Length με ολα τα στοιχεια 0.

 

 

Η Generate σε καθε αναδρομη παιρνει εναν πινακα και παραγει δυο αλλους εχοντας προσθεσει τον επομενο αριθμο,

μετα καλει το Generate των δυο πινακων.

 

{19,23,42,79}

 

ξεκιναμε με [0,0,0,0]

 

βαζουμε το 19 στην αρχη η στο τελος  

[19,0,0,0]

[0,0,0,19]

 

το 23  (4 επιλογες)

[19,23,0,0]

[19,0,0,23]

[23,0,0,19]

[0,0,23,19]

 

μετα το 42 (8 επιλογες)

 

το πολυ 2¹⁴ πινακες θα φτιαχτουν .

Αν δεις οτι δεν ειναι σε αυξουσα οι διαφορες των αριθμων που εχεις προσθεσει μπορεις να τερματίζεις την αναδρομη.

 

Ειναι ψευδο c

 

 

 

main(string[] args)
{
    int start[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
    Generate(start, 0, 14);
}

int sorted[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };

void Generate(int[] arr, int start, int end)
{
	int next=sorted[15 - end - 1 + start];
	if(start == end)
	{
		arr[start] = next;
		for(int i = 0; i < 15; i++)
			printf(arr[i] + " ");
                check(arr);
                printf("\n");
		return;
	}
	int[] copyArr1 = new int[15];
	int[] copyArr2 = new int[15];

        memcpy(arr,copyArr1,15);
        memcpy(arr,copyArr1,15);

	copyArr1[start] = next;
	copyArr2[end] = next;

	Generate(copyArr1, start + 1, end);
	Generate(copyArr2, start, end - 1);
}

void check(int* arr)
{
  bool isOk=true;
  for(int i = 0; i < 13; i++)
    if(arr[i] - arr[i + 1] > arr[i + 1] - arr[i + 2])
	isOk = false;
   if(isOk)
     printf("OK");
}

 

 

[defacer]

 int i,j,pindiaf[15][15],p[15],p2[15],k,x,y,r,t,m;

               

[AlexHello]

@vaggos_ece

Απ'οτι βλεπω το προγραμμα ειναι worst-case O(n ^ 4) σιγουρα δεν γινεται καλυτερα? (no big deal αλλα λαβε το υποψιν πριν την παραδωσεις δεν ξερω πως βαθμολογουν στην σχολη σου)

 

Περα απο αυτο δεν καταλαβαινω γιατι να δωσεις για εξοικειωση μια ασκηση (περα απο αρκετα τσιμπημενη) η οποια δεν εχει λυση για ενα μεγαλο μερος των αριθμων. Με την πρωτη λυση του AlbNik με 10000 trials για 15 τυχαιους αριθμους [0, 100] μονο ενα 3% μπορουσε να ταξινομηθει σε αυξουσα σειρα βαση των διαφορων

 

Περιεργα πραγματα :/

 

Υ.Γ. εδω η υλοποιηση μου σε java βασισμενη στα πρωτα post του albNik πιθανοτατα να μην ειναι η βελτιστη η απολυτα σωστη..

https://www.dropbox.com/s/8sss94l4clq58rx/Askisi.java?dl=0