CyM2005, Ronda Nacional, Problema 5

CyM2005, Ronda Nacional, Problema 5

Rodrigo Belfiore 09 Nov 2007 18:05

Bueno el 5 es un problema porque no puedo guardar un númeo tan grande en una variable numérica, pero como si o si queria hacer algo, usé string =S fui tomando de a 4 números e iba dividiendo por 3 el numero A que al principio era 20052005…2005. y despues era el resultado de la division (entera), el resto (d) lo muestro y si es 1 el contador (z) aumenta en 1. Asi me dio, 9 y 2005.

dim a as string
dim b as string
dim c as string
dim d as string
for i = 1 to 708
a+="2005"
next
z=0
do while val(a) >= 1
    c=""
    d=""
    for i = 0 to len(a)/4-1
        b=d+mid(a,4*i+1,4)
        c+=mid("0000",1,len(mid(a,4*i+1,4))-len(str(val(b) \ 3)))+str(val(b) \ 3)
        d=str(val(b) mod 3)
    next
    print d;
    if d = "1" then z+=1
    a=c
loop
print z
sleep
'RTA: 9; 2005

Última edición el 10 Nov 2007 20:27 por Rodrigo Belfiore Mostrar más

Re: CyM2005, Ronda Nacional, Problema 5

pabloh 10 Nov 2007 00:54

Para empezar, la respuesta es correcta, y el programa, que como hace unas cuentas ligeramente complicadas no estoy 100% seguro, parece correcto.

Lo que hace tu programa, tal como decís, es dividir sucesivamente el número dado por 3 e ir revisando los restos. Éste es el algoritmo que nos enseñan en el colegio para pasar un número a una base distinta de 10. Quiero repasar tus cuentas antes de darte una alternativa.

Básicamente (sea $B=10000$) tu algoritmo va calculando

(1)

\begin{eqnarray} \lefteqn{2005 \cdot B^{708} + 2005 \cdot B^{707} + 2005 \cdot B^{706} + \ldots = } \\ & = & (3 \cdot 668 + 1) \cdot B^{708} + 2005 \cdot B^{707} + 2005 \cdot B^{706} + \ldots \\ & = & 3 \cdot 668 \cdot B^{708} + (1 \cdot B + 2005) \cdot B^{707} + 2005 \cdot B^{706} + \ldots \\ & = & 3 \cdot 668 \cdot B^{708} + (3 \cdot 4001 + 2) \cdot B^{707} + 2005 \cdot B^{706} + \ldots \\ & = & 3 \cdot (668 \cdot B^{708} + 4001 \cdot B^{707}) + (2 \cdot B + 2005) \cdot B^{706} + \ldots \\ & \vdots & \\ & = & 3 \cdot (668 \cdot B^{708} + 4001 \cdot B^{707} + 7335 \cdot B^{706} + \ldots) + 0 \end{eqnarray}

Por lo tanto la cifra de las unidadas (en base 3), que es igual el resto de dividir por 3, es 0.

La cosa se puede repetir, pero tu programa en realidad va tomando de a 4 cifras. Usar strings no es terriblemente malo, pero no es necesario. La cuenta (1) muestra que se puede usar un array (arreglo, vector).

---

En cuanto al otro camino… En la escuela nos enseñan también a convertir a base 10. ¿Cómo es? Simplemente hacer la cuenta:

(2)

\begin{eqnarray} \lefteqn{(201011120120212001201210)_3 = } \\ & = & 0 \cdot 3^{0} + 1 \cdot 3^{1} + 2 \cdot 3^{2} + 1 \cdot 3^{3} + 0 \cdot 3^{4} + \ldots + 2 \cdot 3^{23} \\ & = & 0 + 3 + 2 \cdot 9 + 27 + 0 + \ldots + 2 \cdot 94143178827 \\ & = & 200520052005 \end{eqnarray}

Pero… la cuenta (2) está en base 10. ¿Quién nos obliga? Nadie. Es más, la computadora hace las cuentas en base 2, y convierte a base 10 sólo para mostrar. Entonces, la alternativa es hacer el cambio de base “multiplicando” haciendo las cuentas en base 3. Normalmente es más fácil hacer multiplicación y suma de números largos que división.