我该如何计算的数字序列山谷的数量？ [英] How do I compute the number of valleys in a sequence of numbers?

问题描述

鉴于数字的序列，一个山谷被定义为区域所包围的序列中（左侧和右侧）通过更高的值。的任务是找到序列中谷的数目。 例如，

Given a sequence of digits, a valley is defined as the region in the sequence that is surrounded (to the left and right) by higher values. The task is to find the number of valleys in the sequence. For example,

{9,8,7,7,8,9} has one valley at {7,7}
{9,8,7,7,8,6,9} has two valleys at {7,7} and {6}
{7,8,9,8,7} has no valleys

在code我要计算山谷的数目如下：

The code I have to compute the number of valleys is as follows:

#include <stdio.h>
#define SIZE 40
int main()
{
   int input;
   int store[SIZE];
   int i = 0;
   int j;
   int valley = 0;
   int count = 0;

   printf("Enter sequence: ");
   scanf("%d", &input);
   while(input != -1)
   {
     store[i] = input;

     i++;

     scanf("%d", &input);
   }

   count = count + i;
   for(i = 1; i < count; i++)
   {
     for(j = i; j < i + 1; j++)
     {

       if((store[j-1] > store[j]) && (store[j] < store[j+1]))
       {
         valley = valley + 1;
         break;
      }
    }
  }

  printf("Number of valleys: %d", valley);

  return 0;
}

我能够显示正确答案，如果输入的是3 2 1 2 3。但是，如果在数量之间等于另一个和它们并排（例如，3 1 1 2），该程序将计算错误的答案。 我该如何去写的程序，使我能够显示的山谷是否正确？

I am able to display the correct answer if the input is "3 2 1 2 3". However, if in between the number is equal to another and they are side by side (for example, "3 1 1 2"), the program will compute the wrong answer. How do I go about writing the program so that I am able to display the correct number of valleys?

推荐答案

寻找斜率变化，从下到上。

Look for slope changes from down to up.

而不是一个双重嵌套循环，游行沿线寻找的斜率变化，从下到上。考虑的任何0斜率是相同previous斜率

Rather than a double nested for loop, march along looking for slope changes from down to up. Consider any slope of 0 to be the same as the previous slope.

size_t Valley(const int *store, size_t count) {
  size_t valley = 0;
  int slope = -1;
  size_t i;

  // Find first down slope
  for (i = 1; i < count; i++) {
    if (store[i] < store[i - 1]) {
      break;
    }
  }

  for (; i < count; i++) {
    int newslope = (store[i] > store[i - 1]) - (store[i] < store[i - 1]);
    // Loop for slope changes
    if (newslope == -slope) {
      if (newslope > 0)
        valley++;
      slope = newslope;
    }
  }

  return valley;
}

测试code。

Test code.

void Vtest(const int *store, size_t count) {
  size_t n = Valley(store, count);
  printf("%zu %zu\n", count, n);
}

void Vtests(void) {
  int a1[] = { 9, 8, 7, 7, 8, 9 };
  Vtest(a1, sizeof a1 / sizeof a1[0]);
  int a2[] = { 9, 8, 7, 7, 8, 6, 9 };
  Vtest(a2, sizeof a2 / sizeof a2[0]);
  int a3[] = { 7, 8, 9, 8, 7 };
  Vtest(a3, sizeof a3 / sizeof a3[0]);
  int a4[] = { 3, 2, 1, 2, 3 };
  Vtest(a4, sizeof a4 / sizeof a4[0]);
  int a5[] = { 8, 7, 7, 8, 6 };
  Vtest(a5, sizeof a5 / sizeof a5[0]);
}

int main(void) {
  Vtests();
  return 0;
}

Output
6 1
7 2
5 0
5 1
5 1

这篇关于我该如何计算的数字序列山谷的数量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！