英文:
Getting segmentation fault while using call by reference to return multiple values in recursive function
问题
问题是找到数组中的最大值和最小值,并返回它们的差值。我参考了GeeksforGeeks上的问题解析。我使用了锦标赛法,将包含两个以上元素的数组分成两部分,然后找到这两个数组的最大值和最小值,最后比较这些最终值并返回答案。官方解决方案在这里,使用了一个名为pair的结构体。我想使用引用值来解决这个问题。
最初,我尝试像这样通过函数返回2个值:
int r1, r2 = Sample(a, high, low)
这是错误的(因为我们只能从函数中返回1个值)。所以我尝试通过引用传递值,像这样:
void halfarrsol(int arr[], int low, int high, int &mi, int &ma){
int mid, min, max;
if(low == high){
mi = ma = arr[low];
}
if(high == low + 1){
mi = arr[low], ma = arr[high];
if(arr[low] > arr[high]){
mi = arr[high];
ma = arr[low];
}
}
else {
mid = (low + high) / 2;
halfarrsol(arr, low, mid, mi, ma);
int minl = mi, maxl = ma;
halfarrsol(arr, mid + 1, high, mi, ma);
int minr = mi, maxr = ma, fin = minl;
if(minl > minr){
fin = minr;
}
int fax = maxl;
if(maxl < maxr){
fax = maxr;
}
mi = fin;
ma = fax;
}
}
我的想法是,当我调用这个函数时,最终的最小值和最大值(mi和ma)将可用。一个明显的错误可能会导致问题的出现是:
halfarrsol(arr, low, mid, mi, ma);
int minl = mi, maxl = ma;
这里我尝试将获得的mi和ma值(对于这一半的数组)存储在'minl'和'maxl'变量中。这样做是否有效呢?
整体代码导致分段错误(segmentation error)和超时:监视的命令转储核心错误。我不确定我到底弄错了什么,或者这种方法完全错误。我希望能够在不使用Struct Pair和不使用另一个类并创建对象的情况下解决这个问题。还有一些使用Tuple来存储最小值和最大值的解决方案,但我认为它们更适用于有多个返回值的情况,因为在这里我只使用了2个值。是否有办法递归地使用引用传递解决这个问题?如果需要,你可以查看这里的驱动代码。
(Note: The code provided in the question appears to contain some HTML encoding, which may be causing issues. I have translated it as is, but you may want to review the code for any HTML-related problems.)
英文:
The question is to find the maximum and minimum element in an array and return their difference. I referred to the editorial of the problem on GeeksforGeeks. I used the tournament method, in which we partition any array having more than two elements into 2 parts, and find the maximum and minimum of those two arrays, and then return the answer after comparing these final values. The official solution listed here , uses a struct pair. I wanted to do it using call by reference values.
Initially I tried to return 2 values with the function like:
int r1,r2= Sample(a,high,low)
That is wrong(as we can return only 1 value from the function)
So I tried passing by reference like this:
void halfarrsol(int arr[], int low, int high, int &mi, int &ma){
int mid, min,max;
if(low==high){
mi=ma=arr[low];
}
if(high==low+1){
mi=arr[low], ma=arr[high];
if(arr[low]>arr[high]){
mi=arr[high];
ma=arr[low];
}
}
else {
mid=(low+high)/2;
halfarrsol(arr, low,mid,mi,ma);
int minl=mi, maxl=ma;
halfarrsol(arr, mid+1,high,mi,ma);
int minr=mi, maxr=ma, fin=minl;
if(minl>minr){
fin= minr;
}
int fax=maxl;
if(maxl<maxr){
fax=maxr;
}
mi= fin;
ma=fax;
}
}
The idea is that when I call the function, the final value of min and max (mi and ma) will be available.
One obvious error that I think might be messing things up is the
halfarrsol(arr, low,mid,mi,ma);
int minl=mi, maxl=ma;
What I'm trying to here is store the obtained mi and ma vales(for this half array) in 'minl' and 'maxl' variables. Is this valid?
The overall code gives a segmentation error, and timeout: the monitored command dumped core error.
I'm not sure what exactly I'm messing up, or if this approach is completely wrong. I wanted to be able to solve this question without using a Struct Pair, and without using another class and creating an object.
There are also solutions like using a Tuple to store min and max values, but I considered them to be more applicable for when we have many return values, as here I am using 2 values only.
Is there any way to solve this problem recursively using call by reference?
If required you can view the driver code here
答案1
得分: 0
以下是翻译好的部分:
"这个错误在逻辑上不容易找出。你的逻辑大致正确,问题在于当 low == high
时,它将无限递归调用函数,因为你既没有返回,也没有使用 else if
处理 high == low + 1
的情况。请改为以下方式:"
...
if(low==high){
mi=ma=arr[low];
}
else if(high==low+1){
mi=arr[low], ma=arr[high];
if(arr[low]>arr[high]){
mi=arr[high];
ma=arr[low];
}
}
else {
...
英文:
The bug is not easy to figure out if you are focused on logic. Your logic is more or less correct, issue is that when low == high
, then it will call function recursively for indefinite times since you are not returning neither you have used else if
for high == low + 1
. Change to following:
...
if(low==high){
mi=ma=arr[low];
}
else if(high==low+1){
mi=arr[low], ma=arr[high];
if(arr[low]>arr[high]){
mi=arr[high];
ma=arr[low];
}
}
else {
...
答案2
得分: 0
你的递归永远不会停止。你忘记在第一个情况中结束它:
if(low==high){
mi=ma=arr[low];
}
然后进入第二个条件判断,其中条件为假,然后进入 else 部分...
至少修改为:
if(low==high){
mi=ma=arr[low];
return
}
此外,最小值/最大值可以更容易地计算:
mid=(low+high)/2;
halfarrsol(arr, low, mid, mi, ma); // 获取最小值/最大值
int minr, maxr;
halfarrsol(arr, mid+1, high, minr, maxr); // 获取右侧最小值/最大值
if (mi>minr){ // 如有需要,修正最小值
mi = minr;
}
if (ma<maxr){ // 如有需要,修正最大值
ma=maxr;
}
英文:
Your recursion never stops. You forgot to end it in the very first case:
if(low==high){
mi=ma=arr[low];
}
It then enters the second if, where the condition is false, and then goes to the else...
At least change to:
if(low==high){
mi=ma=arr[low];
return
}
Aside, the min/max can be computed more easily:
mid=(low+high)/2;
halfarrsol(arr, low, mid, mi, ma); // get min/max
int minr, maxr;
halfarrsol(arr, mid+1, high, minr, maxr); // get right min/max
if (mi>minr){ // correct min if needed
mi = minr;
}
if (ma<maxr){ // correct max if needed
ma=maxr;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论