Форум программистов, компьютерный форум, киберфорум
Наши страницы
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
DL33_1
1 / 1 / 2
Регистрация: 19.06.2016
Сообщений: 36
1

Найти число с наибольшим произведением цифр между двух данных чисел

13.01.2019, 19:15. Просмотров 358. Ответов 5

Подскажите, как мне найти число в данном промежутке, произведение цифр которого максимально?
Сразу поясняю проблему: границы промежутка (назовем их min и max) могут быть очень большими - до 10^10000. То есть перебором решить не получится, как и сохранять само произведение.

Примеры:
- от 390 до 420 - 399
- от 400 до 420 - 419
- от 1378 до 1594 - 1589 (вот это, как мне кажется, не очевидно, или по крайней мере, не интуитивно)

Объясните, пожалуйста, алгоритм. Если код - лучше на Java.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.01.2019, 19:15
Ответы с готовыми решениями:

Java2 может ли целое число быть представлено каким-либо произведением цифр, входящих в это число
Разбираю задачу..... Есть код, но некоторые моменты мне не понятны...... Определить функцию для...

Найти разность между произведением нечетных чисел и наибольшим среди отрицательных
Помогите пожалуйста решить задачку,сама пыталась,не выходит:cry:вот условие: Вводится...

Найти разность между произведением нечетных чисел и наибольшим среди отрицательных
Всем привет) Вот дали задачу племяннице, а она соответственно попросила меня ее решить полагая, что...

Найти разность между произведением нечетных чисел и наибольшим среди отрицательных
Вводится последовательность из N целых чисел, найти разность между произведением нечетных чисел и...

Найти разность между произведением нечетных чисел и наибольшим среди отрицательных
В общем сел я вечерком сделать себе лабу. Сделал,запустил...

5
shpi0
2 / 1 / 1
Регистрация: 09.01.2019
Сообщений: 5
14.01.2019, 09:56 2
Наибольшее произведение будет там, где наибольшая сумма.
В диапазоне 390 - 420, 399 имеет наибольшую сумму 3 + 9 + 9 = 21.
С остальными примерами аналогично.
Но ИМХО без перебора никак, для больших значений используйте класс BigInteger.

UPD: тут мысль пришла. Можно попробовать разворачивать числа и искать среди них самое большое.
Например, диапазон 1378 - 1594, разворачивает все числа
1378 -> 8731
1379 -> 9731
...
1594 -> 4951
В итоге получим, что 1589 будет иметь максимального "перевертыша" 9851. Соответственно, произведение его чисел и будет наибольшим.

Добавлено через 12 минут
Цитата Сообщение от shpi0 Посмотреть сообщение
UPD: тут мысль пришла. Можно попробовать разворачивать числа и искать среди них самое большое.
Например, диапазон 1378 - 1594, разворачивает все числа
1378 -> 8731
1379 -> 9731
...
1594 -> 4951
В итоге получим, что 1589 будет иметь максимального "перевертыша" 9851. Соответственно, произведение его чисел и будет наибольшим.
Но это не для всех диапазонов будет работать. Например, 9999 и 10002, произведение цифр 9999 будет больше, чем у 10002, но перевертыш у 10002 больше по значению. Значит, этот прием только для чисел одинаковой длины.
0
Aviz__
1017 / 788 / 186
Регистрация: 17.02.2014
Сообщений: 4,523
14.01.2019, 13:56 3
Цитата Сообщение от DL33_1 Посмотреть сообщение
код
пожалуйста:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Comparator;
import java.util.stream.IntStream;
 
public class Helper {
 
    private static void printMaxValFromInterval(int min, int max) {
        System.out.println(IntStream.rangeClosed(min,max)  // поток чисел, от мин до макс
                .mapToObj(String::valueOf)  // из каждого числа делаем строку
                .map(Pair::new)   // строку в объект класса Pair
                .max(Comparator.comparingLong(p -> p.mulOfNums))); // нахождение объекта с макс. произ-ем цифр и его печать
    }
 
    static class Pair {
        String num;  // число как строк
        long mulOfNums; // произведение цифр числа
 
        Pair(String num) {
            this.num = num; 
            this.mulOfNums = num.chars().map(c -> c - '0').reduce(1, (acc, i) -> acc*i);
        }
 
        @Override
        public String toString() {
            return num;
        }
    }
 
    public static void main(String[] args) {
        printMaxValFromInterval(390, 420);
        printMaxValFromInterval(400, 420);
        printMaxValFromInterval(1378, 1594);
 
    }
}
Bash
1
2
3
Optional[399]
Optional[419]
Optional[1589]
Цитата Сообщение от DL33_1 Посмотреть сообщение
Объясните
читай в коде))
1
xoraxax
2033 / 1800 / 536
Регистрация: 05.07.2013
Сообщений: 8,718
Завершенные тесты: 2
14.01.2019, 15:00 4
типа того

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main(String[] args) {
        maxMulFromRangeOf(1378, 1594);
    }
 
    private static int maxMulFromRangeOf(int start, int stop) {
        int len = String.valueOf(stop).length();
        List<Integer> nums = new ArrayList<>(len);
        nums.add(stop);
        for (int i = 0, j = 1; i < len; i++, j *= 10) {
            nums.add(stop / j * j - 1);
        }
        nums.sort(Comparator.comparingInt(i -> String.valueOf(i).chars().map(c -> c - '0')
                .reduce(1, (x, y) -> x * y))
                .reversed());
        int i;
        for (i = 0; nums.get(i) < start; i++) { }
        return nums.get(i);
    }
Добавлено через 2 минуты
Цитата Сообщение от DL33_1 Посмотреть сообщение
до 10^10000
на BigInteger сам переделывай
1
ViktorFX
14.01.2019, 21:05
  #5

Не по теме:

Цитата Сообщение от shpi0 Посмотреть сообщение
Наибольшее произведение будет там, где наибольшая сумма.
2*9 < 3*8 < 4*7; (сумма = 11)
2*9 < 5*5, притом что 2+9 > 5+5.

0
Catstail
Модератор
25041 / 12741 / 2340
Регистрация: 12.02.2012
Сообщений: 20,741
16.01.2019, 10:26 6
Иногда банан - это просто банан...

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Ideone
{
    public static int prodDig(int n)
    {
        if (n < 9)
           return n;
        else
           return (n%10)*prodDig(n/10);
    }
    public static int maxProd(int a, int b)
    {
        int i,k,max=prodDig(a),imax=a;
        for (i=a+1;i<=b; i++) 
        {
            k=prodDig(i);
            if (k > max) 
            {
                max=k;
                imax=i;
            }
        }
        return imax;
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        System.out.println(maxProd(390,420));
    }
}
3
16.01.2019, 10:26
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.01.2019, 10:26

Заменить из двух данных чисел большее число удвоенным произведением, а меньшее - полусуммой этих чисел
Составить программу, заменяющую из двух данных чисел большее число удвоенным произведением, а...

Составьте программу, заменяющую из двух данных чисел большее число удвоенным произведением, а меньшее – полусуммой этих чисел.
Составьте программу, заменяющую из двух данных чисел большее число удвоенным произведением, а...

Заменить из двух данных чисел меньшее число суммой, а большее произведением
составьте программу заменяющую из двух данных чисел меньшее число суммой а большее произведение...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.