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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вставить пробел http://www.cyberforum.ru/cpp-beginners/thread278803.html
Как Вставить пробел g="кенб,лоп" сделать k="кенб , лоп"
C++ Series(Последовательность) на C/C++ Не получается правильно написать программу Series7.Дано целое число N и набор из N вещественных чисел. Вывести в том же порядке округленные значения всех чисел из данного набора (как целые числа), а также сумму всех округленных значений. http://www.cyberforum.ru/cpp-beginners/thread278801.html
While na C или на C++ C++
Помогите пожалуйста решить While. Дано целое число N (> 0). Используя операции деления нацело и взя-тия остатка от деления, вывести все его цифры, начиная с самой правой (разряда единиц).
Ошибка expected primary-expression before "long" C++
#include<iostream> #include<cstdlib> #include<math.h> using namespace std; int main(void){ long N; long *b; long i;
C++ Чередование символов в строке http://www.cyberforum.ru/cpp-beginners/thread278738.html
Помогите плз решить задачу выяснить, чередуются ли в данной последовательности символы ‘+’ и ‘-‘, и сколько раз каждый из этих символов входит в эту последовательность;
C++ Написать функцию, которая в зависимости от значения первого параметра возвращает количество отрицательных или положительных чисел призвольного массива Написать функцию, которая в зависимости от значения первого параметра (символ + или – ) возвращает количество отрицательных или положительных чисел произвольного массива из N элементов. Каких элементов больше в массиве A10? подробнее

Показать сообщение отдельно
Black-Lord
Сообщений: n/a

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

18.04.2011, 18:07. Просмотров 630. Ответов 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 02:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru