Algorithme pour trouver les Numéros de la Chance

Excellente solution OleGG, Mais ton code n'est pas optimisé. J'ai fait les changements suivants à votre code,

1. Il ne nécessite pas de passer par 9*9*i pour k dans count_lucky fonction, parce que pour 10000 cas, il irait à de nombreuses reprises, à la place j'ai réduit cette valeur à travers de début et de fin.

2. j'ai utilisé sna tableau pour stocker les résultats intermédiaires. Il pourrait ne pas ressembler à beaucoup, mais plus de 10000 cas, c'est le facteur majeur qui réduit le temps.

J'ai testé ce code, et il a passé tous les cas de test. Voici le code modifié:

    #include <stdio.h>
const int MAX_LENGTH = 18;
const int MAX_SUM = 162;
const int MAX_SQUARE_SUM = 1458;
int primes[1460];
unsigned long long dyn_table[20][164][1460];
//changed here.......1
unsigned long long ans[19][10][164][1460];  //about 45 MB
int start[19][163];
int end[19][163];
//upto here.........1
void gen_primes() {
for (int i = 0; i <= MAX_SQUARE_SUM; ++i) {
primes[i] = 1;
}
primes[0] = primes[1] = 0;
for (int i = 2; i * i <= MAX_SQUARE_SUM; ++i) {
if (!primes[i]) {
continue;
}
for (int j = 2; i * j <= MAX_SQUARE_SUM; ++j) {
primes[i*j] = 0;
}
}
}
void gen_table() {
for (int i = 0; i <= MAX_LENGTH; ++i) {
for (int j = 0; j <= MAX_SUM; ++j) {
for (int k = 0; k <= MAX_SQUARE_SUM; ++k) {
dyn_table[i][j][k] = 0;
}
}
}
dyn_table[0][0][0] = 1;
for (int i = 0; i < MAX_LENGTH; ++i) {
for (int j = 0; j <= 9 * i; ++j) {
for (int k = 0; k <= 9 * 9 * i; ++k) {
for (int l = 0; l < 10; ++l) {
dyn_table[i + 1][j + l][k + l*l] += dyn_table[i][j][k];
}
}
}
}
}
unsigned long long count_lucky (unsigned long long maxp) {
unsigned long long result = 0;
int len = 0;
int split_max[MAX_LENGTH];
while (maxp) {
split_max[len] = maxp % 10;
maxp /= 10;
++len;
}
int sum = 0;
int sq_sum = 0;
unsigned long long step_result;
unsigned long long step_;
for (int i = len-1; i >= 0; --i) {
step_result = 0;
int x1 = 9*i;
for (int l = 0; l < split_max[i]; ++l) {
//changed here........2
step_ = 0;
if(ans[i][l][sum][sq_sum]!=0)
{
step_result +=ans[i][l][sum][sq_sum];
continue;
}
int y = l + sum;
int x = l*l + sq_sum;
for (int j = 0; j <= x1; ++j) {
if(primes[j + y])
for (int k=start[i][j]; k<=end[i][j]; ++k) {
if (primes[k + x]) {
step_result += dyn_table[i][j][k];
step_+=dyn_table[i][j][k];
}
}
}
ans[i][l][sum][sq_sum] = step_;
//upto here...............2
}
result += step_result;
sum += split_max[i];
sq_sum += split_max[i] * split_max[i];
}
if (primes[sum] && primes[sq_sum]) {
++result;
}
return result;
}
int main(int argc, char** argv) {
gen_primes();
gen_table();
//changed here..........3
for(int i=0;i<=18;i++)
for(int j=0;j<=163;j++)
{
for(int k=0;k<=1458;k++)
if(dyn_table[i][j][k]!=0ll)
{
start[i][j] = k;
break;                               
}
for(int k=1460;k>=0;k--)
if(dyn_table[i][j][k]!=0ll)
{
end[i][j]=k;
break;                               
}
}
//upto here..........3
int cases = 0;
scanf("%d",&cases);
for (int i = 0; i < cases; ++i) {
unsigned long long a, b;
scanf("%lld %lld", &a, &b);
//changed here......4
if(b == 1000000000000000000ll)
b--;
//upto here.........4
printf("%lld\n", count_lucky(b) - count_lucky(a-1));
}
return 0;
}

Explication:

gen_primes() et gen_table() sont assez explicites.

count_lucky() fonctionne de la manière suivante:

diviser le nombre de split_max[], juste le stockage unique de chiffres pour les unes, des dizaines, des centaines, etc. les positions.
L'idée est la suivante: supposons que split_map[2] = 7, donc nous avons besoin de calculer le résultat pour

