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

Разбиение С глав на В томов. Рекурсия - C++

Восстановить пароль Регистрация
 
Black-Lord
Сообщений: n/a
18.04.2011, 18:07     Разбиение С глав на В томов. Рекурсия #1
Роман состоит из C глав. Нужно, не переставляя главы, разбить его на B (В<С) томов так, чтобы максимальная толщина тома (сумма количеств страниц вошедших в него глав) была как можно меньше. Каждую главу начинают с новой страницы, поэтому толщина тома есть сумма длин глав, входящих в него. Разрывать главы нельзя. Если есть несколько равноценных оптимальных решений, вывести любое из них.

Добавлено через 12 минут
Предисловие (немного лирики)
Люди добрые спасите от Лепендюшки-грозы,
Если я не сдам задачу - получу тогда **ды.
Динамической программой сие чудо навалял
А как сделать мне с рекурсией - нифига не понял.

Зам декана горько плачет - я пока еще студент.
А он пишет приказанья и готовит документ.
Выгнать бедного поэта с универа и в войска
Не хочу туда идти я, гложет, жмет меня тоска.

Но не будем мы печальны: вы готовы мне помочь.
Всем спасибо, изначально я хотел бы быть точь в точь.
Программистом с самокрутью - гуру, властелином си.
Чтобы мне сказать декану: "Я все сдал!"



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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//Aplication is desing and govnokoding for GNU Linux by Annonymous Nemo (Black-Lord)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
 
class Greedy{
private:
vector <unsigned int> C; //длины глав
int c, b; //количество глав и томов
vector < vector<unsigned int> > Res; //матрица результатов
 
public:
Greedy(char * NameInput, char *NameOutput); 
int Calculation();
int ReadFile(char * Name);
int WriteFile(char * Name);
};
 
//конструктор
Greedy:: Greedy(char * NameInput, char *NameOutput) {
if (! ReadFile(NameInput) ) {
Calculation();
WriteFile(NameOutput);
                             }
}
 
//основной фронт деятельности. Вычисления
int Greedy::Calculation() {
for (int i = 0; i < c; i++) Res[0][i] = C[i];
//на каждом этапе сравниваем пары сум соседей и запоминаем минимальную, остальные элементы переезжают наверх. Выбор на каждом этапе считается оптимальным
//матрицу С используем как хранилище сумм соседей
for (int i = 0; i < c- 1; i ++) {
C.clear();
for (int j = 0; j < c  - 1 - i; j++) C.push_back( Res[i][j] + Res[i][j + 1] ); //суммируем
//находим минимальную пару
int Min = C[0],  Index = 0;
for (size_t k = 0; k < C.size(); k ++)
if ( C[k] < Min ) { Min = C[k]; Index = k; }
//строим следующий этаж
int formindex = 0, z = 0;
while (z < c - i) {
if (z == Index  || z == Index + 1) { Res[i + 1][formindex] = Min; formindex++; z += 2;}
else {
Res[i + 1][formindex] = Res[i][z]; 
formindex++;
z ++;
     } 
                 }
                               }
return 0;
}
 
//считывание данных из файла
int Greedy::ReadFile(char *Name) {
fstream F;
F.open(Name);
if (F.fail()) { F.close(); cerr << "\tОшибка при открытии исходного файла! Такого файла не существует.\n"; return 1; }
F >> c; //считали количество глав
F >> b; //считали количество томов
if ( b < 3 || b > 40 ) { cerr << "Количество томов противоречит условию задачи 3<=b<=40. \n"; F.close(); return 1; }
if ( c < b || c > 250) { cerr << "Количество страниц противоречит условию задачи b<=c<=250. \n"; F.close(); return 1;}
//выделяем память под матрицы результатов и массив длин глав
Res.resize(c);
for (int i = 0; i < c; i++) Res[i].resize(c);
C.resize(c);
//считываем длины глав
for (int i = 0; i < c; i ++) F >> C[i];
F.close();
return 0;
}
 
//Запись результата в файл Name
int Greedy::WriteFile(char * Name) {
int q = c - b; //наша цель
//ждать арабов
//ищем максиальный элемент
unsigned int Max = Res[q][0];
for (int i = 0; i < b ; i++) 
if (Res[q][i] > Max) Max = Res[q][i];
//пишем  в файл
fstream F;
F.open(Name, ios::out);
if (F.fail()) { F.close(); cerr << "\tОшибка при открытии  файла на записи! Имя файла не задано.\n"; return 1; }
F << "Максимальный размер тома : " << Max << ".\n";
//определяем границы томов и пишем
unsigned int sum = 0; //сумматор
int j = 0, begin = 0; 
for (int i = 0; i < c ; i ++ ) {
sum += Res[0][i]; 
if (sum == Res[q][j]) {  
if (begin == i) F << "Том " << j + 1 << "  состоит из главы " << i + 1  << ".\n";
           else F << "Том " << j + 1 << ": начало глава " << begin + 1<< ",конец глава " << i + 1  << ".\n";
                j++;
                begin = i + 1;
                sum = 0;
                      } 
                             }
F.close(); 
return 0;
}
 
 
int main(int argc, char ** argv)
{ 
setlocale(LC_ALL, "Russian");
Greedy A(argv[1], argv[2]);
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.04.2011, 18:07     Разбиение С глав на В томов. Рекурсия
Посмотрите здесь:

Разбиение на лексемы C++
scanf. Разбиение. C++
Разбиение на слагаемые C++
Дана действительная квадратная матрица порядка 12. Заменить нулями все её элементы, расположенные на глав-ной диагонали и выше неё. C++
Разбиение функций C++
C++ QR -разбиение
Разбиение строки C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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