最长递增和递减序列序列的暴力求解---C语言版

1920阅读 0评论2015-09-17 九阳神功爱喝茶
分类:C/C++

最长递增子序列的求解,也是经常出现在找工作笔试面试中的一类问题。这里是我自己用C语言写的一个暴力解法。。。哈哈,暴力的才是最简单的,万一以后在线笔试的时候遇到这类问题,直接拿过来用就好了。这里我定义了一个结构体,不仅记录了最长的子序列的大小,还记录了依次是哪几个数字,非常实用方便。

点击(此处)折叠或打开

  1. #pragma warning(disable:4996)
  2. #include<stdio.h>
  3. #include<string.h>
  4. #define MAX_LEN 20
  5. typedef struct {
  6.     int length;
  7.     int a[MAX_LEN];
  8. }node;
  9. //将一个整形数组中的值拷贝到另一个整形数组中
  10. IntStringcpy(node *dst, node src) {
  11.     for (int i = 0; i < src.length; i++) {
  12.         (*dst).a[i] = src.a[i];
  13.     (*dst).length = src.length;
  14.     }
  15. }
  16. Intcpy(node* dst, int num) {
  17.     int length = (*dst).length;
  18.     (*dst).a[length] = num;
  19.     (*dst).length++;
  20. }

  21. LIS(int num[], node dp[],int length) {
  22.     int i = 1, j = 0; dp[0].a[0] = num[0];
  23.     for (; i < length; i++) {
  24.         for (j=0; j < i; j++) {
  25.             if ((num[j] < num[i]) && dp[i].length < dp[j].length+1) {
  26.                 //现将dp[j]中的数组a拷贝到dp[j]的数租dp[i]之中。
  27.                 IntStringcpy(&dp[i],dp[j]);
  28.             }
  29.         }
  30.         //对某个i节点结束之后,也将其放在dp数组中,同时length自增1次
  31.         Intcpy(&dp[i],num[j]);
  32.     }
  33. }

  34. int main(void) {
  35.     int n;
  36.     scanf("%d", &n);
  37.     int array[MAX_LEN];
  38.     for (int i = 0; i < n; i++) {
  39.         scanf("%d", &array[i]);
  40.     }
  41.     node dp[MAX_LEN];
  42.     for (int i = 0; i < n; i++)
  43.         dp[i].length = 1;

  44.     LIS(array, dp, n);
  45.     int max = dp[0].length;
  46.     for (int i = 1; i < n; i++) {
  47.         if (max < dp[i].length) {
  48.             max=dp[i].length;
  49.         }
  50.     }
  51.     for (int i = 0; i < n; i++) {
  52.         if (dp[i].length == max) {
  53.             for (int j = 0; j < max; j++) {
  54.                 printf("%d ", dp[i].a[j]);
  55.             }
  56.             printf("\n");
  57.         }
  58.     }

  59. }

今天又更新了下,写了个最长递减子序列的,思路是一样的,值得注意的是角标,很容易出错弄得不好的话.。。。

点击(此处)折叠或打开

  1. #pragma warning(disable:4996)
    #include<stdio.h>
    #include<string.h>
    #define MAX_LEN 20
    typedef struct {
    int length;
    int a[MAX_LEN];
    }node;
    //将一个整形数组中的值拷贝到另一个整形数组中
    void IntStringcpy(node *dst, node src) {
    for (int i = 0; i < src.length; i++) {
    (*dst).a[i] = src.a[i];
    (*dst).length = src.length;
    }
    }
    void Intcpy(node* dst, int num) {
    int length = (*dst).length;
    (*dst).a[length] = num;
    (*dst).length++;
    }


    void LDS(int num[], node dp[], int n) {
    int i = n-2, j;
    dp[n - 1].a[0] = num[n - 1]; dp[n - 1].length = 1;
    for (; i >=0; i--) {
    for (j = n-1; j > i; j--) {
    if ((num[j] < num[i]) && dp[i].length < dp[j].length + 1) {
    //现将dp[j]中的数组a拷贝到dp[j]的数租dp[i]之中。
    IntStringcpy(&dp[i], dp[j]);
    }
    }
    //对某个i节点结束之后,也将其放在dp数组中,同时length自增1次
    Intcpy(&dp[i], num[j]);
    }
    }


    int main(void) {
    int n;
    scanf("%d", &n);
    int array[MAX_LEN];
    for (int i = 0; i < n; i++) {
    scanf("%d", &array[i]);
    }
    node dp[MAX_LEN];
    for (int i = 0; i < n; i++)
    dp[i].length = 0;


    LDS(array, dp, n);
    int max = dp[n-1].length;
    for (int i = n-2; i >=0; i--) {
    if (max < dp[i].length) {
    max = dp[i].length;
    }
    }
    for (int i =n-1; i >=0; i--) {

    if (dp[i].length == max) {
    for (int j = max-1;j>=0; j--) {
    printf("%d ", dp[i].a[j]);
    }
    printf("\n");
    }
    }


    }














上一篇:字符串C语言常用API
下一篇:八皇后问题的递归实现