Es ist über 10 Jahre her, seit ich die Mathematikabteilung abgeschlossen habe Im Gespräch mit einem alten Freund, der sich für das Programmieren interessierte Um ehrlich zu sein, sind Mathematikkenntnisse der High School für die Programmierung nützlich? Da es ein Thema wurde, werde ich die damals eingeführten Tipps aufschreiben.
Wir werden das Thema der rudimentären Wettbewerbsprogrammierung als Thema aufgreifen. AtCoder Dies ist die erste Frage von Anfängerwettbewerb26.
Der Inhalt ist wie folgt.
Problemstellung
Eine positive gerade Zahl A wird gegeben.
x+y=Positive ganze Zahl x, die A ist,Wählen Sie die mit dem Maximum x × y unter y aus und geben Sie den Wert aus.
Eingang
Die Eingabe erfolgt über die Standardeingabe im folgenden Format.
A
In der ersten Zeile ein positives sogar A.(2≦A≦100)Ist gegeben.
Ausgabe
Geben Sie den Maximalwert von x × y aus. Fügen Sie am Ende der Ausgabe einen Zeilenumbruch ein.
Eingabebeispiel 1
10
Ausgabebeispiel 1
25
x=5, y=Wenn 5, x × y=Es wird 25, was der Maximalwert ist.
Selbst wenn Sie ein erfahrener Programmierer sind, können sich diejenigen, die nicht an wettbewerbsfähiges Programmieren gewöhnt sind (ich denke, das ist ganz normal), fertig machen, aber die Grundlage für wettbewerbsfähiges Programmieren besteht darin, darüber nachzudenken, wie eine vollständige Suche durchgeführt werden kann, ohne schwierig zu denken. Die Leistung, die für wettbewerbsfähiges Programmieren und Üben erforderlich ist, unterscheidet sich häufig im Umfang. Auch wenn Sie dies nicht können, sollten Sie nicht eindellen. Haruki Murakami: Es ist wie: "Es gibt keine perfekte Programmierung. Habe keine perfekte Verzweiflung."
Kommen wir zurück zur Geschichte. Geschrieben in Java. (Bestätigt, mit AtCoder AC zu sein)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int max = 0;
for ( int x = 1; x < n; x++) {
if ( x * (n -x) > max) {
max = x * (n-x);
}
}
System.out.println(max);
return;
}
}
Es ist eine Methode, ehrlich eins nach dem anderen zu untersuchen.
Die Antwort wird korrekt sein und die Punktzahl wird kommen, aber unter dem Gesichtspunkt des Rechenaufwands ist es O (n). Mit anderen Worten, wenn die Eingabegröße n zunimmt, nimmt die Ausführungszeit proportional zu n zu.
In der Tat, wenn Sie dieses Problem kennen ** additive synergistische Durchschnittsformel **, können Sie es O (1) machen. Wenn der Eingabewert immer eine gerade Zahl ist, ist x = y = n / 2 immer die Antwort. Wenn Sie sich die Problemstellung genau ansehen Es heißt: "Eine positive gerade Zahl A ist gegeben."
Es wird wie folgt sein.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(n/2 * n/2);
return;
}
}
Natürlich können Sie immer noch AC bekommen (richtige Antwort). Darüber hinaus beträgt in diesem Fall der Berechnungsbetrag O (1), dh die Ausführungszeit erhöht sich unabhängig von der Anzahl von n nicht proportional. Ist es hier in Bezug auf eine Modellantwort? Es sollte nicht viele Programme geben, denen die Ausführungszeit egal ist, daher ist es aus praktischer Sicht eine interessante Geschichte.
In der Tat beim Programmieren bei der Arbeit oder als Hobby Man kann sagen, dass wenig Fachwissen in Mathematik erforderlich ist. (Ansonsten ist es schwierig zu mieten)
Mathematik ist jedoch in der heutigen Zeit eine praktische Wissenschaft, und es ist oft von Vorteil zu wissen, dass Sie sich in der IT-Gesellschaft befinden. Es ist eine Geschichte.
Recommended Posts