Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Eisenbahn optimieren (Simulationen)

Um einen Berg herum ist eine Eisenbahnlinie angelegt, die 5 Ortschaften besucht. Diese Ortschaften sind hier mit A, B, C, D und E bezeichnet und die Eisenbahnlinie bildet einen geschlossenen Kreis von A über B, C, D und E zurück zu A. Nur die Ortschaft A hat einen Zugang zum Hafen. Alle anderen Ortschaften müssen über die Bahnlinie erreicht werden. Die Abstände zwischen den Ortschaften sind wie folgt gegeben:

AB: 70 km

BC: 80 km

CD: 1020 km

DE: 190 km

EA: 180 km

Gesucht ist die kürzeste Fahrt, die bei A (also im Hafen) beginnt, und alle Ortschaften mindestens einmal besucht. Über Nacht darf der Zug in irgend einem der Orte stehenbleiben, um am nächsten Tag die Reise in umgekehrter Reihenfolge anzutreten um wieder nach A zurückzukehren.

Bei obiger Anordnung ist es klar, dass die Strecke CD möglichst zu vermeiden ist; besser daher, die Strecke AB und BC doppelt zurückzulegen.

Schreiben Sie nun ein Programm, dass die Strecken AB, BC, ..., EA entgegennimmt und den kürzesten Weg ermittelt.

Tipp: Probieren Sie alle Möglichkeiten aus, indem jede Strecke einmal weggelassen wird. Jedes Weglassen einer Strecke liefert uns zwei mögliche Wege, alle Ortschaften zu besuchen: einmal links herum, einmal rechts herum.

Zusatzaufgabe: Die Anzahl der Orte (und somit der Strecken) ist beliebig (> 2). Die Orte müssen hingegen weiterhin in einem geschlossenen Kreis angelegt sein.

2 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

Kommentare (2)

BKluszynski 13. März 2012 17:26   reply report
One of the solutions with programming language "generic" is actually written in ABAP. I could not select ABAP here in this forum so i had to use this workaround :-). my Solution also includes the algorithm for each amount of tracks as suggested in the exersise. you just have to outcommend the testdata in the code. I think its understandable.. Greetz.. Ben
BKluszynski 8. März 2012 17:04   reply report
Wie wäre es mal mit der gleichen Aufgabe, nur das es viel mehr verbindungsstellen gibt. Also ein netz wie im internet z.B. um das zu Lösen bietet sich der Dijkstra-Algorithmus an, ich hab das mal in Java geschrieben, vllt. stell ichs mal unter ner neuen AG rein LG...

3 Lösung(en)

/**
 * @author Mike Wong
 * @date   06.01.2012
 */
public class Eisenbahn {

  private String[] ortschaften = {"A", "B", "C", "D", "E"};
  //                              AB  BC  CD    DE   EA
  private int[]    distanzen   = {70, 80, 1020, 190, 180};
  private int      laengsteDistanz = max(distanzen);
  private int      distanzErsterWeg = 0;
  private int      distanzZweiterWeg = 0;
  private int      kuerzesteDistanz = 0;
  
  public static void main(String[] args) {
    new Eisenbahn().top();
  }
  
  private int max(int[] distArray) {
    int groesste = 0;
    for (int i=0;i<distArray.length;i++) {
      if (distArray[i] > distArray[groesste]) {
        groesste = i;
      }
    }
    return groesste;
  }

  private void top() {
      for (int i=0;i<laengsteDistanz;i++) {
        distanzErsterWeg += (distanzen[i] * 2);
        distanzZweiterWeg += distanzen[i];
      }
      
      for (int j=ortschaften.length-1;j>laengsteDistanz;j--) {
        distanzErsterWeg += distanzen[j];
        distanzZweiterWeg += (distanzen[j] * 2);
      }
      
      kuerzesteDistanz = Math.min(distanzErsterWeg, distanzZweiterWeg);
      
    System.out.println("Kürzeste Distanz: " + kuerzesteDistanz);
  }

}
                

Lösung von: Mike Wong ()

*&---------------------------------------------------------------------*
*& Report  Z_OPTIMIZE_TRACK
*&
*& Programming Language is ABAP!
*&---------------------------------------------------------------------*
*&Instead of track naming "A-B", "B-C" i will use "1-2","2-3" because
*&its simpler to implement it like that
*&
*&---------------------------------------------------------------------*

REPORT  z_optimize_track.

