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

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

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

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

10.04.2016, 14:45. Просмотров 668. Ответов 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; 
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2016, 14:45
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Метод ветвей и границ (задача об экспериментаторе) (C++):

Задача коммивояжера (метод ветвей и границ) - C++
Написать программу для решения задачи коммивояжёра с помощью метода ветвей и границ. Интерфейс должен позволять вводить количество городов...

Какова временная сложность метода ветвей и границ, и генетического алгоритма, которые решают задачу о рюкзаке? - C++
Всем привет!Не подскажете какова временная сложность метода ветвей и границ,и генетического алгоритма,которые решают задачу о рюкзаке? и...

Задача о ранце, метод ветвей и границ - C#
Есть ли у кого реализации метода ветвей и границ именно для решения задачи о ранце(рюкзаке)? Данный метод для каждой конкретной задачи...

Задача о покрытии методом ветвей и границ - C#
В общем мучился, мучился, так ничего и не вышло...В институте дали задание: реализовать задачу о покрытии методом ветвей и границ на C#....

Реализация метода ветвей и границ (задача о рюкзаке) - C#
По работе нужно было реализовать метод ветвей и границ, решающий задачу о рюкзаке. Еле откопал алгоритм реализации этого метода на С++ и...

Метод ветвей и границ: Нахождение минимального пути между городами - C#
Всем привет, не у кого нет случаем уже готовой проги (с исходником), написанной на C#, решающая задачу нахождения минимального пути между,...

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

Реализация метода ветвей и границ - Алгоритмы
Нужен вменяемый (разложенный по пунктам )алгоритм метода упомянутого в теме. Гугл выдаёт решения задачи коммивояжера, алгоритм Литтла,...

Решение задачи о коммивояжера методом ветвей и границ. - Visual Studio
Решение задачи о коммивояжера методом ветвей и границ.

Решение задачи коммивояжера методом ветвей и границ - C#
Нужна помощь в реализации программы которая будет решать задачу коммивояжера методом ветвей и границ . Количество городов(вершин) и...

Программа решающая задачу Коммивояжера методом ветвей и границ - Delphi
Здравствуйте. В просторах интернета наткнулась на сию задачу, но её текст для меня пока что остаётся загадкой. Помогите пожалуйста с...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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