Resolución de algoritmos [Reto semanal] #1

GuaNaGe #91 Feb '18

¿os imagináis que renueva #1? Sería tan fan de este hilo...

Yerkos #92 Feb '18

Debería actualizar #1 o alguien plantear otros 3 algoritmos por aqui.

HeXaN #93 Feb '18

Se podrían proponer los tres primeros de aquí: https://adventofcode.com/

3 1 respuesta

Kanario93 #94 Feb '18

#93 Pues no conocía esa pagina, me parece bien la idea.

GuaNaGe #95 Mar '18

report #1 todos por no actualizar... xDDD <3

L

luisdomarco #96 Mar '18

Hola.

Pues he visto el hilo y aprovechando que estoy aprendiendo Java y que me tocaba practicar un poco con los arrays he sacado un programilla para calcular el primer Fibonacci con mil digitos

visto así es difícil saber si el resultado es correcto asi qué he hecho un pequeño listado para comprobar que funciona correctamente.

y por supuesto el código, no preguntéis cuanto tarde en hacerlo...

spoiler

package Fibonacci;

public class Main 
{

  public static void main(String[] args) 
  {
    final int OPCION = 1;
    

// arrays para manejar números de 1000 digitos
int [] r = new int[1001];  // resultado del último fibonacci
int [] f1 = new int[1001]; // usadas para copiar y hacer los càlculos
int [] f2 = new int[1001];

int c=1;  // indice del ultimo fibonacci
int n=0;

f1[0]=1;
f2[0]=1;

if (OPCION==1) // Primer fibonacci con 1000 digitos
{
  
  do
  {
    c++;  
    sumar(r,f2);
    copiar(f2,f1);
    copiar(f1,r);
    n++;
  }while (n<10000 && r[999]==0);

  ver (r);
  
  System.out.println();
  System.out.println("El primer Fibonacci con 1000 digitos es :  ");
  System.out.print("F"+c); 
  }
  
  // OPCION !=1
  else // listado de los fibonacci hasta 7 digitos
  {
    System.out.println("F1=1");
    do
    {
      c++;
      sumar(r,f2);
      copiar(f2,f1);
      copiar(f1,r);
      
      System.out.print("F"+c);
      System.out.print("=");
      ver(r);
      System.out.println();
      
      n++;
    }while (n<10000 && r[6]==0);

  System.out.println("El primer Fibonacci con 7 digitos es :  ");
  System.out.print("F"+c); 
  }
  }
  

  /*--------------------------------------/
  /  Funcion que copia en m1 el array m2  /
  /--------------------------------------*/
   private static void copiar(int[] m1, int[] m2)
   {
     for (int n=0;n<=999;n++)
     {
       m1[n]=m2[n];
     }
   }
   

  /*-------------------------------------------/
  /  Suma de forma tradicional, llevando una   /  

  / cuando las cifras sumadas suman mas de 10. /              /
  /-------------------------------------------*/  

  private static void sumar(int[] matriz, int[] x)
  {
    int indice=0;
    int llevo=0;
    

for(indice=0;indice<=999;indice++)
{ 
  matriz[indice]+=(x[indice]+llevo);
  llevo=0;
  if (matriz[indice]>9)
  {
    matriz[indice]-=10;
    llevo=1;      
  }   
}
   }
  

   

  /*-------------------------------------------/
  /  Permite ver en pantalla un array (numero) /  

  / sin los ceros a la izquierda.              /
  /-------------------------------------------*/
  private static void ver(int[] matriz)
  { 
    int control=0, control2=0;
    for (int n=999;n>=0;n--)
    {
      if (matriz[n]!=0 && control==0)
      {
        control=1;
      }
      if (control==1)
      {
        System.out.print(matriz[n]);
        control2++;
        if (control2>40)
        {
          System.out.println();
          control2=0;
        }
      } 
    }
  }
  

} // fin class Main

1

stuckED #97 Mar '18

