J'ai une chaîne dont la taille peut être aussi grande que "10 000". Je dois compter ces sous-séquences divisibles par 9.
Sollection: une sous-séquence est un arrangement dans lequel la commande J'ai essayé de générer toutes les sous-séquences (Powerset) de la chaîne donnée à l'aide de bits changeant et de vérification Chaque chaîne si elle est divisible par 9. Mais cela fonctionne bien tant que la longueur de la chaîne est <= 10. Après cela, je ne reçois pas de sous-séquences (certaines sous-séquences sont affichées des nombres négatifs). ci-dessous est mon code:
4 Réponses :
Si vous utilisez pour le P> printf("%ld\n", count);
Mieux encore, stockez chaque chiffre comme son propre Char . Cela prendra beaucoup plus d'espace, mais cela va faire affaire avec des chiffres individuels - que vous faites beaucoup - way plus facile.
@TUGRUL: converti en Int non signé, non signé longtemps .. aucun effet
@Stalin: Printf aurait des problèmes d'affichage des types de long-int. Avez-vous essayé cout? J'ai eu le même problème aussi mais je ne me souviens pas de la façon dont j'ai réparé ça.
@TUGRUL: Essayé Cout .. aucun effet. Je pense que je dois aller avec l'idée de Ghost. Gardez les sous-séquences comme chaînes, trouvez la somme des chiffres et vérifiez la divisibilité par 9. Thnx! Toutes les autres idées sont également les bienvenues!
Étant donné qu'un nombre est divisible par neuf si et uniquement si la somme de ses chiffres est divisible par neuf, vous pouvez vous éloigner de ce problème avec un L'idée est la suivante: à chaque étape, scinder en deux la recherche et déterminer (récursivement) combien de séquences ont la somme de ses chiffres être alors vous avez: p> Le boîtier de base pour une ultérieurement d'un seul chiffre une implémentation complète C ++ 11: P> O (n) code> algorithme récursif. i% 9 code>, où i code> gammes de 0 code> à 8 code>. Ensuite, vous construisez cette même table pour toute la plage en "fusionnant" les deux tables dans O (1) code> de la manière suivante. Disons l code> est la table pour la division gauche et R code> pour la bonne et vous devez construire le tableau f code> pour toute la plage. p> d code> est évident: il suffit de définir f [d% 9] = 1 code> et toutes les autres entrées à zéro. p> #include <iostream>
#include <array>
#include <tuple>
#include <string>
typedef std::array<unsigned int, 9> table;
using std::tuple;
using std::string;
table count(string::iterator beg, string::iterator end)
{
table F;
std::fill(F.begin(), F.end(), 0);
if (beg == end)
return F;
if (beg + 1 == end) {
F[(*beg - '0') % 9] = 1;
return F;
}
size_t distance = std::distance(beg, end);
string::iterator mid = beg + (distance / 2);
table L = count(beg, mid);
table R = count(mid, end);
for (unsigned int i = 0; i < 9; i++) {
F[i] = L[i] + R[i];
for(unsigned int j = 0; j < 9; j++) {
if (j <= i)
F[i] += L[j] * R[i - j];
else
F[i] += L[j] * R[9 + i - j];
}
}
return F;
}
table count(std::string s)
{
return count(s.begin(), s.end());
}
int main(void)
{
using std::cout;
using std::endl;
cout << count("1234")[0] << endl;
cout << count("12349")[0] << endl;
cout << count("9999")[0] << endl;
}
Le l et r dans la boucle interne est-il multiplié, non ajouté?
@Xavierholt: Yup, c'est le produit cartésien (sauf dans le premier cas, lorsque nous voulons simplement collecter les sous-séquences gauche et droite). Corrigé, merci.
J'ai eu une idée!
Puisque vous ne devez compter em> les substrings, vous ne vous souciez pas de ce qu'ils sont sont em>. Donc, à la place, vous pouvez simplement stocker des comptes de leurs sommes possibles. P> Ensuite, que si vous aviez une fonction pouvant combiner les tables de comptage de deux ensembles de sous-chaînes et vous donner le compte de leurs combinaisons? p> Et puisque je sais que c'était une explication horrible, je vais donner un exemple. Dis que vous avez reçu le numéro: p> divisez-le en deux et continuez de fractionnement jusqu'à obtenir des chiffres individuels: p> Que peut 2 code> somme? EASY: 2 code>. Et 4 code> ne peut que somme à 4 code>. Vous pouvez construire des tables de combien de sous-chaînes SUMP à chaque valeur (MOD 9): P> 0 1 2 3 4 5 6 7 8
2493: 3 0 2 2 2 2 2 2 0
t (n) = 2t (n / 2) + O (1) est o (n) : vous avez n (1 + 1/2 + 1 / 4 + ... + 1 / N) <2N .
@akappa - merci - je savais que mes maths étaient un peu funky ... trop de café, j'imagine. Acclamations!
@Xavierholt Lorsque vous écrivez des sous-chaînes Avez-vous réellement signé la recherche après la recherche après la recherche de suivi
@Xavierholt Comment géreriez-vous le cas lorsqu'il y a 0 dans la chaîne d'entrée comme 0189.
@LUV Techniquement parlant, 0 sont divisibles par neuf, mais si vous voulez juste que la somme du chiffre == 9, vous soustrayez ((nombre de zéros) ^ 2) -1 de votre réponse finale
Voici le code C ++ selon l'algorithme d'Akappa. Toutefois, cet algorithme échoue à des chiffres contenant une ou plusieurs 0 à 0. Dans des cas de "10292" et "0189" mais donne des réponses correctes pour "1292" ans "189". J'apprécierais que quelqu'un puisse déboguer cela pour donner des réponses à tous les cas.
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
#include<cctype>
#include<list>
#include<set>
#include<set>
#include<map>
using namespace std;
typedef vector<int> table;
table count(string::iterator beg, string::iterator end)
{
table F(9);
std::fill(F.begin(), F.end(), 0);
if (beg == end)
return F;
if (beg + 1 == end) {
F[(*beg - '0') % 9] = 1;
return F;
}
size_t distance = std::distance(beg, end);
string::iterator mid = beg + (distance / 2);
table L = count(beg, mid);
table R = count(mid, end);
for (unsigned int i = 0; i < 9; i++) {
F[i] = L[i] + R[i];
for(unsigned int j = 0; j < 9; j++) {
if (j <= i)
F[i] += L[j] * R[i - j];
else
F[i] += L[j] * R[9 + i - j];
}
}
return F;
}
table count(std::string s)
{
return count(s.begin(), s.end());
}
int main()
{
cout << count("1234")[0] << endl;
cout << count("12349")[0] << endl;
cout << count("9999")[0] << endl;
cout << count("1292")[0] << endl;cout << count("189")[0] << endl;
cout << count("10292")[0] << endl;cout << count("0189")[0] << endl;
system("pause");
}
Un fait amusant qui peut vous aider ou peut ne pas vous aider: si un nombre est divisible de neuf ans, la somme de ses chiffres est également divisible par neuf.
@Xavier: Alors recommandez-vous de trouver la somme de tous les chiffres, puis de vérifier la divisibilité ?!
Aussi large que "10 000" signifie jusqu'à 6 caractères ou 10000 caractères?
Sur un système 32 bits, le plus grand nombre d'entiers pouvant être tenu dans un int mesure 2 147 483 648. Après cela, il déborde et les valeurs deviennent négatives. Vous devez utiliser quelque chose qui n'est pas un int
Mon approche serait de le conserver sous forme de chaîne, ajoutez une fonction qui prend une chaîne et ajoute les chiffres individuels pour déterminer si le nombre de la chaîne est divisible par 9, puis transmettez toutes les sous-séquences possibles, telles que des chaînes à cette fonction . Il y a probablement une meilleure façon de le faire, mais cela devrait fonctionner
@Ghost - finalement, bien sûr. Mais quand il y a
2 ^ 10000 Substrings possibles, finit par signifier un très vraiment longtemps. Il faut que ce soit un moyen d'optimiser cela beaucoup; Je ne peux pas penser à rien ...@Ghost: J'ai aimé votre idée. Mais comme Xavier dit que cela prendrait beaucoup de temps
Peut-être quelque chose avec MultiPrecision GNU pour les garder comme (genre de) entiers? Ce devoirs sont donc je ne sais pas quelles sont vos limites concernant les bibliothèques externes
@Xavierholt: Ouais, je ne pense pas qu'ils ne donnaient pas de problème de devoirs avec une intensité informatique de 2 ^ 10000. OP: Êtes-vous sûr qu'ils vous donneront une chaîne de 10000 chiffres?
@Wug :: D! C'est un problème Codechef ..!
Toutes les cordes sont-elles purement numériques ou y auront-il des cordes alphanumériques mixtes?
Codechef.com/aug12/problems/lukydriv