Plonger en profondeur : solutions récursives pour les palindromes et les blocs contigus

Dans cet article, nous aborderons deux tâches du Perl Weekly Challenge #288 : trouver le palindrome le plus proche et déterminer la taille du plus grand bloc contigu dans une matrice. Les deux solutions seront implémentées de manière récursive en Perl et Go.

Table des matières

1. Palindrome le plus proche
2. Bloc contigu
3. Conclusion

Palindrome le plus proche

La première tâche est de trouver le palindrome le plus proche qui ne s'inclut pas.

Le palindrome le plus proche est défini comme celui qui minimise la différence absolue entre deux entiers.

S'il y a plusieurs candidats, le plus petit doit être renvoyé.

Description de la tâche

Entrée : Une chaîne, $str, qui représente un entier.

Sortie : Le palindrome le plus proche sous forme de chaîne.

Exemples

• Entrée : "123"
  Sortie : "121"

• Entrée : "2"
  Sortie : "1"
  Il existe deux palindromes les plus proches : « 1 » et « 3 ». Par conséquent, nous renvoyons le plus petit "1".

• Entrée : "1400"
  Sortie : "1441"

• Entrée : "1001"
  Sortie : "999"

Solution

Implémentation Perl

Dans cette implémentation, nous utilisons une approche récursive pour trouver le palindrome le plus proche qui n'est pas égal au nombre d'origine. La fonction récursive explore à la fois les limites inférieures et supérieures autour du nombre d'origine :

