Trouver la double existence et appliquer l'algorithme de Luhn

Dans cet article, nous aborderons deux tâches intéressantes du Perl Weekly Challenge #290 : vérifier la double existence dans un tableau et implémenter l'algorithme de Luhn pour la validation. Nous mettrons en œuvre des solutions en Perl et Go.

Table des matières

• Double Existence
• Algorithme de Luhn
• Conclusion

Double existence

La première tâche consiste à trouver s'il existe deux indices $i et $j tels que :

1. $i != $j
2. 0 <= ($i, $j) < scalar @ints
3. $ints[i] = 2 * $ints[j]

Description de la tâche

Entrée : Un tableau d'entiers, @ints.

Sortie : vrai si la condition est remplie ; sinon, faux.

Exemples :

Input: @ints = (6, 2, 3, 3)
Output: true

For $i = 0, $j = 2
$ints[$i] = 6 => 2 * 3 =>  2 * $ints[$j]

Input: @ints = (3, 1, 4, 13)
Output: false

Input: @ints = (2, 1, 4, 2)
Output: true

For $i = 2, $j = 3
$ints[$i] = 4 => 2 * 2 =>  2 * $ints[$j]

Solution

Implémentation Perl
Dans l'implémentation Perl, nous utilisons un hachage pour suivre les entiers vus et vérifier si la moitié ou le double du nombre actuel existe dans le hachage.

sub double_exist {
    my %seen;

    foreach my $num (@_) {
        return 1 if exists $seen{$num / 2} || exists $seen{$num * 2};
        $seen{$num} = 1;
    }

    return 0;
}

Allez à la mise en œuvre
L'implémentation Go suit une logique similaire, utilisant une carte pour garder une trace des entiers uniques.

func doubleExist(ints []int) bool {
    seen := make(map[int]bool)

    for _, num := range ints {
        if (num%2 == 0 && seen[num/2]) || seen[num*2] {
            return true
        }
        seen[num] = true
    }

    return false
}

L'algorithme de Luhn

La deuxième tâche consiste à implémenter l'algorithme de Luhn pour valider une chaîne de chiffres, en ignorant les caractères non numériques. Le dernier chiffre est considéré séparément comme la charge utile.

Description de la tâche

Vous recevez une chaîne str contenant des chiffres (et éventuellement d'autres caractères qui peuvent être ignorés). Le dernier chiffre est considéré comme la charge utile et traité séparément.

1. En comptant à partir de la droite, doublez la valeur du premier, du troisième, etc., des chiffres restants.
2. Pour chaque valeur désormais supérieure à 9, additionnez ses chiffres.
3. Le chiffre de contrôle correct est celui qui, ajouté à la somme de toutes les valeurs, ramène le total modulo 10 à zéro.

Renvoie true si la charge utile est égale au chiffre de contrôle correct ; sinon, renvoie false.

Exemples :

Input: "17893729974"
Output: true

Payload is 4.

Digits from the right:

7 * 2 = 14, sum = 5
9 = 9
9 * 2 = 18, sum = 9
2 = 2
7 * 2 = 14, sum = 5
3 = 3
9 * 2 = 18, sum = 9
8 = 8
7 * 2 = 14, sum = 5
1 = 1

Sum of all values = 56, so 4 must be added to bring the total mod 10 to zero. The payload is indeed 4.

Input: "4137 8947 1175 5904"
Output: true

Input: "4137 8974 1175 5904"
Output: false

Solution

Implémentation Perl
L'implémentation Perl traite la chaîne d'entrée pour ignorer les caractères autres que des chiffres, puis applique l'algorithme de Luhn pour valider le nombre.

sub luhn_check {
    my ($str) = @_;
    $str =~ s/[^0-9]//g;

    my $payload = substr($str, -1);
    my $sum = 0;
    my $length = length($str);

    for (my $i = 0; $i < $length - 1; $i++) {
        my $digit = substr($str, $length - 2 - $i, 1);
        if ($i % 2 == 0) {
            $digit *= 2;
            $digit -= 9 if $digit > 9;
        }
        $sum += $digit;
    }

    my $check_digit = (10 - ($sum % 10)) % 10;

    return $payload == $check_digit ? 1 : 0;
}

Allez à la mise en œuvre
La version Go implémente la même logique, en utilisant le package Unicode pour filtrer les caractères non numériques.

func luhnCheck(str string) bool {
    sum := 0
    payload := 0
    digits := []int{}

    for _, char := range str {
        if unicode.IsDigit(char) {
            digit := int(char - '0')
            digits = append(digits, digit)
        }
    }

    if len(digits) == 0 {
        return false
    }

    payload = digits[len(digits)-1]

    for i := 0; i < len(digits)-1; i++ {
        digit := digits[i]
        if (len(digits)-2-i)%2 == 0 {
            digit *= 2
            if digit > 9 {
                digit -= 9
            }
        }
        sum += digit
    }

    checkDigit := (10 - (sum % 10)) % 10

    return payload == checkDigit
}

Conclusion

Dans cet article, nous avons exploré deux défis de programmation intéressants : trouver la double existence dans un tableau et implémenter l'algorithme de Luhn pour la validation. Ces tâches mettent en évidence comment différents langages de programmation peuvent résoudre des problèmes similaires avec leurs propres approches. J'espère que ces exemples vous inciteront à approfondir Perl et Go !

Vous pouvez trouver le code complet, y compris les tests, sur 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!