Форум программистов, компьютерный форум CyberForum.ru

Поиск в глубину - C++

Восстановить пароль Регистрация
 
raindeath
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 27
02.12.2013, 03:28     Поиск в глубину #1
Помогите с заданием пожалуйста.
Число 1 можно записать как сумму n чисел вида 1 / i, где i - натуральное число. Например, для n = 3 имеем 1 = 1/2 +1 / 4 +1 / 4. Найти способы записи числа 1 для заданного n методом поиска в глубину.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2013, 03:28     Поиск в глубину
Посмотрите здесь:

Поиск в глубину C++
C++ итеративный поиск в глубину
C++ поиск в глубину
Конечный автомат. Лабиринт (поиск в глубину) C++
C++ Не работает поиск в глубину (DFS)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
02.12.2013, 07:15     Поиск в глубину #2
C++
1
2
3
4
5
6
7
8
9
10
void track(dbl n, int k) {
    if(k == 0 || n < eps)
        return;
    if(k == 1) {
        cout << n << endl;
        return;
    }
    track(n/2, k/2);
    track(n/2, k-k/2);
}
не совсем, конечно, поиск в глубину. но совсем поиск в глубину здесь не при чем совершенно.
raindeath
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 27
02.12.2013, 18:15  [ТС]     Поиск в глубину #3
salam, можно поподробнее? никак все в кучу не сложу
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
02.12.2013, 18:40     Поиск в глубину #4
Цитата Сообщение от raindeath Посмотреть сообщение
salam, можно поподробнее? никак все в кучу не сложу
подозреваю, что алгоритмов таких разложений порядка 1099999999999.... не думайте, что этот какой-то "правильный".
мы написали некоторую рекурсивную функцию. она принимает два аргумента: число, которое нужно разложить, и количество слагаемых, которые мы обязаны предоставить в качестве разложения этого числа. сама схема разложения такова:

C++
1
2
3
4
5
6
7
8
9
10
void track(dbl n, int k) {
    if(k == 0)                          // если мы не имеем права больше добавлять слагаемые
        return 0;                       // (к == 0), то выйдем
    if(k == 1) {                        // если мы имеем право разложить число только в одно слагаемое,
        cout << n << endl;          // то раскладываем в него само :)
        return;                          // выйдем
    }
    track(n/2, k/2);                  // если все сложнее, то будем раскладывать отдельно "по половинке"
    track(n/2, k-k/2);               // нашего числа в "половинку" слагаемых каждое
}
это весьма общая схема решения. мы не знаем сходу, как разложить некое n в k слагаемых, но мы умеем это делать для простых случаев - для одного и двух слагаемых. ну вот и давайте дробить задачу, пока она не разобьется на задачи, которые мы умеем решать, не задумываясь. мы это и сделали.

если вы хотите, чтобы ваши решения работали, вы обязаны уметь их тестить. я тестил эту программу так:

C++
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
vector<dbl> v;
 
void track(dbl n, int k) {
    if (k == 0)
        return;
    if (k == 1) {
        //cout << n << endl;
        v.pub(n);
        return;
    }
    track(n/2, k/2);
    track(n / 2, k - k / 2);
}
 
int main()
{
    for(int i=0; i < 1000; ++i) {
        int k = rand() % (rand() % 2 ? 1000 : 100);
        v.clear();
        track(1.0, k);
        dbl sum = 0;
        for(int i=0; i < v.size(); ++i)
            sum += v[i];
        if(fabs(sum - 1) > EPS || v.size() != k)
            cout << k << endl;
    }
    return 0;
}
если найдете промахи в решении или тестере, будет очень круто. хотя вроде их там нет
как минимум, вы должны понять, как избавиться от работы с вещественными числами в рамках этого алгоритма.
raindeath
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 27
02.12.2013, 18:56  [ТС]     Поиск в глубину #5
salam, что в данном случае подразумевает EPS?
Цитата Сообщение от salam Посмотреть сообщение
if(fabs(sum - 1) > EPS || v.size() != k)
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
02.12.2013, 18:57     Поиск в глубину #6
Цитата Сообщение от raindeath Посмотреть сообщение
salam, что в данном случае подразумевает EPS?
т.к. мы работает с вещественными числами, то при разложении в большое кол-во слагаемых у нас итоговая сумма будет не в точности 1, а 0.9999, например.
raindeath
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 27
02.12.2013, 19:04  [ТС]     Поиск в глубину #7
salam, понятно. Можно ли сделать так, что бы прога работала для определенного n?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
02.12.2013, 19:06     Поиск в глубину #8
в смысле для любого заданного, а не только для 1?
raindeath
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 27
02.12.2013, 19:11  [ТС]     Поиск в глубину #9
нет
Цитата Сообщение от raindeath Посмотреть сообщение
для n = 3 имеем 1 = 1/2 +1 / 4 +1 / 4
я имею ввиду для этого n
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
02.12.2013, 19:12     Поиск в глубину #10
для того и существует параметр k у функции.
raindeath
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 27
02.12.2013, 19:20  [ТС]     Поиск в глубину #11
Цитата Сообщение от salam Посмотреть сообщение
for(int i=0; i < 1000; ++i)
тогда что задает эта переменная?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
02.12.2013, 19:21     Поиск в глубину #12
для того чтобы сделать тысячу случайных тестов и убедится, что программа не кривая.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2013, 19:26     Поиск в глубину
Еще ссылки по теме:

C++ графы,поиск в глубину
графы. поиск в глубину C++
C++ Поиск в глубину

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

Или воспользуйтесь поиском по форуму:
raindeath
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 27
02.12.2013, 19:26  [ТС]     Поиск в глубину #13
ясно
Yandex
Объявления
02.12.2013, 19:26     Поиск в глубину
Ответ Создать тему
Опции темы

Текущее время: 13:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru