C Programmierung

[Anfaenger_2015 (Gast)]

Hallo zusammen,

ich hoffe hier hilfreiche Antworten zu bekommen, wofür ich mich im 
Vorfeld herzlich bedanke!

Es geht um u.g. c-code: er muss mir alle Kombination ausgeben von m von 
n zahlen " vorab  4 von 5 ", was bereits realisiert. jetzt muss ich die 
ausgegeben Möglichkeiten anhand weitere Vorgabe auf Plausibilität.

Mir fehlt der Ansatz und wäre für jeden Tipp sehr dankbar!

#include < stdio.h >
#include < stdlib.h >
#include < string.h >
//#include "_generate.h"

int fak1 ( int wert1 )
 {
 if ( wert1 ==1) return 1;
 else return ( wert1 * fak1 ( wert1 -1));
 }

int fak2 ( int wert2 )
 {
 if ( wert2 ==1) return 1;
 else return ( wert2 * fak2 ( wert2 -1)); 
 }

void print_array( int k, int array[])
{
    static int count = 0;
    int i;
    
    printf( "%d. Moeglichkeit: (", ++count);
    for( i = 0; i < k-1; i++)
        printf( "%d,", array[i]);
    printf( "%d ) \n", array[k-1]);  

  
}
void Moeglichkeiten(int n, int k, int array[], int x)
{
    int i;
    int max;
    
    if( x < k)
    {
        max = x ? array[x-1] : 0;

        for( i=max+1; i <= n-k+x+1; i++)
        {
            array[x] = i;
            Moeglichkeiten( n, k, array, x+1);
        }
    }
    else
        print_array( k, array);
  
}


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

  int n = 5;
    printf("Fakultaet der Gesamtanzahl % d ! = % d \n " , n , fak1 ( n ));

  int m =4;
    printf("Fakultaet der Benutzten Anzahl % d ! = % d \n " , m , fak2 ( m ));

  
    Moeglichkeit= fak1(n)/(fak2(m)*(fak1(n)-fak2(m)));

  printf(" Anzahl der Moeglichkeit= %d \n\n ", Moeglichkeit);  
    

    int array[4];

    printf( "alle 5 vorhandenen Moeglichkeiten \n");
    Moeglichkeiten( 5, 4, array, 0);
  
  //Machine_FSM();



  
     }
    
    
  
    

    system("PAUSE");
    return 0;
}

[Peter II (Gast)]

Anfaenger_2015 schrieb:
> jetzt muss ich die
> ausgegeben Möglichkeiten anhand weitere Vorgabe auf Plausibilität.
>
> Mir fehlt der Ansatz und wäre für jeden Tipp sehr dankbar!

und mir(uns) fehlt was du eigentlich willst.

[zapotek (Gast)]

Kannst du nicht lesen? Steht da doch eindeutig die Aufgabe:
"er muss mir alle Kombination ausgeben von m von
n zahlen " vorab  4 von 5 ", was bereits realisiert."

Was ist daran nicht zu verstehen?
;)

[anderer Ansatz möglich? (Gast)]

Okay, ein Muster

// hier kommt die Lösung rein

[Anfaenger_2015 (Gast)]

Danke für die schnellen Rückmeldungen!

Es werden wie bereits erwähnt alle Möglichkeiten ausgegeben: 1.2.3.4 & 
1.2.3.5 & 1.2.4.5 $ 1.3.4.5 % 2.3.4.5.

Die Zahlen 1 bis 5 müssen Schneidmesser darstellen, die eine Breite x 
haben und alle hintereinander auf einer Schiene positioniert.

jetzt muss ich eine 1800 mm lange Rolle an vier Stellen schneiden: 400, 
700, 1000, und 1300.

Der Breite nach von den Messer wären nur 1.2.3.4 & 2.3.4.5 physikalisch 
realisierbar.

Hat jdn vielleicht eine Idee wie ich vorgehen soll.

Vielen Dank

[Hendrik W. (derhendrik)]

Ich verstehe leider nur Bahnhof, insbesondere das "nur 1.2.3.4 & 2.3.4.5 
sind physikalisch realisierbar."

