时间戳

首页 > 解决方案 > 一个函数，它包含两个 (pos) 整数 k 和 n 以及 1. 打印数字 1-.n 的所有长度为 k 的递增序列 2. 返回数字序列

c - 一个函数，它包含两个 (pos) 整数 k 和 n 以及 1. 打印数字 1-.n 的所有长度为 k 的递增序列 2. 返回数字序列

问题描述

这是完整的问题：

问题 3 [30 分]。编写一个包含两个正整数 k 和 n 的函数，其工作原理如下 1. 打印所有长度为 k 的递增序列，由数字 1...n 组成 2. 返回此类序列的数量。例如

int print_k_sequences( int n, int k)
For example, print_k_sequences( 5 , 3) prints the following sequences
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
and returns 10

打印序列的具体顺序由您决定。数字之间正好加一个空格。不要忘记用新行分隔序列。你的函数应该在合理的时间内对输入 n,k 最多 20 工作。[提示：使用递归。您可能还想使用辅助功能]

我的实现只打印第一个序列然后停止。我哪里错了？

//helper for printing array
void printArr( int arr[], int size){

    for(int i =0; i<size; i++)
    {
        printf("%d", arr[i] );
    }
    printf("\n");

    return;
}

int findSeq ( int arr[], int n, int k){

/* start from last index and find first elelment less than n if righmost element
is n then we have to incremenet arr value with 1 at starting index*/
    int p = k -1;
    while(arr[p == n])
    {
        p=0;
    }

    //  if the last element is the n and the difference of n and k is one greater
    // thant the first elelment that means last sequence is generated
    if(arr[k-1] ==n && (n-k) == arr[0]-1)
    {
        return 0;
    }

    /* else increase the value of array element till n*/
    arr[p] = arr[p] + 1;

    /* the nextr index value of array shoul always be greater than previous value */
    for (int i = p+1; i<k; i++)
    {
        arr[i] = arr[i-1] +1;
    }

    return 1;

}

int print_k_sequences(int n,int k) {
  // implement me

    int arr[k];

    int count = 0;

    /*values of first seq*/
    while (1){
        printArr(arr, k);

        count++;

        if(findSeq(arr, n, k) == 0)
        {
            break;
        }
    }

  return count;
}

这是测试它的代码：请注意，主函数的任何参数都不能更改。

bool test_q3_1()  {
  int ans = print_k_sequences(6, 2);
  if (ans == 15)  {
    // need to also check the actual sequences
    printf("Q3-1 ok\n");
    return true;
  }
  else  {
    printf("Q3-2 ERROR: answer=%d, correct=15 \n", ans);
    return false;
  }
}

bool test_q3_2()  {
  int ans = print_k_sequences(8, 3);
  if (ans == 56)  {
    // need to also check the actual sequences
    printf("Q3-2 ok\n");
    return true;
  }
  else  {
    printf("Q3-2 ERROR: answer=%d, correct=56 \n", ans);
    return false;
  }
}

提前致谢！

标签： crecursion

解决方案

弄清楚了 ：）

对于遇到此问题的任何人：

#include <stdio.h>

int numberOfSequences; // global variable to count number of sequences generated

// function to print contents of arr[0..k-1]
void OutputSequence(int arr[], int k) {
    for (int i = 0; i < k; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// function to generate all increasing sequences from 1..n of length k
void generateSequence(int n, int k, int *len, int arr[]) {

    // If length of the array sequence becomes k
    if (*len == k) {
        numberOfSequences++; // we increment the counter by 1
        OutputSequence(arr, k); // and print that sequence
        return;
    }

    int i;
    // If length is 0, then start putting new numbers in the sequence from 1.
    // If length is not 0, then start from previous element +1.
    if (*len == 0)
        i = 1;
    else
        i = arr[*len - 1] + 1;

    // Increase length of the sequence so far
    (*len)++;

    // Put all numbers (which are greater than the previous element) at new position.
    while (i <= n) {
        arr[(*len) - 1] = i;    // adding the new element to the sequence
        generateSequence(n, k, len, arr);// generating the subsequent elements in the sequence
        i++;
    }

    (*len)--;
}

// driver function to print all increasing sequences from 1..n of length k
// and return the number of such sequences
int print_k_sequences(int n, int k) {
    int arr[k]; // array to store individual sequences
    int len = 0; // Initial length of current sequence
    numberOfSequences = 0; // counter to count number of sequences
    generateSequence(n, k, &len, arr);
    return numberOfSequences;
}

int main() {
    int k = 3, n = 5;
    printf("The sequences between 1.. %d  of length %d are:\n", n, k);
    int ans = print_k_sequences(n, k);
    printf("No of sequences= %d\n", ans);
    return 0;
}

推荐阅读