1

给定一个长度为 的数组n，要求编写程序来计算该给定数组的长度子序列的个数m。

下面是执行此操作的代码。请看一看。

int recCountSubseq(int seqLength, int length, int s[]) {
    int answer;

    if (seqLength == 0) {       /* Base case: found a subseq of correct length */
        return 1;
    }

    if (seqLength >= length) {  /* Base case: only possible is seqLength == length*/
        return (seqLength==length);
    }

    /* Recursive case: two branches */
    answer = recCountSubseq(seqLength-1, length-1, s); /* s[length-1] is in subseq*/
    printf("answer=%d\n", answer);

    answer += recCountSubseq(seqLength, length-1, s);  /* s[length-1] is not in subseq */
    printf("increased answer is %d\n", answer);

    return answer;
}

void countSubseq(int seqLength, int length, int s[]) {    
    printf("#subseq = %d\n", recCountSubseq(seqLength, length, s));    
}

int main() {
    int length;
    scanf("%d", &length);

    int seqLength;
    int i;
    int s[100];

    for (i=0;i<length; i++) {
        scanf("%d", &s[i]);
    }

    countSubseq(seqLength, length, s);

    return 0;
}

现在，我的问题是：为什么seqLength每次减少的价值，以及这段代码究竟是如何工作的？

4

2 回答 2

2

该函数具有未定义的行为，因为至少变量seqLength未初始化：

int seqLength;

而且任务不明确。如果您有一个包含n元素的数组，那么长度的连续子序列的m数量m <= n等于n - m + 1。

所以写这样一个函数没有多大意义。:)此外，我什至看不到函数中的哪里可以访问作为第三个参数传递的数组。:)

Insetad 我可以建议您使用以下功能。至少它有一些意义。:)

#include <stdio.h>

size_t recCountSubseq( const int a[], size_t n, size_t m )
{
    if ( m <= n )
    {
        for ( size_t i = 0; i < m; i++ ) printf( "%d ", a[i] );
        printf( "\n" );
    }

    return n <= m ? n == m : 1 + recCountSubseq( ++a, --n, m );
}

int main( void )
{
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    printf( "There are %zu subsequencies\n", recCountSubseq( a, sizeof( a ) / sizeof( *a ), 3 ) );

    return 0;
}

它的输出是

1 2 3 
2 3 4 
3 4 5 
4 5 6 
5 6 7 
6 7 8 
7 8 9 
There are 7 subsequencies

我认为您错误地解释了作业及其解决方案。你应该重新检查他们的描述。

于 2015-10-27T15:09:35.020 回答
0

据我了解，您需要从用户那里获取子序列的长度，这在您的代码中没有完成。

如果我的猜测是正确的，那么 main() 函数将如下所示：

int main(array<System::String ^> ^args)
{
  int length;

  printf("Length of array:");
  scanf("%d", &length);

  int seqLength;

  printf("Length of sub-seq:");
  scanf("%d", &seqLength);

  int i;
  int s[100];

  printf("Array of %d elements:", length);
  for (i=0;i<length; i++)
  {
    scanf("%d", &s[i]);
  }

  countSubseq(seqLength, length, s);

  return 0;
}
于 2015-10-27T15:30:03.570 回答