Saqué esto para el modo fácil de #1, pero nunca llega a hacerme el print. Haciendo debug si veo como crece el número correctamente.

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	int resultado = 0;
	int next= 1, prev= 0;;
	boolean out = false;
	String fibonacci = "";
	
	for (int i = 0; i> 0 || out != true; i++)
	{
		resultado = prev + next;
		prev = next;
		next = resultado;
		
		fibonacci = String.valueOf(resultado);
		
		if ( fibonacci.length() == 1000)
		{
			out = true;
		}
	}
	System.out.println(fibonacci);
}

1 respuesta

Tony_Toscana #98 Mar '18 Inocente

#97 los int de java no tienen capacidad suficiente para albergar cifras tan grandes como las que requiere el programa, mira como las cifras van bailando entre números positivos y negativos, porque se desborda. Busca BigInteger.

1 2 respuestas

stuckED #99 Mar '18

#98 Muchas gracias!

L

luisdomarco #100 Mar '18

#98 De haberme enterado antes me habría ahorado un monton de trabajo xD, aunque ha sido un ejercicio divertido...

L

luisdomarco #101 Mar '18

Hola.
Me he estado peleando con las ternas pitagóricas y despues de varias versiones diferentes del algoritmo sin que me saliera la solución que habéis puesto pues he llegado a conclusion de que esa solución no es la correcta ni por asomo, solo los múltiplos de las dos primeras ternas primarias ya suman 175k así que por narices tiene que estar mal.

He partido del enlace que ha puesto un compañero en la página anterior, y despues de entender como se desarrolla el árbol y como a partir de esas matrices se sacan todas las ternas pitagóricas es fácil resolver, con una función recursiva para las ternas primarias y otra para los múltiplos de ternas primarias.

He empezado con la versión burra, como casi todos, y aunque solo vale para valores relativente pequeños me ha valido para hacer comprobaciones. He descartado pares en B si A es impar o viceversa, pares en C, y también descarto los números que no son coprimos entre sí y ni con esas, así es imposible...

spoiler

package coprimo;

public class Main 
{
  public static void main(String[] args) 
  {
    long m,n,o,p,i,cont=0,max=150,ult=max/2;
    for( m=3;m<ult;m++)
    {
       for( n=m+1;n<ult;n+=2)
       {
         if ( coprimo2 (m,n))
         {
           if (n%2==0)
             i=n+1;
           else
             i=n+2;
           for( o=i;o<m+n && m+n+o<=max;o+=2)
           {
             if (coprimo3 (m,n,o))
             {
               if ( primitivas(m,n,o))
               {
                 System.out.printf("%d-%d-%d->%d\n",m,n,o,m+n+o);
                 cont++;
                 for (p=2;p<=(max/(m+n+o));p++)
                 {  

                   System.out.printf("%d-%d-%d->%d\n",m*p,n*p,o*p,m*p+n*p+o*p);
                   cont++;
                 }
               }
             }
           }
         }     

       }
     }
     System.out.printf("\n Hay %d ternas pitagóricas con L <= que %d.",cont,max);
  }
  private static boolean primitivas(long a,long b,long c)
  {
    if (a*a+b*b==c*c)
    {
      return true;
    }
    return false;
  }
  private static boolean coprimo3 (long a, long b, long c)
  {
    if( coprimo2(a,b) && coprimo2(a,c) && coprimo2(b,c))
    {
      return true;
    }
    return false;
  }
  

  private static boolean coprimo2(long a,long b)
  {
    for(long m=(b/2);m>1;m--)
    {
      if(a%m==0 && b%m==0)
      {
        return false;
      }
    }
    return true;
  }
}

spoiler

Y luego ya el arbolito de ternas, que lo he repetido varias veces porque no me daba el mismo resultado que hay al princio y que creia bueno, y en todas las versiones que he hecho siempre me ha dado lo mismo, así que imagino que está bien.

A mi me salen 1256149 ternas.

spoiler


package arbolternas; 

public class Main 
{
  static int[] M1={ 1,-2, 2, 2,-1, 2, 2,-2, 3};
  static int[] M2={ 1, 2, 2, 2, 1, 2, 2, 2, 3};
  static int[] M3={-1, 2, 2,-2, 1, 2,-2, 2, 3};
  static int primera[]={3,4,5};
  static int max=1500000; 
  static int cont=1;

