J'essayais de résoudre ce problème sur hackerrank.

On vous donne quatre nombres entiers : N,S,P,Q. Vous allez les utiliser afin de créer la séquence avec le pseudo-code suivant.

a[0] = S (modulo 2^31)
for i = 1 to N-1
a[i] = a[i-1]*P+Q (modulo 2^31) 

Votre tâche consiste à calculer le nombre d'entiers distincts dans la séquence.

Sample Input

3 1 1 1 
Sample Output

3

Constraints

1<= N <= 10^8
0<= S,P,Q < 2^31

Et c'était ma solution en c++.. La plupart du temps, j'avais des erreurs de segmentation.. Je sais que cela était censé être résolu à l'aide de tableaux de bits.. mais je voulais savoir pourquoi cela ne fonctionnait pas.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
unsigned long long n,s,p,q;

cin >> n >> s >> p >> q;

//declaring array to hold sequence
unsigned long long a[n];

// for loop termination
bool termination_check = true;

//initializing sequence
//s<2^31 hence, s modulo 2^31 is always s
a[0] = s;

//creating sequence
for(int i=1;i<n;i++){

    //calculating next term of sequence..
    a[i] = (a[i-1]*p)+q;

    //since a[i] modulo 2^31 is a[i] when a[i] < 2^31
    if(a[i]>=pow(2,31)){
       a[i] = a[i]%31;

        //when the current term matches with any of previous terms of sequence, then the
        //terms just repeat after that (since p and q are constants)
        for(int j=0;j<i;j++){
            if(a[i]==a[j]){
                cout <<i << endl;

                //i was trying to use break but dont know why, it did not work
                termination_check = false;
                break;
                break;
            }
        }
    }
}

//if there was no termination of loop then all the terms are distinct
if(termination_check){
printf("%llu \n", n);
}

/* Enter your code here. Read input from STDIN. Print output to STDOUT */   
return 0;
}
-1
manji369 27 juin 2016 à 17:03

2 réponses

Meilleure réponse

Oui, vous pouvez avoir des tableaux unsigned long long en C++. Mais ce que vous avez n'est pas un tableau : unsigned long long a[n]; requiert que n soit une constante. (Ce serait différent en C, mais vous écrivez du C++).

Qu'il fonctionne toujours est une extension de compilateur qui vous permet de mélanger C et C++, mais le comportement n'est pas défini. La gestion des erreurs en particulier semble faire défaut.

0
MSalters 28 juin 2016 à 10:13

Cette réponse concernait la version précédente du code. Le code a maintenant été édité à l'intérieur de la question (j = i et i = n remplacés par deux pauses)

Voir ce qui se passe lorsque vous rencontrez le cas

a[i] == a[j]

Vous réglez j sur i, puis i sur n. Mais i est plus petit que n, donc la déclaration j<i reste vraie. Votre boucle for continue alors de s'exécuter, votre programme essaie donc d'évaluer

a[i] == a[j]

Avec les nouvelles valeurs que vous avez attribuées, vous demandez en fait si

a[n] == a[i]

Mais si votre tableau a était un tableau de taille n, cela conduit à un comportement indéfini.

0
Irminsul 28 juin 2016 à 10:13