Witam,
mam takie zadanie:
Dany jest wielomian W(x). Należy obliczyć wszystkie wartości wielomianu W dla argumentów 0, 1, 2, ..., 9998, 9999 i stwierdzić, które wartości się powtarzają. Wartości wielomianu należy obliczać modulo 229.
No i oto moja próba rozwiązania tego, ale niezbyt skuteczna...
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int hash_me(int polynomial_value);
int main()
{
int polynomial_grade = 0;
cin >> polynomial_grade;
polynomial_grade++;
int grade = polynomial_grade;
int *coefficients = new int [polynomial_grade];
while(polynomial_grade--)
{
cin >> coefficients[polynomial_grade];
}
vector<int>poly_values[953];
vector<int>poly_repeats;
int total_value;
int repeats = 0;
for(int x = 0; x < 10000; x++)
{
total_value = coefficients[0];
for(int i = 1 ; i < grade ; i++)
total_value += coefficients[i] * x; //obliczanie wartosci wielomianu
total_value = total_value % 536870912; //modulo 2^(29)
int hash_key = hash_me(total_value); //biore hash
poly_values[hash_key].push_back(total_value); //pod tym hashem zapisuje wartosc
}
for(int i = 0; i < 953; i++) //sprawdzam wszystkie vectory
{
sort(poly_values[i].begin() , poly_values[i].end()); //sortuje
for(int y = 0; y < poly_values[i].size() - 1; y++) //sprawdzam pokolei
{
if(poly_values[i][y] == poly_values[i][y + 1]) //jezeli znalazlem dwa takei same elementy
{
poly_repeats.push_back(poly_values[i][y]); //wrzuc do vectora powtorek
repeats++; //dodaj powtorke
}
}
}
cout << repeats << endl;
for(int i = 0; i < poly_repeats.size(); i++)
{
cout << poly_repeats[i] << endl;
}
return 0;
}
int hash_me(int polynomial_value)
{
return (polynomial_value % 13469) % 953;
}
Ogólnie to czuję, że to słaby pomysł... (nie działa) Może ktoś mnie pokierować w dobrą stronę?