Форум программистов, компьютерный форум, киберфорум
Наши страницы

Java SE (J2SE)

Войти
Регистрация
Восстановить пароль
 
Fiora111
3 / 3 / 1
Регистрация: 26.09.2015
Сообщений: 36
#1

Эффективный алгоритм для задачи - Java SE

14.04.2016, 13:47. Просмотров 297. Ответов 6
Метки нет (Все метки)

Условия следующие:
Даны n различных натуральных чисел и число m. Нужно выяснить, можно ли представить число m в виде произведения некоторых из них.
Помогите решить, пожалуйста, или идейку хотя бы подкиньте, а то я понятия не имею как написать эффективный алгоритм к этой задаче.
Заранее спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.04.2016, 13:47
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Эффективный алгоритм для задачи (Java SE):

Эффективный алгоритм перетасовки эелементов массива - Java SE
Друзья, написал вот такую функцию public static void arrayShuffle(int arr) { int length = arr.length; ...

Алгоритм для задачи - Java SE
Задача следующая: Выравнивание команд Для проведения различных игр и конкурсов на военно-патриотическом слете среди лучших...

Алгоритм задачи - Java SE
Простите за тупость, но пишу курсач по дискретной математике. Тема: Перебор размещений с повторениями и без повторений. Все уже давно...

нужен алгоритм для подсчета общей суммы за месяц(для графика) - Java SE
в общем есть сайт на java(с использованием jsf 2.0, hibernate, eclipse, springframework). в нем реализована система подсчета семейного...

Ищу задачи для новичка - Java SE
Доброго времени суток. Я изучаю java и дошел до изучение методов Мне нужно попрактиковаться прошу вас дат мне логике задачи !!!

Алгоритм для морфемы - Java SE
вообщем есть словарь из него будут браться слова и составляется предложение :"купить два пицца" и нужно исправить чтоб вышло "купить две...

6
HOBATOP
309 / 298 / 129
Регистрация: 14.09.2015
Сообщений: 821
14.04.2016, 21:52 #2
Fiora111, вот читайте, проводите параллели...
0
КОП
438 / 345 / 103
Регистрация: 15.08.2010
Сообщений: 932
14.04.2016, 23:23 #3
ну или можно просто в цикле проходить по n и пытаться делить без остатка
0
ya_noob.vrn
1 / 1 / 0
Регистрация: 26.12.2009
Сообщений: 22
16.04.2016, 00:06 #4
Вот вариант в генериками:

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
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
 
/**
 * Created by l1fe on 15.04.16.
 */
public class TestGeneric {
    public static void main(String[] args) {
        Random random = new Random();
        List<Integer> n = new ArrayList<>();
        int intSize = 30;
        int m = 300;
        int tmp;
        for (int i =0;i<intSize;i++){
            n.add(random.nextInt(100) + 1);
        }
        System.out.println(n);
        for (int i =0;i<n.size();i++){
            if (m%n.get(i) == 0){
                tmp = m/n.get(i);
                if (n.contains(tmp))
                    System.out.println("m можно представить в виде: " + n.get(i) + " x " + tmp);
            }
        }
    }
 
 
}
Вот вариант без генериков:

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
import java.util.Random;
 
/**
 * Created by l1fe on 15.04.16.
 */
public class Test {
    public static void main(String[] args) {
        Random random = new Random();
        int[] n = new int[30];
        int tmp;
        int m = 300;
        for (int i = 0; i < n.length; i++){
            n[i] = random.nextInt(101) +1;
            System.out.print(n[i] + " ");
        }
        System.out.println();
        for (int i = 0; i < n.length; i++){
            if (m%n[i]==0){
                tmp = m/n[i];
                for (int j = 0; j < n.length; j++){
                    if (tmp == n[j]){
                        System.out.println("m можно представить в виде: " + n[i] + " x " + tmp);
                    }
                }
            }
        }
    }
}
Критика привествуется, написал первое, что пришло в голову.
0
Den_Ur
8 / 8 / 4
Регистрация: 11.04.2016
Сообщений: 75
16.04.2016, 14:25 #5
Код кривой, но ищет вроде верно

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Example2 {
 
    public static void main(String[] args) {
        
        final int TOTAL_NUMBERS = 3;                // количество элементов в массиве
        final int RESULT = 100;                     // значение искомого результата
        int[] array = new int[TOTAL_NUMBERS];       // 
        
        // Случайные числа помещаем в массив
        
        for(int i = 0; i < array.length; i++){         
            array[i] = (int)(Math.random() * 100);
            System.out.print(" " + array[i]);
        }
        System.out.println();
        
        // Начинаем перебор всевозможных вариантов перемножения всех элементов массива
        // для этого в методе setMultipliers выбираем необходимые множители, 
        // а остальным присваиваем единицу, поскольку перемножение числа на единицу
        // дает это же самое число
        
        for (int i = 0; i < Math.pow(2, array.length); i++){
            int[] tmpArr = setMultipliers(array, i);
            System.out.println();
            int res = 1;
            for (int n = 0; n < tmpArr.length; n++){
                System.out.print(n + " - "  + tmpArr[n]+ "|");
                res *= tmpArr[n];
            }
            // выводим текущий расчет для контроля
            System.out.println("\nres = " + res);
            
            // если вариант найден, то выводится соответствующая строка
            if (res == RESULT) System.out.println("Answer is finded!");    
        }
    }
    
    // в этом методе назначаем множители по маске, которая основана на смещении
    
    private static int[] setMultipliers(int[] array, int value){
        
        int[] mArray = array.clone();
        int mask = 1;
        
        for (int i = 0; i < mArray.length; i++){
            if ((value & mask) == mask){
                mArray[i] = 1;
            }
            mask <<= 1;
        }
        return mArray;
    }
}
0
korvin_
2084 / 1575 / 254
Регистрация: 28.04.2012
Сообщений: 5,672
16.04.2016, 20:02 #6
Цитата Сообщение от ya_noob.vrn Посмотреть сообщение
Критика привествуется
Неэффективно, проходов по массиву n2. И почему ты предположил, что множителей может быть только два?
0
Aviz__
314 / 210 / 44
Регистрация: 17.02.2014
Сообщений: 1,643
18.04.2016, 15:09 #7
Как идея, причем, очень ограниченная, разложить m на множители. Затем, набор множителей сравнивать с данным набором n.
0
18.04.2016, 15:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.04.2016, 15:09
Привет! Вот еще темы с ответами:

Рекурсивный метод для решения задачи - Java SE
Есть 2 точки координат, допустим расстояние между ними 200 метров. Нужно добавить точки по 25 метров между этими 2-мя точками. И...

Нужна идея для задачи с графами - Java SE
Есть условие: Создать классы для организации иерархии сотрудников в фирме (как минимум несколько подразделений, со вложенностями). Данные...

Сделать интерфейс для готовой задачи - Java
Для нижеприведенной программы реализовать общий интерфейс, который реализует функцию «произнести лозунг». import java.util.Scanner; ...

Интересные задачи для начинающих и не только - Java
Сегодня у меня более общий вопрос - подскажите ресурс с задачами по Java, начиная от самого HelloWorld и до, скажем, свободного...


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

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

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