UC知道c++分治算法
来源：百度知道 编辑：UC知道 时间：2024/06/17 08:08:35
要用分治的方法找出数组a中的一个a[i]=i（i是下标） 只有一个
额，请大家帮我看下下面的问题，输不出结果的：
#include<iostream.h>
//要先写 第一个元素的值为0的排除子函数，没写。
int arrange(int a[],int low,int high){
int flag=0;
int mid =(low+high)/2;
if((high-low)==0){ //最后一层的情况
if(a[mid]==mid)
return a[mid];
else
return 0;
}
int left;
int right;
left=arrange(a,low,mid); //向左
right=arrange(a,mid,high); //向右
if(left||right) //整合，有一个非0就是找到值了
return left+right;
else
return 0;
}
int main(){
int a[]={-8,-5,-2,-1,2,5,8,10,18,21};
int result;
result=arrange(a,1,10);
cout<<result;
return 0;
}
谢谢了~
额，请大家帮我看下下面的问题，输不出结果的：
#include<iostream.h>
//要先写 第一个元素的值为0的排除子函数，没写。
int arrange(int a[],int low,int high){
int flag=0;
int mid =(low+high)/2;
if((high-low)==0){ //最后一层的情况
if(a[mid]==mid)
return a[mid];
else
return 0;
}
int left;
int right;
left=arrange(a,low,mid); //向左
right=arrange(a,mid,high); //向右
if(left||right) //整合，有一个非0就是找到值了
return left+right;
else
return 0;
}
int main(){
int a[]={-8,-5,-2,-1,2,5,8,10,18,21};
int result;
result=arrange(a,1,10);
cout<<result;
return 0;
}
谢谢了~
你这题很巧，你用二分法递归排序，最后会只剩下两个相邻的元素，而不会重叠指向一个元素，所以high - low == 0这一句始终不成立，造成死循环。加以个条件就好了
#include<iostream>
using namespace std;
//要先写 第一个元素的值为0的排除子函数，没写。
int arrange(int a[],int low,int high)
{
int flag=0;
int mid =(low+high)/2;
if((high-low)==0 || (high - low) == 1) //二分法排序的最后两种可能
{
if(a[mid]==mid)
return a[mid];
else
return 0;
}
int left;
int right;
left=arrange(a,low,mid); //向左
right=arrange(a,mid,high); //向右
if(left||right) //整合，有一个非0就是找到值了
return left+right;
else
return 0;
}
int main()
{
int a[]={-8,-5,-2,-1,2,5,8,10,18,21};
int result;
result=arrange(a,1,10);
cout<<result << endl;
return 0;
}
我错了ight=arrange(a,mid,high); //向右
这个地方是不是要mid+1？？