Du hast doch dein Problem schon selber gelöst, wenn alle möglichen 
Kombinationen ausgegeben werden, oder?

Zur Not hier mal ein Link, wo andere Leute das Problem umgesetzt haben:

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

(Hoffe es ist okay hier auf andere Seiten zu verlinken)

[Anfaenger_2015 (Gast)]

Vielen Dank Hendrik w. für deine Antwort.

Um das Problem zu erklären: berücksichtigen Wir die 2. Möglichkeit 
1.3.4.5.

dh. dass, die Messer_1, Messer_3, Messer_4, Messer_5 gesetzt werden 
müssen. in der Rhein und  Folge: Messer_5 schneidet an der Stelle 
1300mm.
                         Messer_4 schneidet an der Stelle 1000mm.
                         Messer_3 schneidet an der Stelle 700mm.
                         Messer_2 ist inaktiv. muss aber positioniert 
werden!
                         Messer_1 schneidet an der Stelle 400mm.

Nicht zu vergessen, Dass die Messer auf einer Schiene sind bzw. dass 
alle Messer 200 mm breit sind. Sprich: Messer_2 kann nicht zwischen 
Messer_3 und Messer_1 positioniert werden, weil der übrige Abstand 
zwischen Messer_3 und Messer_1 nur 100 mm.

===> Die Möglichkeit kann physikalisch nicht realisiert werden.

Ich hoffe, dass mir jdn bei dem Lösungsanatz helfen kann.

Viele Grüße

[Anfaenger_2015 (Gast)]

Ich hoffe, dass es jetzt besser ist :)

[Ben (Gast)]

Hallo Anfaenger_2015,

Ich versuche mal, dein Problem verständlicher zu formulieren:

Gegeben ist:
* ein 1800mm langes Werkstück (Rolle)
* 4 Stellen an denen die Rolle gleichzeitig durchgeschnitten werden soll
* 5 Messer mit unterschiedlicher Breite der Halterung

Gesucht sind alle Kombinationen von Messern mit denen die 4 Schnitte 
gleichzeitig durchgeführt werden können.

Richtig?

Ich gehe davon aus, dass die Messerhalterungen unterschiedlich breit 
sind, denn warum würdest du sonst alle Kombinationen durchgehen wollen? 
Wenn die Messerhalterungen alle gleich breit sind, brauchst du nur die 
Abstände zwischen den 4 Schneid-Stellen mit der Messerbreite zu 
vergleichen.

[mnbnasd (Gast)]

Das mit den Kombinationen macht meiner Meinung nach sowieso wenig Sinn 
wenn die Reihenfolge der Messer vorgegeben ist. Ist das eine 
Übungsaufgabe? oder eine reale Aufgabe? Wenn dann müsste man alle 
aufsteigenden Teilfolgen der Indexmenge 1,2,3,4...,m der größe n 
bestimmen aber auch das wäre viel Aufwand wenn das nicht nur auf die 
paar messer im beispiel beschränkt bleiben sollte. Ich würde mal für 
eine andere Perspektive die Messer aneinander ordnen. Im Prinzip wäre 
das ja in einem eigenen Koordinatensystem ein Dirac Kamm mit summe über 
alle i der Indexmenge dirac(x-i*200+100) (um in den ursprung zu 
verschieben). Wenn man (was aus der Aufgabe auch nicht ganz klar ist) 
die Messer verschieben darf, dann kommt noch eine variable verzögerung 
d_i für jedes messer rein.
summe über i der Indexmenge dirac(x-i*200+100-d_i), wobei die d_i 
zwischen 0 (alle direkt aneinander) und einer max Grenze die aus der 
Aufgabe aber auch nicht hervorgeht. Eigentlich müssten ja jetzt die 
Schnittpunkte c_i = i*200-100+d_i erfüllen für alle i der Indexmenge und 
d_i müssen exisieren.
Sieht irgendwie nach ILP aus? Nur eine Idee!

[Anfaenger_2015 (Gast)]

Ich gehe davon aus, dass die Messerhalterungen unterschiedlich breit
> sind, denn warum würdest du sonst alle Kombinationen durchgehen wollen?

die Messerhalterungen sind eben gleich breit " 200 mm ".

