Schreiben Sie eine einfache Giermethode in Python

Gierige Methode

Die gierige Methode ist eine Methode, bei der ein bestimmter Standard festgelegt wird und die optimale Lösung kontinuierlich vor Ort ausgewählt wird, um die optimale Lösung zu finden. Ich denke, es ist effektiv, wenn man in kurzer Zeit zu einem gewissen Grad die optimale Lösung findet. Da die Giermethode selbst im weitesten Sinne angewendet wird, ist es in solchen Fällen schwierig, sie persönlich anzuwenden

Ich denke, es kann jederzeit verwendet werden.

Dieses Problem

AtCoders B - Magic 2 wird mit der gierigen Methode gelöst.

** Problemstellung ** Herr M hat die folgenden drei Karten.

Da er ein genialer Magier ist, kann er die folgenden Operationen bis zu K-mal ausführen.

--Wählen Sie eine der drei Karten und verdoppeln Sie die geschriebene Ganzzahl.

Wenn nach dem Ausführen der Operation die folgenden Bedingungen gleichzeitig erfüllt sind, ist die Magie erfolgreich.

Bestimmen Sie, ob Sie in der Magie erfolgreich sein können.

** Einschränkungen **

Kurz gesagt, es wird davon ausgegangen, dass Sie innerhalb von K-mal "Rot <Grün" und "Grün <Blau" erreichen sollten. In diesem Problem kann die Bedingung erfüllt sein, wenn "die Häufigkeit, mit der Grün auf Rot verdoppelt wird" + "die Häufigkeit, mit der Blau auf Grün verdoppelt wird" kleiner oder gleich K ist.

Wenn Sie früher "einen Wert reparieren" sagen, ist dieses Problem

--Fixieren Sie den roten Wert zum Vergleich

Ich denke, es wird einfacher zu lösen sein.

Deine Antwort

B-Magic2.py


nums = input().split() #A,B,Geben Sie C ein

A = int(nums[0])
B = int(nums[1])
C = int(nums[2])

K = input() #Geben Sie K ein
k = int(K)

cnt = 0 #Wenn die Anzahl kleiner als k ist, ist Magie erfolgreich. Definieren Sie daher zum Vergleich eine Ganzzahl cnt

while A >= B: #Notieren Sie, wie oft B verdoppelt wird und zu A oder mehr wird
    cnt += 1
    B *= 2

while B >= C:  #Notieren Sie, wie oft C verdoppelt wird und zu B oder mehr wird
    cnt += 1
    C *= 2


if cnt <= k:
    print("Yes")
else:
    print("No")


7 4 2    #A,B,C Eingang
3        #K Eingang
No       #Ausgabe

Am Ende (Notizen schreiben)

Wenn es mit AtCoder zu einem schwierigen Problem wird, kann ich die Antwort nicht erreichen, selbst wenn ich die Bedingungen des Problems so übertrage, wie es ist. Daher dachte ich, dass sowohl die Lesefähigkeit als auch die mathematische Denkfähigkeit des Problems notwendig sind. Es fühlt sich an, als hätte ich Japanisch bis zur High School ignoriert. Oh, ich möchte Lesefähigkeit ...

Referenzartikel

https://studyhacker.net/reading-comprehension

https://www.naganomathblog.com/entry/2018/08/21/071918

Recommended Posts

Schreiben Sie eine einfache Giermethode in Python
Schreiben Sie A * (A-Stern) -Algorithmen in Python
Implementierung eines einfachen Algorithmus in Python 2
Führen Sie einen einfachen Algorithmus in Python aus
Schreiben Sie ein einfaches Vim-Plugin in Python 3
Schreiben Sie ein super einfaches molekulardynamisches Programm in Python
Schreiben Sie eine Dichotomie in Python
Schreiben Sie ein Kreisdiagramm in Python
Schreiben Sie das Vim-Plugin in Python
Schreiben Sie eine Suche mit Tiefenpriorität in Python
Es ist schwer, einen sehr einfachen Algorithmus in PHP zu schreiben
Ein einfacher HTTP-Client, der in Python implementiert ist
Schreiben Sie den Test in die Python-Dokumentzeichenfolge
Versuchen Sie, eine einfache Animation in Python zu zeichnen
Schreiben Sie eine kurze Eigenschaftsdefinition in Python
Schreiben Sie ein Caesar-Verschlüsselungsprogramm in Python
Ein * Algorithmus (Python Edition)
Einfacher gRPC in Python
Genetischer Algorithmus in Python
Schreiben Sie Python in MySQL
Algorithmus in Python (Bellman-Ford-Methode, Bellman-Ford)
Algorithmus in Python (Dijkstra)
Richten Sie mit Python 3 einen einfachen HTTPS-Server ein
Einfache Pub / Sub-Programmhinweise in Python
Erstellen Sie in Python ein einfaches Momentum-Investmentmodell
Richten Sie einen einfachen SMTP-Server in Python ein
Machen Sie einen Screenshot in Python
Grundlegende Informationen Schreiben Sie das Problem mit dem Herbst 2018-Algorithmus in Python
Schreiben Sie Pandec-Filter in Python
Erstellen Sie eine Funktion in Python
Erstellen Sie ein Wörterbuch in Python
Schreiben Sie die Beta-Distribution in Python
Algorithmus in Python (Haupturteil)
Schreiben Sie Python in Rstudio (reticulate)
Ich möchte in Python schreiben! (2) Schreiben wir einen Test
Erstellen Sie einen einfachen Slackbot mit einer interaktiven Schaltfläche in Python
Reproduzieren Sie die euklidische Methode der gegenseitigen Teilung in Python
Algorithmus in Python (Dichotomie)
Erstellen Sie ein Lesezeichen in Python
Schreiben Sie in Python ein logarithmisches Histogramm auf die x-Achse
Einfache Regressionsanalyse mit Python
2. Multivariate Analyse in Python 1-2. Einfache Regressionsanalyse (Algorithmus)
Implementieren Sie den Dijkstra-Algorithmus in Python
Zeichne ein Herz in Python
Einfacher IRC-Client mit Python
Ich habe ein einfaches Tippspiel mit tkinter of Python gemacht
Eine einfache Möglichkeit, mehrere for-Schleifen in Python zu vermeiden
Algorithmus in Python (Breitenprioritätssuche, bfs)
Wahrscheinlich in einer Nishiki-Schlange (Originaltitel: Vielleicht in Python)
[Python] Verwalten Sie Funktionen in einer Liste
Erste einfache Regressionsanalyse in Python
Drücken Sie einen Befehl in Python (Windows)
Einfaches OAuth 2 mit Python (urllib + oauthlib)
Sortieralgorithmus und Implementierung in Python
Erstellen Sie einen DI-Container mit Python
Zeichnen Sie eine Streudiagrammmatrix mit Python
Schreiben Sie die AWS Lambda-Funktion in Python
ABC166 in Python A ~ C Problem
Lassen Sie uns mit Python 2 einen Investitionsalgorithmus entwickeln
Erstellen Sie eine Binärdatei in Python