DATA: gt_given_tracks TYPE STANDARD TABLE OF i,
      gl_given_tracks LIKE LINE OF gt_given_tracks.


DATA: g_waychanging_track TYPE c. " Indicates if there is a Track longer than all the others together

DATA: gt_best_way TYPE STANDARD TABLE OF i,
      gl_best_way LIKE LINE OF gt_best_way.


"Entry of the 5 given Tracks
gl_given_tracks = 70.
APPEND gl_given_tracks TO gt_given_tracks.
gl_given_tracks =  80.
APPEND gl_given_tracks TO gt_given_tracks.
gl_given_tracks =  1020.
APPEND gl_given_tracks TO gt_given_tracks.
gl_given_tracks = 190.
APPEND gl_given_tracks TO gt_given_tracks.
gl_given_tracks = 180.
APPEND gl_given_tracks TO gt_given_tracks.



*"Entry of the 6 given Tracks / you can try every tracknumber Just to show you it functions :-)
*gl_given_tracks = 70.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks =  80.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks =  1020.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks = 190.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks = 180.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks = 30.
*APPEND gl_given_tracks TO gt_given_tracks.


*"And one more Example for the case, when starting the other direction is better :-)
*gl_given_tracks = 170.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks =  180.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks =  1020.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks = 90.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks = 80.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks = 30.
*APPEND gl_given_tracks TO gt_given_tracks.


*"And one last example if the simple Check is used because no track is long enough, so that a turnaround does not
*"make any sense
*"And one more Example for the case, when starting the other direction is better :-)
*gl_given_tracks = 170.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks =  180.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks = 90.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks = 80.
*APPEND gl_given_tracks TO gt_given_tracks.
*gl_given_tracks = 30.
*APPEND gl_given_tracks TO gt_given_tracks.

"checks if there is one track, longer than all the others together
PERFORM checkwaychangingtrack CHANGING g_waychanging_track.


IF g_waychanging_track EQ 'X'. " if a track should be avoided use this algorithm

  PERFORM waychangingwaycheck.

ELSE. "another algorithm

  PERFORM simplewaycheck.

ENDIF.

" Print Result

LOOP AT gt_best_way INTO gl_best_way.

  WRITE: / 'Station: ', gl_best_way.
ENDLOOP.

*&---------------------------------------------------------------------*
*&      Form  CHECKWAYCHANGINGTRACK
*&---------------------------------------------------------------------*
*       Checks if here is one track, longer than all the others together
*----------------------------------------------------------------------*
*      -->P_G_WAYCHANGING_TRACK
*----------------------------------------------------------------------*
FORM checkwaychangingtrack CHANGING p_g_waychanging_track.

  DATA: lt_temp_given_tracks LIKE gt_given_tracks,
        ll_temp_given_tracks LIKE LINE OF lt_temp_given_tracks.

  DATA: l_tracksum TYPE i,
        l_max TYPE i.

  MOVE gt_given_tracks TO lt_temp_given_tracks. " copy table temporary for next operations

  SORT lt_temp_given_tracks DESCENDING. "sort temp-table descending

  READ TABLE lt_temp_given_tracks INDEX 1 INTO l_max. "now select maximum value wich is the first becaus of sorting

  " now get sum of the other tracks without this one

  LOOP AT lt_temp_given_tracks INTO ll_temp_given_tracks.
    l_tracksum = ll_temp_given_tracks + l_tracksum.
  ENDLOOP.

  l_tracksum = l_tracksum - l_max.

  " return result

  IF l_max > l_tracksum.
    p_g_waychanging_track = 'X'.
  ELSE.
    p_g_waychanging_track = ' '.
  ENDIF.


ENDFORM.                    " CHECKWAYCHANGINGTRACK



*&---------------------------------------------------------------------*
*&      Form  SIMPLEWAYCHECK
*&---------------------------------------------------------------------*
*       just evaluate if driving the one direction OR the other is better
*----------------------------------------------------------------------*
*  -->  p1        text
*  <--  p2        text
*----------------------------------------------------------------------*
FORM simplewaycheck.

  DATA: l_n TYPE i,
        l_x TYPE i,
        l_forwardsum TYPE i,
        l_reversesum TYPE i.

DATA: l_numb_o_lines TYPE I.

DESCRIBE TABLE gt_given_tracks LINES l_numb_o_lines.

  l_n = l_numb_o_lines.

  WHILE l_n > 0.
    READ TABLE gt_given_tracks INDEX l_n INTO gl_given_tracks.

    l_forwardsum = l_forwardsum + gl_given_tracks.
    l_n = l_n - 1.
  ENDWHILE.


  WHILE l_n < l_numb_o_lines.
    READ TABLE gt_given_tracks INDEX l_n INTO gl_given_tracks.

    l_reversesum = l_reversesum + gl_given_tracks.
    l_n = l_n + 1.
  ENDWHILE.

  IF l_forwardsum <= l_reversesum.

    DO l_n TIMES.
      APPEND sy-index TO gt_best_way.
    ENDDO.

  ELSE.
    l_x = l_n.

    DO l_n TIMES.

      APPEND l_x TO gt_best_way.
      l_x = l_x - 1.

    ENDDO.

  ENDIF.

ENDFORM.                    " SIMPLEWAYCHECK




*&---------------------------------------------------------------------*
*&      Form  WAYCHANGINGWAYCHECK
*&---------------------------------------------------------------------*
*       text
*----------------------------------------------------------------------*
*  -->  p1        text
*  <--  p2        text
*----------------------------------------------------------------------*
FORM waychangingwaycheck .

  DATA: l_count1 TYPE i,
        l_count2 TYPE i,
        l_numb_o_lines,
        l_index_o_max.

  DATA: l_forwardsum TYPE i,
        l_reversesum TYPE i,
        l_max TYPE i.

  DATA: lt_temp_given_tracks LIKE gt_given_tracks,
        ll_temp_given_tracks LIKE LINE OF lt_temp_given_tracks.



  MOVE gt_given_tracks TO lt_temp_given_tracks. " copy table temporary for next operations

  SORT lt_temp_given_tracks DESCENDING. "sort temp-table descending

  READ TABLE lt_temp_given_tracks INDEX 1 INTO l_max. "now select maximum value wich is the first becaus of sorting

  DESCRIBE TABLE gt_given_tracks LINES l_numb_o_lines.

  "_____________TRY FORWARD WAY _____________________________


  LOOP AT gt_given_tracks INTO gl_given_tracks.

    IF gl_given_tracks NE l_max. " summarize all tracks except for the track which should be avoided
      l_forwardsum = l_forwardsum + gl_given_tracks.
    ENDIF.
  ENDLOOP.


  " Add the tracks which are frequented 2 Times, once more

  "check which line is the one with the track to avoid.
  READ TABLE gt_given_tracks WITH TABLE KEY table_line = l_max INTO gl_given_tracks.
  l_index_o_max = sy-tabix.



  l_count1 = l_index_o_max - 1.
  "until this line, the tracklengths should be added once more
  DO l_count1 TIMES.
    READ TABLE gt_given_tracks INDEX sy-index INTO gl_given_tracks.
    l_forwardsum = l_forwardsum + gl_given_tracks.
  ENDDO.

  "_____________TRY REVERSE WAY _____________________________

  LOOP AT gt_given_tracks INTO gl_given_tracks.

    IF gl_given_tracks NE l_max. " summarize all tracks except for the track which should be avoided
      l_reversesum = l_reversesum + gl_given_tracks.
    ENDIF.
  ENDLOOP.

  " Add the tracks which are frequented 2 Times, once more

  "In this case every track after the line which should be avoided must be read one more time

  l_count1 = l_index_o_max + 1. " the line to start
  l_count2 = l_numb_o_lines - l_index_o_max. "amount of remaining lines to loop over

  DO l_count2 TIMES.

    READ TABLE gt_given_tracks INDEX l_count1 INTO gl_given_tracks.
    l_reversesum = l_reversesum + gl_given_tracks.
    l_count1 = l_count1 + 1.
  ENDDO.



  " CHECK IF the Forward or the Reverse Way is better and write result into gt_best_way ! :-)

  CLEAR l_count1.
  CLEAR l_count2.

"IT Starts on Station 1 anyway
    gl_best_way = 1.
    APPEND gl_best_way TO gt_best_way.

  IF l_forwardsum <= l_reversesum.

    
    l_count1 = l_index_o_max - 1.
    l_count2 = 2.

    DO l_count1 TIMES.
      gl_best_way = l_count2.

      APPEND gl_best_way TO gt_best_way.

      l_count2 = l_count2 + 1.

    ENDDO.

    l_count1 = l_count1. "backwards its just one step less
    l_count2 = l_count1.

    DO l_count1 TIMES.

      gl_best_way = l_count2.

      APPEND gl_best_way TO gt_best_way.

      l_count2 = l_count2 - 1.
    ENDDO.

    l_count1 = l_numb_o_lines.
    l_count2 = l_numb_o_lines - l_index_o_max.

    DO l_count2 TIMES.

      gl_best_way = l_count1.

      APPEND gl_best_way TO gt_best_way.

      l_count1 = l_count1 - 1.

    ENDDO.

  ELSE. " if reverse is better

    l_count1 = l_numb_o_lines - l_index_o_max.
    l_count2 = l_numb_o_lines.

    DO l_count1 TIMES.

      gl_best_way = l_count2.

      APPEND gl_best_way TO gt_best_way.

      l_count2 = l_count2 - 1.
      
    ENDDO.


    l_count1 = l_numb_o_lines - l_index_o_max.
    l_count1 = l_count1 - 1.
    l_count2 = l_index_o_max + 2.

    DO l_count1 TIMES.

      gl_best_way = l_count2.

      APPEND gl_best_way TO gt_best_way.

      l_count2 = l_count2 + 1.
    ENDDO.

    l_count1 = l_index_o_max.
    l_count2 = 1.

    DO l_count1 TIMES.

      gl_best_way = l_count2.

      APPEND gl_best_way TO gt_best_way.

      l_count2 = l_count2 + 1.

    ENDDO.

  ENDIF.


ENDFORM.                    " WAYCHANGINGWAYCHECK
                

Lösung von: Benjamin Kluszynski (( Coder :-) ))

// Autor:				Andy Großhennig
// Solution for task:	Eisenbahn optimieren (Simulationen)

#include <iostream>

using namespace std;

void calculateRoutes(short shClosedRoute, int i_arrLength[5])
{		
							//	AB	BC	CD	  DE	EA
	const int i_arrRoutes[5] = {70, 80, 1020, 190, 180}; //Routes
					//	  A		B		C		D	  E
	bool bStations[5] = {true, false, false, false, false}; //Stations
	short shRoute = 0; //Current route
	bool bForward = true; //Direction
	
	// Loop: Drive forward until the route is closed
	while(shRoute != shClosedRoute && bForward == true && (bStations[0] == false || bStations[1] == false || bStations[2] == false || bStations[3] == false || bStations[4] == false))
	{
		i_arrLength[shClosedRoute] += i_arrRoutes[shRoute];

		// If: Reach station
		if(shRoute + 1 != 5)
			bStations[shRoute + 1] = true;
		else
			bStations[0] = true;

		// If: Next route
		if(shRoute < 4)
			shRoute++;
		else
			shRoute = 0;
	}

	bForward = false; //Change direction

	// Loop: Drive reverse until the train has reached all stations
	while(bStations[0] == false || bStations[1] == false || bStations[2] == false || bStations[3] == false || bStations[4] == false)
	{
		if(shRoute - 1 >= 0)
			bStations[shRoute - 1] = true;
		else
			bStations[4] = true;

		if(shRoute > 0)
			shRoute--;
		else
			shRoute = 4;

		i_arrLength[shClosedRoute] += i_arrRoutes[shRoute];
	}
}

int main()
{
	int i_arrLength[5] = {0, 0, 0, 0, 0}; //Length of the total route when one route is closed

	for(short shClosedRoute = 0;shClosedRoute < 5;shClosedRoute++)
		calculateRoutes(shClosedRoute, i_arrLength);

	printf("Laenge bei Sperrung Strecke AB: %i\nLaenge bei Sperrung Strecke BC: %i\nLaenge bei Sperrung Strecke CD: %i\nLaenge bei Sperrung Strecke DE: %i\nLaenge bei Sperrung Strecke EA: %i\n", 
	i_arrLength[0], i_arrLength[1], i_arrLength[2], i_arrLength[3], i_arrLength[4]);
	
	printf("\n\n");
	system("Pause");
	return 0;
}
                

Lösung von: Andy Großhennig (Bundeswehr)

Verifikation/Checksumme:

Eingabe: 70, 80, 1020, 190, 180

Ausgabe: AB, BC, CB, BA, AE, ED: Total 670 km

 

Eingabe: 9, 6, 7

Ausgabe: AC, CB: Total 13 km

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit:
Schwierigkeit: k.A.
Webcode: p2c4-zk4c
Autor: Philipp Gressly Freimann (SANTIS Training AG)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen