Les différends qui surviennent périodiquement dans les forums thématiques sur la question de savoir si un programmeur a besoin de mathématiques sont depuis longtemps devenus un lieu commun et un domaine de guerres saintes. Étant de notre côté (droit) de la frontière séparant le bien du mal, je veux partager un exemple qui démontre clairement combien il est nécessaire et même (nous n'aurons pas peur de ce mot) est nécessaire.
Considérons un problème de programmation intéressant, qui a un caractère un peu olympiade.
Pnp: à partir de maintenant, les partisans de l’idée que la programmation se compose aujourd’hui de pages Web magnifiquement conçues peuvent arrêter de lire, vous avez tout à fait raison, vous n’avez pas besoin de mathématiques ...
Eh bien, vous n'avez pas à insister là-dessus, vous n'êtes pas pire que nous, et votre travail est vraiment important, car j'ai déjà convenu que nous avons des idées différentes sur la programmation ...
Oui, vous avez tout à fait raison de dire que ces olympiades ne pourront pas, à l'aide du dernier framework, tracer sept lignes perpendiculaires rouges en une seule ligne de code ...
Néanmoins, je considère que c'est mon idée qui est correcte (c'est une propriété fatale de la matière hautement organisée sous forme de corps protéiques), donc je présenterai les arguments à l'appui.Je formule le problème - combien de nombres différents de longueur K se terminant par un bouton p donné peuvent être tapés sur le clavier du téléphone (clavier) si nous devons déplacer les boutons avec un chevalier d'échecs. Il est entendu que vous avez vu le clavier (j'ai toujours un téléphone portable normal, pas un smartphone, donc je le vois tous les jours, un lecteur plus avancé devrait contacter Internet pour obtenir de l'aide) et vous savez comment marche un cheval d'échecs (facile à google). les mathématiques n'ont rien à voir avec cela jusqu'à présent, si vous n'avez pas à l'esprit la possibilité de calculer des options.
La première solution est assez évidente - nous prenons les 10 boutons l'un après l'autre (nous désignons leur nombre par n pour la généralité), considérons tous les nombres possibles de K longs et comptons ceux qui se terminent sur le bouton souhaité. Les chiffres résultants sont résumés et la réponse est prête. Le nombre total d'options affichées est approximativement exprimé par n * B (K), où B (K) est le nombre de mouvements possibles de longueur K.En fait, vous devez considérer la somme de n positions, car B (p, K) dépend évidemment du numéro du bouton mais comme une première estimation descendre.
Avant de procéder à la recherche B, on peut réduire considérablement le nombre d'options en appliquant le sens commun (non, pas encore en mathématiques). Puisque le mouvement des boutons dépend de l'arrière-plan, nous pouvons inverser la tâche et rechercher tous les nombres de longueur K à partir du bouton souhaité p. Le nombre total d'options sera alors B (p, K), ce qui est n fois moins. Wow, nous venons de trouver un moyen d'accélérer la recherche d'une solution 10 fois - cool, voyons combien il en reste.
Nous devons évaluer B (p, K), pour lequel nous déterminons qu'à chaque mouvement, nous avons de 2 à 3 variantes de développement d'événements. Il s'ensuit (en général, c'est de la combinatoire, mais intuitivement clair) que le nombre total d'options sera de 2 ** K à 3 ** K (ci-après j'utilise K-1 comme K). On peut même améliorer cette estimation en passant à un modèle probabiliste. Considérant que la présence d'un doigt dans chaque bouton pour le moment est également probable (une déclaration forte, probablement incorrecte, mais acceptable avec des estimations approximatives), nous pouvons calculer le nombre moyen d'options de déplacement 7 * 2 + 2 (boutons 4 et 6) * 3 = 20/9 ~ 2,22 . Ensuite, l'estimation sera de 2,22 ** K, et nous savons avec certitude que nous avons un minimum de 2 ** K. Ensuite, pour K = 100, nous obtenons une borne inférieure 2 ** 100 = (2 ** 10) ** 10> (10 ** 3) ** 10 = 10 ** 30.
Si nous considérons une option en une nanoseconde (et ce n'est pas facile, même sur un PC de bureau puissant), nous avons besoin de 10 ** 30/10 ** 9 = 10 ** 21 secondes. Ensuite, nous rappelons le merveilleux mnononique "π secondes sont égales à un siècle" et le temps requis sera de 10 ** 21 / 3,14 * 10 ** 9 ~ 3 * 10 ** 11 siècles. Il me semble que peu de lecteurs vivront pour voir la fin des calculs en utilisant la méthodologie proposée. L'exposante est terrible, seule la factorielle est pire qu'elle.
Nous améliorerons la solution en fonction du fait que nous sommes intéressés par le nombre d'options, mais pas par les options elles-mêmes. Vous pouvez proposer la formule évidente B (p, K) = la somme de B (p ', K-1) pour tout p' dans laquelle nous obtenons en 1 mouvement de p. Nous partons du bouton final et lui attribuons un poids de 1, puis effectuons la procédure de sommation des poids actuels au suivant, répétons à la profondeur souhaitée.
Nous illustrons ce qui a été dit avec un exemple, en commençant par le nombre 1 {1234567890}:
poids initial {1000000000},
après le premier transfert {0000010100} (2 options),
après le deuxième transfert {2010001001} (5 options),
après le troisième {0102040300} (10 options) et ainsi de suite.
L'algorithme est simple, il peut être implémenté même avec vos mains. Une estimation générale du temps d'exécution est K itérations, à chacune desquelles pour n poids nous ne modifions pas plus de n poids liés,
n total
** 2 * K. Pour le cas considéré précédemment, 10 * 10 * 100 = 10 ** 4 - un peu.
Il ne reste plus qu'à évaluer la durée de chaque opération - c'est l'addition (question de poubelle), mais pas l'addition simple (de cet endroit plus en détail). Nous avons déjà fixé la limite inférieure de la réponse à 2 ** K, c'est-à-dire que nous avons certainement besoin d'au moins K bits pour représenter le résultat. La limite supérieure est de 3 ** K, pour notre cas 3 ** 100 = (3 ** 5) ** 20 <(2 ** 8) * 20 = 2 ** 160, c'est-à-dire que nous sommes garantis pour tenir dans 160 bits. Nous pouvons supposer que 128 bits nous suffisent, puisque 2,2 ** 100 <2 ** 128, mais accepter une telle déclaration sur la foi est effrayant, nous avons donc besoin d'un nombre d'au moins 160 bits ou de 49 chiffres décimaux, selon votre bibliothèque de numéros haute précision.
PNP: Ne proposez pas de virgule flottante, nous avons besoin d'un résultat complètement précis.Dans les hypothèses acceptées, l'opération d'addition occupera 160/8 = 20 octets / 4 = 5 ajouts d'entiers de 32 bits de long, ce qui n'affecte en rien l'ordre du temps (il reste linéaire en K), mais peut augmenter considérablement le temps de calcul réel (de plusieurs fois).
Dans tous les cas, le résultat est tout simplement magnifique - nous avons transformé la tâche de fondamentalement insoluble dans un délai raisonnable à complètement résoluble: si une opération d'addition élémentaire est effectuée en une microseconde (et cela est facile à assurer même sur la carte Arduino), le temps total ne dépassera pas 10 ** 4 * 20 / 10 ** 6, moins d'une seconde) et nous l'avons fait sans maths.
Néanmoins, et si nous avons besoin d'un K plus grand - bien sûr, l'ordre linéaire des calculs - c'est merveilleux, mais cela peut (et entraînera) des pertes de temps importantes pour les grandes valeurs. Il s'avère que vous pouvez améliorer considérablement le temps prévu, surveillez vos mains.
Ce que nous faisons à chaque étape du calcul (pseudo-code):
= 0;
1
2
* ( 1 2)
* 1 2.
=
2 ( 1 * )
0 1, . '=* =(...((*)*)...). , =***. , . **3,
***3 — , ? , …
— , **3 , , , ( ) ( ), . , 100 99 8. , 2*log2(), ( =100 1000/10=100 ) ,
2*log2()***3. , , , . , , log2(K), , , 100.
- ( , ), , , .