Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Reisegruppe (Simulationen)

Eine Reisegruppe will Ägypten bereisen und dort Sehenswürdigkeiten besuchen. Die Anzahl und die Reihenfolge der Sehenswürdigkeiten bestimmt, wie viele mögliche Touren es geben wird. Lösen Sie die folgenden vier Teilaufgaben:

Trampeltier
  1. Die Gruppe will vier Sehenswürdigkeiten besuchen. Nummerieren Sie diese und geben Sie alle möglichen Touren an: 1234, 1243, 1324, ..., 4321.
  2. Wie Aufgabe a). Es sollen jedoch neun Sehenswürdigkeiten besucht werden. Geben Sie zudem die Anzahl der Touren aus.
  3. Unter den neun Sehenswürdigkeiten der Aufgabe b) müssen die Pyramiden von Giseh (Nr. 1) und der Basar von Kairo (Nr. 2) mit dabei sein. Diese beiden Sehenswürdigkeiten müssen unbedingt unmittelbar nacheinander, wenn auch nicht unbedingt in dieser Reihenfolge besucht werden. Geben Sie die verbleibenden möglichen Touren und deren Anzahl an.
  4. Der Karnak-Tempel bei Luxor (Nr. 3) ist unter den neun Sehenswürdigkeiten mit dabei. Zwischen den Pyramiden und dem Karnak-Tempel müssen mindestens drei andere Sehenswürdigkeiten liegen. Die Bedingung von Aufgabe c) muss aber weiterhin erfüllt sein. Geben Sie alle Touren und deren Anzahl an.

Tipp: Bei Aufgabe c) und d) kann eine abstand(a, b)-Funktion hilfreich sein.

Diese Aufgabe zeigt, wie mathematisch komplizierte Problemstellungen durch simples Durchnummerieren aller Möglichkeiten gelöst werden können.

Zusatzaufgabe: Wie viele Sehenswürdigkeiten müssen total vorhanden sein, damit ein stures Durchnummerieren aller Möglichkeiten nicht mehr sinnvoll ist.

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

2 Lösung(en)

public class Reisegruppe {
  public static void main(String[] args) {
    new Reisegruppe().top(); }

  void top() {
    Permutationen ps = new Permutationen(); 
    int[] sehenswuerdigkeiten;
    int anzahlTouren;
    
    System.out.println("Aufgabe a)");
    sehenswuerdigkeiten = new int[] {1,2,3,4};
    ps.ausgabe(sehenswuerdigkeiten);
    while(ps.hatNaechstePermutation(sehenswuerdigkeiten)) {
       ps.naechstePermutation(sehenswuerdigkeiten);
       ps.ausgabe(sehenswuerdigkeiten); }
      
    
    System.out.println("Aufgabe b)");
    sehenswuerdigkeiten = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
    anzahlTouren = 1;
    ps.ausgabe(sehenswuerdigkeiten);
    while(ps.hatNaechstePermutation(sehenswuerdigkeiten)) {
        anzahlTouren = anzahlTouren + 1;
        ps.naechstePermutation(sehenswuerdigkeiten); 
        ps.ausgabe(sehenswuerdigkeiten); }
    System.out.println("Aufgabe b: Total der Touren: " + anzahlTouren);
    
    System.out.println("Aufgabe c)");
    sehenswuerdigkeiten = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
    anzahlTouren = 0;
    while(ps.hatNaechstePermutation(sehenswuerdigkeiten)) {
        if(1 == abstand(1, 2, sehenswuerdigkeiten))  {
            anzahlTouren = anzahlTouren + 1;
            ps.ausgabe(sehenswuerdigkeiten);  }
        ps.naechstePermutation(sehenswuerdigkeiten);  }
    if(1 == abstand(1, 2, sehenswuerdigkeiten))  {
        anzahlTouren = anzahlTouren + 1;
        ps.ausgabe(sehenswuerdigkeiten); }
    System.out.println("Aufgabe c: Total der Touren: " + anzahlTouren);
    
    System.out.println("Aufgabe d)");
    sehenswuerdigkeiten = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
    anzahlTouren = 0;
    while(ps.hatNaechstePermutation(sehenswuerdigkeiten)) {
        if(1 == abstand(1, 2, sehenswuerdigkeiten) &&
           4 <= abstand(1, 3, sehenswuerdigkeiten))   {
            anzahlTouren = anzahlTouren + 1;
            ps.ausgabe(sehenswuerdigkeiten);  }
        ps.naechstePermutation(sehenswuerdigkeiten);  }
    if(1 == abstand(1, 2, sehenswuerdigkeiten) &&
            4 <= abstand(1, 3, sehenswuerdigkeiten))   {
             anzahlTouren = anzahlTouren + 1;
             ps.ausgabe(sehenswuerdigkeiten);  }
    System.out.println("Aufgabe d: Total der Touren: " + anzahlTouren);
 
    
  } // end method top();
  