• Il vérifie si les candidats actuels (inférieurs et supérieurs) sont des palindromes valides (et non égaux à l'original).
• Si aucun des candidats n'est valide, la fonction décrémente récursivement le candidat inférieur et incrémente le candidat supérieur jusqu'à ce qu'elle trouve un palindrome valide.

Cette stratégie récursive réduit efficacement l'espace de recherche, garantissant que nous identifions le palindrome le plus proche tout en respectant les contraintes du problème.

sub is_palindrome {
    my ($num) = @_;
    return $num eq reverse($num);
}

sub find_closest {
    my ($lower, $upper, $original) = @_;
    return $lower if is_palindrome($lower) && $lower != $original;
    return $upper if is_palindrome($upper) && $upper != $original;
    return find_closest($lower - 1, $upper + 1, $original) if $lower > 0;
    return $upper + 1;
}

sub closest_palindrome {
    my ($str) = @_;
    my $num = int($str);
    return find_closest($num - 1, $num + 1, $num);
}

Aller à la mise en œuvre

L'implémentation Go suit une stratégie récursive similaire. Il vérifie également les candidats autour du numéro d'origine, en utilisant la récursivité pour ajuster les limites jusqu'à ce qu'un palindrome valide soit trouvé.

package main

import (
    "strconv"
)

func isPalindrome(num int) bool {
    reversed := 0
    original := num

    for num > 0 {
        digit := num % 10
        reversed = reversed*10 + digit
        num /= 10
    }

    return original == reversed
}

func findClosest(lower, upper, original int) string {
    switch {
        case isPalindrome(lower) && lower != original:
            return strconv.Itoa(lower)
        case isPalindrome(upper) && upper != original:
            return strconv.Itoa(upper)
        case lower > 0:
            return findClosest(lower-1, upper+1, original)
        default:
            return strconv.Itoa(upper + 1)
    }
}

func closestPalindrome(str string) string {
    num, _ := strconv.Atoi(str)
    return findClosest(num-1, num+1, num)
}

Hier ist die erweiterte Definition für den Bloc contigu :

Bloc contigu

La deuxième tâche consiste à déterminer la taille du plus grand bloc contigu dans une matrice donnée, où toutes les cellules contiennent x ou o.

Un bloc contigu se compose d'éléments contenant le même symbole qui partagent un bord (pas seulement un coin) avec d'autres éléments du bloc, créant ainsi une zone connectée.

Description de la tâche

Entrée : Une matrice rectangulaire contenant x et o.

Sortie : La taille du plus grand bloc contigu.

Exemples

• Entrée :
  

  [
      ['x', 'x', 'x', 'x', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'x', 'x', 'o', 'o'],
  ]
  

Sortie : 11
Il existe un bloc de 9 cellules contiguës contenant x et un bloc de 11 cellules contiguës contenant o.

• Entrée :
  

  [
      ['x', 'x', 'x', 'x', 'x'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'x', 'x', 'x', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
  ]
  

Sortie : 11
Il existe un bloc de 11 cellules contiguës contenant x et un bloc de 9 cellules contiguës contenant o.

• Entrée :
  

  [
      ['x', 'x', 'x', 'o', 'o'],
      ['o', 'o', 'o', 'x', 'x'],
      ['o', 'x', 'x', 'o', 'o'],
      ['o', 'o', 'o', 'x', 'x'],
  ]
  

Sortie :7
Il y a un bloc de 7 cellules contiguës contenant o, deux autres blocs de 2 cellules de o, trois blocs de 2 cellules de x et un bloc de 3 cellules de x.

Solution

Implémentation Perl

Dans cette implémentation, nous utilisons une approche de recherche récursive en profondeur d'abord (DFS) pour déterminer la taille du plus grand bloc contigu dans une matrice. La fonction principale initialise une matrice visitée pour suivre quelles cellules ont été explorées. Il parcourt chaque cellule, appelant la fonction récursive DFS chaque fois qu'il rencontre une cellule non visitée.

La fonction DFS explore les quatre directions possibles (haut, bas, gauche, droite) à partir de la cellule actuelle. Il compte la taille du bloc contigu en s'appelant récursivement les cellules voisines partageant le même symbole et n'ayant pas été visitées. Cette méthode récursive agrège efficacement la taille du bloc tout en garantissant que chaque cellule n'est comptée qu'une seule fois.

sub largest_contiguous_block {
    my ($matrix) = @_;
    my $rows = @$matrix;
    my $cols = @{$matrix->[0]};
    my @visited = map { [(0) x $cols] } 1..$rows;

    my $max_size = 0;

    for my $r (0 .. $rows - 1) {
        for my $c (0 .. $cols - 1) {
            my $symbol = $matrix->[$r][$c];
            my $size = dfs($matrix, \@visited, $r, $c, $symbol);
            $max_size = $size if $size > $max_size;
        }
    }

    return $max_size;
}

sub dfs {
    my ($matrix, $visited, $row, $col, $symbol) = @_;

    return 0 if $row = @$matrix || $col = @{$matrix->[0]}
                || $visited->[$row][$col] || $matrix->[$row][$col] ne $symbol;

    $visited->[$row][$col] = 1;
    my $count = 1;

    $count += dfs($matrix, $visited, $row + 1, $col, $symbol);
    $count += dfs($matrix, $visited, $row - 1, $col, $symbol);
    $count += dfs($matrix, $visited, $row, $col + 1, $symbol);
    $count += dfs($matrix, $visited, $row, $col - 1, $symbol);

    return $count;
}

Aller à la mise en œuvre

L'implémentation Go reflète cette stratégie DFS récursive. De la même manière, il parcourt la matrice et utilise la récursivité pour explorer les cellules contiguës portant le même symbole.

package main

func largestContiguousBlock(matrix [][]rune) int {
    rows := len(matrix)
    if rows == 0 {
        return 0
    }
    cols := len(matrix[0])
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    maxSize := 0

    for r := 0; r  maxSize {
                maxSize = size
            }
        }
    }

    return maxSize
}

func dfs(matrix [][]rune, visited [][]bool, row, col int, symbol rune) int {
    if row = len(matrix) || col = len(matrix[0]) ||
        visited[row][col] || matrix[row][col] != symbol {
        return 0
    }

    visited[row][col] = true
    count := 1

    count += dfs(matrix, visited, row+1, col, symbol)
    count += dfs(matrix, visited, row-1, col, symbol)
    count += dfs(matrix, visited, row, col+1, symbol)
    count += dfs(matrix, visited, row, col-1, symbol)

    return count
}

Conclusion

In this article, we explored two intriguing challenges from the Perl Weekly Challenge #288: finding the closest palindrome and determining the size of the largest contiguous block in a matrix.

For the first task, both the Perl and Go implementations effectively utilized recursion to navigate around the original number, ensuring the closest palindrome was found efficiently.

In the second task, the recursive depth-first search approach in both languages allowed for a thorough exploration of the matrix, resulting in an accurate count of the largest contiguous block of identical symbols.

These challenges highlight the versatility of recursion as a powerful tool in solving algorithmic problems, showcasing its effectiveness in both Perl and Go. If you're interested in further exploration or have any questions, feel free to reach out!

You can find the complete code, including tests, on GitHub.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!