Cela fait plus de 10 ans que je suis diplômé du département de mathématiques Lorsque vous parlez à un vieil ami qui a commencé à s'intéresser à la programmation Pour être honnête, les connaissances du niveau secondaire en mathématiques sont-elles utiles pour la programmation? Puisqu'il est devenu un sujet, j'écrirai les conseils présentés à ce moment-là.
Nous aborderons la question de la programmation compétitive rudimentaire comme sujet. AtCoder C'est la première question du concours débutant26.
Le contenu est le suivant.
Énoncé du problème
Un nombre pair positif A est donné.
x+y=Entier positif x qui est A,Sélectionnez celui avec le maximum x × y parmi y et sortez la valeur.
contribution
L'entrée est donnée à partir de l'entrée standard dans le format suivant.
A
Sur la première ligne, un positif même A(2≦A≦100)Est donnée.
production
Sortez la valeur maximale de x × y. Insérez un saut de ligne à la fin de la sortie.
Exemple d'entrée 1
10
Exemple de sortie 1
25
x=5, y=Lorsque 5, x × y=Il devient 25, qui est la valeur maximale.
Même si vous êtes un programmeur expérimenté, ceux qui ne sont pas habitués à la programmation compétitive (je pense que c'est tout à fait normal) peuvent se préparer, mais la base de la programmation compétitive est de réfléchir à la façon de faire une recherche complète sans réfléchir difficile. La puissance requise pour la programmation et la pratique compétitives est souvent de portée différente, donc même si vous ne pouvez pas le faire, ne vous en faites pas. Haruki Murakami: C'est comme: "Il n'y a pas de programmation parfaite. N'ayez pas de désespoir parfait."
Revenons à l'histoire. Écrit en Java. (Confirmé pour être AC avec AtCoder)
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;
}
}
C'est une méthode pour enquêter honnêtement un par un.
La réponse sera correcte et le score viendra, mais du point de vue de la quantité de calcul, c'est O (n). En d'autres termes, à mesure que la taille d'entrée n augmente, le temps d'exécution augmente proportionnellement à n.
En fait, si vous connaissez ce problème ** formule moyenne synergique additive **, vous pouvez le rendre O (1). Si la valeur d'entrée est toujours un nombre pair, alors x = y = n / 2 est toujours la réponse. Si vous regardez attentivement l'énoncé du problème Il dit: "Un nombre pair positif A est donné."
Ce sera comme suit.
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;
}
}
Bien sûr, vous pouvez toujours obtenir AC (bonne réponse). De plus, dans ce cas, la quantité de calcul est O (1), c'est-à-dire que le temps d'exécution n'augmente pas proportionnellement quel que soit le nombre de n. Est-ce ici en termes de réponse modèle? Il ne devrait pas y avoir beaucoup de programmes qui ne se soucient pas du temps d'exécution, c'est donc une histoire intéressante d'un point de vue pratique.
En fait, lors de la programmation au travail ou comme passe-temps On peut dire que peu de connaissances spécialisées en mathématiques sont requises. (Sinon, il est difficile de recruter)
Cependant, les mathématiques sont une science pratique des temps modernes, et il est souvent bénéfique de savoir que vous êtes dans la société informatique. C'est une histoire.
Recommended Posts