Vérifier si un nombre épelé est dans une plage en C++.

Question

Je veux vérifier l'entrée (numérique) par rapport à une liste de plages (min, max) alors que l'entrée est partiellement saisie ; en d'autres termes, j'ai besoin d'un algorithme élégant pour vérifier le préfixe d'un nombre par rapport à une plage (sans utiliser d'expressions régulières).

Exemples de cas de test :

 1 is in (  5,   9) -> false
 6 is in (  5,   9) -> true
 1 is in (  5,  11) -> true  (as 10 and 11 are in the range)
 1 is in (  5, 200) -> true  (as e.g. 12 and 135 are in the range)
11 is in (  5,  12) -> true
13 is in (  5,  12) -> false 
13 is in (  5,  22) -> true
13 is in (  5, 200) -> true  (as 130 is in the range)
 2 is in (100, 300) -> true  (as 200 is in the range)

Vous avez une idée ?

Answer 1

Je crois qu'il est vrai que l'entrée est acceptable si et seulement si soit :

• C'est une sous-chaîne préfixe de la borne inférieure convertie en chaîne de caractères.

ou

• L'entrée suivie d'un nombre quelconque de zéros supplémentaires (éventuellement aucun) se situe dans la plage suivante

La première règle est requise par exemple par 13 is in range (135, 140) . La deuxième règle est requise par exemple par 2 is in range (1000, 3000) .

La deuxième règle peut être testée efficacement par une série de multiplications par 10, jusqu'à ce que l'entrée mise à l'échelle dépasse la limite supérieure.

Answer 2

Une formulation itérative :

bool in_range(int input, int min, int max)
{
  if (input <= 0)
    return true;    // FIXME handle negative and zero-prefixed numbers
  int multiplier = 1;
  while ((input + 1) * multiplier - 1 < min)         // min <= [input]999
    multiplier *= 10;    // TODO consider overflow
  return input * multiplier <= max;                  //        [input]000 <= max
}

Une méthode plus simple [edit : et plus efficace ; voir ci-dessous] consiste à utiliser la division entière tronquée :

bool in_range(int input, int min, int max)
{
  if (input <= 0)
    return true;
  while (input < min) {
    min /= 10;
    max /= 10;
  }
  return input <= max;
}

---

Test et profilage :

#include <iostream>
#include <chrono>

bool ecatmur_in_range_mul(int input, int min, int max)
{
  int multiplier = 1;
  while ((input + 1) * multiplier - 1 < min)         // min <= [input]999
    multiplier *= 10;    // TODO consider overflow
  return input * multiplier <= max;                  //        [input]000 <= max
}

bool ecatmur_in_range_div(int input, int min, int max)
{
  while (input < min) {
    min /= 10;
    max /= 10;
  }
  return input <= max;
}

bool t12_isInRange(int input, int min, int max)
{
    int multiplier = 1;
    while(input*multiplier <= max)
    {
        if(input >= min / multiplier) return true;
        multiplier *= 10;
    }
    return false;
}

struct algo { bool (*fn)(int, int, int); const char *name; } algos[] = {
{ ecatmur_in_range_mul, "ecatmur_in_range_mul"},
{ ecatmur_in_range_div, "ecatmur_in_range_div"},
{ t12_isInRange, "t12_isInRange"},
};

struct test { int input, min, max; bool result; } tests[] = {
{  1,   5,   9, false },
{  6,   5,   9, true },
{  1,   5,  11, true }, // as 10 and 11 are in the range
{  1,   5, 200, true }, // as e.g. 12 and 135 are in the range
{ 11,   5,  12, true },
{ 13,   5,  12, false },
{ 13,   5,  22, true },
{ 13,   5, 200, true }, // as 130 is in the range
{  2, 100, 300, true }, // as 200 is in the range
{ 13, 135, 140, true }, // Ben Voigt
{ 13, 136, 138, true }, // MSalters
};
int main() {
    for (auto a: algos)
        for (auto t: tests)
            if (a.fn(t.input, t.min, t.max) != t.result)
                std::cout << a.name << "(" << t.input << ", " << t.min << ", " << t.max << ") != "
                    << t.result << "\n";

    for (auto a: algos) {
        std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now();
        for (auto t: tests)
            for (int i = 1; i < t.max * 2; ++i)
                for (volatile int j = 0; j < 1000; ++j) {
                    volatile bool r = a.fn(i, t.min, t.max);
                    (void) r;
                }
        std::chrono::time_point<std::chrono::system_clock> end = std::chrono::system_clock::now();
        std::cout << a.name << ": "
            << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << '\n';
    }
}

De manière surprenante (du moins pour moi), la division itérée est la plus rapide :

ecatmur_in_range_mul: 17331000
ecatmur_in_range_div: 14711000
t12_isInRange: 15646000

Answer 3

bool isInRange(int input, int min, int max)
{
    int multiplier = 1;
    while(input*multiplier <= max)
    {
        if(input >= min / multiplier) return true;
        multiplier *= 10;
    }
    return false;
}

Il passe tous vos testcases.

Answer 4

(input >= lower_bound) && input <= upper_bound

OR

(f(input) >= lower_bound) && (f(input) <= upper_bound)

OR

(lower_bound - f(input) < pow(10, n_digits_upper_bound - n_digits_input)) && 
(lower_bound - f(input) > 0)

where

f(input) == (input * pow(10, n_digits_upper_bound - n_digits_input))

 1 is in (  5,   9) -> 1 * pow(10,0) -> same                 -> false
 6 is in (  5,   9)                                          -> true
 1 is in (  5,  11) -> 1 * pow(10,1)  -> 10 is in (5,11)     -> true
 1 is in (  5, 200) -> 1 * pow(10,2)  -> 100 is in (5, 200)  -> true
11 is in (  5,  12)                                          -> true
13 is in (  5,  12) -> 13 * pow(10,0) -> same                -> false 
13 is in (  5,  22)                                          -> true
13 is in (  5, 200)                                          -> true
 2 is in (100, 300) -> 2 * pow(10,2) -> 200 is in (100,300)  -> true
 4 is in (100, 300) -> 4 * pow(10,2)  -> 400 is in (100,300) -> false
13 is in (135, 140) -> 135 - 130                             -> true
14 is in (135, 139) -> 135 - 140                             -> false

Answer 5

Je préfère une approche qui utilise des algorithmes déjà mis en œuvre. Alors que beaucoup d'autres solutions utilisent des divisions récursives par 10 je pense qu'il est préférable d'utiliser les logarithmes à 10 bases, qui ont O(1) de sorte que la complexité totale de la solution est O(1) .

Divisons le problème en deux parties.

Premier gérera le cas où la partie number * 10^n est entre min y max pour au moins un n . Cela nous permettrait de vérifier par exemple si number = 12 y min,max = 11225,13355 que x = 12000 = 12*10^3 est entre min y max . Si ce test est positif, cela signifie que le résultat est True .

Deuxièmement traitera les cas où number est le début de l'un ou l'autre min o max . Par exemple, si number = 12 y min,max = 12325,14555 le premier test échouera, car 12000 n'est pas entre min y max (ainsi que tous les autres numéros) 12*10^n pour tout n ). Mais le deuxième test permettra de constater que 12 est le début de 12325 et retourner True .

Premier

Vérifions, si le premier x = number*10^n qui est égal ou supérieur à min est inférieur ou égal à max (donc min <= x <= max, where x is number*10^n for any integer n ). Si elle est supérieure à max que tous les autres x es seront plus grandes, car nous avons pris les plus petites.

log(number*10^n) > log(min)
log(number) + log(10^n) > log(min)
log(number) + n > log(min)
n > log(min) - log(number)
n > log(min/number)

Pour obtenir le nombre à comparer, il suffit de calculer le premier satisfaisant n :

n = ceil(log(min/number))

Et calculer alors le nombre x :

x = number*10^n

Deuxièmement

Nous devons vérifier si notre nombre est un début littéral de l'une ou l'autre limite.

Nous calculons simplement x commençant par les mêmes chiffres que number et rembourré avec 0 à l'extrémité, ayant la même longueur que les min :

magnitude = 10**(floor(log10(min)) - floor(log10(number)))
x = num*magnitude

Et ensuite, vérifiez si min et x la différence (en échelle de magnitude) est inférieure à 1 et supérieur ou égal à 0 :

0 <= (min-x)/magnitude < 1

Donc, si number es 121 y min es 132125 entonces magnitude es 1000 , x = number*magnitude serait 121000 . min - x donne 132125-121000 = 11125 qui devrait être inférieur à 1000 (autrement min le début serait plus grand que 121 ), nous le comparons donc avec magnitude en divisant par sa valeur et en comparant à 1 . Et ce n'est pas grave si min es 121000 mais pas si min es 122000 c'est pourquoi 0 <= y < 1 .

Le même algorithme est utilisé pour max .

Pseudo code

En incorporant tout cela dans un pseudo-code, on obtient cet algorithme :

def check(num,min,max):
    # num*10^n is between min and max
    #-------------------------------
    x = num*10**(ceil(log10(min/num)))
    if x>=min and x<=max: 
        return True

    # if num is prefix substring of min
    #-------------------------------
    magnitude = 10**(floor(log10(min)) - floor(log10(num)))
    if 0 <= (min-num*magnitude)/magnitude < 1:
        return True

    # if num is prefix substring of max
    #-------------------------------
    magnitude = 10**(floor(log10(max)) - floor(log10(num)))
    if 0 <= (max-num*magnitude)/magnitude < 1:
        return True

    return False

Ce code pourrait être optimisé en évitant les calculs répétés de log10(num) . De plus, dans la solution finale, je passerais d'une portée flottante à une portée entière ( magnitude = 10**int(floor(log10(max)) - floor(log10(num))) ) et ensuite effectuer toutes les comparaisons sans division, c'est-à-dire 0 <= (max-num*magnitude)/magnitude < 1 -> 0 <= max-num*magnitude < magnitude . Cela réduirait les risques d'erreurs d'arrondi.

Il est également possible de remplacer magnitude = 10**(floor(log10(min)) - floor(log10(num))) avec magnitude = 10**(floor(log10(min/num))) , donde log10 n'est calculé qu'une seule fois. Mais je ne peux pas prouver que cela donnera toujours des résultats corrects, ni le réfuter. Si quelqu'un pouvait le prouver, je lui en serais très reconnaissant.

_{Tests (en Python) : <a href="http://ideone.com/N5R2j" rel="nofollow noreferrer">http://ideone.com/N5R2j </a>(vous pourriez modifier l'entrée pour ajouter d'autres tests).}