  public static void main(String[] args) 
  {   

    if (max<=500) 
     System.out.printf("%d-%d-%d->%d\n",primera[0],primera[1],primera[2],(primera[0]+primera[1]+primera[2]));
    multiplos(primera);
    ternas3 (primera);
    System.out.printf("\n Hay %d ternas pitagóricas \ncon L <= que %d.",cont,max);  

  }
  

  public static  void multiplos(int[] t)
  {  

    int p=2; 
    do
    {  

      if (max<=500)
        System.out.printf("%d-%d-%d->%d\n",t[0]*p,t[1]*p,t[2]*p,(t[0]*p+t[1]*p+t[2]*p));
      cont++;
      p++;   

    } while( ((t[0]+t[1]+t[2])*p)<=max);   

  }
   

  public static void ternas3(int[] t)
  {
    int r1[]=new int[3];
    int r2[]=new int[3];
    int r3[]=new int[3];
    // primera rama   

    r1[0]=t[0]*M1[0]+t[1]*M1[1]+t[2]*M1[2];
    r1[1]=t[0]*M1[3]+t[1]*M1[4]+t[2]*M1[5];
    r1[2]=t[0]*M1[6]+t[1]*M1[7]+t[2]*M1[8];
      

if (r1[0]+r1[1]+r1[2]<=max)
{
  cont++;
  if (max<=500)
    System.out.printf("%d-%d-%d->%d\n",r1[0],r1[1],r1[2],r1[0]+r1[1]+r1[2]);
  ternas3(r1);   
  if(((r1[0]+r1[1]+r1[2])*2)<=max)
    multiplos(r1);
}  
// segunda rama   
r2[0]=t[0]*M2[0]+t[1]*M2[1]+t[2]*M2[2];
r2[1]=t[0]*M2[3]+t[1]*M2[4]+t[2]*M2[5];
r2[2]=t[0]*M2[6]+t[1]*M2[7]+t[2]*M2[8];
  
if (r2[0]+r2[1]+r2[2]<=max)
{
  cont++;
  if (max<=500)
   System.out.printf("%d-%d-%d->%d\n",r2[0],r2[1],r2[2],r2[0]+r2[1]+r2[2]);
  ternas3(r2);   
  if(((r2[0]+r2[1]+r2[2])*2)<=max)
    multiplos(r2);
  
 }
  


/*----------*/
// tercera rama  
r3[0]=t[0]*M3[0]+t[1]*M3[1]+t[2]*M3[2];
r3[1]=t[0]*M3[3]+t[1]*M3[4]+t[2]*M3[5];
r3[2]=t[0]*M3[6]+t[1]*M3[7]+t[2]*M3[8];
  
if (r3[0]+r3[1]+r3[2]<=max)
{
  cont++;
  if (max<=500)
    System.out.printf("%d-%d-%d->%d\n",r3[0],r3[1],r3[2],r3[0]+r3[1]+r3[2]);
  ternas3(r3);  
  if(((r3[0]+r3[1]+r3[2])*2)<=max)
    multiplos(r3);     
}      
  }
}

spoiler

1 respuesta

S

Sarwaz #102 Mar '18

#101
El problema te pide cuantos valores para L pueden formar EXACTAMENTE 1 triangulo rectángulo. Yo en tu solución veo muchos triángulos repetidos, estas sumando de mas.
La solución para L = 15 es 16 no 29.

1 respuesta

L

luisdomarco #103 Mar '18

#102
Pues no te entiendo, no hay ningun triángulo repetido, mi inglés es muy justito, quizás no he entendido bien el enunciado...

1 respuesta

S

Sarwaz #104 Mar '18

#103
Como que no, ahi aparece 120 3 veces. El problema te pregunta por las medidas que solo pueden formar 1 triangulo rectángulo, si se puede formar mas de uno no hay que sumarlo.

solo los múltiplos de las dos primeras ternas primarias ya suman 175k así que por narices tiene que estar ma

En esa lista la mayoría forman mas de un triangulo y no hay que sumarlos.

