Comment vérifier la division par 7 du grand nombre en C ++?
Je dois vérifier si le nombre donné est divisible par 7, ce qui se fait habituellement en faisant quelque chose comme n % 7 == 0 , mais le problème est que ce nombre peut avoir jusqu’à 100000000, ce qui ne rentre même pas long long .
Une autre contrainte est que je ne dispose que de quelques kilo-octets de mémoire, donc je ne peux pas utiliser de tableau.
Je m’attends à ce que le nombre soit sur stdin et la sortie à 1/0.
Ceci est un exemple
- Grand nombre en C ++
- Bibliothèque d’entiers 128 bits la plus rapide
- Gérer des entiers de longueur arbitraire en C ++
- Une bonne implémentation de base de la classe BigInt en C ++
- Bibliothèque Bigint (bigbit)
34123461273648125348912534981264376128345812354821354127346821354982135418235489162345891724592183459321864592158 0
Il devrait être possible d’utiliser seulement environ 7 variables entières et cin.get() . Cela devrait également être fait en utilisant uniquement des bibliothèques standard.
- C ++ traitant de très grands entiers
- Bibliothèque de grands nombres en c ++
- Gestion de grands nombres en C ++?
Pensez à la division sur papier. Vous regardez le ou les deux premiers chiffres et notez le multiple de sept le plus proche, le rest, et ainsi de suite. Vous pouvez le faire sur n’importe quel nombre de longueur abstraite, car vous n’avez pas à charger le nombre entier en mémoire.
vous pouvez utiliser une règle connue sur la division par 7 qui dit: regroupez chaque 3 chiffres en commençant par la droite et commencez à les soustraire et à les append alternativement, la divisibilité du résultat par 7 est identique à celle du nombre original:
ex.:
testing 341234612736481253489125349812643761283458123548213541273468213 549821354182354891623458917245921834593218645921580 (580-921+645-218+593-834+921-245+917-458+623-891+354-182 +354-821+549-213+468-273+541-213+548-123+458-283+761-643 +812-349+125-489+253-481+736-612+234-341 = 1882 ) % 7 != 0 --> NOK!
Il existe d’autres alternatives à cette règle, toutes faciles à mettre en œuvre.
La plupart des règles de divisibilité par sept fonctionnent au niveau des chiffres, vous ne devriez donc avoir aucun problème à les appliquer à votre chaîne.
Vous pouvez calculer la valeur du nombre modulo 7.
Autrement dit, calculez n = (10 * n + d)% 7 pour chaque chiffre d et n jusqu’à présent.
Ceci a l’avantage de fonctionner indépendamment du diviseur 7 ou de la base 10.
Je commencerais par soustraire un grand nombre divisible par 7.
Des exemples de nombres qui sont divisibles par 7 incluent 700, 7000, 70000, 140000000, 42000000000, etc.
Dans l’exemple particulier que vous avez donné, essayez de soustraire 280000000000 (un certain nombre de zéros) 0000.
Encore plus facile à implémenter, soustrayez à plusieurs resockets le plus grand nombre possible, comme 70000000000 (un certain nombre de zéros) 0000.
Vous pouvez calculer la valeur du nombre modulo 7.
Autrement dit, calculez n = (10 * n + d)% 7 pour chaque chiffre d et n jusqu’à présent.
Ceci a l’avantage de fonctionner indépendamment du diviseur 7 ou de la base 10.
J’ai résolu ce problème exactement de la même manière sur l’un des concours de programmation. Voici le fragment de code dont vous avez besoin:
int sum = 0; while (true) { char ch; cin>>ch; if (ch<'0' || ch>'9') break; // Reached the end of stdin sum = sum*10; // The previous sum we had must be multiplied sum += (int) ch; sum -= (int) '0'; // Remove the code to get the value of the digit sum %= 7; } if (sum==0) cout<<"1"; else cout<<"0";
Ce code fonctionne grâce à de simples règles d'arithmétique modulaire. Cela fonctionne également non seulement pour 7, mais pour n'importe quel diviseur réellement.
Étant donné que j’ai récemment travaillé sur la division des nombres, je vais insister sur le fait que pour obtenir des nombres spécifiques (ce dont vous aurez besoin avec certaines des autres réponses), pensez à la division entière et à l’utilisation du module pour en extraire les chiffres.
Si vous aviez un nombre inférieur, disons 123 , comment obtiendriez-vous le 1 , le 2 et le 3 ? Surtout que vous travaillez en base 10 …
N = abc
Un algorithme simple permet de vérifier si un nombre à trois chiffres est un multiple de 7:
Remplacez a par x et ajoutez-le à bc, étant x les dizaines d’un nombre à deux chiffres multiple de 7 dont les centaines sont a.
N = 154; x = 2; 2 + 54 = 56; 7 | 56 et 7 | 154
N = 931; x = 4; 4 + 31 = 35; 7 | 35 et 7 | 931
N = 665; x = 5; 5 + 65 = 70; 7 | 70 et 7 | 665
N = 341; x = 6; 6 + 41 = 47; 7ł47 et 7ł341
Si N est formé de différentes périodes, l’additif inverse du résultat d’une période doit être ajouté à la sum de la période suivante, de la manière suivante:
N = 341,234
6 + 41 = 47; – 41 mod 7 ≡ 1; 1 + 4 + 34 = 39; 7ł39 et 7łN
N = 341.234.612.736.481
Le résultat pour 341.234 est 39. Suite à ce résultat, nous avons:
-39 mod 7 ≡ 3; 3 + 5 + 6 + 1 + 2 + 1 = 18; – 18 mod 7 ≡ 3; 3 + 0 + 36 = 39; – 39 mod 7 ≡ 3; 3 + 1 + 81 = 85; 7ł85 et 7łN
Cette règle peut être appliquée entièrement par calcul mental et est très rapide. Il a été dérivé d’une autre règle que j’ai créée en 2.005. Cela fonctionne pour les nombres de n’importe quelle grandeur et pour la divisibilité par 13.
Voici un moyen simple de vérifier la divisibilité par 7:
Multipliez chaque chiffre commençant à la droite du nombre donné par le chiffre correspondant dans ce motif [1,3,2,6,4,5] (ou [1,3,2, -1, -3, -2 ]). Répétez le motif si nécessaire. Si la sum des produits est divisible par 7, le nombre original le est également.
Exemple: 2016 (6 * 1 + 1 * 3 + 0 * 2 + 2 * 6 = 21) est divisible par 7 car 21 est divisible par 7.
Voir les règles de divisibilité .
Au début, prenez ce grand nombre dans la chaîne, puis additionnez chaque chiffre de la chaîne. lors de la dernière vérification si (sum% 7 == 0)
Code:
#include using namespace std; int main() { long long int n,i,j,sum,k; sum=0; ssortingng s; cin>>s; for(i=0;i