設(shè)計(jì)思想與策略

• 分治法的設(shè)計(jì)思想是：將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。

• 分治策略是：對(duì)于一個(gè)規(guī)模為n的問(wèn)題，若該問(wèn)題可以容易地解決（比如說(shuō)規(guī)模n較?。﹦t直接解決，否則將其分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。這種算法設(shè)計(jì)策略叫做分治法。

可以把原問(wèn)題分解為已經(jīng)解決的部分和未解決的部分，這兩個(gè)部分的長(zhǎng)度都有可能是0，對(duì)于已經(jīng)解決的部分我們不去探討，對(duì)于未解決的部分我們可以把其分解為若干個(gè)最小子問(wèn)題的集合，對(duì)于每一個(gè)最小子問(wèn)題我們都能簡(jiǎn)單求解。

分治法的適用條件

• 該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決。絕大多數(shù)問(wèn)題都可以滿足的，因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加

• 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。這條特征是應(yīng)用分治法的前提它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用。
• 利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解。這條特征是關(guān)鍵，能否利用分治法完全取決于問(wèn)題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動(dòng)態(tài)規(guī)劃法。
• 該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子子問(wèn)題。這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。

步驟和設(shè)計(jì)模式

• 分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；
• 解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題；
• 合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。

設(shè)計(jì)模式

Divide-and-Conquer(P)
    1. if |P|≤n0
    2. then return(ADHOC(P))
    3. 將P分解為較小的子問(wèn)題 P1 ,P2 ,...,Pk
    4. for i←1 to k
    5. do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi
    6. T ← MERGE(y1,y2,...,yk) △ 合并子問(wèn)題
    7. return(T)

• 其中|P|表示問(wèn)題P的規(guī)模；

• n0為一閾值，表示當(dāng)問(wèn)題P的規(guī)模不超過(guò)n0時(shí)，問(wèn)題已容易直接解出，不必再繼續(xù)分解。

• ADHOC(P)是該分治法中的基本子算法，用于直接解小規(guī)模的問(wèn)題P。因此，當(dāng)P的規(guī)模不超過(guò)n0時(shí)直接用算法ADHOC(P)求解。
• 算法MERGE(y1,y2,…,yk)是該分治法中的合并子算法，用于將P的子問(wèn)題P1 ,P2 ,…,Pk的相應(yīng)的解y1,y2,…,yk合并為P的解。

思維過(guò)程

實(shí)際上就是類(lèi)似于數(shù)學(xué)歸納法，找到解決本問(wèn)題的求解方程公式，然后根據(jù)方程公式設(shè)計(jì)遞歸程序。

1. 一定是先找到最小問(wèn)題規(guī)模時(shí)的求解方法；

2. 然后考慮隨著問(wèn)題規(guī)模增大時(shí)的求解方法；

3. 找到求解的遞歸函數(shù)式后（各種規(guī)?；蛞蜃樱O(shè)計(jì)遞歸程序即可。

例

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