0

Определите, сколько раз во входной последовательности встречается подпоследовательность 1, 2, 3, . . . , 10.

Помогите пожалуйста, ни одной мысли по решению.

Имеющийся код:

/*Определите, сколько раз во входной последовательности встре-
чается подпоследовательность 1, 2, 3, . . . , 10..*/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stddef.h>
#include <string.h>
#include <malloc.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>
#include <float.h>

#define NUM_MEMB    32

int main()
{
    int *arrX = (int*)malloc(sizeof(int) * NUM_MEMB);
    printf("arrX:\n");
    for(int i = 0; i < NUM_MEMB; i++)
    {
        //arrX[i] = (rand()- RAND_MAX/2)%10 + i;
        arrX[i] = rand()%10;
        //printf(" %i ",arrX[i]);
    }
    arrX[5] = 1;
    arrX[6] = 2;
    arrX[7] = 3;
    arrX[8] = 4;
    arrX[9] = 5;
    arrX[10] = 6;
    arrX[11] = 7;
    arrX[12] = 8;
    arrX[13] = 9;
    arrX[14] = 10;

    for(int i = 0; i < NUM_MEMB; i++)
        printf(" %i ",arrX[i]);
    printf("\n");

    printf("Hello World!\n");
    return 0;
}
2
  • Неточно указано. Например, в последовательности 1 2 3 7 4 8 5 6 7 8 9 10 — нужная подпоследовательность есть или нет?
    – Harry
    1 авг 2022 в 13:30
  • Если нужна именно "цельная" подпоследовательность — можно применить любой метод поиска подстрок в строке. Например, просто идти по строке и, встретив 1, проверять — это искомая подстрока или нет.
    – Harry
    1 авг 2022 в 13:42

1 ответ 1

0

Пусть a последовательность длины n, b - последовательность длины m. Будем искать сколько раз последовательность b может быть подпоследовательностью последовательность a. Для удобства индексируем последовательности с единицы.

Введём функцию c(i, j) которая берёт из a первые i элементов, из b - первые j элементов и решает задачу для этих частичных последовательностей.

Число которое нас интересует - c(n, m).

Как можно вычислить c(i, j)?

Если a[i] = b[j], то подпоследовательность или заканчивается в a[i] или заканчивается раньше. Первых c(i - 1, j - 1) штук, вторых - c(i - 1, j) штук.

Если a[i] != b[j], то любая подпоследовательность заканчивается раньше. Таких c(i - 1, j) штук.

Заметим что c(i, 0) = 1 - в любой последовательности одна пустая подпоследовательность. И c(0, j > 0) = 0.

Имея набор c(i, *) можно вычислить c(i + 1, *).

2
  • 1
    Судя по тому, как ТС создает массив, у вас решение слишком серьезное, и нужно просто искать 10 последовательных чисел.
    – Mikhailo
    2 авг 2022 в 10:18
  • @Mikhailo, что-то есть в ваших словах. 2 авг 2022 в 10:46

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.