Перебор всех вариантов

@Raketa · Регистрация: 31.01.2015

Author24 — интернет-сервис помощи студентам

Доброго времени суток...помогите пожалуйста...а то уже мучаюсь не один день...есть такая задачка сколькими вариантами можно сложить число 10 с чисел 2 3 5 (с повторениями 33222 22233)?

@megastriker · 04.12.2015, 09:41

а при чем тут java se?)
судя по вашему вопросу, ответ бесконечное число раз

@Alradalion · 04.12.2015, 10:24

В смысле сложить? 10=2+3+5, так, что ли?

@Raketa · 04.12.2015, 10:48 **[ТС]**

Alradalion, нет вы не правильно поняли...
есть число 10 нужно посчитать сколькими комбинациями сумм чисел 2 3 5 его можно сложить
типа(22222;2233;55 и т.д.)

@Alradalion · 04.12.2015, 10:59

Raketa, а я по-вашему, не сумму написал?
Ладно, попробуем по-другому. То есть если я сложу числа из вашей записи

Сообщение от Raketa

(с повторениями 33222 22233)?

я должен получить в сумме 10?

@Raketa · 04.12.2015, 11:02 **[ТС]**

Alradalion, пардон(22222;2233;3322;55 и т.д.)

@HOBATOP · 04.12.2015, 13:15

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

Добавлено через 13 минут
...редактировать не получается уже, время истекло. Вот ещё ссылка на похожую задачу с решением. А вообще, конечно, было бы неплохо и самому автору темы поискать на просторах, прежде чем помощи просить...

Pablito · 04.12.2015, 16:41

без оптимизаций, тупо перебором

Java

public class TupoPerebor {
 
    public static void main(String[] args) {
 
        int[] s = {0, 2, 3, 5};
        int count = 0;
        for (int i1 = 0; i1 < 4; i1++) {
            for (int i2 = 0; i2 < 4; i2++) {
                for (int i3 = 0; i3 < 4; i3++) {
                    for (int i4 = 0; i4 < 4; i4++) {
                        for (int i5 = 0; i5 < 4; i5++) {
                            int sum = s[i1] + s[i2] + s[i3] + s[i4] + s[i5];
                            if (sum == 10) {
                                count++;
                                System.out.printf("%d+%d+%d+%d+%d = %d%n", s[i1], s[i2], s[i3], s[i4], s[i5], sum);
                            }
                        }
                    }
                }
            }
        }
        System.out.println("Всего вариантов " + count);
    }
}

вариантов получилось 101

@Raketa · 04.12.2015, 18:03 **[ТС]**

