Tema: Petando la pila. Problemas y retos usando recursividad.
Ver Mensaje Individual
  #50 (permalink)  
Antiguo 01/12/2014, 04:15
Avatar de leosansan
leosansan
 
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 6 meses
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.
Cita:
Iniciado por Pantaláimon Ver Mensaje
Bien, bien leosan
Aún no me lo he mirado con profundidad pero remitiéndome al primer post que puse:

aún debes corregir ciertas cosas para que sea válido!

Un saludo!
Buuueno, pero que conste que es de lo más efectivo el código anterior.

Pero las reglas son las reglas y las has puesto tú aunque un poco de manga ancha no vendría mal.

Para que no se diga: sin un for ni do ni while ni goto. Tutti con funciones recursivas, y son unas cuantas para que no se diga.

La idea es usar la fuerza bruta, pero de forma proporcional.

* Obtengo el tamaño del número, vamos sus dígitos.

* Saco los valores mínimo y máxima que pueden alcanzar los dos números que multiplicados nos darán el número original.

* Pruebo los posibles productos a partir de los valores anteriores que nos puedan dar el número.

* Obtenido cualquier posibilidad, compruebo que los dígitos que componen los números parciales se corresponden con el número original: si es sí, O.k, es Vampiro y si no, no lo es.

Sencillito, ¿ verdad ? y todo usando una "nomenclatura" que puedan seguir los usuarios menos avanzados. De ahí que me haya molestado en poner nombres muy descriptivos a las variables....eferion estará muy contento por ello.

¡¡¡ Ahí va el "pedazo" de código:

Código C++: 
Ver original
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int cantidadDigitos ( int num ) ;
  5. int esVampiro ( int numero ) ;
  6. int obtenerNumMinimo ( int digitos ) ;
  7. int obtenerNumMaximo ( int digitos )  ;
  8. int probar ( int numero , int num_1 , int num_0 , int n_minimo , int n_maximo , int digitos , int DigitosNumero [ 10 ] ) ;
  9. int DigitosNumero ( int digitosNumero [ 10 ], int numero , int flag )  ;
  10.  
  11. int main ( ) {
  12.   int numero = 939658 ; /** 939658 = 953 * 986 **/
  13.   return printf ( "\n!!! Como lo quiere Pantalaimon ( 0 - 1 ) !!! ==> : [%d]\n\n" , esVampiro ( numero ) ) , 0 ;
  14.   return 0;
  15. }
  16.  
  17. int cantidadDigitos ( int num ) {
  18.   return ( num == 0 ) ? 0 : 1 + cantidadDigitos ( num / 10 ) ;
  19. }
  20.  
  21. int obtenerNumMinimo ( int digitos ) {
  22.   return ( digitos == 0 ) ? 1 : 10 * obtenerNumMinimo ( - 1 + digitos ) ;
  23. }
  24.  
  25. int obtenerNumMaximo ( int digitos ) {
  26.   return ( digitos == 0 ) ? 1 : 10 * obtenerNumMinimo ( - 1 + digitos ) ;
  27. }
  28.  
  29. void inicializar_digitosNumero ( int digitosNumero [ 10 ] , int indice ) {
  30.   if ( indice < 10 )
  31.     digitosNumero [ indice ] = 0 , inicializar_digitosNumero ( digitosNumero , indice + 1 ) ;
  32. }
  33.  
  34. int DigitosNumero ( int digitosNumero [ 10 ], int numero , int flag ) {
  35.   if ( numero > 0 && flag == 0 )
  36.     digitosNumero [ numero % 10 ]++ , DigitosNumero ( digitosNumero , numero / 10 , 0 ) ;
  37.   else if ( numero > 0 && flag == 1 )
  38.     digitosNumero [ numero % 10 ]-- , DigitosNumero ( digitosNumero , numero / 10 , 1 ) ;
  39.   if ( digitosNumero [ numero % 10 ] < 0 )
  40.     return  0 ;
  41.   else return 1 ;
  42. }
  43.  
  44. int ComprobarDigitos ( int digitosNumero [ 10 ] , int indice , int cont ) {
  45.   if ( indice < 10 )
  46.     if ( digitosNumero [ indice ] == 0 )
  47.       return 1 + ComprobarDigitos ( digitosNumero , indice + 1 , cont + 1 ) ;
  48.     else return
  49.       ComprobarDigitos ( digitosNumero , indice + 1 , cont  ) ;
  50.   return 0 ;
  51. }
  52.  
  53. int esVampiro ( int numero ) {
  54.   int  i , indice = 0 , n_maximo , n_minimo , numero_0 , numero_1 , digitos , digitosNumero [ 10 ] ;
  55.   inicializar_digitosNumero ( digitosNumero , indice ) ;
  56.   DigitosNumero ( digitosNumero , numero , 0 ) ;
  57.   digitos = cantidadDigitos ( numero ) ;
  58.   if ( digitos %2 != 0 )
  59.     return puts ( "\n\n\tNO ES VAMPIRO por numero impar de cifras.\n\n" ) , 0 ;
  60.   n_minimo = obtenerNumMinimo ( - 1 + digitos / 2 ) ;
  61.   n_maximo = obtenerNumMaximo ( digitos / 2 ) ;
  62.   numero_0 = numero_1 = n_minimo ;
  63.   return probar ( numero , numero_1 , numero_0 , n_minimo , n_maximo , digitos , digitosNumero ) ;
  64. }
  65.  
  66.  int probar ( int numero , int num_1 , int num_0 , int n_minimo , int n_maximo , int digitos , int digitosNumero [ 10 ]  ) {
  67.   int  i , indice = 0 , flag = 0  ;
  68.   if ( num_1 < n_maximo - 1 && num_0 == n_maximo )
  69.     num_0 = n_minimo , num_1 = numero / n_maximo  ;
  70.   if ( num_0 == n_maximo - 1 )
  71.     return printf ( "\n\n\t::%d NO ES VAMPIRO\n\n"  , numero ) , 0 ;
  72.   if ( num_0 < n_maximo ){
  73.     num_1 = numero / num_0  ;
  74.     if ( num_0 * num_1 == numero  ) {
  75.     inicializar_digitosNumero ( digitosNumero , 0  ) ;
  76.     DigitosNumero ( digitosNumero , numero , 0 ) ;
  77.     if ( num_0 * num_1 == numero  ) {
  78.       DigitosNumero ( digitosNumero , num_0 , 1 ) ;
  79.       DigitosNumero ( digitosNumero , num_1 , 1 ) ;
  80.       if ( ComprobarDigitos ( digitosNumero , 0 , 0 ) == 10 && ( num_0 % 10 != 0 ||  num_1 % 10 != 0 ) )
  81.         return printf ( "\n\n\tES VAMPIRO: %d = %d * %d\n\n" , numero , num_1 , num_0 ) , 1 ;
  82.     }
  83.   }
  84.   return  probar ( numero , num_1  , 1 + num_0 , n_minimo , n_maximo , digitos , digitosNumero )  ;
  85.  }
  86. }

Lo he testeado un ratito así que espero no tenga bugs y si no ya me lo dirán.....

Por cierto, dar la bienvenida a kspr, HackmanC y amchacon por su incorporación a los retos.

Notita::1:: HaxkmanC no me da como vampiro el "939658".

Notita::2::
Cita:
amchcon:: Vaya código tan grande te ha salido Leo.

El uso de variables estáticas no me convence mucho, y bueno los bucles habría que quitarlos tramposo ;)
Pues el código es increiblemente eficiente comparado con los otros propuestos. Pero ya ves que me he aplicado y pongo ahora uno "sin trampas", campeón. Yo por lo menos me he lanzado a por el difícil, je,je.

Por cierto, paso una breve lista de números vampiros:

