当前位置:   article > 正文

时间序列问题_给定事件列表

给定事件列表

已知N个时间的发生时刻和结束时刻(见下表)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件{ 2,8,10 }。

事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长事件序列



  up主这里为了让输入方便一点 就用文件的方式 读取数据

 

  文件名:1.txt

 

  1. 0 1 3
  2. 1 3 4
  3. 2 0 7
  4. 3 3 8
  5. 4 2 9
  6. 5 5 10
  7. 6 6 12
  8. 7 4 14
  9. 8 10 15
  10. 9 8 18
  11. 10 15 19
  12. 11 15 20

 程序:

  1. #include<iostream>
  2. #include<fstream>
  3. using namespace std;
  4. struct b
  5. {
  6. int number;
  7. int head;
  8. int end;
  9. };
  10. b tp[12];
  11. int a[12]={0};
  12. int maxs[12]={0};
  13. int max_len=0;
  14. int max_bs=0;
  15. int getEnd(int n) //获取 n=number 的end 的值
  16. {
  17. int i,end;
  18. for(i=0;i<=11;i++)
  19. {
  20. if(tp[i].number==n)
  21. {
  22. end=tp[i].end;
  23. break;
  24. }
  25. }
  26. return end;
  27. }
  28. int getHead(int n) //获取 n=number 的 head 的值
  29. {
  30. int i,head;
  31. for(i=0;i<=11;i++)
  32. {
  33. if(tp[i].number==n)
  34. {
  35. head=tp[i].head;
  36. break;
  37. }
  38. }
  39. return head;
  40. }
  41. bool End(int n) //当前深度是否还能继续
  42. {
  43. int i,j;
  44. if(n>0)
  45. {
  46. for(i=0;i<n;i++)
  47. if(a[i]==a[n]) return true; //一旦有重复的
  48. if(getHead(a[n])>=getEnd(a[n-1])) return false;
  49. }
  50. else
  51. {
  52. return false;
  53. }
  54. return true;
  55. }
  56. void bre(int n)
  57. {
  58. static int max=0;
  59. int i=0,sum=0;
  60. for(i=0;i<n;i++)
  61. {
  62. sum=sum+getEnd(a[i])-getHead(a[i]);
  63. }
  64. if(sum>max)
  65. {
  66. max=sum;
  67. max_bs=sum;
  68. max_len=n;
  69. for(i=0;i<n;i++)
  70. maxs[i]=a[i];
  71. }
  72. }
  73. void getAll(int n,int num)
  74. {
  75. //当前的end 已经没有所匹配的head的时候
  76. int i;
  77. a[n]=num;
  78. if(End(n))
  79. bre(n);
  80. else
  81. {
  82. for(i=0;i<=11;i++)
  83. getAll(n+1,i);
  84. }
  85. }
  86. int main()
  87. {
  88. int number,head,end,i;
  89. ifstream out("1.txt");
  90. if (!out.is_open())
  91. {
  92. cout << "Error opening file"; exit (1);
  93. }
  94. i=0;
  95. while (!out.eof())
  96. {
  97. out>>number>>head>>end;
  98. tp[i].number=number;
  99. tp[i].head=head;
  100. tp[i].end=end;
  101. i++;
  102. }
  103. for(i=0;i<12;i++)
  104. getAll(0,i);
  105. for(i=0;i<max_len;i++)
  106. cout<<maxs[i]<<" ";
  107. cout<<endl<<"最长的事件长度为:"<<max_bs;
  108. return 0;
  109. }


 

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

闽ICP备14008679号