   int abstand(int a, int b, int[] sehenswuerdigkeiten) {
     int posA;
     int posB;
     posA = findPos(a, sehenswuerdigkeiten);
     posB = findPos(b, sehenswuerdigkeiten);
     if(posA < posB) {
        return posB - posA; }
     else {
        return posA - posB; }
   } // end method: abstand

   
   int findPos(int a, int[] sehenswuerdigkeiten) {
     int checkPos;
     checkPos = 0;
     while(checkPos < sehenswuerdigkeiten.length) {
        if(a == sehenswuerdigkeiten[checkPos]) {
            return checkPos;        }
        checkPos = checkPos + 1; }
     return -1; // error, darf nicht passieren!
   }
    
   
   
  
}  // end of class Schulreise



import java.util.Arrays;


public class Permutationen {

   public static void main(String args []) {
       new Permutationen().test();
   }
    
   void test() {
       // Initialpermutation muss aufsteigend sein.
       int permut[] = {1, 3, 4, 6, 9};
       ausgabe(permut);
       while(naechstePermutation(permut)) {
           ausgabe(permut);
       }
   }
    
   void ausgabe(int [] arr) {
       for(int val : arr) {
           System.out.print(val + "");           
       }
       System.out.println();
   }
   
   boolean hatNaechstePermutation(int [] permutation) {
       int aktPos = permutation.length - 1;
       while(aktPos > 0) {
           if(permutation[aktPos - 1] < permutation[aktPos]) {
               return true;
           }
           aktPos = aktPos - 1;
       }
       return false;
   }
   
   /** 
    * Suche numerisch die nächstgrößere Permutation
    * @return false, wenn es bereits die letzte Permutation war.
    */
   boolean naechstePermutation(int[] permutation) {
        int aktPos = permutation.length - 1;
        while(aktPos > 0) {
            if(permutation[aktPos - 1] < permutation[aktPos]) {
                neuOrdnen(permutation, aktPos - 1);
                return true;
            }
            aktPos = aktPos - 1;
        }
        return false;
   }

   /**
    * Beispiel: 123956874
    * Eingabe startPosition: Gegeben ist die Startposition, wo zum ersten mal "<" auftaucht.
    * Im Beispiel die Position, wo die "6" steht: 123956<8>7>4
    * 
    * 1. Finde den minimalen Tauschpartner:
    *    Nennen wir die Zahl an position "startPosition" kurz "startWert".
    *    (in Obigem beispiel: StartWert = 6)
    *    Der Tauschpartner ist die kleinset Zahl rechts der startPosition, die aber größer als der
    *    startWert ist. (im Beispiel 7)
    *    Die Position, wo die "7" steht, nennen wir "naechstesfureStartPos".
    * 2. Tausche "7" mit "6".
    * 3. Sortiere ab >startPos aufsteigend. 
    * 
    */
   void neuOrdnen(int[] permutation, int startPosition) {
        int naechstesFuerStartPos = findeMinimalenTauschpartner(permutation, startPosition);
        tausche(permutation, startPosition, naechstesFuerStartPos);
        sortiereAb(permutation, startPosition + 1);  
   }

   /**
    * Ab "startPosition" soll aufsteigend sortiert werden.
    * @param permutation
    * @param startPosition
    */
   void sortiereAb(int[] permutation, int startPosition) {
        Arrays.sort(permutation, startPosition, permutation.length);
   }


   void tausche(int[] permutation, int a, int b) {
        int temp       = permutation[a];
        permutation[a] = permutation[b];
        permutation[b] = temp;
   }

   /**
    * Siehe doku "neuOrdnen()"
    */
   int findeMinimalenTauschpartner(int[] permutation, int referenzPosition) {
        int referenzWert = permutation[referenzPosition];
        int min = Integer.MAX_VALUE; // next
        int minPos = -1;
        int i = referenzPosition + 1;
        while(i < permutation.length)
        {
          int actValue = permutation[i];
          if(min > actValue && actValue > referenzWert) {
             min = actValue;
             minPos = i;
          }
          i = i + 1;
        }
        return minPos;
   }
   
} // end of class NextPermutation
                
// https://stackoverflow.com/questions/9960908/permutations-in-javascript
// die schnellste und robusteste funktion, die ich jemals zum thema
// gefunden habe.
function permute(arr) {
  let length = arr.length,
      result = [arr.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;
  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = arr[i];
      arr[i] = arr[k];
      arr[k] = p;
      ++c[i];
      i = 1;
      result.push(arr.slice());
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

let pois, tours;

// a)
console.log('a)');
pois = [1, 2, 3, 4];
tours = permute(pois);
console.table(tours);
console.log(tours.length);

// b)
pois = [1, 2, 3, 4, 5, 6, 7, 8, 9];
tours = permute(pois);
console.log(tours.length);

// c)
let tours12 = [],
    tmp;
for (let i = 0; i < tours.length; i++) {
  tmp = tours[i];
  if (Math.abs(tmp.indexOf(1) - tmp.indexOf(2)) == 1) tours12.push(tmp);
}
console.log(tours12.length);

// d)
let tours13 = [];
for (i = 0; i < tours12.length; i++) {
  tmp = tours12[i];
  if (Math.abs(tmp.indexOf(3) - tmp.indexOf(1)) >= 4) tours13.push(tmp);
}
console.log(tours13);
console.log(tours13.length);

                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

Verifikation/Checksumme:

a) 4! = 24

b) 9! = 362 880

c) 2! * 8! = 80 640

d) 36 000

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 2
Schwierigkeit: k.A.
Webcode: aoy8-chnm
Autor: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen