Модераторы: LSD, AntonSaburov
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Рекурсивный поиск, в векторе, все возможные числа сумма которых = n  
:(
    Опции темы
VitaL
Дата 23.1.2009, 02:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 94
Регистрация: 24.6.2006

Репутация: нет
Всего: нет
Пытаюсь реализировать следующий алгоритм который исчет рекурсивным методом все возможные наборы цифр сумма которых равняется цифре н

сделанный код

Код


package recursividad;
import java.io.*;
import java.util.*;



/**
 *
 * @author VitaL
 */
public class Main {
        int n,nn,i,ii;
        int pos = 0;
        int cont = 0;
        String texto1; 
        Vector C = null;
        Vector CC = null;
        InputStreamReader isr=new InputStreamReader(System.in);
        BufferedReader br=new BufferedReader(isr);
        
    public static void main(String[] args) throws IOException {
        Main prog = new Main();
//колличество цифр в векторе
        System.out.println("Ingrese el numero n, la cantidad de numeros positivos: ");
        prog.texto1=prog.br.readLine();
        prog.n = Integer.parseInt(prog.texto1);
        prog.C = new Vector(prog.n);
        prog.CC = new Vector(prog.n);
        while(prog.pos<prog.n){
//цифра в такомто месте в векторе
            System.out.println("Ingrese el numero "+(prog.pos+1)+" del conjunto C: ");
            prog.texto1=prog.br.readLine();
            prog.C.addElement (Integer.parseInt(prog.texto1));
            prog.pos++;
        }
        for(int j = 0; j<prog.n;j++){
           System.out.print ( prog.C.elementAt (j) + " "); 
        }
//цифра н которой должна равнятся сумма набора цифр
        System.out.println("\nIngrese el numero i: ");
        prog.texto1=prog.br.readLine();
        prog.i = Integer.parseInt(prog.texto1);
        for(int g = 0; g < prog.n ;g++){
            prog.CC.removeAllElements();
            prog.pos = 0;
            prog.cont = 0;
            prog.ii = 0;
            if(g != 0){
                prog.nn = (Integer)prog.C.elementAt(g);
                prog.C.set(g, prog.C.elementAt(0));
                prog.C.set(0, prog.nn);
            }
//            System.out.print ("\nConjuntos\n"); 
            prog.buscar_conjunto(prog.pos);
        }
    }
//Рекурсивная функция
        public void buscar_conjunto(int pos){
            if(pos<0 || pos>=C.size())
                return;

            CC.addElement(C.elementAt(pos));
            ii+=(Integer)C.elementAt(pos);
                
            if (ii == i){
                print();
                ii-=(Integer)C.elementAt(pos);
                CC.remove(C.elementAt(pos));
            }
            if(ii>i){
                ii-=(Integer)C.elementAt(pos);
                CC.remove(C.elementAt(pos));
            }
            buscar_conjunto(pos+1);
        }
        
        public void print(){
            System.out.print (CC); 
        }
}



испытательный пример.... вектор 1 2 3 4 5

цифра 5 которой должна равнятся сумма наборов цифр

результат [4, 1][5]

В результаты невходит [2,3]

Помогите разобраться пожалуйста  smile 
 
PM MAIL WWW Skype   Вверх
ecologist
Дата 23.1.2009, 08:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 452
Регистрация: 28.2.2007

Репутация: 2
Всего: 9
А искать должен только сумму двух чисел или может быть и 3, и 5, и 10 ? 

Например в векторе есть 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Надо найти числа для 8. Это может быть - 3+5, 1+2+5, 7+1, 1+3+4.
PM MAIL   Вверх
math64
Дата 23.1.2009, 09:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72
А зачем ты портишь исходный вектор C?
После того как ты удалил из него первый элемент, он стал [2, 3, 4, 5]. Дальше ты продолжаешь поиск с pos=1, т.е. 2 пропускаешь.
PM   Вверх
VitaL
Дата 23.1.2009, 13:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 94
Регистрация: 24.6.2006

Репутация: нет
Всего: нет
набор цифр может быть с неважным колличесвтом цифр, главное чтоб их сумма равнялась цифре н

я  меняю местами элементы в векторе для дальнейшего поиска, например

вектор 1 2 3 4 5 

начинаю поиск с 1 пробую все варианты с оставшимися цифрами

возвращаюсь, делаю тоже самое но теперь первый элемент это тот который был на втором месте

меняю местами 1 и 2

начинаю поиск с 2 ...

это как мат. дерево


ЗЫ в векторе только позитивные цифры
PM MAIL WWW Skype   Вверх
dorogoyIV
Дата 23.1.2009, 19:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46
найти два числа не сложно:
Код

import java.util.*;

public class FindNumbers
{
 static Vector <Integer> v = new Vector <Integer> ();
 static int N = 11; // какое то число

 public FindNumbers()
 {
  v.add(6);
  v.add(4);
  v.add(7);
  v.add(5);
  v.add(3);

  Collections.sort(v);
 }

 public static void main(String [] args)
 {
  new FindNumbers();

  int pos = 0;

  for(int i = 0; i < v.size(); i++)
  {
   int first = v.get(pos);

   for(int j = pos + 1; j < v.size(); j++)
   {
    int second = v.get(j);

    if((first + second) == N)
     System.out.println(first + " + " + second + " = " + N);
   }
   pos++;
  }
 }
}

что бы найти больше двух чисел - обдумываю несколько вариантов поиска  smile 
PM MAIL   Вверх
AndrewMormysh
Дата 23.1.2009, 19:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 50
Регистрация: 8.2.2008

Репутация: 1
Всего: 1
причем здесь Java?
PM MAIL   Вверх
VitaL
Дата 24.1.2009, 00:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 94
Регистрация: 24.6.2006

Репутация: нет
Всего: нет
алгоритм должен быть рекурсивным  smile 

написанный на яве вот при чёт тут ява...
PM MAIL WWW Skype   Вверх
dorogoyIV
Дата 24.1.2009, 01:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46
Цитата(VitaL @  24.1.2009,  00:13 Найти цитируемый пост)
алгоритм должен быть рекурсивным   

ну это понятно... просто выходные, и мой Орган из двух букв плохо соображает под воздействием паров алкоголя.
если никто не подскажет, то после выходных постараюсь отписаться (если время будет, потерпишь?).  smile 

по крайней мере мой код не пропускает варианты, в отличие от твоего  smile 
PM MAIL   Вверх
ivg
Дата 24.1.2009, 07:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Autonomous R&D
**


Профиль
Группа: Участник
Сообщений: 686
Регистрация: 8.2.2006
Где: Екатеринбург

Репутация: 33
Всего: 81
Код

import java.util.*;

public class Test {

    static final int ARRAY_LENGTH = 10;
    static final int MAX_NUMBER = 32;

    static int[] extract(int[] src, BitSet which) {
        int res[] = new int[which.cardinality()];
        for (int i = 0, j = 0; i < src.length; ++i) {
            if (which.get(i))
                res[j++] = src[i];
        }
        return res;
    }

    static void reqSearch(int test, int[] src, int fIndex, BitSet res,
            List<BitSet> results) {
        int sub = test - src[fIndex];
        if (sub == 0) {
            BitSet clon = (BitSet) res.clone();
            clon.set(fIndex);
            results.add(clon);
        }
        if (++fIndex < src.length) {
            res.set(fIndex - 1);
            reqSearch(sub, src, fIndex, res, results);
            res.clear(fIndex - 1);
            reqSearch(test, src, fIndex, res, results);
        }
    }

    public static void main(String[] args) throws Exception {
        List<BitSet> results = new ArrayList<BitSet>();
        int[] array = new int[ARRAY_LENGTH];
        int sum = 0;
        Random rnd = new Random();
        for (int i = 0; i < array.length; ++i) {
            array[i] = rnd.nextInt(MAX_NUMBER);
            sum += array[i];
        }
        sum = sum * 3 / 4;
        System.out.println("Array:" + Arrays.toString(array));
        System.out.println("sum = " + sum);
        long t1 = System.nanoTime();
        reqSearch(sum, array, 0, new BitSet(array.length), results);
        long t2 = System.nanoTime();
        System.out.println("Results:");
        for (BitSet res : results) {
            System.out.println(Arrays.toString(extract(array, res)));
        }
        System.out.println("Search time: " + (double) (t2 - t1) / 1000 + " mks");
    }
}
PM MAIL   Вверх
dorogoyIV
Дата 24.1.2009, 12:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46
ivg, Random тут как прописался? для чего он? по моему он тут ни к селу ни к городу  smile 
PM MAIL   Вверх
ivg
Дата 24.1.2009, 15:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Autonomous R&D
**


Профиль
Группа: Участник
Сообщений: 686
Регистрация: 8.2.2006
Где: Екатеринбург

Репутация: 33
Всего: 81
Цитата(dorogoyIV @  24.1.2009,  14:05 Найти цитируемый пост)
ivg, Random тут как прописался? для чего он? по моему он тут ни к селу ни к городу

Для задания содержимого исходного массива. Улучшаем навыки чтения чужих неоткомментированных исходников. smile

Это сообщение отредактировал(а) ivg - 24.1.2009, 15:38
PM MAIL   Вверх
VitaL
Дата 24.1.2009, 20:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 94
Регистрация: 24.6.2006

Репутация: нет
Всего: нет
ivg, ого, работает, только ниииипоняяяяяяяяяятно  smile  smile буду разбираться что к чему, спасибо!  smile   smile 
PM MAIL WWW Skype   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Java"
LSD   AntonSaburov
powerOn   tux
javastic
  • Прежде, чем задать вопрос, прочтите это!
  • Книги по Java собираются здесь.
  • Документация и ресурсы по Java находятся здесь.
  • Используйте теги [code=java][/code] для подсветки кода. Используйтe чекбокс "транслит", если у Вас нет русских шрифтов.
  • Помечайте свой вопрос как решённый, если на него получен ответ. Ссылка "Пометить как решённый" находится над первым постом.
  • Действия модераторов можно обсудить здесь.
  • FAQ раздела лежит здесь.

Если Вам помогли, и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, LSD, AntonSaburov, powerOn, tux, javastic.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Java: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0538 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.