Diving Deep: Penyelesaian Rekursif untuk Palindrom dan Blok Bersebelahan

Dalam artikel ini, kami akan menangani dua tugasan daripada Cabaran Mingguan Perl #288: mencari palindrom yang paling hampir dan menentukan saiz bongkah bersebelahan terbesar dalam matriks. Kedua-dua penyelesaian akan dilaksanakan secara rekursif dalam Perl dan Go.

Jadual Kandungan

1. Palindrom Terhampir
2. Blok Bersambung
3. Kesimpulan

Palindrom terdekat

Tugas pertama ialah mencari palindrom terdekat yang tidak termasuk dirinya.

Palindrom terdekat ditakrifkan sebagai palindrom yang meminimumkan perbezaan mutlak antara dua integer.

Jika terdapat berbilang calon, yang terkecil hendaklah dikembalikan.

Penerangan Tugas

Input: Rentetan, $str, yang mewakili integer.

Output: Palindrom terdekat sebagai rentetan.

Contoh

• Input: "123"
  Output: "121"

• Input: "2"
  Output: "1"
  Terdapat dua palindrom terdekat: "1" dan "3". Oleh itu, kami mengembalikan "1" terkecil.

• Input: "1400"
  Output: "1441"

• Input: "1001"
  Output: "999"

Penyelesaian

Pelaksanaan Perl

Dalam pelaksanaan ini, kami menggunakan pendekatan rekursif untuk mencari palindrom terdekat yang tidak sama dengan nombor asal. Fungsi rekursif meneroka kedua-dua sempadan bawah dan atas di sekeliling nombor asal:

• Ia menyemak sama ada calon semasa (bawah dan atas) adalah palindrom yang sah (dan tidak sama dengan yang asal).
• Jika kedua-dua calon tidak sah, fungsi tersebut mengurangkan secara rekursif calon bawah dan menambah calon atas sehingga ia menemui palindrom yang sah.

Strategi rekursif ini mengecilkan ruang carian secara berkesan, memastikan kami mengenal pasti palindrom terdekat sambil mematuhi kekangan masalah.

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

Perlaksanaan Go

Pelaksanaan Go mengikut strategi rekursif yang serupa. Ia juga menyemak calon di sekeliling nombor asal, menggunakan rekursi untuk melaraskan sempadan sehingga palindrom yang sah ditemui.

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 Definisi für den Blok Bersebelahan:

Blok Bersebelahan

Tugas kedua ialah menentukan saiz blok bersebelahan terbesar dalam matriks tertentu, di mana semua sel mengandungi sama ada x atau o.

Blok bersebelahan terdiri daripada elemen yang mengandungi simbol yang sama yang berkongsi tepi (bukan hanya sudut) dengan elemen lain dalam blok, mewujudkan kawasan bersambung.

Penerangan Tugas

Input: Matriks segi empat tepat yang mengandungi x dan o.

Output: Saiz blok bersebelahan terbesar.

Contoh

• Input:
  

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

Output: 11
Terdapat satu blok 9 sel bersebelahan yang mengandungi x dan satu blok 11 sel bersebelahan mengandungi o.

• Input:
  

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

Output: 11
Terdapat satu blok 11 sel bersebelahan yang mengandungi x dan satu blok 9 sel bersebelahan mengandungi o.

• Input:
  

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

Output: 7
Terdapat satu blok 7 sel bersebelahan yang mengandungi o, dua blok 2 sel o yang lain, tiga blok 2 sel x dan satu blok 3 sel x.

Penyelesaian

Pelaksanaan Perl

Dalam pelaksanaan ini, kami menggunakan pendekatan carian mendalam pertama (DFS) rekursif untuk menentukan saiz blok bersebelahan terbesar dalam matriks. Fungsi utama memulakan matriks yang dilawati untuk menjejaki sel yang telah diterokai. Ia berulang melalui setiap sel, menggunakan fungsi DFS rekursif apabila ia menemui sel yang tidak dilawati.

Fungsi DFS meneroka semua empat arah yang mungkin (atas, bawah, kiri, kanan) dari sel semasa. Ia mengira saiz blok bersebelahan dengan memanggil dirinya secara rekursif pada sel jiran yang berkongsi simbol yang sama dan belum pernah dilawati. Kaedah rekursif ini mengagregatkan saiz blok dengan berkesan sambil memastikan setiap sel hanya dikira sekali.

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 < 0 || $row >= @$matrix || $col < 0 || $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;
}

Perlaksanaan Go

Pelaksanaan Go mencerminkan strategi DFS rekursif ini. Ia juga merentasi matriks dan menggunakan rekursi untuk meneroka sel bersebelahan dengan simbol yang sama.

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 < rows; r++ {
        for c := 0; c < cols; c++ {
            symbol := matrix[r][c]
            size := dfs(matrix, visited, r, c, symbol)
            if size > maxSize {
                maxSize = size
            }
        }
    }

    return maxSize
}

func dfs(matrix [][]rune, visited [][]bool, row, col int, symbol rune) int {
    if row < 0 || row >= len(matrix) || col < 0 || 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.

Atas ialah kandungan terperinci Diving Deep: Penyelesaian Rekursif untuk Palindrom dan Blok Bersebelahan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!