How to calculate the number of valleys in a sequence of numbers?
Given a sequence of numbers, a valley is defined as an area in a sequence that is surrounded (left and right) by higher values. The challenge 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
The code I have to compute for 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;
}
I can display the correct answer if the input is "3 2 1 2 3". However, if the number between them is different and they are side by side (for example, "3 1 1 2"), the program will calculate the wrong answer. How do I start writing a program so that I can display the correct number of valleys?
source to share
Look for slope changes from down to.
Instead of a double nested loop, march to find slope changes from down. Consider any 0 slope 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;
}
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
source to share
The problem is here:
if((store[j-1] > store[j] )&&(store[j] < store[j+1]))
In both comparisons, you are using an index j
, so this program only finds valleys with length 1. Try this modification:
if((store[i-1] > store[i] )&&(store[j] < store[j+1]))
Also I'm not sure if this is correct in this situation [t23>. But now it is not clear which answer is correct in the case 3 1 2 3
- one ( 1
) or two ( 1
and 1 2
). From your first example, we can see that there is only one correct answer, but this is not obvious from the definition.
source to share
Depending on how much you define the valley as a higher value for IMMEDIATE to the left / right of a given point , you may need to tweak the function Valley
provided by chux as follows:
size_t Valley (const int *store, size_t count) {
...
i++;
for (; i < count; i++) {
int newslope = (store[i] > store[i - 1]) - (store[i] < store[i - 1]);
if (newslope == -slope) {
if (newslope > 0)
valley++;
}
slope = newslope;
}
...
}
output:
$ ./bin/valleyt
6 0
7 1
5 0
5 1
5 0
This is an addition to the answer provided by chux and the input is given in his answer. This code simply restricts the definition of the valley to be created by three adjacent points. (a special case of the general answer of the transition from negative to positive slope with intermediate equivalent points)
source to share