VPF::Поиск в ширину - Форум программистов

nightspirit

Дата 14.4.2009, 12:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: нет

Всем доброго времени суток!
Есть такая проблемка:
первое число-1234567,второе-7654321.
Первое число состоит из пар цифр 12,23,34,45,56 и 67.
Нужно взяв все пары поочередно,раскидать их по краям исходного числа(то есть беря первую пару,получим новое число 1345672,вторую пару-2145673,ну и т.д для всех пар).
Для новых получиных чисел(в нашем случае 1345672,2145673 и т.д) проделать тоже самое,что и с исходным числом.
Проделывать нужно этот алгоритм до тех,пока не наткнемся на число 7654321.
В итоге работы получится что то вроде дерева с корнем 1234567.
Получение новых чисел с помощью разброса пар по краям организовано,надо сделать сам поиск.
Подскажите пожалуста,кто знает.

mes

Дата 14.4.2009, 12:50 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

Репутация: 79
Всего: 250

как я понял, необходимое Вам решается рекурсией.
примерно так :

Код


bool find_mutation (unsigned long ul, unsigned long val) // ul - для изменения, val - эталон для сравнения
{
    unsigned long mutant = ul;
    const unsigned len = get_length(ul);
    for (unsigned i=0; i<len-1; mutant = make_mutation (ul,i++))   //  make_mutation - ф-я раскидываюшая пару по краям
    if (mutant ==val) return true;
    else if (find_mutation (mutant, val)) return true;
    return false;
}

Это сообщение отредактировал(а) mes - 14.4.2009, 15:48

--------------------

http://opendots.net

nightspirit

Дата 14.4.2009, 13:08 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: нет

mes,да все спасибо,она находит.А я там придумывал такие огромные ф-ии smile

можно еще только один вопрос:
как добавить сюда количество итераций,ну то есть не булевской ф-ия была а лонговской например.
че то так и сяк попробывал,не идет...

Cheloveck

Дата 14.4.2009, 13:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 5
Всего: 32

Цитата

как добавить сюда количество итераций,ну то есть не булевской ф-ия была а лонговской например.

Код


unsigned long find_mutation (unsigned long ul, unsigned long val) // ul - для изменения, val - эталон для сравнения
{
    unsigned long mutant = ul;
    const unsigned len = get_length(ul);
    unsigned long i;
    for (i=0; i<len-1; mutant = make_mutation (ul,i))   //  make_mutation - ф-я раскидываюшая пару по краям
    if (mutant ==val) return i;
    else if (find_mutation (ul, val)) return i;
    return -1;
}

так например?

--------------------

mes

Дата 14.4.2009, 13:15 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

Репутация: 79
Всего: 250

Цитата(nightspirit @ 14.4.2009, 12:08

)

как добавить сюда количество итераций,н

думаю так, проверяйте:

Код


unsigned find_mutation (unsigned long ul, unsigned long val) // ul - для изменения, val - эталон для сравнения
{
    unsigned long mutant = ul;
    const unsigned len = get_length(ul);
    for (unsigned i=0; i<len-1; mutant = make_mutation (ul,i++))   //  make_mutation - ф-я раскидываюшая пару по краям
    if (mutant ==val) return i+1;
    else { unsigned j = find_mutation (mutant, val); if (j) return j+i; }
    return 0; // 0 значит не найдено
}

подправлено..

Добавлено @ 13:17

Цитата(Cheloveck @ 14.4.2009, 12:13

)

unsigned long fin....
return -1;

Добавлено @ 13:20

Цитата(Cheloveck @ 14.4.2009, 12:13

)

else if (find_mutation (ul, val)) return i;

будет считать шаги только участка, а не всей ветки.

Добавлено @ 13:21

Цитата(Cheloveck @ 14.4.2009, 12:13

)

unsigned long i;

а ее зачем вынесли из цикла ?

Это сообщение отредактировал(а) mes - 14.4.2009, 15:49

--------------------

http://opendots.net

Cheloveck

Дата 14.4.2009, 13:28 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 5
Всего: 32

Цитата

будет считать шаги только участка, а не всей ветки.

сорри, не стал углублятся в код, понатыкал сразу во всех return'ах))

Цитата

а ее зачем вынесли из цикла ?

чтоб вернуть её. Ну да, в данном случае можно всё сделать и внутри, но часто требуется работать с переменной после цикла. Обычно я такие счётчики выношу.

Это сообщение отредактировал(а) Cheloveck - 14.4.2009, 13:32

--------------------

nightspirit

Дата 14.4.2009, 13:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: нет

mes,че то не хочет,выдает Unhandled exception at 0x00411549 in obr.exe: 0xC00000FD: Stack overflow.

math64

Дата 14.4.2009, 15:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 12
Всего: 72

Заменините рекурсивный вызов на int j = find_mutation (mutant, val); а то вы повторяете поиск с тем те числом
Но и после этой замениу в процессе перестановок можно вернуться к числу, которое уже было.
Нужно запоминать опробованные числа
Кроме того, это поиск в глубину, а автор хотел поиск в ширину.

mes

Дата 14.4.2009, 15:36 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

Репутация: 79
Всего: 250

Цитата(math64 @ 14.4.2009, 14:10

)

Кроме того, это поиск в глубину, а автор хотел поиск в ширину.

решается путем разделения тела цикла на два (вначале склонился в пользу первого варианта, так как во втором будет немного повторений, а на слово из топика "ширина" не обратил внимания smile

)

Код


...
    for (unsigned i=0; i<len-1; mutant = make_mutation (ul,i++))   
    if (mutant == val) return i+1;
    mutant=ul;
    for (unsigned i=0; i<len-1; mutant = make_mutation (ul,i++))
    { unsigned j = find_mutation (mutant, val); if (j) return j+i; }
...

Добавлено @ 15:39

Цитата(math64 @ 14.4.2009, 14:10

)

Замените рекурсивный вызов на int j = find_mutation (mutant, val);

ага

и еще инкрементация счетчика была забыта... smile

подправил в предыдущих постах smile

Это сообщение отредактировал(а) mes - 14.4.2009, 15:54

--------------------

http://opendots.net

nightspirit

Дата 15.4.2009, 15:59 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: нет

mes,че то все равно тажа самая ошибка выскакивает,что стек переполнин...

math64

Дата 15.4.2009, 16:09 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 12
Всего: 72

Я же сказал: нужно запоминать список использованных чисел:

Код


unsigned find_mutation (unsigned long ul, unsigned long val, std::vector<unsigned long>& used_numbers)
{
   ...
}

nightspirit

Дата 15.4.2009, 16:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: нет

math64,а куда вставить used_numbers?
глупец я еще в с++ smile

Dov

Дата 15.4.2009, 18:17 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 11
Всего: 88

Цитата(nightspirit @ 15.4.2009, 15:59

)

mes,че то все равно тажа самая ошибка выскакивает,что стек переполнин...

В бесконечную рекурсию втулился, скорее всего. Код покажи, что бы не гадать на кофейной гуще.

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

Anikmar

Дата 15.4.2009, 19:26 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 5
Всего: 59

Цитата(nightspirit @ 15.4.2009, 16:31

)

math64,а куда вставить used_numbers?

Ох, опять про гусар вспомнил... smile

math64

Дата 16.4.2009, 08:30 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 12
Всего: 72

Код


typedef unsigned long number;
typedef std::vector<number> numbers;
numbers find_mutation (number ul, number val, numbers used=numbers())
{
    numbers res;
    if (ul == val) {
       res.push_back(val);
       return res;
    }
    if (contains(used, ul)
      return res; // вернулись к пройденному числу - пропускаем
    const unsigned len = get_length(ul);
    for (unsigned i=0; i<len-1; i++) {
      number mutant = make_mutation (ul,i)
      if (mutant == val) {
        res.push_back(ul);
        res.push_back(val);
        return res;
      }
    }
    used.push_back(ul);
    for (unsigned i=0; i<len-1; i++) {
      number mutant = make_mutation (ul,i);
      if (contains(used, mutant))
        continue; // вернулись к пройденному числу - пропускаем
      numbers res1 = find_mutation (mutant, val, used);
      if (!res1.empty()) {
        used.pop_back();
        res1.insert(res1.begin(), ul);
        return res1;
      }
    }
    used.pop_back();
    return res; //  пустой res значит не найдено
}

contains(numbers&, number) - проверка содержится ли number в векторе
PS: Данных алгоритм остаётся поиском в глубину (хотя на глубину 1 производится предварительный поиск в ширину) и результат не обязательно кратчайший

Это сообщение отредактировал(а) math64 - 16.4.2009, 11:44

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »