回溯算法（C++版）(2)

cout<<\ for(i=1;i<=8;i++) cout<int search(int i) { int j; for(j=1;j<=8;j++) if((!b[j])&&(!c[i+j])&&(!d[i-j+7])) { a[i]=j; b[j]=1; c[i+j]=1; d[i-j+7]=1; if(i==8) print(); else search(i+1); b[j]=0; c[i+j]=0; d[i-j+7]=0; } }

int main() { search(1); system(\}

例4、自然数拆分

【问题描述】输入自然数n，然后将其拆分成若干数相加的形式，参与加法运算的数可以重复。

输入：待拆分的自然数n 输出：若干数的加法式子 【样例输入】 5

【样例输出】 5=1+1+1+1+1 5=1+1+1+2 5=1+1+3 5=1+2+2 5=1+4 5=2+3

【问题分析】

算法分析：等式中后一个数必须大于等于前一个数，因为这个可以1、避免重复2提高效率我们用一个数组a[i]来记录拆分的数字，用b[i]记录剩下的数字。K记录第几个拆分的