Паблито, спасибо...но должно вийти 14(

Добавлено через 10 минут
Паблито, а если мне нада будет поменять условия с 10 например на 40...это уже не подойдет ведь(

Pablito · 04.12.2015, 18:05

точно, мой косяк
тогда вот такой быдлокод

Java

import java.util.HashSet;
import java.util.Set;
 
public class TupoPerebor {
 
    public static void main(String[] args) {
 
        Set<String> set = new HashSet<>();
        int[] s = {0, 2, 3, 5};
        int count = 0;
        for (int i1 = 0; i1 < 4; i1++) {
            for (int i2 = 0; i2 < 4; i2++) {
                for (int i3 = 0; i3 < 4; i3++) {
                    for (int i4 = 0; i4 < 4; i4++) {
                        for (int i5 = 0; i5 < 4; i5++) {
                            int sum = s[i1] + s[i2] + s[i3] + s[i4] + s[i5];
                            if (sum == 10) {
                                String str = s[i1] + "" + s[i2] + "" + s[i3] + "" + s[i4] + "" + s[i5];
                                set.add(str.replace("0", ""));
                            }
                        }
                    }
                }
            }
        }
        for (String str: set) System.out.println(str);
        System.out.println("Всего вариантов " + set.size());
    }
}

Добавлено через 54 секунды
по первых пойдет, там поменять с 10 на 40
во-вторых по условию было сказано ДЕСЯТЬ

@Raketa · 04.12.2015, 18:06 **[ТС]**

Паблито, это да спасибо) я для себя просто хочу спросить как его сделать универсальным

Pablito · 04.12.2015, 18:10

мой вариант не выйдет сильно универсальным, потому что это прямой перебор именно под задачу
а вообще там надо добавлять вложенные циклы
сейчас их пять потому что при условии что есть слагаемые 2 3 5 максимум может быть пять двоек что бы получить в сумме 10
для сумы 40 прийдется городить слишком мого вложенных циклов

@Raketa · 04.12.2015, 18:11 **[ТС]**

Паблито, вот блин...а что ж тогда предпринять?

Pablito · 04.12.2015, 18:14

выпей
это я к тому что сразу надо говорить что там может быть не 10 а 40 или вообще boolean значение

@Raketa · 04.12.2015, 18:49 **[ТС]**

Паблито, не вариант...нада будет как то еще модифицировать а потом уже выпить,но спасибо

Добавлено через 6 минут
Паблито, мой косяк не спорю...10 просто для примера привел....

Добавлено через 27 минут
HOBATOP, спасибо да я находил эту тему...но не смог разсмотреть что ето то что мне нужно...

@HOBATOP · 04.12.2015, 21:07

Raketa, так а доработать? Не судьба? Первый вариант вероятно и не смотрели? Тут какая-то непонятная чепуха со ссылкой произошла, но можно было бы найти и по тем осколкам, которые остались. Вообще я ни когда не выкладываю чужой код, стараюсь давать ссылку. Ну раз уж не выходит, то вот такой вариант (он мне больше нравится, но допиливать его сложнее):

Кликните здесь для просмотра всего текста

Java

import java.util.*;
public class PerestInt {
    private static final int SUM = 10;
    private static final int[] a = {2, 2, 2, 2, 2, 3, 3, 5, 5};
    private static final int m = a.length;
    private static int[] pole = new int[m];    
    private static ArrayList<ArrayList<Integer>> summs = new ArrayList<ArrayList<Integer>>();
    
    public static void perest(int n, int[] r) {
        int[] r1 = new int[m];        
        if (n == m) {
            sum(pole);                
        } else {
            for (int i = 0; i < m - n; i++) {
                pole[n] = r[i];
                int k = 0;            
                for (int j = 0; j < m - n; j++) {
                    if (j != i) {
                        r1[k] = r[j];
                        k++;
                    }
                }
                perest(n + 1, r1);
            }
        }
    }
    
    private static void sum(int [] p) {
        ArrayList<Integer> v = new ArrayList<Integer>();            
        int s = 0;
        for(int el : p) {
            s += el;
            if (s <= SUM) {
                v.add(el);
                Collections.sort(v);
            }
            
            if (s == SUM && !summs.contains(v)) {                
                summs.add(v);
                break;
            }
        }
    }
        
    public static void main(String[] args) {
        perest(0, a);
        for(ArrayList<Integer> v : summs) {
            System.out.println(v);
        }
    }
}

при таких параметрах выдаёт следующее:

Java

[2, 2, 2, 2, 2]
[2, 2, 3, 3]
[2, 3, 5]
[5, 5]

@Raketa · 04.12.2015, 21:54 **[ТС]**

HOBATOP,ага..спасибо...я уже решил задание...спасибо большое за помощь!!!
P.S. Тему можно закрывать

@Raketa 1 / 1 / 0 Регистрация: 31.01.2015 Сообщений: 197
	04.12.2015, 21:54 [ТС]	17
	HOBATOP,ага..спасибо...я уже решил задание...спасибо большое за помощь!!! P.S. Тему можно закрывать 0

@Raketa 1 / 1 / 0 Регистрация: 31.01.2015 Сообщений: 197
		1
	Перебор всех вариантов 03.12.2015, 23:51. Показов 2257. Ответов 16 Метки нет (Все метки) Доброго времени суток...помогите пожалуйста...а то уже мучаюсь не один день...есть такая задачка сколькими вариантами можно сложить число 10 с чисел 2 3 5 (с повторениями 33222 22233)? 0

@megastriker 53 / 53 / 39 Регистрация: 05.12.2010 Сообщений: 261
	04.12.2015, 09:41	2
	а при чем тут java se?) судя по вашему вопросу, ответ бесконечное число раз 0

