VPF::Обход в ширину - Форум программистов

nightspirit

Дата 18.4.2009, 18:30 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Это сообщение отредактировал(а) nightspirit - 18.4.2009, 18:31

Anikmar

Дата 18.4.2009, 20:32 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(nightspirit @ 18.4.2009, 18:30

)

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

Так если расброс пар у вас организован - в чем надо производить поиск? Вы эти пары в массиве храните или где?

nightspirit

Дата 19.4.2009, 06:14 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата(Anikmar @ 18.4.2009, 20:32

)

Вы эти пары в массиве храните или где?

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

math64

Дата 19.4.2009, 09:58 (ссылка)

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

Загрузка ...

Эксперт

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

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

а чем не устроило решение из старой темы? Зачем было открывать заново, а не добавлять новые сообщения в старую тему? Она стала бы первой в списке.
Поиск в ширину:

Код


typedef unsigned long number;
typedef std::vector<number> numbers;
numbers searchDepth(number first, number last, int depth = 0x7FFFFFFF, numbers used = numbers());
numbers searchWidth(number first, number last) {
   if (!hasSameDigits(first, last)) {
     numbers res = numbers();
     return res;
   }
   for(int depth = 1; ; depth++) {
      numbers res = searchDepth(first, last, depth);
      if (!res.empty())
        return res;
   }
}

math64

Дата 19.4.2009, 10:25 (ссылка)

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

Загрузка ...

Эксперт

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

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

Если всё же хочешь стоить дерево, оцени, хватит ди памяти чтобы его хранить?
Возможно, лучше организовать поиск сразу от двух концов?

Код


class Number {
private:
   unsigned number;
   int depth; // глубина поиска, положительна, если искали от first, отрицательна - если искали от last
   Number** nexts; // следующие числа 
   Number** prevs; // предыдущие числа
   static Number* first;
   static Number* last;
   static std::set<Number*> allNumbers; // Все созданные числа
public:
   Number(unsigned int);
   ~Number();
   void FindNexts(); // поиск следующих чисел 
   void FindPrevs(); // поиск предыдущих чисел 
   static Number* FindNumber(unsigned int); // поиск числа
};

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