Retos - 004: Tres últimos dígitos

Nivel de dificultad aproximado (1 a 5): 4  

Enunciado del problema

Debes encontrar los tres últimos dígitos antes de la coma decimal para (3 + raíz(5)) elevado a n.

Por ejemplo, para n = 5, (3 + √5)5 = 3935.73982... La respuesta es 935.

Para n = 2, (3 + √5)2 = 27.4164079... La respuesta es 027.

El primer dato de entrada será la cantidad de valores que se van a analizar.

Nota: el programa no debe avisar al usuario con mensajes como "Introduzca un número". Debe leer directamente de consola en el formato que se muestra en el apartado "Entradas y salidas de ejemplo". La salida debe ser exactamente como se muestra en ese apartado. El programa debe comportarse bien con valores grandes, de al menos n=30 (sería deseable que también con valores por encima de 1.000.000).

Entradas y salidas de ejemplo 
Ejemplo de entrada
2
5
2
11
22
29

Salida correspondiente
Case #1: 935
Case #2: 027
Case #3: 943
Case #4: 527
Case #5: 135
Procedencia del reto

Original en: Google Code Jam 2008 - Fase 1A, problema C

Aporta tu solución

Aportar una solución

Tu nombre (si quieres que aparezca):
Tu web/blog (si quieres que incluyamos un enlace a ella):
Tu e-mail (no se mostrará; si quieres que te avisemos cuando esté publicado):
¿Eres humano? ¿Cuánto es 3 menos dos?
Lenguaje
Fuente:

Ejemplo de solución en C++ 

// Solucion al reto 004
// Autor: Anonymous (Omar)
// Aportado: 29-10-2014
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
int main()
{
    int cant,n,pent,a[100],i;
    float x,res;
    x=3+sqrt(5);
    // La version definitiva no debe escribir avisos en pantalla
    // cout<<"Ingrese la cantidad de veces: ";
    cin>>cant;
    int caso = 1;
    while(cant>0)
    {
        // La version definitiva no debe escribir avisos en pantalla
        //cout<<"Ingrese el exponente: ";
        cin>>n;
        res=pow(x,n);
        pent=floor(res);
        i=1;
        while(pent!=0)
        {
            a[i]=pent%10;
            pent=pent/10;
            i++;
        }
        if(i==3)
            a[3]=0;
        if(i==2)
            {a[2]=0;
            a[3]=0;}
        if(i==1)
        {
            a[1]=0;
            a[2]=0;
            a[3]=0;
        }
        cout << "Case #" << caso << ": ";
        cout <<a[3]<<a[2]<<a[1]<<endl;
        cant--;
        caso++;
    }
}
 

Ejemplo de solución en C# 

// Solución de ejemplo al reto 004
// Tres cifras antes de la coma de 3+raiz(5) elevado a N
// Nacho Cabanes, 2015
// Nota: sólo se comporta bien hasta n=39, desborda con números mayores
 
 
using System;
 
class Reto004
{
    static void Main()
    {
        int casos = Convert.ToInt32(Console.ReadLine());
 
        for (int c = 1; c <= casos; c++)
        {
            int n = int.Parse(Console.ReadLine());
 
            decimal x = 1;
            //decimal a = (decimal)(3 + Math.Sqrt(5.0));
            decimal a = 5.236067977499789696409173668731276235440618359611525724270897245410520925638m;
            for (int i = 1; i <= n; i++) 
                x = x * a;
 
            //Console.WriteLine(x);
            string numeroTexto = "00"+string.Format("{0:g}", x);
            int posicionComa = numeroTexto.IndexOf(',');
            string respuesta = numeroTexto.Substring(
                posicionComa-3,3);
            Console.WriteLine("Case #{0}: {1}", c, respuesta);
        }
    }
}
 

Ejemplo de solución en C# (2) 

// Solucion al reto 004
// Autor: Anónimo (marf_br)
// Aportado: 09-Ene-2014
 
// Nota: se aproxima, pero no es totalmente correcta: 
// da errores de redondeo a partir de 18 y desborda a partir de 26
 
using System;
 
class TresUltimosDigitos
{
    static void Main(string[] args)
    {
        int n;
        n = int.Parse(Console.ReadLine());
 
        int[] po = new int[n];
 
        for (int i = 0; i < n; i++)
        {
            po[i] = int.Parse(Console.ReadLine());
        }
 
        for (int i = 0; i < n; i++)
        {
            Console.WriteLine("Case #{0}: " + Mat(po[i]), (i+1));
        }
    }
 
    public static string Mat(int po)
    {
        string retorno = "";
        double result = Math.Pow((3 + Math.Sqrt(5)), po);
 
        //Obtener parte entera y convertirla a Integer
        int parteEntera = Convert.ToInt32(Math.Truncate(result)); 
        //Convertir a string con un formato de 10 digitos        
        string format = parteEntera.ToString("D10"); 
 
        char[] digitos = format.ToCharArray();
 
        for (int i = 7; i < 10; i++)
        {
            retorno += digitos[i];
        }
 
        return retorno;
    }
}