Código C++: 
Ver original
  1. 1395=15*93
  2. 1260=21*60
  3. 1827=21*87
  4. 2187=27*81
  5. 1530=30*51
  6. 1435=35*41
  7. 6880=80*86
  8. 108135=135*801
  9. 129640=140*926
  10. 118440=141*840
  11. 136948=146*938
  12. 105750=150*705
  13. 139500=150*930
  14. 115672=152*761
  15. 125248=152*824
  16. 146952=156*942
  17. 110758=158*701
  18. 116725=161*725
  19. 156915=165*951
  20. 117067=167*701
  21. 162976=176*926
  22. 129775=179*725
  23. 102510=201*510
  24. 120600=201*600
  25. 126027=201*627
  26. 180297=201*897
  27. 105264=204*516
  28. 125460=204*615
  29. 105210=210*501
  30. 126000=210*600
  31. 182700=210*870
  32. 190260=210*906
  33. 192150=210*915
  34. 136525=215*635
  35. 186624=216*864
  36. 211896=216*981
  37. 172822=221*782
  38. 180225=225*801
  39. 182250=225*810
  40. 123354=231*534
  41. 125433=231*543
  42. 135828=231*588
  43. 173250=231*750
  44. 175329=231*759
  45. 156240=240*651
  46. 125460=246*510
  47. 218488=248*881
  48. 229648=248*926
  49. 125500=251*500
  50. 152608=251*608
  51. 215860=251*860
  52. 201852=252*801
  53. 205785=255*807
  54. 104260=260*401
  55. 126846=261*486
  56. 152685=261*585
  57. 156289=269*581
  58. 226498=269*842
  59. 218700=270*810
  60. 197725=275*719
  61. 226872=276*822
  62. 124483=281*443
  63. 182650=281*650
  64. 262984=284*926
  65. 251896=296*851
  66. 150300=300*501
  67. 153000=300*510
  68. 131242=311*422
  69. 133245=315*423
  70. 134725=317*425
  71. 146137=317*461
  72. 296320=320*926
  73. 217638=321*678
  74. 312975=321*975
  75. 132430=323*410
  76. 216733=323*671
  77. 260338=323*806
  78. 193257=327*591
  79. 319536=336*951
  80. 233896=338*692
  81. 213466=341*626
  82. 329346=342*963
  83. 140350=350*401
  84. 143500=350*410
  85. 253750=350*725
  86. 135837=351*387
  87. 145314=351*414
  88. 315900=351*900
  89. 319059=351*909
  90. 153436=356*431
  91. 329656=356*926
  92. 336960=360*936
  93. 346968=366*948
  94. 361989=369*981
  95. 174370=371*470
  96. 369189=381*969
  97. 371893=383*971
  98. 338296=392*863
  99. 362992=392*926
  100. 193945=395*491
  101. 163944=396*414
  102. 284760=420*678
  103. 245182=422*581
  104. 304717=431*707
  105. 312475=431*725
  106. 378418=431*878
  107. 384912=432*891
  108. 378450=435*870
  109. 263074=437*602
  110. 404968=446*908
  111. 241564=461*524
  112. 429664=464*926
  113. 386415=465*831
  114. 286416=468*612
  115. 416988=468*891
  116. 254740=470*542
  117. 378400=473*800
  118. 447916=476*941
  119. 428980=482*890
  120. 284598=489*582
  121. 414895=491*845
  122. 326452=524*623
  123. 336550=530*635
  124. 341653=533*641
  125. 365638=533*686
  126. 315594=534*591
  127. 456840=540*846
  128. 489955=545*899
  129. 458640=546*840
  130. 489159=549*891
  131. 536539=563*953
  132. 475380=570*834
  133. 529672=572*926
  134. 368550=585*630
  135. 559188=588*951
  136. 498550=590*845
  137. 392566=593*662
  138. 486720=624*780
  139. 538650=630*855
  140. 416650=641*650
  141. 457600=650*704
  142. 568750=650*875
  143. 638950=650*983
  144. 567648=657*864
  145. 629680=680*926
  146. 516879=681*759
  147. 673920=720*936
  148. 679500=750*906
  149. 736695=765*963
  150. 769792=776*992
  151. 729688=788*926
  152. 688000=800*860
  153. 794088=807*984
  154. 789525=825*957
  155. 738468=843*876
  156. 792585=855*927
  157. 815958=858*951
  158. 789250=875*902
  159. 809919=891*909
  160. 841995=891*945
  161. 809964=894*906
  162. 829696=896*926
  163. 939658=953*986

¡¡¡Saluditos!!!



Puntitos Puntitos
Me gusta me gusta
[/QUOTE]