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

Найти самую длинную возрастающую цепочку простых чисел - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Чем отличается С++ от Visual С++? http://www.cyberforum.ru/cpp-beginners/thread350822.html
Здравствуете товарищи программисты! Только начал изучать язык программирования С++ и возникло пару вопросов. Чем отличается С++ от Visual С++? И еще посаветуйте какую-нибудь литературу на русском языке, для понятия основ языка.(В Универе дают только на английском) В поисковике искать не хотел, т.к. у бывалых программистов спросить лучше.Спасибо.
C++ как кодить на с в Microsoft visual studio 2010 первый раз встречаюсь с вижлой.как кодить на с в Microsoft visual studio 2010?обьясните поподробнее как что где создавать и как компилировать http://www.cyberforum.ru/cpp-beginners/thread350801.html
Solutions manual по книге c++ how to programm C++
Апну темку и заодно мб, кто-нибудь имеет еще 1 книжку. Нужен solutions manual по книге c++ how to programm (5 издания). Заранее спс.
Описать класс, реализующий бинарное дерево C++
Здравствуйте! Возникли проблемы с реализацией одной программы ....Описать класс, реализующий бинарное дерево, обладающее возможностью добавления новых элементов, удаления существующих, поиска элемента по ключу, а также последовательного доступа ко всем элементам. Написать программу, использующую этот класс для представления англо-русского словаря. Программа должна содержать меню, позволяющее...
C++ Не получаеться решить http://www.cyberforum.ru/cpp-beginners/thread350749.html
Дана функция y(x)=Ax2+Bx+C, где A – количество букв в фамилии студента, B количество букв в имени студента, C количество букв в отчестве студента. Для функции y(x) составить программу построения таблицы значений функции при изменении аргумента от L до R с шагом T. В каждой строке выводить значения аргумента и соответствующее ему значение функции. Кроме того, в конце таблицы напечатать...
C++ как удалить все елементы с очереди queue Есть очередь queue и в ней элементы, как удалить их все чтобы очередь осталась пустой? подробнее

Показать сообщение отдельно
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.09.2011, 16:06     Найти самую длинную возрастающую цепочку простых чисел
Цитата Сообщение от ZeonExpert Посмотреть сообщение
2, 3, 4, 5, 6, 7, 3, 5, 7
2, 3, 10,5, 6, 7, 3, 5, 7
Но здесь не цепочка, у вас закрашенные элементы расположены непоследовательно.
А задача простая в общем-то...
Решается динамикой кстати.

Добавлено через 15 минут
Для подпоследовательности(не цепочки, для цепочки нужно подправить пару строк) как-то так получится.
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
#include <iostream>
 
int main()
{   
    const int MAX_VALUE = 100500; //максимально возможная цифра
 
    char sieve[ MAX_VALUE ] = { 1, 1 }; //решето Эратосфена
    
    //заполнение решета
    
    for (int i = 2; i < MAX_VALUE ; ++i)
    {
        
        if ( sieve[i] == 0 )
        {
            for ( int j = i * 2 ; j < MAX_VALUE ; j += i )
                sieve[j] = 1;
        }
    }
    
    int arr[] = { 2, 3, 10,5, 6, 7, 3, 5, 7 };
    int size = sizeof( arr ) / sizeof( *arr );
    
    int * dinamic = new int [ size ];
    
    /* 
     * Для каждого члена последовательности находим длину максимальной
     * подпоследовательности, заканчивающейся на этом элементе
     */
    
    dinamic[0] = 0;
    for (int i = 1; i < size ; ++i)
    {
        dinamic[0] = 0;
        
        //если число не простое, последовательность не может оканчиваться на этот элемент
        if ( sieve[ arr[i] ] != 0 )
            continue;
        
        for ( int j = i - 1; j >= 0 ; --j)
            if ( sieve[arr[j]] == 0 && arr[j] < arr[i] )
                dinamic[i] = std::max( dinamic[i], dinamic[j] + 1 );
    }
    
    /*
     * нахождение длины максимальной подпоследовательности и элемента, 
     * на котором она заканчивается
     */
     
    int max = 0, pos = 0;
    for (int i = 0; i < size ; ++i)
    if ( dinamic[i] > max )
    {
        max = dinamic[i];
        pos = i;
    }
    
    //заполнение массива с ответом
    int * answer = new int [ dinamic[pos] + 1];
    
    answer[0] = arr[pos];
    int end = 0;
    
    for (int i = pos - 1, x = pos; i >= 0; --i)
    {
        if ( dinamic[i] + 1 == dinamic[x] )
        { 
            answer[++end] = arr[i];
            x = i;
        }
    }
    
    
    for (int i = end; i >= 0 ; --i)
        std::cout << answer[i] << ' ';
    
    delete[] answer;    
    delete[] dinamic;
}
За O(nlogn) примерно находит.

Для цепочки еще проще
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
/*
 * Найти максимальную по длине возрастающую цепочку простых чисел
 */
 
#include <iostream>
 
int main()
{   
    const int MAX_VALUE = 100500; //максимально возможная цифра
 
    char sieve[ MAX_VALUE ] = { 1, 1 }; //решето Эратосфена
    
    //заполнение решета
    
    for (int i = 2; i < MAX_VALUE ; ++i)
    {
        
        if ( sieve[i] == 0 )
        {
            for ( int j = i * 2 ; j < MAX_VALUE ; j += i )
                sieve[j] = 1;
        }
    }
    
    int arr[] = { 2, 3, 3, 5, 6, 7, 3, 5, 7  };
    int size = sizeof( arr ) / sizeof( *arr );
    
    int * dinamic = new int [ size ];
    
    /* 
     * Для каждого члена последовательности находим длину максимальной
     * подпоследовательности, заканчивающейся на этом элементе
     */
    
    dinamic[0] = 0;
    for (int i = 1; i < size ; ++i)
    {
        dinamic[0] = 0;
        
        //если число не простое, последовательность не может оканчиваться на этот элемент
        if ( sieve[ arr[i] ] != 0 )
            continue;
        
        if ( sieve[ arr[i - 1] ] == 0 && arr[i - 1] < arr[i] )
            dinamic[i] = std::max( dinamic[i], dinamic[i - 1] + 1 );
    }
    
    /*
     * нахождение длины максимальной подпоследовательности и элемента, 
     * на котором она заканчивается
     */
     
    int max = 0, pos = 0;
    for (int i = 0; i < size ; ++i)
    if ( dinamic[i] > max )
    {
        max = dinamic[i];
        pos = i;
    }
    
    //заполнение массива с ответом
    for (int i = pos - dinamic[pos] ; i <= pos ; ++i)
        std::cout << arr[i] << ' '; 
    
    delete[] dinamic;
}
 
Текущее время: 03:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru