Fragenbank: Algorithmen und Probleme: Mittel

Ein Geldautomat einer Bank muss so programmiert werden, dass er eine minimale Anzahl von Geldscheinen gemäß dem Betrag ausgibt, den der Kunde verlangt. Die Bank arbeitet mit Geldscheinen von 2 R$, 5 R$, 10 R$, 20 R$, 50 R$ und 100 R$. Der Programmierer des Geldautomaten hat sich entschieden, einen Algorithmus zur Teilung und Eroberung zu verwenden, um die minimale Anzahl erforderlicher Geldscheine für jeden Auszahlungsbetrag zu berechnen. Der Algorithmus beginnt damit, zu überprüfen, ob es möglich ist, den Betrag mit dem größten Geldschein zu erfüllen, andernfalls wird auf den zweithöchsten und so weiter gewechselt, bis der angeforderte Betrag erreicht oder festgestellt wird, dass es nicht möglich ist, die Geldscheine für den angeforderten Betrag bereitzustellen. Schreiben Sie ein Flussdiagramm für diesen Algorithmus und verwenden Sie es, um zu erklären, wie der Geldautomat die minimale Anzahl an Geldscheinen für eine Abhebung von 126 R$ berechnen würde. Erläutern Sie in jedem Schritt, welche Geldscheine verwendet werden und welcher Betrag verbleibt. Beschreiben Sie anschließend, wie sich der Algorithmus verhalten würde, wenn der Auszahlungsbetrag 147 R$ beträgt.

Aussage: João entwirft ein Sicherheitssystem, das die Erzeugung und Validierung von Zugangscodes umfasst. Er hat entschieden, dass zur Maximierung der Sicherheit die Zugangscodes einer komplexen mathematischen Regel folgen müssen. Die Regel ist wie folgt: Eine positive ganze Zahl N wird als gültig angesehen, wenn und nur wenn die Summe der Quadrate ihrer Ziffern eine perfekte Zahl ist. Eine Zahl gilt als perfekt, wenn die Summe ihrer eigenen Teiler (ohne sich selbst) gleich der Zahl selbst ist. Zum Beispiel hat die Zahl 3025 die folgende Summe der Quadrate ihrer Ziffern: 3^2 + 0^2 + 2^2 + 5^2 = 38, und die Zahl 38 hat die eigenen Teiler 1, 2 und 19, deren Summe 22 ergibt, was anders als 38 ist. Daher ist der Code 3025 nicht gültig. Wenn wir jedoch einen 4-stelligen Code erstellen wollen, sei die kleinste positive 4-stellige Zahl, die dieser Regel entspricht. Erstellen Sie außerdem ein Flussdiagramm, das die Schritte zur Validierung darstellt, ob eine bestimmte Zahl dieser Regel entspricht. Erklären Sie dann, wie Sie das Flussdiagramm verwenden würden, um zu überprüfen, ob die Zahl 1313 einen gültigen Code generiert.

Ein Programmierer entwickelt einen Algorithmus, um die Quadratwurzel einer positiven ganzen Zahl 'n' mit dem Bisektionsverfahren zu finden. Der Algorithmus funktioniert folgendermaßen: Zunächst wird ein Intervall [a, b] betrachtet, wobei a eine Schätzung der Quadratwurzel von 'n' ist und b eine Zahl ist, die größer als a ist, so dass b² größer als n ist. Bei jeder Iteration prüft der Algorithmus den Mittelpunkt 'm' des Intervalls und vergleicht 'm²' mit 'n'. Wenn 'm²' kleiner als 'n' ist, wird die Quadratwurzel auf 'm' und die Untergrenze des Intervalls auf 'm' festgelegt. Andernfalls wird die Quadratwurzel auf 'a' und die Obergrenze des Intervalls auf 'm' festgelegt. Der Algorithmus setzt diesen Prozess fort, bis die Differenz zwischen 'a' und 'b' kleiner als ein kleiner Toleranzwert 't' ist. Wenn man eine Zahl 'n' betrachtet, deren Quadratwurzel irrational ist, erkläre, warum das Bisektionsverfahren keine Genauigkeit des Ergebnisses garantiert und wie der Programmierer den Algorithmus anpassen könnte, um eine genauere Annäherung der Quadratwurzel von 'n' zu finden.

Betrachten Sie den folgenden Algorithmus zur Findung des größten Wertes in einem Array positiver Ganzzahlen: 1. Initialisieren Sie die Variable 'größter' mit dem ersten Element des Arrays. 2. Für jedes Element 'x' im Array, außer dem ersten: a) Wenn 'x' größer ist als 'größter', aktualisieren Sie 'größter', sodass er gleich 'x' wird. 3. Der Wert von 'größter' am Ende des Algorithmus ist das größte Element des Arrays. Stellen Sie sich nun vor, der Algorithmus wird in einem Array mit n Elementen ausgeführt. Basierend auf diesem Algorithmus beantworten Sie: (1) Erklären Sie, wie die Verwendung der Schleifenstruktur 'Für jedes Element' interpretiert und in einem Flussdiagramm implementiert werden könnte. (2) Demonstrieren Sie, dass die rechnerische Kosten dieses Algorithmus O(n) ist, indem Sie eine detaillierte Begründung liefern, einschließlich der Analyse der Anzahl von Ausführungen in Abhängigkeit von der Größe des Arrays.

Betrachten Sie ein Verfahren zur Bestimmung, ob eine positive ganze Zahl durch eine andere teilbar ist, basierend auf der Summe ihrer Ziffern. Zum Beispiel, wenn die Summe der Ziffern einer ganzen Zahl N durch 3 teilbar ist, dann ist N durch 3 teilbar. Wenn wir diese Regel analysieren und berücksichtigen, dass die Quadratwurzel einer ganzen Zahl n keine ganze Zahl ist, wie können wir einen Algorithmus erstellen, um festzustellen, ob die Zahl n eine perfekte Quadrat ist? Erklären Sie Ihre Überlegungen Schritt für Schritt und begründen Sie die Effektivität Ihres Algorithmus. Verwenden Sie gegebenenfalls numerische Beispiele, um den Prozess zu veranschaulichen.