B

[Borrado] #105 Mar '18

Se van a proponer más ? O esto ya ha muerto

1 respuesta

L

luisdomarco #106 Mar '18

#105
Vale, vale, creo ahora lo entiendo ¿tendría que hacer una matriz de 1 millón y medio de elementos e ir sumando y luego comprobar? algo así ¿no?:-|

L

luisdomarco #107 Mar '18

Efectivamente, son 161667 longitudes con una única solución, no estaba mal planteado mi código, pero no entendí el enunciado. Apenas tuve que modificar nada, además de un contador de ternas solo tengo que poner un contador para cada longitud y no sumar si ya se ha sumado esa longitud o restar ese valor al final si es mayor que 1, he preferido hacerlo así para cambiar menos cosas.

spoiler

package arbolternas;

public class Main
{
  static int[] M1={ 1,-2, 2, 2,-1, 2, 2,-2, 3};
  static int[] M2={ 1, 2, 2, 2, 1, 2, 2, 2, 3};
  static int[] M3={-1, 2, 2,-2, 1, 2,-2, 2, 3};
  static int primera[]={3,4,5};
  static int cnt[]= new int[1500001];
  static int max=1500000;
  static int cont=1;
  static int suma;

  public static void main(String[] args)
  {
    multiplos(primera);
    ternas3 (primera);
    System.out.printf("\n Hay %d ternas pitagóricas \ncon L <= que %d",cont,max);
    for(int n=0;n<=max;n++)
    {
      if (cnt[n]>1)
        cont-=cnt[n];
    }
    System.out.printf("\npero sólo %d longitudes \ntienen una única solución.",cont);
  }
  public static  void multiplos(int[] t)
  {
    int p=2;
    do
    {
      suma=(t[0]+t[1]+t[2]);
      cont++;
      cnt[suma*p]++;
      p++;
    } while(suma*p<=max);
  }
  public static void ternas3(int[] t)
  {
    int R1[]=new int[3];
    int R2[]=new int[3];
    int R3[]=new int[3];
    // primera rama
    R1[0]=t[0]*M1[0]+t[1]*M1[1]+t[2]*M1[2];
    R1[1]=t[0]*M1[3]+t[1]*M1[4]+t[2]*M1[5];
    R1[2]=t[0]*M1[6]+t[1]*M1[7]+t[2]*M1[8];
    suma=R1[0]+R1[1]+R1[2];
    if (suma<=max)
    {
      cont++;
      cnt[suma]++;
      ternas3(R1);
      suma=R1[0]+R1[1]+R1[2];
      if(suma*2<=max)
        multiplos(R1);
    }
    // segunda rama
    R2[0]=t[0]*M2[0]+t[1]*M2[1]+t[2]*M2[2];
    R2[1]=t[0]*M2[3]+t[1]*M2[4]+t[2]*M2[5];
    R2[2]=t[0]*M2[6]+t[1]*M2[7]+t[2]*M2[8];
    suma=R2[0]+R2[1]+R2[2];
    if (suma<=max)
    {
      cont++;
      cnt[suma]++;
      ternas3(R2);
      suma=R2[0]+R2[1]+R2[2];
      if(suma*2<=max)
        multiplos(R2);
    }
    // tercera rama
    R3[0]=t[0]*M3[0]+t[1]*M3[1]+t[2]*M3[2];
    R3[1]=t[0]*M3[3]+t[1]*M3[4]+t[2]*M3[5];
    R3[2]=t[0]*M3[6]+t[1]*M3[7]+t[2]*M3[8];
    suma=R3[0]+R3[1]+R3[2];
    if (suma<=max)
    {
      cont++;
      cnt[suma]++;
      ternas3(R3);
      suma=R3[0]+R3[1]+R3[2];
      if(suma*2<=max)
        multiplos(R3);
    }
  }
}

spoiler

Problema resuelto, a ver si me sale el de los palíndromos.

Saludos.

L

luisdomarco #108 Mar '18

Mi código para la suma de palíndromos, debería estar bien porque para números menores que mil me sale el resultado del enunciado 11 palíndromos que suman 1464, pero no me sale el mismo resultado que el otro compañero para números menores que 10^8...

