当前位置:   article > 正文

“谷底”类题目及一些自己的思考_c语言求数字谷底个数

c语言求数字谷底个数

题目:我们把字符串A中符合下列属性的任意连续子串 B 称为“谷底”:存在0<i<B.length-1使得B[0]>B[1]>......B[i-1]>B[i]<B[i+1]<......<B[B.length>=3]。输入一个整数字符串A,输出最长“谷底”和“谷底”长度;如果不含有“谷底”则输出不存在谷底。

我是一个大一新生,这个是我们学校工作室的考核题的内容之一。作为一个还没接触过算法,C语言也接触不久的萌新,可以说这一题对我来说挺有挑战性的。

如果看成一个函数 如图                                                                                         A:代表字符串A    B:代表字符串B

如图

这一题的要点是需要在字符串A中寻找到字符串B并且找到最长的字符串B

我一开始的思路是先找到每一个字符串B的左边第一个字符,然后先找B的单调递减区间,再找单调递增区间,把两个区间合起来组合成一个字符串B的区间,区间的长度为字符串B的长度,在比较每一个字符串B的长度,找到最长的字符串B。后来发现如果这样去解这一个题目的话会使的代码过于冗长,且需要的变量十分的多

后来我一个同学给了我一个新的思路那就是通过锚定字符串B中最小的字符来确定每一个字符串B的位置,然后从这个位置向两边寻找字符串B的边界。

如图                                                 

  这一种方法无疑比我之前的方法更加方便使用代码实现

上代码

  1. #include<stdio.h>
  2. #include<string.h>//为了使用字符数组
  3. int main()
  4. {
  5. char number[20] = {};//定义一个字符数组用来储存每一位数字
  6. int len=0,len_1=0,len_2=0;//用来确定数组长度,谷底区间长度
  7. int i, k,h;//用来作为数组下标
  8. printf("输入:");
  9. getchar();
  10. gets_s(number);//把数字作为字符串放入数组中
  11. len = strlen(number);//求得字符串长度数。
  12. for (i = 0; i <= len - 1; i++)
  13. {
  14. if (number[i]<number[i - 1] && number[i + 1]>number[i])//用于求出谷底数位置
  15. {
  16. for (k = i; number[k + 1] > number[k]; k++){}
  17. //用于求右峰位置
  18. for (h = i; number[h - 1] > number[h]; h--){}
  19. //用于求左峰位置
  20. len_1 = h + k - 3;//求出谷间长度
  21. if (len_2 >= len_1)//求出最长谷间长度
  22. len_1 = len_2;
  23. }
  24. }
  25. printf("输出:%d", len_1);
  26. if (len_1 == 0)
  27. printf("解释:不含谷底");
  28. else
  29. {
  30. printf("解释:最长谷底是");
  31. for (h = h; h <= k; h++)//输出谷间
  32. {
  33. printf("%c", number[h]);
  34. }
  35. printf("长度为:%d", len_1);
  36. }
  37. return 0;
  38. }

这就是使用这一种方法的解题代码 

其中的关键在于

  1. for (i = 0; i <= len - 1; i++)
  2.     {
  3.         if (number[i]<number[i - 1] && number[i + 1]>number[i])//用于求出谷底数位置
  4.         {
  5.             for (k = i; number[k + 1] > number[k]; k++){}
  6.                 //用于求右峰位置
  7.             for (h = i; number[h - 1] > number[h]; h--){}
  8.                 //用于求左峰位置
  9.                     len_1 = h + k - 3;//求出谷间长度
  10.             if (len_2 >= len_1)//求出最长谷间长度
  11.                 len_1 = len_2;
  12.         }
  13.     }
  • 使用第一个循环来检索数组中的每一个字符元素。
  • 使用一个判断来确定每一个字符串B的最小字符。
  • 使用两个循环来分别找出左值和右值。
  • 使用一个判断来找到最大字符串B长度。

这一个方法不仅可以作用于这一个题目还可以用于其他类似的题目,其符合的条件应该要满足

1、在一长串的数中找一段数

2、每一段数存在对称性

如果这两个条件满足大概率是可以运用这一个方法解决问题的。

 

                                                                                                     第一次写博客,如果有不对的地方欢迎各位大佬的斧正。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/920404
推荐阅读
相关标签
  

闽ICP备14008679号