Einführung in Algorithmen mit Java-Suche (Vollsuche, Halbierungssuche)

Überblick

Dies ist eine Zusammenfassung des Wortes "vollständige Suche", das häufig bei der Lösung wettbewerbsfähiger Programme vorkommt. Es ist nur mein eigenes Memo, aber ich hoffe es hilft. Von nun an werden wir der Einführung von Algorithmen eine dynamische Planungsmethode und eine Dixtra-Methode hinzufügen. Ein tugendhafter Zyklus, in dem die AtCoder-Rate steigt, wenn Sie Codebeispiele schreiben. Im Grunde ist es nur eine Zusammenstellung des im Internet und in Qiita gewonnenen Wissens.

Die verwendete Sprache ist Java, an die ich gewöhnt bin, aber alles ist in Ordnung.

Was ist eine vollständige Suche?

Wie Sie dem Namen entnehmen können, denke ich, dass das Nachdenken über "alle möglichen Möglichkeiten" eine vollständige Suche ist. Es scheint, dass es verschiedene Typen gibt. Betrachten wir also Probleme und Codebeispiele für jeden Typ. Die Arten der vollständigen Suche sind wie folgt.

--Volle Suche --Dichotomie (auch als binäre Suche bekannt)

• Tiefe Prioritätssuche (auch mit DFS)
• Breite Prioritätssuche (auch mit BFS) --bit vollständige Suche

Vorerst scheint es gut zu sein, so viel zu wissen. Schauen wir uns jeden mit einem Beispiel an.

Beschreibung des Suchalgorithmus und Codebeispiel

Ich werde jeden erklären.

Volle Suche

Suchen Sie nach allen möglichen Antworten, indem Sie nach Anweisungen verschachteln. Es ist einfach. Schauen wir uns ein Beispiel an. Wir werden versuchen, ein Problem so einfach wie möglich zu lösen. Es ist leichter zu verstehen und weil ich es nicht lösen kann, wenn es nicht einfach ist.

Beispiel: AtCoder --abc144-b "81"

[Problemsatz](Es ist etwas einfacher zu schreiben.) Da die ganze Zahl N gegeben ist, beurteilen Sie, ob N durch das Produkt von ganzen Zahlen zwischen 1 und 9 dargestellt werden kann, und geben Sie "Ja" aus, wenn es dargestellt werden kann, und "Nein", wenn es nicht dargestellt werden kann.

[Beschränkungen] 1 ≤ N ≤ 100, N ist eine ganze Zahl

[Antwortbeispiel]

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();

		//Markieren Sie, ob N die Bedingung erfüllt
		boolean flg = false;

		// i * j =Ich das wird N.,Suche alle nach 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");
		}
	}
}

Es ist so. Die for-Anweisung ist doppelt verschachtelt, um alle neunundneunzig Muster zu durchsuchen.

Die Einschränkung der vollständigen Suche ist, dass ** der Rechenaufwand groß ist **. Diesmal war es neunundneunzig, im schlimmsten Fall also nur 9 ^ 2 = 81 Schleifen, aber wenn man Ihnen zum Beispiel das Produkt von Multiplikationen bis zu 10 ^ 5 statt neunundneunzig, 10 ^ 5 * sagte Beachten Sie, dass die Berechnung von 10 ^ 5 = 10 ^ 10 viel Zeit in Anspruch nimmt.

Halbierungssuche

Auf diese Weise kann wiederholt werden, ob sich die zutreffenden Dinge in der ersten oder in der zweiten Hälfte der gesamten Gruppe befinden. Nehmen wir zum Beispiel an, Herr A fragt: "Was ist meine Lieblingsnummer von 1 bis 11?" Angenommen, Herr A beantwortet diese Frage, ob sie größer oder kleiner als die von Ihnen gestellte Zahl ist oder ob es sich um die Antwort handelt. Wenn es sich zu diesem Zeitpunkt um eine einfache vollständige Suche handelt, ohne an irgendetwas zu denken, fragen Sie "1?" "2?" ... in der richtigen Reihenfolge und im schlimmsten Fall 11 Mal. Ich brauche eine Frage. In Bezug auf den Berechnungsbetrag ist es O (N) mal.

Wenn Sie dies mit einer Dichotomie tun, sieht es wie folgt aus. Angenommen, die Antwort von Herrn A lautet 10.

Beispiel für Dichotomie

1:Sie"(Zwischen 1 und 11)Ist es 6? "Mr. A" Es ist größer als 6. "
2:Sie"(Zwischen 6 und 11)Ist es 9? "Mr. A" Es ist größer als 9. "
3:Sie"(Zwischen 9 und 11)Ist es 10? "Mr. A" Es ist da. "

Und so haben Sie die Antwort in nur drei Fragen gefunden. Ausgehend vom mittleren Wert der Gruppe bestimmt jede Frage, ob es in der ersten oder zweiten Hälfte der Gruppe eine Antwort gibt. Die folgende Abbildung kann hilfreich sein. Der Bereich wird für jede Frage halbiert. Wenn Sie also nur 11 Kandidaten haben, werden Sie feststellen, dass Sie höchstens 4 Fragen (2 ^ 4 = 16) benötigen. Ist es O (logN) in Bezug auf den Berechnungsbetrag? Gehen wir zum Beispiel.

Beispiel: AtCoder --abc146-c "Buy a Integer"

Problem Takahashi ging zu einem Integer-Laden, um eine Integer zu kaufen.

Ganzzahlen von 1 bis 10 ^ 9 werden in Integer-Stores verkauft, um Integer N zu kaufen Ein Kreis × N + B × d (N) ist erforderlich. Wobei d (N) die Anzahl der Stellen in Dezimalschreibweise für N ist. Wenn Takahashi-kuns Geld X Yen beträgt, finden Sie die größte Ganzzahl, die Takahashi-kun kaufen kann. Wenn Sie jedoch keine Ganzzahlen kaufen können, geben Sie 0 aus.

[Beschränkungen] Alle Eingaben sind ganze Zahlen. 1≤A≤10^9 1≤B≤10^9 1≤X≤10^18

[Antwortbeispiel]

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;

		//Halbierungssuche
		for (;;) {
			//2 Durchschnittswert der Zahlenwerte
			long mid = (max + min) / 2;
			if (canSolve(mid)) {
				//Wenn Sie mit dem Durchschnittswert lösen können, suchen Sie in der zweiten Hälfte
				min = mid;
			} else {
				//Wenn Sie nicht mit dem Durchschnittswert lösen können, suchen Sie in der zweiten Hälfte
				max = mid;
			}

			if (max - min <= 1) {
				//Die dichotomisierte Suche endet
				break;
			}
		}

		System.out.println(min);

	}

	//Holen Sie sich die Anzahl der Ziffern
	static long len(long num) {
		return String.valueOf(num).length();
	}

	//Ob es gelöst werden kann
	static boolean canSolve(long num) {
		return A * num + B * len(num) <= X ? true : false;
	}
}

Wenn Sie versuchen, dieses Problem mit einer einfachen vollständigen Suche zu lösen, müssen Sie natürlich an alle N denken, und da N eine ganze Zahl zwischen 1 und 10 ^ 9 ist, wird es im schlimmsten Fall 10 ^ 9 Mal verarbeitet. Muss sein. Deshalb ist die Dichotomie hier. Können Sie es sehen, indem Sie sich den Code ansehen?

long max = 1000000000l + 1l; Dies ist ein etwas schwieriger Ort. Wenn Sie Java lang teilen, werden Brüche abgeschnitten. Wenn Sie also maximal 1.000.000.000 festlegen, Wenn min: 999.999.999 und max: 1.000.000.000, wird mid zu 999.999.999 (= min), und es wird unmöglich, 1.000.000.000 zu überprüfen.

Außerdem gefällt mir einfach die einfache Anzeige und die Aufteilung der Methoden, sodass ich nicht beurteilen kann, ob ich die Anzahl der Ziffern ermitteln oder kaufen kann, aber beide sind in Ordnung.

Ich habe dieses Problem mit einer Dichotomie gelöst, aber ich denke, der Vorteil ist, dass der Rechenaufwand gering ist. Im schlimmsten Fall dieses Problems können Sie die Antwort erreichen, indem Sie etwa 30 Mal eine Schleife durchführen. Weil 2 ^ 30 größer als 10 ^ 9 ist.

Es scheint jedoch besser zu bedenken, dass die Dichotomie nur für "sortierte Gruppen" nützlich ist. Wenn es sich um eine "aufeinanderfolgende Ganzzahl" handelt, kann sie meiner Meinung nach für die Halbierungssuche verwendet werden.

Ich habe die vollständige Suche und die dichotomisierte Suche studiert und erklärt, aber wie war es? Ich dachte, ich würde den gleichen Artikel für die Suche nach Tiefenpriorität, die Suche nach Breitenpriorität und die vollständige Suche nach Bit ausführen, aber später dachte ich, es wäre schwierig, zurückzublicken, und beschloss, die Artikel separat zu veröffentlichen. Das nächste Mal werde ich die Suche nach Tiefenprioritäten und die Suche nach Breitenprioritäten studieren und erklären. Ich freue mich darauf.