Introduction aux algorithmes avec java-Search (recherche complète, recherche de bisection)
Aperçu
Ceci est un résumé du mot «recherche complète» qui apparaît souvent lors de la résolution de programmes concurrentiels. C'est juste mon propre mémo, mais j'espère que cela aide. Désormais, nous ajouterons la méthode de planification dynamique et la méthode dixtra à l'introduction des algorithmes. Un cycle vertueux dans lequel le taux d'AtCoder augmente à mesure que vous écrivez des exemples de code. Fondamentalement, il ne s'agit que d'une compilation des connaissances acquises sur le net et sur Qiita.
J'utilise java, auquel j'ai l'habitude, mais tout va bien.
Qu'est-ce qu'une recherche complète?
Comme vous pouvez le voir d'après le nom, je pense que penser à "toutes les possibilités possibles" est une recherche complète. Il semble qu'il existe différents types, alors examinons les problèmes et les exemples de code pour chaque type. Les types de recherche complète sont les suivants.
- Recherche complète --Dichotomie (également appelée recherche binaire)
- Recherche de priorité en profondeur (également avec DFS) --Width priorité recherche (également avec BFS) --bits recherche complète
Pour le moment, il semble bon de savoir cela. Jetons un coup d'œil à chacun d'eux avec un exemple.
Description de l'algorithme de recherche et exemple de code
Je vais expliquer chacun d'eux.
Recherche complète
Recherchez toutes les réponses possibles en imbriquant des déclarations. C'est facile. Regardons un exemple. Nous essaierons de résoudre un problème aussi simple que possible. C'est plus facile à comprendre et parce que je ne peux pas le résoudre à moins que ce soit facile.
Exemple: AtCoder --abc144-b "81"
[Phrase problématique](C'est un peu plus facile à écrire.) Puisque l'entier N est donné, jugez si N peut être représenté par le produit d'entiers entre 1 et 9, et affichez "Oui" s'il peut être représenté, et "Non" s'il ne peut pas être représenté.
[Restrictions] 1 ≤ N ≤ 100, N est un entier
[Exemple de réponse]
main.java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
//Indique si N remplit la condition
boolean flg = false;
// i * j =I qui devient N,Rechercher tout pour j
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
if (i * j == N) {
flg = true;
break;
}
}
if (flg) {
break;
}
}
if (flg) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
C'est comme ça. L'instruction for est doublement imbriquée pour rechercher tous les quatre-vingt-dix-neuf modèles.
La mise en garde de la recherche complète est que ** la quantité de calcul est importante **. Cette fois, c'était quatre-vingt-dix-neuf, donc dans le pire des cas, ce n'était que 9 ^ 2 = 81 boucles, mais si on vous disait, par exemple, le produit des multiplications jusqu'à 10 ^ 5 au lieu de quatre-vingt-dix-neuf, 10 ^ 5 * Notez que le calcul de 10 ^ 5 = 10 ^ 10 prend beaucoup de temps.
Recherche de bisection
C'est une façon de répéter si les choses qui s'appliquent sont dans la première moitié ou la seconde moitié de tout le groupe. Par exemple, disons que M. A demande: "Quel est mon numéro préféré de 1 à 11?" Disons que M. A répond à cette question si elle est plus grande ou plus petite que le nombre que vous avez demandé, ou si c'est la réponse. À ce stade, s'il s'agit d'une simple recherche complète sans penser à rien, demandez "1?" "2?" ... dans l'ordre, et dans le pire des cas, 11 fois. J'ai besoin d'une question. En termes de montant de calcul, c'est O (N) fois.
Si vous faites cela avec une dichotomie, cela ressemble à ce qui suit. Disons que la réponse de M. A est 10.
Exemple de dichotomie
1:tu"(Entre 1 et 11)Est-ce 6? "Mr. A" Il est plus grand que 6. "
2:tu"(Entre 6 et 11)Est-ce 9? "Mr. A" Il est plus grand que 9. "
3:tu"(Entre 9 et 11)Est-ce 10? "Mr. A" C'est autour. "
Et, comme ça, vous avez trouvé la réponse en seulement trois questions.
En partant de la valeur très moyenne du groupe, chaque question détermine s'il y a une réponse dans la première moitié ou la seconde moitié du groupe.
La figure ci-dessous peut être utile.
La plage est divisée par deux pour chaque question, donc si vous n'avez que 11 candidats, vous constaterez que vous n'avez besoin que de 4 questions (2 ^ 4 = 16) au maximum. Est-ce O (logN) en termes de montant de calcul?
Passons à l'exemple.
Exemple: AtCoder --abc146-c "Buy an Integer"
Problème Takahashi est allé dans un magasin de nombres entiers pour acheter un entier.
Les entiers de 1 à 10 ^ 9 sont vendus dans les magasins d'entiers, et pour acheter l'entier N Un cercle × N + B × d (N) est requis. Où d (N) est le nombre de chiffres en notation décimale pour N. Lorsque l'argent de Takahashi-kun est de X yen, trouvez le plus grand entier que Takahashi-kun peut acheter. Cependant, s'il n'y a pas d'entiers que vous pouvez acheter, imprimez 0.
[Restrictions] Toutes les entrées sont des entiers. 1≤A≤10^9 1≤B≤10^9 1≤X≤10^18
[Exemple de réponse]
main.java
import java.util.Scanner;
public class Main {
static long A;
static long B;
static long X;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
A = sc.nextLong();
B = sc.nextLong();
X = sc.nextLong();
long max = 1000000000l + 1l;
long min = 0l;
//Recherche de bisection
for (;;) {
//2 Valeur moyenne des valeurs numériques
long mid = (max + min) / 2;
if (canSolve(mid)) {
//Si vous pouvez résoudre avec la valeur moyenne, recherchez dans la seconde moitié
min = mid;
} else {
//Si vous ne pouvez pas résoudre avec la valeur moyenne, recherchez dans la seconde moitié
max = mid;
}
if (max - min <= 1) {
//La recherche dichotomisée se termine
break;
}
}
System.out.println(min);
}
//Obtenez le nombre de chiffres
static long len(long num) {
return String.valueOf(num).length();
}
//S'il peut être résolu
static boolean canSolve(long num) {
return A * num + B * len(num) <= X ? true : false;
}
}
Bien sûr, si vous essayez de résoudre ce problème avec une simple recherche complète, vous devez penser à tous les N, et comme N est un entier compris entre 1 et 10 ^ 9, dans le pire des cas, il est traité 10 ^ 9 fois. Doit être. C'est pourquoi la dichotomie est là. Pouvez-vous le voir en regardant le code?
long max = 1000000000l + 1l;
C'est un endroit un peu difficile.
Si vous divisez java long, les fractions seront tronquées, donc si vous définissez max à 1 000 000 000,
Lorsque min: 999 999 999 et max: 1 000 000 000, mid devient 999 999 999 (= min) et il devient impossible de vérifier 1 000 000 000.
De plus, j'aime simplement la facilité de visualisation et la division des méthodes, donc je ne vais pas juger si je peux obtenir le nombre de chiffres ou l'acheter, mais l'un ou l'autre convient.
J'ai résolu ce problème avec une dichotomie, mais je pense que l'avantage est que la quantité de calcul est faible. Dans le pire des cas, vous pouvez atteindre la réponse en bouclant environ 30 fois. Parce que 2 ^ 30 est supérieur à 10 ^ 9.
Cependant, il semble préférable de garder à l'esprit que la dichotomie n'est utile que pour les «groupes triés». S'il s'agit d'un "entier consécutif", je pense qu'il peut être utilisé pour la dichotomie.
J'ai étudié et expliqué la recherche complète et la recherche dichotomisée, mais comment était-ce? Je pensais que je ferais le même article pour la recherche de priorité de profondeur, la recherche de priorité de largeur et la recherche de bits complète, mais plus tard, j'ai pensé qu'il serait difficile de regarder en arrière, alors j'ai décidé de publier les articles séparément. La prochaine fois, j'étudierai et expliquerai la recherche de priorité de profondeur et la recherche de priorité de largeur. impatient de.
Recommended Posts