Damit du besser nachvollziehen kannst, warum nicht alle Möglichkeiten 
realisierbar sind, Sieh dir bitte das Foto im Anhang an.

[Ben (Gast)]

Ich habe mir das Bild vorhin schon mehrfach angesehen und sehe nicht was 
das mit Kombinationen zu tun hat.

Was ich aber sehe ist, dass du es in 5 Posts noch immer nicht geschafft 
hast, das Problem für andere verständlich zu beschreiben. Im ersten 
Posting steht bis auf das Wort "Plausibilität" kein Wort zur 
eigentlichen Aufgabenstellung.

[Quappenkaul (Gast)]

Was genau willst du denn herausbekommen? Wenn es nur die physisch 
möglichen Kombinationen bei gegebenen Schnittbreiten sind, musst du doch 
nur die paar 4er-Kombinationen durchprobieren. Sobald eines der Messer 
nicht "passt" (Mindestabstand unterschritten), scheidet die 
entsprechende Kombination aus.

[Salewski, Stefan (Gast)]

Ich habe das in etwa so verstanden:

# test data
Knifes = 5
Thickness = 200
Pos = [400, 700, 1000, 1300]

def min_sep(a, b)
  (b - a).abs * Thickness
end

def test(cut_pos, num_knifes, thickness)
  cuts = cut_pos.length
  disabled = num_knifes - cuts
  all_knifes = (1..cuts + 1).to_a
  active_knifes = all_knifes.combination(disabled).map{|el| all_knifes - el}.sort
  active_knifes.each{|k|
    ok = true
    k.each_cons(2){|a, b|
      ok = false if cut_pos[k.index(b)] - cut_pos[k.index(a)].abs < min_sep(a, b)
    }
    puts ok ? "valid:" : "invalid:" 
    puts k.map{|el| "knife #{el} at #{cut_pos[k.index(el)]}"}
    puts
  }
end

test(Pos, Knifes, Thickness)

$ ruby messer.rb
valid:
knife 1 at 400
knife 2 at 700
knife 3 at 1000
knife 4 at 1300

invalid:
knife 1 at 400
knife 2 at 700
knife 3 at 1000
knife 5 at 1300

invalid:
knife 1 at 400
knife 2 at 700
knife 4 at 1000
knife 5 at 1300

invalid:
knife 1 at 400
knife 3 at 700
knife 4 at 1000
knife 5 at 1300

valid:
knife 2 at 400
knife 3 at 700
knife 4 at 1000
knife 5 at 1300

[Salewski, Stefan (Gast)]

(cut_pos[k.index(b)] - cut_pos[k.index(a)]).abs sollte das heißen, wobei 
das abs wegen der vorhergehenden Sortierung aber entbehrlich ist.

[Karl H. (kbuchegg)]

Klingt für mich nach einer Backtracking Aufgabe.

Messer n wird entweder benutzt oder nicht benutzt.
Wenn es benutzt wird, dann wird es so positioniert, dass es an der 
gewünschten Stelle schneidet, wenn das geometrisch möglich ist.
Wenn es nicht benutzt wird, dann wird es einfach an das vorhergehende 
Messer rangeschoben (bzw. auf 0).

Und dann: 'Backtracken'.

