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

Динамическое программирование: самая длинная строго возрастающая подпоследовательность - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Std::thread автоматическая многопоточность http://www.cyberforum.ru/cpp-beginners/thread1311270.html
Есть данный пример создания массива thread и инициализации его в цикле. #include<iostream> #include<sstream> #include<thread> using namespace std; class printId { public: void operator()() { ostringstream out;
C++ Скопировать в текстовой файл слова содержащие символ 'C' Дан символ C — строчная (маленькая) латинская буква и текстовый файл. Создать строковый файл и записать в него все слова из исходного файла, содержащие хотя бы одну букву C (прописную или строчную). Словом считать набор символов, не содержащий пробелов, знаков препинания и ограниченный пробелами, знаками препинания или началом/концом строки. Если исходный файл не содержит подходящих слов, то... http://www.cyberforum.ru/cpp-beginners/thread1311264.html
C++ Как ускорить пирамидальную сортировку?
Второй цикл for в пирамидальной сортировке можно было бы сократить, добавив условие завершения i > 3. Следует ли добавить после этого цикл, и если да, то что, для того, чтобы конечный список как и раньше был отсортированным? Приводят ли подобные изменения к уменьшению числа сравнений?
Написать программу: Определить разность между наибольшей и наименьшей цифрами натурального числа C++
Напишите код. Определить разность между наибольшей и наименьшей цифрами натурального числа N, представленного в шестиричной системе счисления.
C++ Написать программу: могут ли три числа быть длинами сторон треугольника? http://www.cyberforum.ru/cpp-beginners/thread1311253.html
Решите эту задачу: даны три числа если они могут быть длинами сторон равнобедренного тупоугольного треугольника, то вычислите его площадь. Выведите длины сторон и площадь в порядке возрастания значений.
C++ Rnunif() Не могу ничего найти про эту процедуру. Кто-нибудь может подсказать, что она делает и с ккими параметрами работает? подробнее

Показать сообщение отдельно
Байт
 Аватар для Байт
13968 / 8799 / 1224
Регистрация: 24.12.2010
Сообщений: 15,943
28.11.2014, 00:07     Динамическое программирование: самая длинная строго возрастающая подпоследовательность
Цитата Сообщение от Байт Посмотреть сообщение
Тогда это несколько сложнее
Вот, попытался решить... То работает, то нет (значит - не работает!) Тем не менее показываю код (неправильный!), если для кого-то это актуально, может быть попробует найти мою ошибку. Код находит правильные последовательности, если они начинаются с первого члена. Идея довольно проста. Создаешь приемлемую (возрастающую) последовательность, а потом двигаешь ее элементы в надежде найти лучшую. Так вот, первый элемент у меня двигаться не хочет!
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
#include <stdio.h>
#include <stdlib.h>
#define N 12
 
int main()
{ int i, a[N], nn[N], b[N], Mn, Mx, old;
 
 randomize();
 for(i=0; i<N; i++) {
   a[i] = rand()%N;
   printf("%d ", a[i]);
 }
 printf("\n");
 b[0] = nn[0] = 0;  //  Начальное заполнение
 for(i=0, Mx=1; i<N; i++) if (a[i] > a[nn[Mx-1]]) b[Mx] = nn[Mx++] = i;
 Mn = Mx;  // Mn - Длина текущей последовательности в nn,
           // Mx - Длина лучшей последовательности в b
           // в массивах nn, b храню не сами элементы, а их номера
 while (1) {
       //  for(i=0; i<Mn; i++) printf("%d ", nn[i]); printf("\n");
       //  for(i=0; i<Mn; i++) printf("%d ", a[nn[i]]);
       //  printf(" Mn=%d Mx=%d nn0=%d\n", Mn, Mx, nn[0]);
   if (nn[0] >= N-1) break;  // Дальше некуда
   if (Mn<=2) {
     nn[0]++;
     Mn = 1;
   }
   else Mn -= 1;
   old = Mn;
   for(i=nn[Mn]+1; i<N; i++) if (a[i] > a[nn[Mn-1]]) nn[Mn++] = i;
   if (Mn==old) {  // Ничего нового
     Mn--;
     continue;
   }
   if (Mn > Mx) {  // Нашли лучшую
     Mx = Mn;
     for(i=0; i<Mx; i++) b[i] = nn[i];  // Фиксируем ее
   }
 }
 for(i=0; i<Mx; i++) printf("%d ", a[b[i]]);
 printf("\nMx=%d\n", Mx);
 return 0;
}
Надеюсь на свежую голову эту штуку допилить, хотя прекрасно понимаю, что ни по эстетике программизма, ни по эффективности, это - не лучший вариант.

Не по теме:

Там была дырка глупая (как и все дырки) и вот она съела у меня всю энергию...

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