Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Эвристика. Рюкзак Алладина. http://www.cyberforum.ru/cpp-beginners/thread1025254.html
Помогите с заданием пожалуйста. Разработать алгоритм и написать программу для задания Алладина: сколько ценных вещей (заданных массе и цене) может поместиться в рюкзак (заданный объем) Алладина.
C++ Составить функцию вычисления суммы Прошу помощи, не понимаю, как записать числитель, что означает это троеточие? Заранее спасибо! http://www.cyberforum.ru/cpp-beginners/thread1025250.html
Конвертация из heximal в int C++
Нужно написать функцию для конвертации строки, представленной как heximal, в int. Например: Вход: char * pStr = "0xFF"; Выход: int iRes = 255;
C++ Значение бесконечности для неизвестного типа
Доброго времени суток, уважаемые эксперты! Просьба помочь с возникшим у меня вопросом: для решение некоторой задачи, мне приходится иметь в программе значение бесконечности float difference =...
C++ Проверка числа открывающихся и закрывающихся скобок http://www.cyberforum.ru/cpp-beginners/thread1025231.html
Нужно написать функцию, которая проверяет правильность расположения скобок в строке. Если открывающимся скобкам соответствует столько-же закрывающихся, функция должна возвращать true. Пример...
C++ Строки. Сравнить количество гласных и согласных Задание: Дана строка. Определить, больше в строке гласных или согласных букв. Что то со вводом строки не то. И не считает гласные. Помогите исправить пожалуйста. #include <iostream> #include... подробнее

Показать сообщение отдельно
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
02.12.2013, 18:40
Цитата Сообщение от 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;
}
если найдете промахи в решении или тестере, будет очень круто. хотя вроде их там нет
как минимум, вы должны понять, как избавиться от работы с вещественными числами в рамках этого алгоритма.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru