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

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

Войти
Регистрация
Восстановить пароль
 
Black-Lord
Сообщений: n/a
#1

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

18.04.2011, 18:07. Просмотров 633. Ответов 0
Метки нет (Все метки)

Роман состоит из 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     Разбиение С глав на В томов. Рекурсия
Посмотрите здесь:

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

QR -разбиение - C++
Доброго всем времени суток. У кого есть красиво написанное QR-разложение матриц с помощью преобразования Хаусхолдера? Если не сложно,...

Разбиение функций - C++
Добрый вечер, помогите пожалуйста разбить каждую из функций на две - первая часть ТОЛЬКО считывает строку посимвольно, а вторая - делает...

Разбиение на лексемы - C++
Нужно написать программу, запрашивающую строку текста, разбивающую ее на лексемы и выводящую лексемы в обратном порядке. Желательно си, не...

Разбиение массива - C++
Одним весенним днем, идя в университет, Леша нашел массив A. Леша очень любит разбивать массив на несколько частей. В этот раз он решил,...

разбиение на подмножества - C++
Здраствуйте. Есть такая задача: разбить последовательность чисел от 1 до n * n на n подмножеств так, чтобы все они состояли из n чисел и...

Разбиение проекта на .h - C++
Эсть класс А от его наследую класс Б, в .h пишу #ifndef B_H #define B_H #include &quot;A.h&quot; class B:public A{ ......} #endif ...

Разбиение на слагаемые - C++
Задание:нужно вывести на экран в лексикографическом порядке все разбиения на слагаемые числа n от 1 до 20. пример: n=5 5=1+1+1+1+1 ...

Разбиение строки - C++
Доброго времени суток. Я новичок в кодинге. Передо мной такая задача: есть строка str с числами, разделенными через пробел. ...

Разбиение строк - C++
Доброго времени суток! Собственно нужна помощь в поиске ошибки. вот код: #include &quot;stdafx.h&quot; typedef struct { char...

Разбиение точек - C++
Дано n точек. n &lt;= 100. Необходимо разбить их на 2 выпуклых, непересекающихся многоугольника так, чтобы любая точка являлась вершиной...

scanf. Разбиение. - C++
Помогите с задачей. Не могу додуматься как это сделать: С клавиатуры вводится следующий набор символов: AGENT007:1234567.25 В...


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

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

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