hilfe bei programmierbsp in c

@wadim: der code hat mit der definition von inversion wenig zu tun

Schade , naja ich habe ja vorsichtshalber auf meine Mathefähigkeiten hingewiesen, obwohl die mittleren beiden Beispiele aus dem Beitrag von
wolondong bei mir das richtige Ergebnis geliefert haben.

Aus Deinem Code entnehme ich, dass man bei der Inversion das Array vom Ende
bis zum Anfang durchlaufen und die nächstliegenden Paare vergleichen muss?

Nein das ist falsch Mr.N.
Es müssen alle Elemente paarweise auf eine Inversion getestet werden, nicht nur die benachbarten.
wadims Code war schon richtig, außer, dass k bei j+1 und nicht bei j beginnen sollte.

EDIT: Richtig insofern, dass eine vorliegende Permutation korrekt als ungerade bzw. gerade erkannt wird. Ob Code notwendig ist der überhaupt erst prüft ob es eine Permutation ist wird der Fragende wohl wissen...

[ Dieser Beitrag wurde am 05.01.2003 um 12:13 Uhr von space editiert. ]

mi+chl

aber wieso sind das erste und letzte beispiel der angabe keine permutationen?
das ist mir überhaupt nicht klar

mfg

wolondong

das erste und das letzte beispiel sind deswegen nicht permutationsfähig, da ein zahlenelement der natürlichen zahlenfolge fehlt!

so ist zwar 1 2 3 4 eine permutation, da alle natürlichen zahlen von 1 bis 4 vorkommen, jedoch ist beispielsweise

1 2 4 5 keine permutation, da die 3 fehlt!

die hilfe von wadmin war mir sehr hilfreich! vielen dank, hab den code so umgeändert, dass ich entweder eine gerade oder eine ungerade permutation bekomme!
jedoch weiß ich noch nicht wie ich es schaffen soll, dass das programm prüft ob keine permutation vorliegt! eben wenn ein zahlenwert der natürlichen abfolge fehlt! vielleicht hat dazu noch jemand eine idee!

hier mein bisheriger quellcode:

#include <stdio.h>
#define ANZAHL 5

void ausgabe(const int array[], int laenge, int stellen);
int inversion(int *werte, int len);

int feld[ANZAHL];
int i;int n;
int ergebnis = 2;

int main() {
for (i=0; i<ANZAHL; i++) {
printf("%2d.Zahl -->", i+1);
scanf("%d", &feld[i]);
}

n = sizeof(feld) / sizeof(feld[0]);
printf("das feld lautet:");
ausgabe(feld,n,4);
putchar('\n');
inversion(feld,n);

return 0;
}

void ausgabe(const int array[], int n, int breite) {
int i;

for(i=0;i<n;i++)
printf("%*d", breite, array[i]);
}

int inversion(int *werte, int len) /* len ist die Länge des Arrays, wo man
die Werte eingegeben hat */
{
int j=0, k=0, count=0;

for(j=0; j<len; j++)
for(k=j; k<len; k++)
if(werte[j]>werte[k])
count++; /* count wird stets erhöht, wenn*/
printf("es musste %d mal getauscht werden!!\n", count); //ein Element im Array > als einer der nachfolgenden ist

if((count%2)==0)
printf("es liegt eine gerade permutation vor!\n\n");
else
printf("es liegt eine ungerade permutation vor!\n\n");

return 0;
}

vielen dank, wolondong

Mr. N

also das ist ja merkwürdig... zB wäre - wenn ich mir das im Kopf richtig überlegt habe - 2 4 1 3 nach wadims (korrigiertem, da k bei j + 1 beginnen sollte) code eine gerade permutation : [4 1] und [4 3] - oder seh ich das jetzt falsch?

mi+chl

ja, das siehst du falsch, 1. inversion da die 2 vor 1 kommt, und die anderen beiden wegen der 4..

mfg

Mr. N

jetzt müsste man mal jede menge permutationen nehmen und die beiden funktionen vergleichen. ich habe nämlich das gefühl, dass die ergebnisse identisch sein werden. aus faulheit teste ich das jetzt aber nicht *g*.

wadim

wolondonq hat geschrieben:

das erste und das letzte beispiel sind deswegen nicht permutationsfähig, da ein zahlenelement der natürlichen zahlenfolge fehlt!
so ist zwar 1 2 3 4 eine permutation, da alle natürlichen zahlen von 1 bis 4 vorkommen, jedoch ist beispielsweise

1 2 4 5 keine permutation, da die 3 fehlt!

Ich glaube ich fange langsam an zu vers tehen was Permutation ist . Wenn man also die Werte sortiert und jeder Wert vom Anfang an gesehen grösser sein muss als der nächste, den letzten Wert ausgeschlossen,
sollte demnach folgende Funktion von Nutzen sein, die wieder true oder false
liefert, je nachdem... :

int ispermut(int *array,int len)
{
  int i=0, j=0, tmp;
  for(i=len-1; i>0; i--)
    for(j=0; j<i; j++)
      if(array[j]>array[j+1])
      {
        tmp=array[j];
        array[j]=array[j+1];
        array[j+1]=tmp;
      }

  for(j=0; j<len-1; j++)
    if( (array[j+1]-array[j]) >1)
      return 0;
  return 1;
}

Ich habe übrigens Bubble-Sort verwendet. Ich hoffe das hilft.

P.S. man sollte natürlich nicht das Original an die Funktion übergeben,
da sie die Werte sortiert und dann ein Vergleich auf gerade/ungerade mit
dem Array nicht mehr möglich ist.

[ Dieser Beitrag wurde am 05.01.2003 um 20:34 Uhr von wadim editiert. ]

Mr. N

Fuck, dass manche Leute keine Standard-Bibliothek kennen.
@wadim: Nimm qsort()

Hi

Sortieren ist teuer und unnötig.
Du kannst es so machen:

Rückgabe: -1 = keine Permutation, 0 = gerade Perm, 1 = ungerade Perm.

int Perm(int* array, int ArraySize)
{
 int counter=0; 
 int sum=array[0];
 bool checksum=true;

 for(int i=0; i<ArraySize; ++i)
 {
  for(int j=i+1; j<ArraySize; ++j)
  {
   if(checksum)
    sum+=array[j];

   if(array[i]==array[j])
    return -1;

   else if(array[j]>array[i])
    ++counter;
  }

  if(checksum)
  {
   checksum=false;
   if( sum!= 0.5*ArraySize*(ArraySize+1) )
    return -1;
  }
 }

 return counter & 1;
}

Hier wird getestet ob die Zahlenfolge eine gültige Permutation ist mit folgendem Trick:
Die Summe 1+2+3+...+n ergibt 0.5*n*(n+1)
Eine Summe über die Elemente der Permutation muss laut der Formel 0.5*n*(n+1) sein. Ist das nicht der Fall kann -1 zurückgegeben werden => Keine Perm..
Das allein reicht aber nicht aus. Bei diesem Fall z.b. stimmt die Summe mit dem Resultat der Formel überein, trotzdem ist das zweite keine Perm.
1+2+3+4 = 10
2+2+3+3 = 10
Deshalb wird noch getestet ob Gleichheit von je zwei Elementen irgendwann vorkommt. Das kann wie die Summenbildung in den beiden eigentlichen Schleifen der Inversionszählung getestet werden.

[ Dieser Beitrag wurde am 06.01.2003 um 00:38 Uhr von space editiert. ]