可不可以帮忙找两个分别使用c语言实现分治法和减治法的例子最好能体现出这两种算法的特点。谢了。

发布网友发布时间：2022-04-23 09:55

共2个回答

热心网友时间：2023-10-10 09:16

递归求阶乘，二分查找就是典型的减治法。递归的归并排序，快速排序就是典型的分治法。减治法只是将问题规模缩小，而分治法是将原问题分成多个规模更小的同类问题。追问可以直接贴代码吗？我找到得不知道是不是我要的。。谢了

追答减治法给你举两个例子：
1、求阶乘
long fun(int n)
{
long s;
if(n <= 1) return 1;
s = fun(n - 1); //该行与下面这行合起来等价于return (fun(n-1) * n);
return (s * n);
}
2、二分查找
int BinSearch(int s[], int left, int right, int key)
{
int mid;
if(right < left) return -1;
mid = (left + right) / 2;
if(s[mid] == key) return mid;
if(s[mid] < key) return BinSearch(s, mid + 1, right, key);
else return BinSearch(s, left, right, key);
}

分治法给你举个例子
3，快速排序
void QuickSort(int s[], int left, int right)
{
if((right - left) < 2) return;
int q = partition(s, left, right);
QuickSort(s, left, q - 1);
QuickSort(s, q + 1, right);
}

从上面的程序可以看出，减治法和分治法，它们与递归往往时相伴的。减治法递归时，只进行一次递归调用，每次递归只是将规模缩小，尽管程序2看上去好像是进行两次递归，但仔细看就可以发现，在进行递归调用时，它是有选择的在两个中选择一个进行递归，因此还是只进行一次递归。而分治法，则需进行至少两次递归。

热心网友时间：2023-10-10 09:17

没说清楚追问就是举两个例子。。一个用了分治法，一个用减治法，最好能体现这两种算法的特点