1 dans des centaines de position et tous les de 00 à 99.

2 dans des centaines de position et tous les de 00 à 99.

.
.

7 dans des centaines de position et tous les de 00 à 99.

c'est fait(dans l de la boucle) en termes de somme des chiffres et de la somme des carrés des chiffres qui a été precalcutaled.
pour cet exemple: somme varie de 0 à 9*i & somme des carré varie de 0 à 9*9* - je...c'est fait en j et k les boucles.
Ceci est répété pour toutes les longueurs je boucle

C'était l'idée de OleGG.

Pour l'optimisation suivant est considéré comme:

1. son inutile d'exécuter la somme des carrés de 0 à 9*9*i comme pour le particulier, les sommes des chiffres qu'il n'irait pas jusqu'à la gamme complète. Comme si i = 3 et la somme est égale à 5, la somme des carrés ne serait pas varier de 0 à 9*9*3.Cette partie est stockée dans des start[] et à la fin[] tableaux à l'aide de valeurs précalculées.

2. valeur pour un nombre donné de chiffres et de particulier chiffre le plus significatif de la position de numéro et jusqu'à somme et jusqu'à la somme des carrés isstored pour la mémorisation. Ses trop long, mais son environ 45 MO.
   Je crois que ça pourrait être encore optimisé.

Au lieu d'énumérer l'espace des nombres, l'énumération des différents "signatures" des chiffres qui ont de la chance. et puis l'impression de toutes les differnet combinaison de ceux-ci.

Cela peut être fait avec trivial retour en arrière:

#define _GNU_SOURCE
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#define bitsizeof(e)   (CHAR_BIT * sizeof(e))
#define countof(e)     (sizeof(e) / sizeof((e)[0]))
#define BITMASK_NTH(type_t, n) ( ((type_t)1) << ((n) & (bitsizeof(type_t) - 1)))
#define OP_BIT(bits, n, shift, op) \
((bits)[(unsigned)(n) / (shift)] op BITMASK_NTH(typeof(*(bits)), n))
#define TST_BIT(bits, n)    OP_BIT(bits, n, bitsizeof(*(bits)), &  )
#define SET_BIT(bits, n)    (void)OP_BIT(bits, n, bitsizeof(*(bits)), |= )
/* fast is_prime {{{ */
static uint32_t primes_below_1M[(1U << 20) / bitsizeof(uint32_t)];
static void compute_primes_below_1M(void)
{
SET_BIT(primes_below_1M, 0);
SET_BIT(primes_below_1M, 1);
for (uint32_t i = 2; i < bitsizeof(primes_below_1M); i++) {
if (TST_BIT(primes_below_1M, i))
continue;
for (uint32_t j = i * 2; j < bitsizeof(primes_below_1M); j += i) {
SET_BIT(primes_below_1M, j);
}
}
}
static bool is_prime(uint64_t n)
{
assert (n < bitsizeof(primes_below_1M));
return !TST_BIT(primes_below_1M, n);
}
/* }}} */
static uint32_t prime_checks, found;
static char     sig[10];
static uint32_t sum, square_sum;
static void backtrack(int startdigit, int ndigits, int maxdigit)
{
ndigits++;
for (int i = startdigit; i <= maxdigit; i++) {
sig[i]++;
sum        += i;
square_sum += i * i;
prime_checks++;
if (is_prime(sum) && is_prime(square_sum)) {
found++;
}
if (ndigits < 18)
backtrack(0, ndigits, i);
sig[i]--;
sum        -= i;
square_sum -= i * i;
}
}
int main(void)
{
compute_primes_below_1M();
backtrack(1, 0, 9);
printf("did %d signature checks, found %d lucky signatures\n",
prime_checks, found);
return 0;
}

Quand je le lance il ne:

$ time ./lucky
did 13123091 signature checks, found 933553 lucky signatures
./lucky  0.20s user 0.00s system 99% cpu 0.201 total

Au lieu de trouvé++ vous souhaitez générer toutes les permutations distinctes de chiffres que vous pouvez construire avec ce numéro. J'ai aussi précalculer la première 1M de nombres premiers jamais.

Je n'ai pas vérifié si le code est correct à 100%, vous pouvez avoir à le corriger un peu. Mais le rought idée est là, et je suis en mesure de générer toutes les chance de permutation en dessous de 0,2 s (même sans les bugs, il ne devrait pas être plus de deux fois plus lent).

Et bien sûr, vous voulez générer les permutations que de vérifier Un <= B. Vous pouvez ignorer la génération des partitions qui ont plus de chiffres que de B ou de moins que trop. De toute façon vous pouvez améliorer sur mon idée générale à partir d'ici.

