Пример: если я возьму число 4544, то максимальное произведение, которое я получу, будет 2376, если я переставлю цифры как 5444. (54 х 44) = 2376, что больше, чем (45 х 44) = 1980.
Мой подход к решению задачи состоял в том, чтобы переставить число всеми возможными способами, разделить его на две части и затем найти оттуда максимальное произведение. Есть ли более быстрый способ решить проблему или возможен совсем другой подход к проблеме?
Вот мой код:
import java.util.*;
class MaxProduct
{
static int maxprod = 0;
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter a no");
String n = sc.next();
permute(n,0);
System.out.println("Max Product is "+maxprod);
}
public static void permute(String s,int i)
{
if ( i==s.length()-1)
{
int a = Integer.parseInt(s.substring(0,i/2+1));
int b = Integer.parseInt(s.substring(i/2+1));
maxprod = Math.max(a*b,maxprod);
}
else
{
for(int k=i;k<s.length();k++)
{
s =swapelement(s,k,i);
permute(s,i+1);
s=swapelement(s,k,i);
}
}
}
public static String swapelement(String a,int i, int j)
{
char x[]=a.toCharArray();
char ch = x[i];
x[i]=x[j];
x[j]=ch;
return String.valueOf(x);
}
}
Благодарю вас!
Это не домашнее задание, и я не только заинтересован в более быстром решении, я также хотел бы знать, есть ли другой подход к проблеме, чем мой. Это все.
Один подход может заключаться в том, чтобы найти две самые высокие цифры и сохранить их в самом левом месте, а затем сделать обратное для оставшегося 2-го места.
Например:
если у вас есть число 1234, старшие цифры - 3 и 4, поэтому давайте оставим их на первой позиции, а для оставшихся 2 сделайте то же самое, чтобы числа были:
(41*32) = 1312
так что здесь вы видите, что 1312 - это максимально возможное число
Итак, что именно я буду делать для 123456?
Сначала рассмотрим меньшую проблему. Для переменных x,y
вам дано
x + y = c (constant)
Вопрос в том, когда x*y
будет максимальным? Это можно решить разными способами, один из них — дифференциальная математика. Короче говоря, чем ближе x
и y
друг к другу, тем больше их произведение.
A
и B
)A>B
), назначьте оставшиеся цифры, чтобы максимизировать B
(большие цифры в порядке убывания). Для A
мы используем оставшиеся меньшие цифры, чтобы составить из них наибольшее число. Присвоение больших цифр B
сделано, чтобы сделать его ближе к A
.Номер = 123456
Взяв самые большие цифры, A = 6 and B = 5
. Теперь мы будем жадно максимизировать B
, чтобы числа стали A = 621 and B = 543
Номер = 88871256
Взяв самые большие цифры, A = 8 and B = 8
. Поскольку они все еще равны, мы повторяем шаг 1, поэтому A = 88 and B = 87
. Теперь мы будем жадно максимизировать B
, чтобы числа стали A = 8821 and B = 8765
.
Поскольку это довольно простая проблема, добавление какой-либо реализации кажется ненужным.
Пожалуйста, покажите нам код вашего решения. (Что бы это ни стоило, если у вас есть решение головоломки, которое выполняется в течение практического времени, вы не необходимость более быстрое решение. Если только это не домашнее задание, и они требовать самое быстрое решение для максимальной оценки. И даже тогда, возможно, вы не должны просить о помощи, как это...)