Retos C/C++

[ace332]

disculpame compañero pero me parece que no leiste bien el enunciado del problema :

Calcular el factorial de un número n, 0<=n<=100

El programa que pusiste sólo calcula bien hasta el factorial de 12.

Saludos.

PD: Si gustan pongo la solución y pasamos al reto planteado por Og 

[ghastlyX]

He reaprovechado un código que hice hace un tiempo que multiplica usando Karatsuba, por lo que el código es largo y feo. Si alguien lo prefiere dejo una versión nueva y más legible sin usar Karatsuba. De hecho, Karatsuba sólo se usa si los dos números a multiplicar son suficiente grandes (unos 100 dígitos) en mi código, pero lo dejo por si a alguien le interesa.

Código (cpp) [Seleccionar] Expandir

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

typedef vector<long long> VL;

VL mult(VL& a, int i1, int f1, VL& b, int i2, int f2) {
    if (i1 > f1 or i2 > f2) return VL(1,0);
    if (f1 >= a.size()) return mult(a, i1, a.size() - 1, b, i2, f2);
    if (f2 >= b.size()) return mult(a, i1, f1, b, i2, b.size() - 1);
    if (i1 >= a.size() or i2 >= b.size()) return VL(1,0);
    int n = f1 - i1 + 1, m = f2 - i2 + 1;
    VL c(max(n,m)*2 + 1, 0);
    for (int i = i1; i <= f1; ++i) {
        for (int j = i2; j <= f2; ++j) {
            c[i - i1 + j - i2] += (a[i]*b[j]);
            c[i - i1 + j - i2 + 1] += (c[i - i1 + j - i2]/1000000000);
            c[i - i1 + j - i2] %= 1000000000;
        }
    }
    int pos = c.size() - 1;
    while (pos > 0 and c[pos--] == 0) c.pop_back();
    return c;
}

VL suma(VL& a, int i1, int f1, VL& b, int i2, int f2) {
    if (i1 > f1 or i1 >= a.size()) {
        VL cero(1,0);
        return suma(cero, 0, 0, b, i2, f2);
    }
    if (i2 > f2 or i2 >= b.size()) {
        VL cero(1, 0);
        return suma(a, i1, f1, cero, 0, 0);
    }
    if (f1 >= a.size()) return suma(a, i1, a.size() - 1, b, i2, f2);
    if (f2 >= b.size()) return suma(a, i1, f1, b, i2, b.size() - 1);
    int n = f1 - i1 + 1, m = f2 - i2 + 1;
    VL c(n + m + 2, 0);
    int i = i1, j = i2, k = 0;
    while (i <= f1 and j <= f2) {
        c[k] += (a[i] + b[j]);
        c[k + 1] += (c[k]/1000000000);
        c[k] %= 1000000000;
        ++i; ++j; ++k;
    }
    while (i <= f1) {
        c[k] += a[i];
        c[k + 1] += (c[k]/1000000000);
        c[k] %= 1000000000;
        ++i; ++k;
    }
    while (j <= f2) {
        c[k] += b[j];
        c[k + 1] += (c[k]/1000000000);
        c[k] %= 1000000000;
        ++j; ++k;
    }
    int pos = c.size() - 1;
    while (pos > 0 and c[pos--] == 0) c.pop_back();
    return c;
}
   
VL resta(VL& a, int i1, int f1, VL& b, int i2, int f2) {
    VL c;
    c = a;
    for (int i = i2; i <= f2; ++i) {
        c[i] -= b[i];
        while (c[i] < 0) {
            c[i] += 1000000000;
            c[i + 1]--;
        }
    }
    int pos = c.size() - 1;
    while (pos > 0 and c[pos--] == 0) c.pop_back();
    return c;
}

VL karatsuba(VL& a, int i1, int f1, VL& b, int i2, int f2) {
    if (i1 > f1 or i2 > f2) return VL(1,0);
    if (f1 >= a.size()) return karatsuba(a, i1, a.size() - 1, b, i2, f2);
    if (f2 >= b.size()) return karatsuba(a, i1, f1, b, i2, b.size() - 1);
    if (i1 >= a.size() or i2 >= b.size()) return VL(1,0);
    int p = f1 - i1 + 1, m = f2 - i2 + 1;
    if (min(p, m) <= 10) return mult(a, i1, f1, b, i2, f2);
    int n = max(p, m);
    VL c1, c2, c3, x, y;
    int mit = n/2;
    c1 = karatsuba(a, i1 + mit, f1, b, i2 + mit, f2);
    c3 = karatsuba(a, i1, i1 + mit - 1, b, i2, i2 + mit - 1);
    x = suma(a, i1, i1 + mit - 1, a, i1 + mit, f1);
    y = suma(b, i2, i2 + mit - 1, b, i2 + mit, f2);
    c2 = karatsuba(x, 0, x.size() - 1, y, 0, y.size() - 1);
    c2 = resta(c2, 0, c2.size() - 1, c1, 0, c1.size() - 1);
    c2 = resta(c2, 0, c2.size() - 1, c3, 0, c3.size() - 1);
    VL res(2*n + 3, 0);
    for (int i = 0; i < c1.size(); ++i) {
        res[i + 2*mit] += c1[i];
        res[i + 2*mit + 1] += (res[i + 2*mit]/1000000000);
        res[i + 2*mit] %= 1000000000;
    }
    for (int i = 0; i < c2.size(); ++i) {
        res[i + mit] += c2[i];
        res[i + mit + 1] += (res[i + mit]/1000000000);
        res[i + mit] %= 1000000000;
    }
    for (int i = 0; i < c3.size(); ++i) {
        res[i] += c3[i];
        res[i + 1] += (res[i]/1000000000);
        res[i] %= 1000000000;
    }
    int pos = res.size() - 1;
    while (pos > 0 and res[pos--] == 0) res.pop_back();
    return res;
}