@Alradalion 132 / 126 / 85 Регистрация: 13.09.2013 Сообщений: 485
	04.12.2015, 10:24	3
	В смысле сложить? 10=2+3+5, так, что ли? 0

@Raketa 1 / 1 / 0 Регистрация: 31.01.2015 Сообщений: 197
	04.12.2015, 10:48 [ТС]	4
	Alradalion, нет вы не правильно поняли... есть число 10 нужно посчитать сколькими комбинациями сумм чисел 2 3 5 его можно сложить типа(22222;2233;55 и т.д.) 0

@Alradalion 132 / 126 / 85 Регистрация: 13.09.2013 Сообщений: 485
	04.12.2015, 10:59	5
	Raketa, а я по-вашему, не сумму написал? Ладно, попробуем по-другому. То есть если я сложу числа из вашей записи Сообщение от Raketa (с повторениями 33222 22233)? я должен получить в сумме 10? 0

@Raketa 1 / 1 / 0 Регистрация: 31.01.2015 Сообщений: 197
	04.12.2015, 11:02 [ТС]	6
	Alradalion, пардон(22222;2233;3322;55 и т.д.) 0

@HOBATOP 323 / 310 / 206 Регистрация: 14.09.2015 Сообщений: 827
	04.12.2015, 13:15	7
	Raketa, вот взгляните, что в похожем направлении. Проанализировать и подправить для Ваших нужд уже не так сложно, как с нуля велосипед изобретать. Добавлено через 13 минут ...редактировать не получается уже, время истекло. Вот ещё ссылка на похожую задачу с решением. А вообще, конечно, было бы неплохо и самому автору темы поискать на просторах, прежде чем помощи просить... 0

@Raketa 1 / 1 / 0 Регистрация: 31.01.2015 Сообщений: 197
	04.12.2015, 18:03 [ТС]	9
	Паблито, спасибо...но должно вийти 14( Добавлено через 10 минут Паблито, а если мне нада будет поменять условия с 10 например на 40...это уже не подойдет ведь( 0

@Raketa 1 / 1 / 0 Регистрация: 31.01.2015 Сообщений: 197
	04.12.2015, 18:06 [ТС]	11
	Паблито, это да спасибо) я для себя просто хочу спросить как его сделать универсальным 0

Pablito 2884 / 2296 / 769 Регистрация: 12.05.2014 Сообщений: 7,978
	04.12.2015, 18:10	12
	мой вариант не выйдет сильно универсальным, потому что это прямой перебор именно под задачу а вообще там надо добавлять вложенные циклы сейчас их пять потому что при условии что есть слагаемые 2 3 5 максимум может быть пять двоек что бы получить в сумме 10 для сумы 40 прийдется городить слишком мого вложенных циклов 0

@Raketa 1 / 1 / 0 Регистрация: 31.01.2015 Сообщений: 197
	04.12.2015, 18:11 [ТС]	13
	Паблито, вот блин...а что ж тогда предпринять? 0

Pablito 2884 / 2296 / 769 Регистрация: 12.05.2014 Сообщений: 7,978
	04.12.2015, 18:14	14
	выпей это я к тому что сразу надо говорить что там может быть не 10 а 40 или вообще boolean значение 0

@Raketa 1 / 1 / 0 Регистрация: 31.01.2015 Сообщений: 197
	04.12.2015, 18:49 [ТС]	15
	Паблито, не вариант...нада будет как то еще модифицировать а потом уже выпить,но спасибо Добавлено через 6 минут Паблито, мой косяк не спорю...10 просто для примера привел.... Добавлено через 27 минут HOBATOP, спасибо да я находил эту тему...но не смог разсмотреть что ето то что мне нужно... 0

Перебор всех вариантов

Решение