Man kann natürlich alle Kombinationen von 'benutzt/nicht benutzt' 
bestimmen und dann nachsehen, welche davon gültig sind. Backtracking hat 
halt den Charme, dass es während des Abarbeitens gleich viele 
Kombinationen ausschliesst (was bei 5 Messern sicher nicht das grosse 
Problem ist. Messer 1 auf 400 und Messer 3 auf 700 funktioniert nicht, 
egal wie man Messer 4 oder 5 (oder wenn es noch mehr sind dann alle 
weiteren) positioniert.

[Tek (Gast)]

Wieso werden die Messer nicht einfach der Reihenfolge nach auf den 
Schnitten positioniert? Dann müsste man ja nur die minimale 
Schnittbreite von 200mm überwachen.

[Anfaenger_2015 (Gast)]

Karl Heinz schrieb:
> Klingt für mich nach einer Backtracking Aufgabe.
>
> Messer n wird entweder benutzt oder nicht benutzt.
> Wenn es benutzt wird, dann wird es so positioniert, dass es an der
> gewünschten Stelle schneidet, wenn das geometrisch möglich ist.
> Wenn es nicht benutzt wird, dann wird es einfach an das vorhergehende
> Messer rangeschoben (bzw. auf 0).
>
> Und dann: 'Backtracken'.
>
> Man kann natürlich alle Kombinationen von 'benutzt/nicht benutzt'
> bestimmen und dann nachsehen, welche davon gültig sind. Backtracking hat
> halt den Charme, dass es während des Abarbeitens gleich viele
> Kombinationen ausschliesst (was bei 5 Messern sicher nicht das grosse
> Problem ist. Messer 1 auf 400 und Messer 3 auf 700 funktioniert nicht,
> egal wie man Messer 4 oder 5 (oder wenn es noch mehr sind dann alle
> weiteren) positioniert.

Lieber karl Heinz,
das hast du 100% richtig verstanden. bei 4 aus 5 Messer ist es einfach 
zu lösung. Die Proleme hat man wie du richtig beschrieben hast, ab 4 
Messer aus 6 Messer.

[Anfaenger_2015 (Gast)]

Tek schrieb:
> Wieso werden die Messer nicht einfach der Reihenfolge nach auf den
> Schnitten positioniert? Dann müsste man ja nur die minimale
> Schnittbreite von 200mm überwachen.

lieber Tek, wdas würde gehen bei 4 aus 5 messer. Wenn du aber 6 , 7 oder 
mehr Messer hast, davon aber logischerweise nur 4 verwenden kannst [ an 
den Stellen ( 400,700,1000,1300)] dann kannst du die INAKTIVE Messer aus 
Platzmangel nicht positionieren

[Karl H. (kbuchegg)]

Anfaenger_2015 schrieb:

> Lieber karl Heinz,
> das hast du 100% richtig verstanden. bei 4 aus 5 Messer ist es einfach
> zu lösung. Die Proleme hat man wie du richtig beschrieben hast, ab 4
> Messer aus 6 Messer.

Ja, gut. Macht ja nix.
Für eine Backtracking Lösung ist die Anzahl der Messer algorithmisch 
recht irrelevant.

[Karl H. (kbuchegg)]

Tek schrieb:
> Wieso werden die Messer nicht einfach der Reihenfolge nach auf den
> Schnitten positioniert? Dann müsste man ja nur die minimale
> Schnittbreite von 200mm überwachen.

Stell dir eine Komplettschnittbreite von 2000 vor und du sollst 1 
Schnitt bei 1700 machen. Du hast 5 Messer auf der Schiene (jedes ist 
200mm breit) und musst die so verschieben und aktiv/inaktiv machen, dass 
du den gewünschten Schnitt bei 1700 hinkriegst ohne dass ein Messer von 
der Schiene runtergenommen werden muss.

Du kannst dafür nicht einfach Messer 1 benutzen, denn alle weiteren 
Messer sind ja rechts davon. Sitzt Messer 1 auf 1700, dann ist seine 
rechte Kante bei 1800 und zwischen 1800 und 2000 passen die restlichen 4 
Messer nicht mehr rein.

An dieser Stelle geht nur
* Lösung 1
  Messer 1 ganz links, inaktiv
  Messer 2 rechts neben 1, inaktiv
  Messer 3 rechts neben 2, inaktiv
  Messer 4 auf 1700 eingestellt, aktic
  Messer 5 rechts neben 4, inaktiv

* Lösung 2
  Messer 1 ganz links, inaktiv
  Messer 2 rechts neben 1, inaktiv
  Messer 3 rechts neben 2, inaktiv
  Messer 4 rechts neben 3
  Messer 5 auf 1700 eingestellt, aktiv


D.h. diese Aufgabe ist entweder mit Messer 4 oder mit Messer 5 lösbar. 
Mit allen anderen funktioniert es nicht, weil sich sonst die inaktiven 
Messer gegenseitig im Weg sind.

Alles in allem: eine schöne Backtracking Aufgabe. Ordne n Elemente so an 
(Abstand + Aktivierung), dass gewisse Nebenbedingungen eingehalten 
werden.

Wenn ich jetzt noch wüsste, ob das Ganze Hausaufgabe oder 
Produktionscode ist.

[Anfaenger_2015 (Gast)]

> Wenn ich jetzt noch wüsste, ob das Ganze Hausaufgabe oder
> Produktionscode ist.

Das ist eine Aufgabe, die mir Als Praktikant gegeben wurde.


int schnitte[] = {0,400, 700, 1000, 1300,1800};
Beispiel: { 3.4.5.6} im Fall 4 aus 6 Messern

Mein Problem ist wie ich die Formel/  if ( schnitte[b]-schnitte[b-1] < 
(combination[b]-combination[b-1]) * mindestbreite ) verbessern kann, 
dass die Möglichkeit als nicht realisierbar ausgegeben wird

[Salewski, Stefan (Gast)]

Anfaenger_2015 schrieb:
> Mein Problem ist

Hatte ich doch oben in dem Ruby Text angegeben:

cut_pos[k.index(b)] usw.

(Das mit dem index() ist eigentlich nicht schön da recht ineffizient, 
aber mit fiel da so spontan nichts besseres ein...)

Du musst den Index des Messers auf dessen räumliche Position abbilden, 
dann die Differenz benachbarter Messer berechnen und testen ob sie groß 
genug ist. Aber für einen 16 jährigen Praktikanten, und dann noch in C, 
ist das wirklich etwas unangenehm. Übrigens, mein Code oben funktioniert 
wohl nicht, wenn alle Messer im Einsatz sind, dann ist 
combination(disabled) undefiniert, man muss da eine Fallunterscheidung 
einbauen. Na ja, vielleicht macht Dir Herr Buchegger das ja in C, 
womöglich noch mit Backtracking. Das traurige ist aber eigentlich, dass 
Du die Aufgabe anfangs auch nicht ansatzweise selbst beschreiben 
konntest. Was mir übrigens nicht klar war, ist ob die gesamtlänge der 
Rolle relevant ist. Ich hatte angenommen dass die nicht von Bedeutung 
ist, aber womöglich kann ein Messer ja auch nicht ganz nah am Ende 
positioniert werden?

[Anfaenger_2015 (Gast)]

Salewski, Stefan schrieb:
> Anfaenger_2015 schrieb:
>> Mein Problem ist
>
> Hatte ich doch oben in dem Ruby Text angegeben:
>
> cut_pos[k.index(b)] usw.
>
> (Das mit dem index() ist eigentlich nicht schön da recht ineffizient,
> aber mit fiel da so spontan nichts besseres ein...)
>
> Du musst den Index des Messers auf dessen räumliche Position abbilden,
> dann die Differenz benachbarter Messer berechnen und testen ob sie groß
> genug ist. Aber für einen 16 jährigen Praktikanten, und dann noch in C,
> ist das wirklich etwas unangenehm.

Ich bin ein Praktikant, aber kein 16 jähriger :). Praktikant der sich 
während des Studium mit Prorammiersprachen halbwegs beschäftigen durfte.


 Übrigens, mein Code oben funktioniert
> wohl nicht, wenn alle Messer im Einsatz sind, dann ist
> combination(disabled) undefiniert, man muss da eine Fallunterscheidung
> einbauen. Na ja, vielleicht macht Dir Herr Buchegger das ja in C,
> womöglich noch mit Backtracking. Das traurige ist aber eigentlich, dass
> Du die Aufgabe anfangs auch nicht ansatzweise selbst beschreiben
> konntest. Was mir übrigens nicht klar war, ist ob die gesamtlänge der
> Rolle relevant ist. Ich hatte angenommen dass die nicht von Bedeutung
> ist, aber womöglich kann ein Messer ja auch nicht ganz nah am Ende
> positioniert werden?

Viel dank für deine Aufklärung und verzeiht bitte alle zusammen, dass 
ich ungenau mein Problem beschrieben habe. Das liegt an meine 
Unerfahrenheit. Ich war der Meinung, dass ich mit den Angaben: Anzahl 
der Messern + Schnittstellen+ wie die Messer auf einer Schiene 
positioniert sind, meine Aufgabe vollständig beschrieben habe.