设计思想与策略
- 分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
- 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
可以把原问题分解为已经解决的部分和未解决的部分，这两个部分的长度都有可能是0，对于已经解决的部分我们不去探讨，对于未解决的部分我们可以把其分解为若干个最小子问题的集合，对于每一个最小子问题我们都能简单求解。
分治法的适用条件
- 该问题的规模缩小到一定的程度就可以容易地解决。绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。这条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用。
- 利用该问题分解出的子问题的解可以合并为该问题的解。这条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
步骤和设计模式
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
- 合并：将各个子问题的解合并为原问题的解。
设计模式
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
7. return(T)
- 其中|P|表示问题P的规模；
- n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。
- ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。
- 算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。
思维过程
实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。
- 一定是先找到最小问题规模时的求解方法；
- 然后考虑随着问题规模增大时的求解方法；
- 找到求解的递归函数式后（各种规模或因子），设计递归程序即可。
例
Write function
void stringSplit (char *str, int n, int *length, ...);
which is able to split the string str into an undefined number of sub-strings whose sizes are stored in length[0], length[1], . . ., length[n-1]. Write an error message when it is not possible to split the string into sub-strings of those lengths. Print-out the generated sub-strings when it is possible.
For example, with:
• str = Hello, n = 2, and length = (2, 3), the program may produce sub-strings (He, llo), or (Hel, lo).
• str = Hello, n = 2, and length = (3, 4), there is no decomposition.
• str = sampleTest, n = 3, and length = (2, 3, 6), the program may produce sub-strings (sa, mp, le, Te, st), or sub-strings (sa, mp, leT, est), or sub-strings (sa, mpleTe, st), etc.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1024;
void stringSplit (
char *str,
int n,
int *length
)
{
char *s;
int i;
s = (char *) malloc ((strlen (str) + 1) * sizeof (char));
if (s==NULL) {
fprintf (stderr, "Allocation Error.\n");
exit (1);
}
for (i=0; i<strlen(str); i++) {
s[i] = 0;
}
stringSplitRec (str, n, length, s, 0, 0);
return;
}
int stringSplitRec (
char *str,
int n,
int *length,
char *res,
int ind,
int len
)
{
int i, j, k;
// Termination with no solution
if (len>strlen (str)) {
return (0);
}
// Termination with a solution
if (len==strlen (str)) {
for (i=k=0; i<ind; i++) {
for (j=0; j<res[i]; j++) {
fprintf (stdout, "%c", str[k]);
k++;
}
fprintf (stdout, " ");
}
fprintf (stdout, "\n");
return (1);
}
// Try to use all lengths
for (i=0; i<n; i++) {
res[ind] = length[i];
#if 0
/*
* Enable the following 2 lines
* to have ALL solutions
*/
stringSplitRec (str, n, length, res, ind+1, len+length[i]);
#else
/*
* Enable the following 2 lines
* to have only ONE solution
*/
if (stringSplitRec (str, n, length, res, ind+1, len+length[i]))
return (1);
#endif
}
return (0);
}
int main(int argc, char const *argv[]) {
char str[1024];
int n=0;
int* length=(int*)malloc(sizeof(int)*n);
if(length==NULL)
{
fprintf(stderr, "Allocation error\n" );
exit(-1);
}
printf("input N and length vector\n" );
scanf("%d",&n );
for(int i=0;i<n;i++)
{
scanf("%d",&length[i] );
}
printf("string input\n" );
scanf("%s",str);
stringSplit(str,n,length);
return 0;
}
