使用递归和没有循环寻找最长上行子系列的长度以阵列 [英] Finding the length of the longest ascending sub-series in an array using recursion and no loops
问题描述
我一直坚持了几个小时试图找出我怎么能写，获取和整数数组的函数，并使用递归查找数组中的最长上升子序列的长度并没有循环可言。即时通讯只允许使用另一个1递归函数
例如，对于以下的数组：{45,1,21,3,3,6,53,9,18}的outpot应为5，因为最长子系列是{1,3,6,9,18 }。
因此，基本上，该得到的阵列和它的大小，以及需要的功能不使用循环可言，没有全局/静态类型打印最长子序列的长度，并且它可以使用另一种帮助递归函数并且那它。
这是pretty多所有我想出了，和它的一个烂摊子，而不是运作良好。
我试图扫描阵列，同时在所有的时间，我知道目前指数IM看，正被相比，目前的指数，并从其中我开始了当前子系列originla指数。
我试图扫描阵列，同时知道应该比较指标，但我卡住了，这里是我的话，我就真的AP preciate任何提示和建议。
谢谢。
无效max_set（INT ARR []，INT大小）
{
INT bigSeries [2] = {0};
calcSeries（ARR，bigSeries，0，0，1，大小-1，1）;
的printf（马克斯部分人数上升％d个\\ N，bigSeries [0]）;}
无效calcSeries（INT ARR []，INT bigSeries []，INT originalCHeckedIndex，诠释checkedIndex，诠释CURRENTINDEX，诠释lastIndex的，诠释升序）
{
如果（（checkedIndex == lastIndex的）||（CURRENTINDEX＆GT; lastIndex的））
{
如果（升序＆GT; bigSeries [0]）
bigSeries [0] =升;
如果（originalCHeckedIndex == lastIndex的）
返回;
其他
{
calcSeries（ARR，bigSeries，originalCHeckedIndex + 1，originalCHeckedIndex + 1，originalCHeckedIndex + 2和lastIndex，0）;
返回;
}
}
如果（ARR [CURRENTINDEX＆GT;常用3 [checkedIndex]）
{
calcSeries（ARR，bigSeries，originalCHeckedIndex，CURRENTINDEX，CURRENTINDEX + 1，lastIndex的，上升+ 1）;
}
其他
{
如果（ARR [originalCHeckedIndex＆LT;常用3 [CURRENTINDEX]）
calcSeries（ARR，bigSeries，CURRENTINDEX，CURRENTINDEX，CURRENTINDEX + 1，lastIndex的，上升）;
calcSeries（ARR，bigSeries，originalCHeckedIndex，checkedIndex，CURRENTINDEX + 1，lastIndex的，上升）;
}
}
该算法有一个第一个答案的，但涉及您可能要注意的几个角落案件有许多相似之处。而不是写长篇评论，我选择了写一个新的答案吧。
健康检查
执行阵列上一些理智的检查，就像我在功能max_set做（）。
- 是在所有提供一个数组（检查NULL）？
- 是提供的数组大小至少为阳性（考虑为size_t）？
允许值
数据类型的 INT 的允许积极的和的负值。该算法应同时处理。至少我没有从您的文章，他们必须是积极的阅读。如果你跳过这部分我的code看起来有点更好。
递归
这种算法（以及从第一个答案的那个）的想法是递归通过数组行走，在第一元件开始，最后结束。因此，这已经定义了开始和递归的结束，记录在源$ C $ C。
要找出最长的子系列的数字这样，总会有三种可能性：
- 最长的子系列可通过跳过当前处理的人数达到
- 最长的子系列，可以通过添加当前处理的人数达到
- 当前处理的数量可以不适合在
如果它比pviously增加数量最多$ P $大可以添加一个数字;我们寻找毕竟上升的序列。的当前数量可能比其他阵列中具有要处理大，尚未。因此，我们必须采取两种可能性考虑：继续递归步骤，没有它，并与它 - 只要它符合标准
可能的监督
要考虑到INT_MIN，机器上的最小可能int值，是阵列中的一个完全有效的数字。我已经添加了可变的可见的，这只是记录如果INT_MIN已经看到阵列中至少有一次或没有。在第一次遇到，的看到的翻转从0到1，不允许任何进一步的INT_MIN值因的升的子系列的要求。您的例子显示了3号两个OCCURENCES这一要求。
测试
试着找各种测试用例，并认为开箱的时间。空数组，大小为负，空数组。接下来，添加花哨的价值观像负数，INT_MIN。或创建升系列，降的人，交错。数字存在的多次...
的#include＆LT; SYS / limits.h中＆GT;＃包括LT＆;＆stdio.h中GT;INT
分析（INT ARR []，诠释大小，INT分钟，诠释见过）
{
INT SUB_COUNT = 0，计数= 0; / *递归结束* /
如果（大小== 0）
返回0; / *递归步，无与当前号码* /
SUB_COUNT =分析（ARR + 1，大小 - 1分钟，看到的）;
如果（改编[0]≥分钟||（分钟== INT_MIN＆放大器;＆放大器;常用3 [0] == INT_MIN＆放大器;＆放大器;！看到））
计数= 1 +分析（改编+ 1，尺寸 - 1，ARR [0]，ARR [0] == INT_MIN）; / *最大的子系列的回归长度* /
返回SUB_COUNT＆GT;算什么？ SUB_COUNT：计数;
}空虚
max_set（INT ARR []，INT大小）
{
INT SEQ = 0; 如果（ARR = NULL＆放大器;！＆安培;尺寸大于0）{
/ *递归开始* /
SEQ =分析（ARR，大小，INT_MIN，0）;
} 的printf（最大的序列为％d \\ n，SEQ）;
}INT
主要（无效）
{
INT ARR [] = {45，1，21日，3，3，6，53，9，18};
max_set（ARR，sizeof的（ARR）/ sizeof的（* ARR））;
返回（0）;
}
i've been stuck for hours trying to figure how can i write a function that gets and array of integers, and finds the length of the longest ascending sub-series in the array using recursion and no loops at all. im only allowed to use another 1 recursive function for example, for the following array: {45,1,21,3,3,6,53,9,18} the outpot should be 5, because the longest sub-series is {1,3,6,9,18}. So, basicly, a function that gets an array and its size, and needs to print the length of the longest sub-series using no loops at all, no global/static types, and it may use another "help" recursive function and thats it. this is pretty much all i came up with, and its a mess and not working well. I'm trying to scan the array while at all time i know the current index im looking at, the index that is being compared to the current, and the originla index from which i started the current sub-series. I tried to scan the array while knowing the indexes that should be compared but i got stuck, here's what i got, i would really appreciate any tips and advices. thanks.
void max_set(int arr[], int size)
{
int bigSeries[2] = { 0 };
calcSeries(arr, bigSeries,0, 0, 1, size -1, 1);
printf("number of max parts going up %d \n", bigSeries[0]);
}
void calcSeries(int arr[], int bigSeries[],int originalCHeckedIndex, int checkedIndex, int currentIndex, int lastIndex, int ascending)
{
if ((checkedIndex == lastIndex) || (currentIndex > lastIndex))
{
if (ascending > bigSeries[0])
bigSeries[0] = ascending;
if (originalCHeckedIndex == lastIndex)
return;
else
{
calcSeries(arr, bigSeries, originalCHeckedIndex + 1, originalCHeckedIndex + 1, originalCHeckedIndex + 2, lastIndex, 0);
return;
}
}
if (arr[currentIndex] > arr[checkedIndex])
{
calcSeries(arr, bigSeries, originalCHeckedIndex, currentIndex, currentIndex + 1, lastIndex, ascending + 1);
}
else
{
if (arr[originalCHeckedIndex] < arr[currentIndex])
calcSeries(arr, bigSeries, currentIndex, currentIndex, currentIndex + 1, lastIndex,ascending);
calcSeries(arr, bigSeries, originalCHeckedIndex, checkedIndex, currentIndex + 1, lastIndex, ascending);
}
}
The algorithm has many similarities with the one of first answer, yet covering a few corner cases you might want to watch out. Instead of writing a lengthy comment, I chose to write a new answer instead.
Sanity Checks
Do some sanity checks on the array, as I did in function max_set().
- Is an array supplied at all (check for NULL)?
- Is the supplied array size at least positive (consider size_t)?
Allowed Values
Data type int allows positive and negative values. The algorithm should handle both. At least I didn't read from your post that they have to be positive. My code looks a bit nicer if you skip that part.
Recursion
The idea of this algorithm (and the one from first answer) is to recursively walk through the array, beginning at the first element, ending at last. So this already defines the start and end of recursion, as documented in source code.
To find the longest sub-series of numbers this way, there are always three possibilities:
- The longest sub-series can be reached by skipping the number that is currently processed
- The longest sub-series can be reached by adding the number that is currently processed
- The currently processed number cannot fit in
A number can be added if it's larger than the largest previously added number; we look for an ascending series after all. The current number could be larger than others in the array that have to be processed, yet. So we have to take both possibilities into account: continuing recursive steps without it and with it -- as long as it fits criteria.
Possible oversight
Take into account that INT_MIN, the smallest possible int value on the machine, is a perfectly valid number in the array. I have added the variable seen, which just records if INT_MIN has been seen at least once in the array or not. On first encounter, seen flips from 0 to 1, not allowing any further INT_MIN values due to requirement of ascending sub-series. Your example shows this requirement with two occurences of number 3.
Tests
Try to find various test cases, and think out of the box at times. NULL for array, negative size, empty array. Next, add fancy values like negative numbers, INT_MIN. Or create ascending series, descending ones, interlacing. Numbers occuring multiple times ...
#include <sys/limits.h>
#include <stdio.h>
int
analyze(int arr[], int size, int min, int seen)
{
int sub_count = 0, count = 0;
/* end of recursion */
if (size == 0)
return 0;
/* recursion step, without and with current number */
sub_count = analyze(arr + 1, size - 1, min, seen);
if (arr[0] > min || (min == INT_MIN && arr[0] == INT_MIN && !seen))
count = 1 + analyze(arr + 1, size - 1, arr[0], arr[0] == INT_MIN);
/* return length of largest sub-series */
return sub_count > count ? sub_count : count;
}
void
max_set(int arr[], int size)
{
int seq = 0;
if (arr != NULL && size > 0) {
/* start of recursion */
seq = analyze(arr, size, INT_MIN, 0);
}
printf("max sequence is %d\n", seq);
}
int
main(void)
{
int arr[] = { 45, 1, 21, 3, 3, 6, 53, 9, 18 };
max_set(arr, sizeof(arr) / sizeof(*arr));
return (0);
}
这篇关于使用递归和没有循环寻找最长上行子系列的长度以阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
