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

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

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

Метод ветвей и границ (задача об экспериментаторе) - C++

10.04.2016, 14:45. Просмотров 423. Ответов 2
Метки нет (Все метки)

Добрый день. Не получается написать программу на метод ветвей и границ. Задача: профессор поднимается по очереди на каждый этаж некоего дома и сбрасывает оттуда транзисторы. Заведомо известно, что с первого этажа транзисторы не бьются. Пусть, упав с какого-то этажа какой-то транзистор разбился, тогда профессор спускается вниз, подбирает уцелевшие и снова скидывает их с каждого этажа. Нужно найти минимальный этаж, с которого всё бьётся и посчитать минимальное количество подъёмов по лестнице.
Написала рекурсивную функцию MBB, но не вижу ошибки. Первые подъём и спуск работают нормально, а потом нет. Помогите, пожалуйста, понять, что не так.

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
void MBB(int floor, int summ, int numbers_of_trans, int delta_of_floors) {
    
    summ += delta_of_floors;
 
    file << "Встали на этаж: " << floor << "\n";
    file << "Текущая сумма: " << summ << "\n";
    file << "Количество транзисторов на руках: " << numbers_of_trans << "\n";
    file << "Количество хороших транзисторов внизу: " << good_trans << "\n";
 
    numbers_of_trans--;
    file << "Скинули один транзистор\n";
    
    if (floor<durable) {
        good_trans++;
        file << "Транзистор не разбился\n";
        file << "Количество транзисторов на руках: " << numbers_of_trans << "\n";
        file << "Количество хороших транзисторов внизу: " << good_trans << "\n";
        for (int i = floor + 1; i <= numbers_of_floors; i++) {
            MBB(i, summ, numbers_of_trans, i - floor);
            file << "\n";
        }
        
    }
    else {
        file << "Транзистор разбился\n";
        file << "Количество транзисторов на руках: " << numbers_of_trans << "\n";
        file << "Количество хороших транзисторов внизу: " << good_trans << "\n";
        if (best_summ == -1) {
            best_summ = summ;
            best_floor = floor;
            file << "Текущая лучшая сумма: " << best_summ << "\n";
            file << "Текущий лучший этаж: " << best_floor << "\n\n";
            floor = 0;
            if (good_trans > 0) {
                summ += floor;
                numbers_of_trans += good_trans;
                file << "Подняли " << good_trans << " транзисторов\n";
                file << "Количество транзисторов на руках: " << numbers_of_trans << "\n";
                good_trans = 0;
                file << "Количество хороших транзисторов внизу: " << good_trans << "\n\n";
            }
            else {
                file << "Транзисторы на руках и внизу закончились!!\n\n";
                return;
            }
            for (int i = floor + 1; i <= numbers_of_floors; i++) {
                MBB(i, summ, numbers_of_trans, i - floor);
                file << "\n";
            }
 
        }
        
    }
    
}
void ConsoleEnter(){
    
        cout << "Введите количество этажей: ";
        cin >> numbers_of_floors;
        cout << "Введите число транзисторов: ";
        cin >> numbers_of_trans;
        durable = rand() % numbers_of_floors + 2; // изначальная прочность, которая должна меняться, если будет найдена прочность меньше
        
        while (cin.fail())
        {
            cout << "Попробуйте снова.";
            cin.clear();
            cin.sync();
        }
        
        good_trans = 0;
 
        best_summ = -1;
        best_floor = -1;
 
        MBB(1, 0, numbers_of_trans, 1);
 
        cout << "Этаж, с которого транзистор точно разобьётся: " << best_floor << "\n";
        cout << "Лучшее число подъёмов: " << best_summ; 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2016, 14:45     Метод ветвей и границ (задача об экспериментаторе)
Посмотрите здесь:

C++ Задача на Метод сортировки (Слияние)
C++ Бинарное дерево. Поиск числа ветвей по значению
Задача на метод дихотомии(половинного деления) C++
Симплекс метод. Задача с двусторонними ограничениями C++
C++ Определение глубины (числа ветвей) непустого дерева от вершины до заданного узла
Транспортная задача(метод минимального элемента) C++
Какова временная сложность метода ветвей и границ, и генетического алгоритма, которые решают задачу о рюкзаке? C++
Проверить класс. Обмотка электродвигателя при заданном числе параллельных ветвей C++
C++ Найти суммы ветвей дерева
C++ Узнать сколько максимально прямоугольников можно составить из ветвей
Транспортная задача: метод северо-западного угла C++
Задача коммивояжера (метод ветвей и границ) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
3021 / 1677 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
10.04.2016, 17:22     Метод ветвей и границ (задача об экспериментаторе) #2
А слабо написать условия задачи, т.е. что задано и что нужно получить?
schecter6661
0 / 0 / 0
Регистрация: 28.06.2014
Сообщений: 8
10.04.2016, 18:36  [ТС]     Метод ветвей и границ (задача об экспериментаторе) #3
Цитата Сообщение от Mr.X Посмотреть сообщение
А слабо написать условия задачи, т.е. что задано и что нужно получить?
не слабо, просто там много текста:
Профессор хочет экспериментально исследовать на прочность транзисторы. Он выбрал следующий способ проведения эксперимента: профессор намерен, перемещаясь по пожарной лестнице, сбрасывать транзисторы с высоты различных этажей. Таким образом, он планирует определить, при падении с какого минимального этажа транзистор разбивается. При этом профессору известно, что транзистор не выдерживает падения с последнего этажа, а падение с первого этажа не причиняет ему (транзистору) вреда.
Известно, что все транзисторы данной партии абсолютно одинаковы, и если транзистор разбивается при падении с некоторого этажа, то он разбивается и при падении с большей высоты. Разбившиеся транзисторы снова использовать нельзя, а оставшиеся целыми после падения могут использоваться повторно. Для того чтобы поднять оставшийся целым транзистор, профессору надо спуститься на первый этаж. Оказавшись на первом этаже, профессор может поднять все лежащие там транзисторы. Профессор хочет минимизировать суммарное расстояние, которое ему придется в худшем случае подниматься по лестнице. У профессора хорошее зрение, и он может с любого этажа определить, разбился транзистор или нет.
Изначально профессор находится на первом этаже, и у него имеется m транзисторов. В доме, где проводится эксперимент, n этажей, и все они имеют одинаковую высоту (её можно принять за единицу измерения расстояния).
Yandex
Объявления
10.04.2016, 18:36     Метод ветвей и границ (задача об экспериментаторе)
Ответ Создать тему
Опции темы

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