Informatik 10

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Aufgabe "Martkwaage" des 40. Bundeswettbewerbs Informatik ======
  * [[https://bwinf.de/bundeswettbewerb/40/1/|Das Aufgabenblatt findest Du hier zum Download.]]
  * {{ :bwinf:bwinf40:bwinf40-runde1-beispieldaten.zip |Hier eine Zipdatei mit allen Beispieldaten}}


<HTML>
<div class="java-online" style="height: 70vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'bwInfMarktwaage'}">

<script type="text/plain" title="Main Program.java">
new Hauptprogramm("gewichtsstücke0.txt").start();




class Hauptprogramm {

   Data data;

   boolean[] istMessbar;   // istMessbar[i] == true <=> i * 10g messbar sind


   Hauptprogramm(String filename) {
      data = new Data(filename);

      istMessbar = new boolean[1001];  // anfangs mit [false, false, false, ... ] belegt.

   }


   void start() {
      legeHinzu(0, 0);
      ausgabe(); 
   }



   void legeHinzu(int indexNächstesGewicht, int bisherigesGesamtgewicht) {

      int anzahlAktuellesGewicht = data.anzahlListe[indexNächstesGewicht];

      for (int i = -anzahlAktuellesGewicht; i <= anzahlAktuellesGewicht; i++) {

         int neuesGesamtgewicht = bisherigesGesamtgewicht + i * data.gewichte[indexNächstesGewicht];

         if(neuesGesamtgewicht > 0 && neuesGesamtgewicht <= 10000 && neuesGesamtgewicht % 10 == 0) {
            istMessbar[neuesGesamtgewicht / 10] = true;
         }

         // Abbruchbedingung für die Rekursion
         if(indexNächstesGewicht < data.anzahl - 1) {
            legeHinzu(indexNächstesGewicht + 1, neuesGesamtgewicht); 
         }

      }

   }

   void ausgabe() {

      int count = 0;

      for (int i = 0; i <= 1000; i++) {
         
         if(istMessbar[i]) {
            println(i * 10 + " g");
            count++;
         }
         
      }

      println(count + " Gewichte im Bereich 10 g bis 10000 g sind mit dem vorgegebenen Gewichtssatz erreichbar.");
   }


}
</script>

<script type="text/plain" title="Data.java">
class Data {
   
   int anzahl;
   int[] gewichte;
   int[] anzahlListe;

   Data(String filename) {
      String[] lines = Files.read(filename).split("\n");
      anzahl = Integer.parseInt(lines[0]);
      gewichte = new int[anzahl];
      anzahlListe = new int[anzahl];

      for (int i = 0; i < anzahl; i++) {
         String line = lines[i + 1];
         String[] zahlen = line.split(" ");
         gewichte[i] = Integer.parseInt(zahlen[0]);
         anzahlListe[i] = Integer.parseInt(zahlen[1]);
      } 

   }
}
</script>

<script type="text/plain" title="gewichtsstücke0.txt">
6
10 3
50 2
100 3
500 3
1000 3
5000 1
</script>

<script type="text/plain" title="gewichtsstücke1.txt">
4
42 3
127 3
371 6
2000 5
</script>

<script type="text/plain" title="gewichtsstücke2.txt">
10
10 1
20 1
40 1
80 1
160 1
320 1
640 1
1280 1
2560 1
5120 1
</script>

<script type="text/plain" title="gewichtsstücke3.txt">
7
10 1
30 1
90 1
270 1
810 1
2430 1
7290 1
</script>

<script type="text/plain" title="gewichtsstücke4.txt">
7
5 1
21 3
29 3
259 1
287 1
399 1
2993 3
</script>

<script type="text/plain" title="gewichtsstücke5.txt">
13
11 1
99480 1
99511 1
299836 2
599761 1
4497786 3
1499171 1
10499654 4
41999427 1
94499810 3
283501867 1
661499326 3
1984505261 1
</script>
<script type="text/plain" title="Beschreibung des Dateiformats.txt">
Jede Datei beschreibt einen Satz von Gewichtsstücken und enthält

  * in der ersten Zeile die Anzahl n der vorkommenden verschiedenen Gewichte mit
    verschiedenem Gewicht
  * in den weiteren m Zeilen jeweils zwei Zahlen:
    * das Gewicht w der jeweiligen Gewichtsstücke in Gramm und
    * die Anzahl n_w der Gewichtsstücke mit diesem Gewicht.

</script>
</div>

</HTML>