Recherche de bits complète avec Python

Qu'est-ce qu'une recherche binaire complète? 2 ^ n recherche complète

Exemple ARC061: plusieurs formules

Vous recevrez la chaîne S, qui se compose uniquement de nombres> 1 et 9 ou moins. Dans cette chaîne, vous pouvez mettre un + à certains endroits entre ces caractères. Vous n'êtes pas obligé d'en mettre un. Cependant, le + ne doit pas être consécutif. Toutes les chaînes de caractères créées de cette manière peuvent être considérées comme des formules mathématiques et la somme peut être calculée. Calculez les valeurs de toutes les formules possibles et sortez la somme.

Contraintes ・ 1 ≤|S|≤10 ・ Toutes les lettres contenues dans S sont des nombres de 1 à 9.

Exemple d'entrée / sortie

[in]  125
[out] 176
#  125、1+25、12+5、1+2+4 modèles de 5 peuvent être considérés.

Façon de penser

Si c'est 125, il y a deux endroits (1 {a} 2 {b} 5) où vous pouvez mettre "+", donc 2 ^ 2 = 4 manières de formules peuvent être considérées. ab Il existe deux choix, avec ou sans "+". Et comme il s'agit de bit, cherchez l'endroit où se trouve bit. L'image ressemble à ce qui suit.

index a b
0 0 0
1 0 1
2 1 0
3 1 1

Vous pouvez voir qu'il y a 4 modèles en tout.

Implémentation en python

Utilisez l'opérateur bit de python avec décalage vers la droite ">>" bitAND "&". Pour plus de détails sur les opérateurs de bits, ici a été très utile.

--Droite shift >>

Essayez de décaler 11 un peu vers la droite. Le 1 le plus à droite disparaît et le 0 le plus à gauche est inséré. 1011 = 11 0101 = 5

Prenons 10 et 12 bits ET. (Ne laissez 1 que là où les deux valent 1 pour chaque place.) 1010 = 10 1100 = 12 1000 = 08

#Entrée: 125
s = ["1", "2", "5"]
n = len(s)

for i in range(2 ** (n-1)):
    tmp = [False] * (n-1)
    for j in range(n-1):
        if i >> j & 1:
            tmp[j] = True
    pattern.append(tmp)

print(pattern)
[[False, False], [True, False], [False, True], [True, True]]

J'ai pu trouver tous les modèles par une recherche peu complète. Au fait, la réponse à l'exemple que j'ai résolu est comme ça. (Bien que le code soit sale et qu'il devrait y avoir un moyen plus intelligent de le résoudre)

Recommended Posts

Recherche de bits complète avec Python
recherche complète de bits python
Recherche de bits complète avec Go
Recherche séquentielle avec Python
Confirmer la recherche de bits complète
Dichotomie avec python
Dichotomie avec Python 3
Les moteurs de recherche fonctionnent avec python
Rechercher des tweets Twitter avec Python
Rationalisez la recherche Web avec Python
Construire mlpy avec python3.3 (64 bits) (Windows 64 bits)
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (010 --014 Recherche complète: Recherche complète de bits)
FizzBuzz en Python3
Grattage avec Python
Changer l'environnement Python 64 bits en environnement 32 bits avec Anaconda
Statistiques avec python
Grattage avec Python
Python avec Go
Twilio avec Python
Intégrer avec Python
Rechercher le labyrinthe avec l'algorithme python A *
Jouez avec 2016-Python
AES256 avec python
Testé avec Python
Je souhaite rechercher le texte intégral avec elasticsearch + python
python commence par ()
avec syntaxe (Python)
Bingo avec python
Zundokokiyoshi avec python
peu de recherche complète et ensemble de produits direct
Version 64 bits de PYTHON2.7
Résolvez les problèmes de somme partielle avec une recherche complète en Python
Excel avec Python
Micro-ordinateur avec Python
Cast avec python
Rechercher et télécharger automatiquement des vidéos YouTube avec Python
Raisonnement causal et recherche causale par Python (pour les débutants)
Utilisez Search Tweets: Archive complète / Sandbox en Python
À propos de la recherche peu complète qui apparaît souvent chez les professionnels de la concurrence Aux yeux des débutants avec python
Communication série avec Python
Zip, décompressez avec python
Django 1.11 a démarré avec Python3.6
Jugement des nombres premiers avec Python
Communication de socket avec Python
Analyse de données avec python 2
Essayez de gratter avec Python.
Apprendre Python avec ChemTHEATER 03
"Orienté objet" appris avec python
Exécutez Python avec VBA
Manipuler yaml avec python
Résolvez AtCoder 167 avec python
Communication série avec python
[Python] Utiliser JSON avec Python
Apprendre Python avec ChemTHEATER 05-1
Exécutez prepDE.py avec python3
1.1 Premiers pas avec Python
Collecter des tweets avec Python