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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
raindeath
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 27
#1

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

02.12.2013, 03:28. Просмотров 900. Ответов 12
Метки нет (Все метки)

Помогите с заданием пожалуйста.
Число 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++
Здравствуйте. Как реализовать поиск кратчайшего пути в невзвешенном графе через поиск в глубину? Пробовал сделать так const...

поиск в глубину - C++
Дали задание реализовать поиск в глубину.Пробую релизовать по e-maxx http://e-maxx.ru/algo/dfsно не получается. vector<char> used; int...

Поиск в глубину - C++
"В рождественскую ночь Санта-Клаус спускается по каминной трубе и раскладывает детям подарки. Кровати в комнате стоят очень плотно. Чтобы...

Рекурсивный поиск в глубину - C++
Нужно найти путь по простому лабиринту от точки к точке, используя в программе рекурсивный поиск в глубину. Фотографию примера лабиринта...

графы,поиск в глубину - C++
очень нужна помощь!нужно в неориентированном графе найти компоненты связности поиском в глубину. Есть готовый алгоритм поиска,из...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
02.12.2013, 19:21 #12
для того чтобы сделать тысячу случайных тестов и убедится, что программа не кривая.
raindeath
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 27
02.12.2013, 19:26  [ТС] #13
ясно
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2013, 19:26
Привет! Вот еще темы с ответами:

Поиск в глубину. Графы. С++ - C++
Задана ,допустим, такая матрица смежности 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 Node.h #pragma once

графы. поиск в глубину - C++
Здраствуйте. Вот такая задача N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i,...

Итеративный поиск в глубину - C++
Здравствуйте! Вопрос связан с поиском в графе. Меня интересуют идеи решения или ссылка на литературу. Пожалуйста, подскажите... ...

Не работает поиск в глубину (DFS) - C++
Вот код (заполнен для ориентированного графа 0 2 | + +/ 1--+3--+4 | + 5--+6 |


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.12.2013, 19:26
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru