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

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

Войти
Регистрация
Восстановить пароль
 
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
#1

Динамика - C++

01.11.2011, 22:50. Просмотров 561. Ответов 9
Метки нет (Все метки)

Пожалуйста ребят, кому не трудно, сделайте. Очень вас прошу. Заранее огромное спасибо вам..
Задан массив A[1..N]. Подпоследовательность A[i_1], A[i_2], ..., A[i_k] называется четночередующейся, если любые два последовательные ее члена имеют разную четность.
Найдите длину наидлинейшей четночередующейся возрастающей подпоследовательности.

Входные данные
В первой строке заданы N (1 <= N <= 3000). Во второй строке последовательность целых чисел A[1..N]. Все числа по модулю не превосходят 10^8.

Выходные данные
Выведите искомую величину.

Пример

Ввод
6
3 2 5 1 6 2

Вывод
3
Друзья, если вам не сложно, помогите пожалуйста

Добавлено через 18 минут
Не поможете?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2011, 22:50     Динамика
Посмотрите здесь:

Динамика, динамика и снова динамика - C++
Вот как сделать например, что бы динамический массив например int **pArray = new int*; for(int i = 0; i &lt; rows; i++) pArray =...

Динамика - C++
При вводе студента появляется одновременно фамилия и число. Как сделать так чтобы поэтапно появлялось ? #include &lt;iostream&gt; ...

О сигналах динамика ПК - C++
Есть ли другой вариант подачи определенного кол-ва звуковых сигналов динамиком компьютера? count=5; for (count; count !=0; count--) ...

Динамика и статика (массивы) - C++
1)Почему при статическом выделении памяти массив обязательно объявлять в функции main? 2)Почему его нельзя вернуть через return из...

Динамика в двумерном массиве - C++
Всем привет. Подскажите, пожалуйста, реально ли реализовать такое. Есть заранее найденное n - не константа. Нужно, чтобы массив...

Уменьшение числа(динамика) - C++
Здравствуйте, помогите найти ошибку в коде для задачи - имеется натуральное число(1&lt;=n&lt;=10^6), к нему применимы операции -1 /2 и /3, при...

Beep() - музыка из динамика - C++
Сидел на форуме и на толкнулся на функцию Beep(). Есть ли у кого нибудь исходники с музыкой из встроенных динамиков в ПК??=) Вот пример...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
01.11.2011, 23:36     Динамика #2
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
#include <stdio.h>
#include <stdlib.h>
 
struct range {
    int *begin;
    int *end;
};
 
int distance(struct range r)
{
    return r.end - r.begin;
}
 
struct range alternating_parity(int *lb, int *ub)
{
    struct range r;
 
    for ( ; lb < ub-1
        && (*lb & 1) == (*(lb+1) & 1); lb++)
        ;
    if (lb == ub-1) {
        r.begin = r.end = lb;
        return r;
    }
    r.begin = lb;
    while (lb < ub-1
        && (*lb & 1) != (*(lb+1) & 1))
        lb++;
    r.end = lb + 1;
    return r;
}
 
int main()
{
    int n, *arr, *p, i, dist;
    struct range longest, r;
 
    while (printf("enter n: ") && scanf("%d", &n) && n > 0) {
        if ((arr = (int *) malloc(n * sizeof(int))) == NULL) {
            printf("error: cannot allocate memory\n");
            return 1;
        }
        printf("enter an array: ");
        for (i = 0; i < n; i++)
            scanf("%d", &arr[i]);
        p = arr;
        dist = 0;
        do {
            if (distance(r = alternating_parity(p, arr+n)) > dist) {
                longest = r;
                dist = distance(longest);
            }
            p = r.end;
        } while (p < arr+n && r.begin != r.end);
        if (longest.begin != longest.end) {
            printf("the longest sequence with alternating parity: ");
            for (p = longest.begin; p < longest.end; p++)
                printf("%d ", *p);
            printf("\nits length is %d\n\n", distance(longest));
        } else
            printf("there is no a such sequence\n\n");          
        free(arr);
    }
    return 0;
}
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
02.11.2011, 00:14  [ТС]     Динамика #3
Цитата Сообщение от Net_Wanderer Посмотреть сообщение
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
#include <stdio.h>
#include <stdlib.h>
 
struct range {
    int *begin;
    int *end;
};
 
int distance(struct range r)
{
    return r.end - r.begin;
}
 
struct range alternating_parity(int *lb, int *ub)
{
    struct range r;
 
    for ( ; lb < ub-1
        && (*lb & 1) == (*(lb+1) & 1); lb++)
        ;
    if (lb == ub-1) {
        r.begin = r.end = lb;
        return r;
    }
    r.begin = lb;
    while (lb < ub-1
        && (*lb & 1) != (*(lb+1) & 1))
        lb++;
    r.end = lb + 1;
    return r;
}
 
int main()
{
    int n, *arr, *p, i, dist;
    struct range longest, r;
 
    while (printf("enter n: ") && scanf("%d", &n) && n > 0) {
        if ((arr = (int *) malloc(n * sizeof(int))) == NULL) {
            printf("error: cannot allocate memory\n");
            return 1;
        }
        printf("enter an array: ");
        for (i = 0; i < n; i++)
            scanf("%d", &arr[i]);
        p = arr;
        dist = 0;
        do {
            if (distance(r = alternating_parity(p, arr+n)) > dist) {
                longest = r;
                dist = distance(longest);
            }
            p = r.end;
        } while (p < arr+n && r.begin != r.end);
        if (longest.begin != longest.end) {
            printf("the longest sequence with alternating parity: ");
            for (p = longest.begin; p < longest.end; p++)
                printf("%d ", *p);
            printf("\nits length is %d\n\n", distance(longest));
        } else
            printf("there is no a such sequence\n\n");          
        free(arr);
    }
    return 0;
}
А чуть чуть попроще нельзя? Без классов например...
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
02.11.2011, 00:20     Динамика #4
Цитата Сообщение от Shato Посмотреть сообщение
Без классов например...
Здесь нет классов.
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
02.11.2011, 00:23  [ТС]     Динамика #5
Цитата Сообщение от Net_Wanderer Посмотреть сообщение
Нет.Здесь нет классов.
cтруктуры
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.11.2011, 09:53     Динамика #6
Net_Wanderer,
Контрпримеры:
Ввод:
2
1 1
Вывод:
1

Ввод:
5
1 2 3 4 3
Вывод:
4

Ну и свой вариант:
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
#include <stdio.h>
 
int main()
{ 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int n, mas[3000][2], i, j, res=1, max;
    scanf("%d", &n);
    for(i=0; i<n; i++)
        scanf("%d", &mas[i][0]);
    mas[0][1]=1;
    for(i=1; i<n; i++)
    {
        max=0;
        for(j=0; j<i; j++)
            if(mas[j][0]<mas[i][0] && (mas[j][0]+mas[i][0])%2==1 && max<mas[j][1])
                max=mas[j][1];
        mas[i][1]=max+1;
        if(mas[i][1]>res)           
            res=mas[i][1];      
    }
    printf("%d", res);
    return 0;
}
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
02.11.2011, 11:11     Динамика #7
valeriikozlov, скриншот.

А при
вводе
2
1, 1
нет вывода, программа просто падает, потому как longest не инициализирована.
достаточно добавить
C
1
 longest.begin = longest.end = NULL;
перед циклом do и изменить условие в строке 55 на
C
1
if (longest.begin != NULL) {
Миниатюры
Динамика  
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.11.2011, 11:22     Динамика #8
Net_Wanderer, вот как раз в миниатюре неправильный ответ:
При вводе:
5
1 2 3 4 3
Правильный вывод:
4
потому что:

Цитата Сообщение от Shato Посмотреть сообщение
Найдите длину наидлинейшей четночередующейся возрастающей подпоследовательности.
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
02.11.2011, 11:39     Динамика #9
Цитата Сообщение от valeriikozlov Посмотреть сообщение
возрастающей
Да, невнимательно прочитал условия.

Добавлено через 14 минут
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
#include <stdio.h>
#include <stdlib.h>
 
struct range {
        int *begin;
        int *end;
};
 
int distance(struct range r)
{
        return r.end - r.begin;
}
 
int condition(int a, int b)
{
    return (a & 1) != (b & 1) && a < b;
}
 
struct range alternating_parity(int *lb, int *ub)
{
        struct range r;
  
        r.begin = lb;
        while (lb < ub-1 
            && condition(*lb, *(lb+1)))
                lb++;
        r.end = lb + 1;
        return r;
}
 
int main()
{
        int n, *arr, *p, i, dist;
        struct range longest, r;
 
        while (printf("enter n: ") && scanf("%d", &n) && n > 0) {
                if ((arr = (int *) malloc(n * sizeof(int))) == NULL) {
                        printf("error: cannot allocate memory\n");
                        return 1;
                }
                printf("enter an array: ");
                for (i = 0; i < n; i++)
                        scanf("%d", &arr[i]);
                p = arr;
                dist = 0;
        longest.begin = longest.end = NULL;
                do {
                        if (distance(r = alternating_parity(p, arr+n)) > dist) {
                                longest = r;
                                dist = distance(longest);
                        }
                        p = r.end;
                } while (p < arr+n && r.begin != r.end);
                if (longest.begin != NULL) {
                        printf("the longest sequence with alternating parity: ");
                        for (p = longest.begin; p < longest.end; p++)
                                printf("%d ", *p);
                        printf("\nits length is %d\n\n", distance(longest));
                } else
                        printf("there is no a such sequence\n\n");                      
                free(arr);
        }
        return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.11.2011, 15:27     Динамика
Еще ссылки по теме:

Динамика,С++,предметная область Аптека - C++
Сказали сделать задачу на С++,дали только предметную область Аптека,которая состоит из:класс поставщик,класс база,класс сотрудники,класс...

Динамика. Не могу к подзадаче свести и всё тут( - C++
Рассмотрим прямолинейное поле длины N, в первой клетке которого стоит игровая фишка. За один ход мы можем переместить ее на не более чем K...

Динамика. Определить номера строк матрицы в которых знаки элементов чередуются. - C++
Доброго времени суток Господа программисты. Очень прошу Вашей помощи с решением следующей задачи:Определить номера строк матрицы, в которых...

Динамика - Физика
1)По двум наклонным линейкам катится шарик массой m, r ; Найти ускорение; 2)Будем считать что при скольжение тела F=m*g*(мю), при...

Динамика. - Free Pascal
Помогите решить задачу!! В метрополитене есть возможность приобрести проездной на месяц и весь месяц ездить бесплатно. Однако, проездной...


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

Или воспользуйтесь поиском по форуму:
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
02.11.2011, 15:27     Динамика #10
Net_Wanderer, у меня почему то получилось гораздо проще.

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
#include <iostream>
 
typedef long long lol;
 
int main()
{
        lol arr[3000];
    int n, z[3000], result;
        std::cin >> n;
 
        for (int i = 0; i < n; ++i)
        {
                std::cin >> arr[i];
                z[i] = 1;
                for (int j = i - 1; j >= 0; --j)
                        if (abs(arr[i]%2 == 0) != abs(arr[j]%2 == 0) && arr[i] > arr[j])
                                z[i] = std::max(z[i], z[j] + 1);
                result = std::max(result, z[i]);
        }
 
        std::cout << result << std::endl;
 
        return 0;
}
Yandex
Объявления
02.11.2011, 15:27     Динамика
Ответ Создать тему
Опции темы

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