A mi me sale esto.

Para números <= que 100000000
Número de palíndromos=168
Suma total=2916867073

spoiler

package palindromo;

public class Main 
{
  

  public static void main(String[] args)
  {  

    long[] pow2= new long[7072];
    long suma,cont=0, total=0;
    long max=100000000,maxfor=387;
    int n,m;
    for(n=1;n<7071;n++)
      pow2[n]=(long)Math.pow(n,2);   

    for (n=1;n<7070;n++)
    {
      suma=pow2[n];
      for(m=n+1;m<7071 && suma<=max;m++)
      {
        suma+=pow2[m];
        if(palindromo(suma)  && suma<= max)
        {
          System.out.printf("%d - n=%d m=%d\n",suma,n,m);
          total+=suma;
          cont++;
        }
      }
    }
    System.out.printf(" Para números <= que %d \n",max);
    System.out.printf(" Número de palíndromos=%d \n",cont);
    System.out.printf(" Suma total=%d",total);
  }
  

  public static boolean palindromo(long num)
  {
    long[] cifra= new long[10];
    int n,m,ult=0;
    boolean rt=true;
    for (n=9;n>0;n--)
    {
       long p=(long)Math.pow(10,n);
       while (num>=p)
       {
         cifra[n]++;
         num-=p;  

         if(ult==0)
          ult=n;
       }                

    }
    cifra[n]=num;
    ult++;
    if (ult==1)
      return true;
    for(n=0;n<=ult/2;n++)  

    {
      if(cifra[n]!=cifra[ult-1-n])
      rt=false;
    }
    return rt;
  }
}

spoiler

5 - de 1 a 2
55 - de 1 a 5
505 - de 2 a 11
818 - de 2 a 13
77 - de 4 a 6
636 - de 4 a 12
595 - de 6 a 12
181 - de 9 a 10
434 - de 11 a 13
313 - de 12 a 13
545 - de 16 a 17
 Para números <= que 1000 
 Número de palíndromos=11 
 Suma total=4164

spoiler