(Note: Le texte de présentation au début parce que j'ai couper et de coller le code que j'ai écrit pour le projet euler, d'où la très rapide is_prime qui travaille pour le N <= 1M 😉 )

Je viens de résoudre ce problème.

C'est juste un problème de Programmation Dynamique. Prendre DP[n](sum-square_sum) que le DP de la fonction, et DP[n](sum-square_sum) est le nombre de tous les nombres dont les chiffres est inférieur ou égal à n, avec la somme et square_sum de chiffres du nombre est respectivement représentés par la somme et l'square_sum. Par exemple:

DP[1](1-1) = 1      # only 1 satisfies the condition                        
DP[2](1-1) = 2      # both 1 and 10 satisfies the condition                        
DP[3](1-1） = 3      # 1 10 100
DP[3](2-4） = 3      # 11 110 101

Puisque l'on peut aisément comprendre la première DP DP état[1][..][..], il est:

(0-0) => 1     (1-1) => 1    (2-4) => 1     (3-9) => 1     (4-16) => 1    
(5-25) => 1    (6-36) => 1   (7-49) => 1    (8-64) => 1    (9-81) => 1

alors nous pouvons déduire DP[1] à partir de DP[1], puis DP[3] ... DP[18]
le déduire ci-dessus est faite par le fait que chaque fois, quand n augmente de 1, par exemple à partir de DP[1] pour DP[2], nous avons obtenu un nouvel chiffres (0..9), et l'ensemble des (somme, square_sum) paire (c'est à dire DP[n]) doit être mis à jour.

Enfin, nous pouvons parcourir le DP[18] est réglé et le nombre des chiffres qui ont de la chance.

Bien, que diriez-vous le temps et l'espace de la complexité de l'algorithme ci-dessus?
Comme nous le savons somme <= 18*9=162, square_sum <= 18*9*9 = 1458, ainsi, l'ensemble de (somme, square_sum) paire
(c'est à dire DP[n]) est très faible, moins de 162*1458=236196, en fait, il est beaucoup plus petit que 236196;
Le fait est: mon ruby programme de comptage de tous les numéros de la chance entre 0 et 10^18 se termine en moins de 1s.

ruby lucky_numbers.rb  0.55s user 0.00s system 99% cpu 0.556 total

et je test mon programme en écrivant une fonction de test en utilisant la force brute de l'algorithme, et c'est juste pour les nombres inférieurs à 10^7 .

Je n'ai pas analysé avec soin votre solution actuelle, mais cela pourrait l'améliorer:

Depuis l'ordre des chiffres n'a pas d'importance, vous devez passer par toutes les combinaisons possibles de chiffres de 0 à 9 de longueur 1 à 18, garder une trace de la somme de chiffres et de leurs places et l'ajout d'un chiffre à un moment, en utilisant le résultat du calcul précédent.

Donc, si vous savez que pour 12 somme des chiffres est 3 et de places est de 5, examinez les chiffres
120, 121, 122, etc... et de calculer des sommes pour eux trivialement à partir de la 3 et la 5 pour 12.

J'ai essayé de trouver une solution à l'aide de Pierre de la méthode d'énumération, mais n'est jamais venu avec suffisamment rapide façon de compter les permutations. OleGG de la méthode de comptage est très intelligent, et les pirates du optimisations sont nécessaires pour les rendre assez rapidement. Je suis venu avec une légère amélioration, et une solution à un problème grave.

Tout d'abord, l'amélioration: vous n'avez pas à parcourir toutes les sommes et squaresums un par un pour vérifier les nombres premiers dans pirate's j et k de la boucle. Vous avez (ou peut facilement générer une liste de nombres premiers. Si vous utilisez les autres variables à comprendre que les nombres premiers sont dans la gamme, vous pouvez tout simplement par le biais de la liste des nombres premiers pour la somme et l'squaresum. Un tableau de nombres premiers et une table de recherche pour rapidement déterminer à partir de quel indice le premier >= un nombre est à est utile. Cependant, ce n'est probablement qu'une assez légère amélioration.

Le gros problème, c'est avec des pirates du sna tableau de cache. Il n'est pas 45 MO comme l'a prétendu; avec la version 64 bits d'entrées, c'est quelque chose comme 364MB. C'est à l'extérieur (en cours) admis les limites de la mémoire en C et Java. Elle peut être réduite à 37MB par se débarrasser de la "l" de dimension, ce qui est inutile et mal les performances du cache de toute façon. Vous êtes vraiment intéressés par la mise en cache de compte pour l + somme et l*l + squaresum, pas l, somme, et squaresum individuellement.