javascript - saber - palindromo sinonimo
Encuentre el palíndromo más grande hecho del producto de dos números de 3 dígitos-Javascript (20)
Así es como lo hice en Javascript. ¡Simplemente fácil!
let num1 = 999;
let num2 = 999;
let arr = [];
function check(x, y)
{
if(String(x*y) == String(x*y).split("").reverse().join(""))
{
return true;
}
return false;
}
for(let i=0; i<999999; i++)
{
if(check(num1, num2))
{
arr.push(num1*num2);
num1--;
num2 = num1+1;
}
num2--;
}
console.log(arr.sort((x, y) => y-x)[0]);
¿Alguien puede decirme qué está mal con el código? Encuentra el palindrome más grande hecho del producto de dos números de 3 dígitos.
function largestPalindrome(){
for(var i =999; i>100; i--){
for(var j = 999; j>100; j--){
var mul = j*i;
if(isPalin(mul)){
return i * j;
}
}
}
}
function isPalin(i){
return i.toString() == i.toString().split("").reverse().join("");
}
console.log(largestPalindrome());
Esta respuesta fue cercana a mi pregunta, pero aún siento la forma en que estoy haciendo el bucle; debería devolverse el producto más grande.
Así es como lo hice. Utilicé la forma antigua para buscar un palíndromo. Parece que se ejecuta más rápido en mi computadora, pero puedo estar equivocado. Empujar a una matriz, como en la publicación anterior, fue definitivamente muy lento en mi computadora. Retraso notable en la consola. Recomendaría simplemente verificar si su producto es mayor que su máximo actual, si lo es, guárdelo en lugar de enviarlo todo a una matriz. Por favor, siéntase libre de corregirme si me equivoco. Muy apreciado.
//should find the largest palindrome made from the product of two 3 digit numbers
var largestPalindrome = function() {
var max = 0,
product = 0;
for (var num1 = 999; num1 >= 100; num1--) {
for (var num2 = 999; num2 >= 100; num2--) {
product = num1 * num2;
product > max && isPalindrome(product.toString()) ? max = product : 0;
}
}
return max;
};
//check to see if product is a palindrome
var isPalindrome = function(product) {
var palindromeCheck = true;
for (var i = 0; i < product.length / 2; i++) {
if (product[i] != product[product.length - i - 1])
palindromeCheck = false;
}
return palindromeCheck;
//return product === product.split("").reverse().join("");
};
Como se explica en el comentario de @ VisioN:
995*583 = 580085 es un palíndromo.
993*913 = 906609 también es un palíndromo (más grande).
Su código verifica 995*583 antes de 993*913 y sale en el primer palíndromo encontrado, por lo que no devuelve el palíndromo más grande.
Solución: obtenga los palíndromos más grandes comenzando desde 999*999 = 998001 hacia abajo y verifique si pueden escribirse como xyz*abc .
O simplemente use la solución aceptada de la pregunta que vinculó :). Su solución, pero en lugar de volver cuando encuentre el primer palíndromo, verifique si es más grande que el más grande que ya se encontró, en cuyo caso deberá reemplazarlo. Puede detenerse tan pronto como el palíndromo más grande sea más grande que i*999 .
Como una solución muy simple, ésta funciona.
public class LargestPallendrome {
public static void main(String[] args) {
int a = 999;
int b = 999;
long max = 0;
while (a > 100) {
long num = a * b;
if (checkPallendrome(num)) {
if (num > max)
max = num;
}
if (b >= 100)
b--;
else {
a--;
b = 999;
}
}
System.out.println(max);
}
public static boolean checkPallendrome(long num) {
String a = num + "";
String b = new StringBuffer(num + "").reverse().toString();
if (a.equals(b))
return true;
return false;
}
}
Creo que esto debería ser óptimo.
#include <functional>
#include <algorithm>
#include <iostream>
using namespace std;
template <typename T>
bool IsPalindrome(const T num) {
T reverse = 0;
T n = num;
while (n > 0) {
reverse = (reverse * 10) + n % 10;
n /= 10;
}
return reverse == num;
}
template <typename T = long long int>
T LongestPalindromeFromProductOfNDigitNums(int n) {
T result = 0, val = 0, max_n_digit_num = std::pow(10, n)-1,
least_n_digit_num = std::pow(10, n-1);
int n_checks = 0;
for (T i = max_n_digit_num; i >= least_n_digit_num; --i) {
if ((i*i) < result) {//found the highest palindrome
break;
}
for (T j = i; j >= least_n_digit_num; --j) {
val = i*j;
++n_checks;
if (val < result) // any product i*j for the value of ''j'' after this will be less than result
break;
if (IsPalindrome(val)) {
if (val > result)
result = val;
break; // whenever a palindrome is found break since we only need highest one
}
}
}
std::cout << " Total num of checks = " << n_checks << std::endl;
return result;
}
int main() {
int n = 3;
std::cout << " LongestPalindromeFromProductOfNDigitNums for n = "
<< n << " is " << LongestPalindromeFromProductOfNDigitNums(n) << std::endl;
n = 4;
std::cout << " LongestPalindromeFromProductOfNDigitNums for n = "
<< n << " is " << LongestPalindromeFromProductOfNDigitNums(n) << std::endl;
return 0;
}
Creo que puede ir por el código dado en este enlace http://www.mathblog.dk/project-euler-problem-4/
Como esto guarda el ciclo de la CPU de la multiplicación, que es una operación bastante costosa.
Bueno, incluso en esto puedes hacer algunos más para que sea más parecido, puedes modificar su bucle while un poco
while (!found) {
firstHalf--;
palin = makePalindrome(firstHalf);
for (int i = 999; i > 99; i--) {
if ((palin / i) > 999 || i*i < palin) {
break;
}
if ((palin % i == 0)) {
found = true;
factors[0] = palin / i;
factors[1] = i;
break;
}
}
}
Entonces, en lugar de pasar de i=999 : 100, podemos escribirlo como i=sqrt(palin):100 , ya que puedes encontrar factorial de número dentro de su raíz cuadrada. Consulte el enlace Cómo encontrar el número es el número primo o no!
Y también puede cambiar if(condition) a if(!(palin%i)) ya que comparar con cero generalmente no se considera una buena práctica, ya que la comparación requiere más ciclos de CPU en comparación con sus bits de negación simples.
Creo que si aplicas las matemáticas al problema, puedes disminuir las conjeturas realmente de manera significativa.
Escribiré los números de tres dígitos como 1000 - a y 1000 - b que significa que el palíndromo es 1 000 000 - 1000(a+b) + ab .
Primero, encontremos soluciones donde ab < 1000 . Luego, los tres dígitos de la izquierda son 1000 - (a+b) y los tres dígitos de la derecha son ab .
Entonces diré que este es un palíndromo con dígitos x,y,z :
100x+10y+z=ab
100z+10y+x=1000-a-b
así
99x-99z = ab+a+b-1000
x-z = 1/99(ab+a+b-10)-10
Entonces (ab + a + b-10) es divisible por 99 y también sabemos que x y z son dígitos, el lado izquierdo está entre -9 y 0 (todo el shebang es simétrico, por lo que podemos suponer que x <= z) así que entonces 1/99(ab+a+b-10) está entre 1 y 9. Podemos reescribir ab+a+b-10 como ab+a+b+1-11=99p así que (a+1)(b+1)=99p+11=11*(9p+1) donde p se ejecuta entre 1 y 9. Eso es muy fácil:
for ($p = 1; $p <= 9; $p++) {
$n = 9 * $p + 1;
// This could be vastly optimized further.
for ($j = 1; $j <= $n; $j++) {
if ($n % $j === 0) {
$a = 1001 - $n / $j;
$b = 1001 - 11 * $j;
$test = $a * $b;
if (strrev($test) === (string) $test) {
print "$a $b " . $a * $b . "/n";
}
}
}
}
Ahora esto imprime solo una solución que es la correcta.
Ahora sabemos que 906609 es una solución, entonces ¿hay una solución donde ab> 1000 y 1000 (a + b) - ab <93391? No hay :)
El suyo no funciona correctamente ya que comprueba 999*999 , luego 999*998 , luego 999*997 hasta que alcanza aproximadamente 999*583 . Si bien no marca 997*995 o algo más cerca de la parte superior, se genera un número mayor
function largestPalindrome(){
var arr = [];
for(var i =999; i>100; i--){
for(var j = 999; j>100; j--){
var mul = j*i;
if(isPalin(mul)){
arr.push(j * i);
}
}
}
return Math.max.apply(Math, arr);
}
function isPalin(i){
return i.toString() == i.toString().split("").reverse().join("");
}
console.log(largestPalindrome());
Este es otro enfoque : almacene todo el palindrome generado por 3 números en una matriz, luego use Math.max on the array para obtener el palindrome más grande
En lugar de crear un Array o ArrayList para almacenar todos los palíndromos, simplemente creé otra variable max y almacené el palíndromo de mayor valor en él.
Mi código está en Java, pero puedes entender la lógica a partir de él. Aquí está mi código para explicar mejor lo que dije (lea los comentarios):
package euler;
import java.util.ArrayList; import java.util.Collections;
public class Problem4 {
public static void main (String[] args)
{
int product=0;
int max=0;
for(int i=999;i>100;i--)
{
for (int j=i;j>100;j--)
{
product=i*j;
if(isPalindrome(product))
{
//Just store maximum value of product.
//Following if loop is required in your code,in place of return i*j;
if(product>max)
{ max=product; }
}
}
}
System.out.println(max);
}
//might be inefficient to create StringBuilder and again String to compare.
public static boolean isPalindrome(int product)
{
boolean isPalindrome=false;
StringBuilder temp = new StringBuilder(Integer.toString(product)).reverse();
if(temp.toString().equals(Integer.toString(product)))
{
isPalindrome=true;
}
return isPalindrome;
}
}
Lo que está haciendo es regresar y salir del ciclo tan pronto como obtenga el primer palíndromo. Que en su caso no es el palíndromo de máximo valor.
En su lugar, utilice una condición if, mantenga un seguimiento de los valores máximos y deje que el bucle continúe hasta el final.
He añadido la condición if que permite que el bucle se ejecute y registra el valor.
Tengo la respuesta correcta de este código.
PD. Gracias Xan por tu aporte. Supongo que podría haberlo explicado mejor la primera vez.
Esto es mejor porque utiliza la complejidad en el tiempo O (N) para encontrar todo el palíndromo (ya que calcular el palíndromo de un número de seis dígitos es constante) y O (N 2 ) casi para encontrar el palíndromo real en el peor de los casos en el momento en que se encuentra. Primero no, no tenemos que hacer más cálculos y aquí estamos usando el peor de los casos en el posible palindrómico no. Así que creo que es mejor
package ProjectEuler;
import java.util.ArrayList;
import java.util.Arrays;
public class Largest_Palindrome_Product {
public static void main(String[] args) {
int count=0;
for(int i=10000;i<998002;i++) {
int x=i,c=0;
while(x!=0) {
c=c*10+x%10;
x/=10;
}
if(c==i) {
count++;
}
}
int a[]=new int[count],count1=0;
for(int i=10000;i<998002;i++) {
int x=i,c=0;
while(x!=0) {
c=c*10+x%10;
x/=10;
}
if(c==i) {
a[count1]=i;
count1++;
}
}
Arrays.sort(a);
tp:for(int i=count-1;i>=0;i--)
{
for(int j=999;j>100;j--)
if(a[i]%j==0&&a[i]/j<=999) {
System.out.println(a[i]+" "+j+" "+a[i]/j);
break tp;
}
}
}
}
He visto muchas publicaciones para esta pregunta, esta es la solución que he encontrado:
- El número más pequeño que es múltiplo de dos números de 3 dígitos es 10000 (100 * 100)
- El número más grande que es múltiplo de dos números de 3 dígitos es 998001 (999 * 999)
Nuestro palíndromo se encuentra entre estos dos números, escriba un programa para recorrerlos y cada vez que obtenga un palíndromo compruebe si es perfectamente divisible entre un número de 3 dígitos y el cociente también es un número de 3 dígitos.
A continuación se encuentra mi programa en C #, el último número que imprime es nuestra respuesta requerida, disfrute.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using System.Collections;
namespace E
{
public class Program
{
public static void Main(string[] args)
{
//Your code goes here
for(int i=10000;i<=998001;i++)
{
string s1 = i.ToString();
char[] array = s1.ToCharArray();
Array.Reverse(array);
string s2 = new String(array);
if(s1==s2)
{
for(int j=100;j<=999;j++)
{
if(i%j==0 && i/j <= 999)
{
System.Console.WriteLine(i);
continue;
}
}
}
}
System.Console.WriteLine("done");
}
}
}
La mayoría de las respuestas aquí son correctas. Si desea guardar a través de 900 * 900 bucles, simplemente puede recorrer todos los palíndromos entre 10000 y 998001 y encontrar si son divisibles por un número de 3 dígitos.
static void largestpalindromeproduct(){
int a=999,b=999,c=a*b,loopcounter=0;
while(c>10000){
loopcounter++;
c--;
if(isPalindrome(c))
if(isDivisible(c))
break;
}
System.out.println(" largest : " + c+ "/nloops:"+ loopcounter);
}
static boolean isDivisible(int n){
int a=999;
while(a>=100){
if(n%a==0){
if(secondDividerIs3Digit(n,a))
return true;
}
a--;
}
return false;
}
static boolean secondDividerIs3Digit(int n, int a){
Integer b=n/a;
if(b.toString().length()==3)
return true;
return false;
}
static boolean isPalindrome(int n){
Integer i=new Integer(n);
String p=i.toString();
StringBuffer s=new StringBuffer(i.toString());
s.reverse();
if(p.equals(s.toString()))
return true;
return false;
}
La solución anterior funcionará perfectamente bien, pero tendremos un problema SOLAMENTE cuando intentemos averiguar cuáles son esos 2 números (i = 913 y j = 993)
Solo modificaré la solución propuesta por Azder.
int max = 0;
int no1 = 0;
int no2 = 0;
// not using i >= 100 since 100*100 is not palindrome! :)
for (var i = 999; i > 100; i--) {
// because i * j === j * i, no need of both i and j
// to count down from 999
for (var j = i; j > 100; j--) {
var mul = j * i;
if (isPalin(mul)) {
if ((i+j) > max) {
max = i+j;
no1 = i; no2 = j;
}
}
}
}
//Now we can get the 2 numbers (no1=993 and no2=913)
return (no1*no2);
Lo random.randint algunas veces con random.randint . En Python 3.7.1, debes ejecutarlo con CMD y después de 20 segundos obtendrás la respuesta correcta.
import random
x,y,z,a,b=100,100,'' '','''',0
while 100<=x<=999 and 100<=y<=999:
a=x*y
x=random.randint(900,999)
y=random.randint(900,999)
print(x,'' x '',y,''='')
z=len(str(a))
if z==6:
if str(a)[0] == str(a)[5]:
if str(a)[1] == str(a)[4]:
if str(a)[2] == str(a)[3]:
print(a,''yes'')
exit(a)
else:
pass
#906609
Otra solución simple en JavaScript
function reverseNumber(n)
{
n = n + "";
return n.split("").reverse().join("");
}
function palindrom(){
var r= 1 , y =1;
var largest = 0;
while(r <= 1000){
var num1 = r;
var num2 = 0;
while(num1 <= 1000 && num2 <= num1){
product = num1 * num2;
if (product == reverseNumber(product)){
console.log(`${num1} x ${num2} = ${product}`);
if(product > largest){
largest = product;
}
}
num1 = num1 + 1;
num2= num2 + 1;
}
r++;
}
console.log(``)
console.log(`The largest is ${largest}`);
}
console.log(palindrom());
Sugerir una solución usando underscore.js. Primero, encuentre todos los palíndromos y luego recórtelos desde el más grande y devuelva el que tiene dos factores primos de 3 dígitos.
function isPalindrome(num) {
var str = num.toString();
return str.split('''').reverse().join('''') === str;
}
function palindromes() {
var max = 999 * 999;
var min = 100 * 100;
return _.select(_.range(max, min, -1), isPalindrome);
}
palindromes().find(function (x) {
if (_.find(_.range(999, 100, -1), function (y) {
return (x % y === 0 && y != x / y && x / y < 1000) ? true : false;
})) return true;
})
Swift 3:
// my approach is to make 6-digit palindrome first and then
// check if I can divide it by 3-digit number
// (you can see some visual listing at the end of the code)
// execution time on my laptop is around: 2.75409698486328 sec
import Foundation
func maxPalindrom() -> Int {
var result = 999999
var i = 9
var j = 9
var k = 9
while true {
while true {
while true {
print("in K loop: /(result) k = /(k)")
if isDivisible(number: result) {
return result
}
if k <= 0 {
k = 9
result += 9900
break
}
result -= 1100
k -= 1
}
print("in J loop: /(result)")
if isDivisible(number: result) {
return result
}
if j < 0 {
j = 9
result += 90090
break
}
result -= 10010
j -= 1
}
print("in I loop: /(result)")
if isDivisible(number: result) {
return result
}
if i < 0 {
break
}
result -= 100001
i -= 1
}
if result == 100001 {
return -1
}
return -1
}
func isDivisible(number: Int) -> Bool {
var i = 999
while true {
if number % i == 0 && number / i < 999 {
return true
}
if i < 500 {
return false
}
i -= 1
}
}
let start = NSDate()
print(maxPalindrom()) // 906609
let end = NSDate()
print("executio time: /(end.timeIntervalSince(start as Date)) sec") // ~ execution time: 2.75409698486328 sec
//in K loop: 999999 k = 9
//in K loop: 998899 k = 8
//in K loop: 997799 k = 7
//in K loop: 996699 k = 6
//in K loop: 995599 k = 5
//in K loop: 994499 k = 4
//in K loop: 993399 k = 3
//in K loop: 992299 k = 2
//in K loop: 991199 k = 1
//in K loop: 990099 k = 0
//in J loop: 999999
//in K loop: 989989 k = 9
//in K loop: 988889 k = 8
//in K loop: 987789 k = 7
//in K loop: 986689 k = 6
//in K loop: 985589 k = 5
//in K loop: 984489 k = 4
//in K loop: 983389 k = 3
.....
Versión un poco más optimizada con comentarios incluidos. Tenga en cuenta que no hay necesidad de un retorno rápido, simplemente almacene el max y optimice los ciclos para no volver a calcular j*i si i*j ya se ha verificado.
function largestPalindrome() {
var max = 0;
// not using i >= 100 since 100*100 is not palindrome! :)
for (var i = 999; i > 100; i--) {
// because i * j === j * i, no need of both i and j
// to count down from 999
for (var j = i; j > 100; j--) {
var mul = j * i;
if (isPalin(mul) && mul > max) {
max = i * j;
}
}
}
return max;
}
function isPalin(i) {
// adding empty string to i instead using of .toString
// avoids unnecessary wrapping in String object on the left side
i = '''' + i;
// don''t rely on ==, use === instead
return i === i.split("").reverse().join("");
}
console.log(largestPalindrome());
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int largestPalindrome()
{
int ret = 0;
for (int i = 999; i > 100; --i)
{
int jLimit = MAX(ret / i, 100);
for (int j = i; j > jLimit; --j)
{
int ans = i * j;
if (isPalin(ans))
{
ret = MAX(ans, ret);
}
}
}
return ret;
}
Razones explicadas anteriormente.
Podemos volver a calcular el rango de j cuando encontramos un producto de palíndromo. Esto debería ser más rápido.
public static void main(String[] args) {
int tempAns = 0;
int max = 999;
for (int i = 100; i <= max; i++) {
for (int j = max; j >= i; j--) {
if (findPalindrome(i * j) && (i * j) > tempAns) {
System.out.println("Palindrome: " + j + " * " + i + " = " + j * i);
tempAns = i * j;
}
}
}
}
private static boolean findPalindrome(int n) {
String nString = String.valueOf(n);
int j = 0;
int stringLength = nString.length() - 1;
for (int i = stringLength; i >= 0; i--) {
if (nString.charAt(j) == nString.charAt(i)) {
if (i == 0) {
return true;
}
j++;
} else if (nString.charAt(j) != nString.charAt(i)) {
return false;
}
}
return false;
}