5 - de 1 a 2
55 - de 1 a 5
1992991 - de 1 a 181
505 - de 2 a 11
818 - de 2 a 13
42924 - de 2 a 50
77 - de 4 a 6
636 - de 4 a 12
1001 - de 4 a 14
1771 - de 4 a 17
595 - de 6 a 12
1441 - de 6 a 16
34277243 - de 7 a 468
63866836 - de 8 a 576
181 - de 9 a 10
17371 - de 9 a 37
554455 - de 9 a 118
434 - de 11 a 13
1111 - de 11 a 16
148841 - de 11 a 76
313 - de 12 a 13
166661 - de 14 a 79
545 - de 16 a 17
11600611 - de 16 a 326
3242423 - de 17 a 213
485584 - de 18 a 113
6446 - de 19 a 29
21712 - de 19 a 41
95177159 - de 21 a 658
99199 - de 22 a 67
8424248 - de 22 a 293
981189 - de 23 a 143
9313139 - de 26 a 303
363363 - de 27 a 103
3015103 - de 27 a 208
17871 - de 29 a 42
635536 - de 29 a 124
97679 - de 31 a 68
46564 - de 32 a 55
1365631 - de 34 a 160
5479745 - de 36 a 254
4334 - de 37 a 39
63844836 - de 41 a 576
127721 - de 44 a 77
6277726 - de 46 a 266
46433464 - de 46 a 518
19691 - de 50 a 56
108801 - de 50 a 76
444444 - de 51 a 113
65756 - de 54 a 70
6546456 - de 54 a 270
6843486 - de 54 a 274
1077701 - de 63 a 151
139931 - de 69 a 90
44444 - de 71 a 78
9105019 - de 72 a 302
5367635 - de 73 a 254
6106016 - de 74 a 265
81818 - de 77 a 88
525525 - de 77 a 126
904409 - de 83 a 148
52155125 - de 83 a 539
646646 - de 85 a 136
982289 - de 88 a 153
435534 - de 92 a 127
138831 - de 93 a 106
18244281 - de 93 a 381
51015 - de 99 a 103
41214 - de 100 a 103
4776774 - de 101 a 248
3628263 - de 102 a 228
9343439 - de 102 a 307
171171 - de 104 a 117
656656 - de 106 a 146
1949491 - de 106 a 191
161161 - de 116 a 126
188881 - de 126 a 136
4424244 - de 128 a 248
9940499 - de 136 a 318
5718175 - de 146 a 272
137731 - de 149 a 154
923329 - de 151 a 183
1681861 - de 156 a 206
18699681 - de 158 a 391
6844486 - de 159 a 290
11922911 - de 160 a 341
1972791 - de 164 a 217
9435349 - de 167 a 320
4211124 - de 172 a 260
9814189 - de 172 a 325
629926 - de 173 a 191
1224221 - de 173 a 206
191191 - de 176 a 181
45555554 - de 182 a 522
2176712 - de 189 a 236
45755754 - de 192 a 524
68688686 - de 194 a 597
37533573 - de 197 a 493
494494 - de 207 a 217
5276725 - de 210 a 292
17488471 - de 215 a 396
9838389 - de 223 a 343
7355537 - de 224 a 321
5588855 - de 226 a 304
16955961 - de 226 a 396
56722765 - de 239 a 568
972279 - de 257 a 270
5603065 - de 261 a 325
47622674 - de 261 a 543
50244205 - de 275 a 555
944449 - de 288 a 298
52344325 - de 292 a 566
26744762 - de 304 a 476
97299279 - de 312 a 685
53166135 - de 315 a 575
67233276 - de 320 a 616
554455 - de 331 a 335
69933996 - de 331 a 626
52722725 - de 341 a 582
12888821 - de 409 a 474
44366344 - de 412 a 587
5536355 - de 415 a 444
58366385 - de 421 a 629
69388396 - de 429 a 659
16755761 - de 471 a 536
9334339 - de 477 a 514
15822851 - de 479 a 539
9793979 - de 482 a 520
10711701 - de 491 a 531
66999966 - de 539 a 709
964469 - de 566 a 568
92800829 - de 577 a 777
18422481 - de 589 a 637
2904092 - de 599 a 606
4338334 - de 623 a 633
6523256 - de 631 a 646
40211204 - de 632 a 719
53933935 - de 645 a 754
9343439 - de 657 a 677
9072709 - de 682 a 700
5090905 - de 709 a 718
41577514 - de 742 a 810
6831386 - de 749 a 760
13922931 - de 785 a 806
53211235 - de 793 a 869
9563659 - de 820 a 833
6780876 - de 864 a 872
56800865 - de 895 a 960
1690961 - de 919 a 920
72299227 - de 924 a 1001
43699634 - de 975 a 1018
55344355 - de 976 a 1030
62988926 - de 1075 a 1126
32344323 - de 1202 a 1223
32611623 - de 1207 a 1228
16399361 - de 1216 a 1226
3162613 - de 1257 a 1258
3187813 - de 1262 a 1263
69722796 - de 1284 a 1324
11122111 - de 1359 a 1364
57488475 - de 1606 a 1627
5258525 - de 1621 a 1622
5824285 - de 1706 a 1707
9051509 - de 1736 a 1738
49066094 - de 2107 a 2117
64633646 - de 2419 a 2429
51488415 - de 3207 a 3211
95544559 - de 3988 a 3993
 Para números <= que 100000000 
 Número de palíndromos=168 
 Suma total=2916867073

D

dialomer #109 Mar '18

este también puede ser uno de tus retos: Buenas tardes, realice una aplicación en vb.net tipo un banner que ocupa todo el ancho superior del monitor y unos 3 centímetros de alto, mi consulta es saber si es posible que las demás aplicaciones o web que se puedan abrir en la pc solo ocupen el espacio vació que no ocupa el banner para que este banner siempre pueda estar visible ya que es informativo.

saludos.

1 respuesta

Camp1 #110 Mar '18

#109 tu respuesta está aqui

spoiler

Usuarios habituales

Tags