string str(long long x) {
    string s;
    do {
        s += char(x%10 + '0');
        x /= 10;
    } while(x > 0);
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    int n;
    cin >> n;
    VL res(1,1);
    for (int i = 1; i <= n; ++i) {
        VL a(1,i);
        VL c;
        c = karatsuba(a, 0, a.size() - 1, res, 0, res.size() - 1);
        res = c;
    }
    cout << res[res.size() - 1];
    for (int i = res.size() - 2; i >= 0; --i) {
        string s = str(res[i]);
        cout << string(9 - s.size(), '0') << s;
    }
    cout << endl;
}


Ahora pasemos al reto de Og. y a ver si alguien se anima, que es una dinámica sencillita.

[ace332]

Solved 

Código [Seleccionar] Expandir



#include <stdio.h>
#include <string.h>

#define MAX_TAM_BASE 1000

#define max(a,b) (((a)>(b))?(a):(b))

int main(void)
{
  int N,i,j,maxmax=0,maximos[MAX_TAM_BASE];
 
  scanf("%d",&N);
  memset(maximos,0,sizeof(int)*MAX_TAM_BASE);
  for(i=0;i<N;i++)
  {
    int temp1=0,temp2,piedras;
    for(j=0;j<=i;j++)
    {
      temp2=maximos[j];
      scanf("%d",&piedras);
      maximos[j]=piedras+max(temp1,maximos[j]);
      temp1=temp2;
    }
  }

  for(j=0;j<N;j++)
  {
    if(maximos[j]>maxmax)
      maxmax=maximos[j];
  }
  printf("%d\n",maxmax);
  return 0;
}


Reto #20: Dado un año N (N>=1600), determinar qué día será (o fue) el primero de enero de ese año.

Por ejemplo para una entrada N = 2009, la respuesta seria 'Jueves'.

[ace332]

Bueno parece que nadie se animo a resolver el reto por lo que aqui va la solución:

Código [Seleccionar] Expandir


#include <stdio.h>
#include <stdlib.h>

#define anyo_ref  2010
#define diainicio Viernes

enum Dia{ Domingo, Lunes, Martes, Miercoles, Jueves, Viernes, Sabado };
const char *strdia[]={"Domingo", "Lunes", "Martes", "Miercoles", "Jueves", "Viernes", "Sabado" };

int esbisiesto(int anyo);

int main(void)
{
  int a, anyo, ai=anyo_ref, af, ndias=0, dia1enero;

  scanf("%d",&anyo);

  af = anyo-1;
  if(anyo < anyo_ref)
  {
    ai = anyo;
    af = anyo_ref-1;
  }
  for(a = ai; a <= af; a++)
    ndias += esbisiesto(a)?2:1;

  dia1enero = (diainicio + ((anyo >= anyo_ref)?1:-1) * ndias) %7;
  if(dia1enero < 0)
    dia1enero += 7;

  printf("%s\n",strdia[dia1enero]);
  return 0;
}

int esbisiesto(int anyo)
{
  return (anyo%4) == 0 && ((anyo%100) != 0 || (anyo%400) == 0);
}


[[L]ord [R]NA]

Publica el proximo reto.

[ace332]

Bueno.. aqui va uno un tanto sencillo.

Un número perfecto es un número natural que es igual a la suma de sus divisores propios positivos, sin incluirse él mismo. Dicho de otra forma, un número perfecto es aquel que es amigo de sí mismo.

Así, 6 es un número perfecto, porque sus divisores propios son 1, 2 y 3; y 6 = 1 + 2 + 3. Los siguientes números perfectos son 28, 496 y 8128.

fuente: Wikipedia.

Reto #21: Hacer un programa que imprima en pantalla todos los números perfectos hasta un número N dado como entrada.

[[L]ord [R]NA]

Código (cpp) [Seleccionar] Expandir

#include <iostream>
int main()
{
int a,b;
std::cin>>a;
for(int i=1;i<=a;i++)
{
b=0;
for(int j=1;j<i;j++)if(i%j==0)b+=j;
if(b==i)std::cout<<b<<std::endl;
}
return 0;
}


PsData: En unas horas traigo reto... tengo un sueño que no me deja siquiera pensar.

[[L]ord [R]NA]

Reto #22: Dada dos fechas, verificar cuantos dias han transcurrido... se debe de tomar en cuenta los años bisiestos.

[Wazzp]

Disculpen mi impaciencia pero.. tengo un codigo,que a mi parecer esta bien,pero tiene un error ya que se cuelga y no hace nada.. alguien podria revisarlo? Si lo corrijo creo que solucionaria el reto # 22.. Respondan asi lo posteo,sino,borren este post y busco alguna otra forma de conseguir mi respuesta..

Gracias y Saludos 

[[D4N93R]]

Postealo a ver, lo vamos revisando y arreglando.

Saludos.