2010-03-16 1 views
4

J'essaie de résoudre le problème Code secret sur SPOJ, et c'est évidemment un problème de maths.CODE1 à SPOJ - ne peut pas le résoudre

The full problem

Pour ceux qui sont paresseux pour aller lire, il est comme ça:

a0, a1, a2, ..., an - sequence of N numbers 
B - a Complex Number (has both real and imaginary components) 
X = a0 + a1*B + a2*(B^2) + a3*(B^3) + ... + an*(B^n) 

Donc, si vous êtes donné B et X, vous devriez trouver a0, a1, ..an. Je ne sais pas comment ni par où commencer, parce que N n'est pas connu, seulement X et B.

Le problème n'est pas aussi simple que d'exprimer un nombre dans une base B, car B est un nombre complexe.

Comment peut-il être résolu?

+1

En fait, le problème est indiqué comme un problème de programmation sur le site Web. Vérifiez-le. – Grembo

Répondre

7

La clé est que a0 .. an ne sont pas des nombres arbitraires, ils sont entiers (sinon, cela ne serait pas possible en général). On vous donne le numéro X, et on vous demande de l'exprimer en base B. Pourquoi ne commencez-vous pas en travaillant quelques exemples pour une valeur spécifique de B?

Si je vous demandais d'écrire 17 dans la base 2, seriez-vous capable de faire cela? Pouvez-vous trouver un moyen de généraliser l'algorithme que vous utilisez à des bases autres que 2?

+0

Pouvez-vous clarifier votre suggestion concernant l'expression en base B? Pour votre ex, je ne sais pas comment écrire 17 en base 2? – VaioIsBorn

+0

@VaioIsBorn - Voici quelques informations sur la conversion entre les bases de nombres, cela devrait aussi vous aider à voir ce que le problème demande: http://www.brainjammer.com/math/bases/ et http: //www.math.grin. edu/~ rebelsky/Cours/152/97F/Lectures/student-binary – IVlad