设计思想与策略

---

• 分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

• 分治策略是：对于一个规模为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的解。

思维过程

实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。

1. 一定是先找到最小问题规模时的求解方法；

2. 然后考虑随着问题规模增大时的求解方法；

3. 找到求解的递归函数式后（各种规模或因子），设计递归程序即可。

例

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;
}