如何用C语言实现长尾词的搜索与回溯算法？

本文共计915个文字，预计阅读时间需要4分钟。

1、组合的输出[题目描述]组合与排列是常用的数学方法，其中组合是从n个元素中抽取r个元素的组合方式（不分顺序且r≤n），我们可以简单地将n个元素理解为自然数1、2、……、n，从中任意选取r个数。

1、组合的输出

排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。

现要求你用递归的方法输出所有组合。

例如n＝5，r＝3，所有组合为：

1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

一行两个自然数n、r(1<n<21，1≤r≤n)。

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

5 3 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

分析： 这题与一般的全排列题不同之处是：其中的元素按由小到大的顺序排列。这就意味着像 5 4 3 这样的排列是不行的，即后一个位置的元素要比前一个大

#include<iostream> #include<iomanip> using namespace std; int n,r; int a[300]; bool f[300]={0}; void print(); void search(int); int main() { cin>>n>>r; search(1); return 0; } void search(int k) { if(k==r+1)//已经筛选出 1-r 位的数 { print(); } for(int i=1;i<=n;i++)//枚举 1-n { if(!f[i]&&i>a[k-1])//该元素要比前一个大，没有使用过 { a[k]=i;//把 该数放入k位 f[i]=1;//标记该数用过 search(k+1);//搜索下一位 f[i]=0;//还原状态 } } } void print() { for(int i=1;i<=r;i++) { cout<<setw(3)<<a[i]; } cout<<endl; }

2、自然数的拆分

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

当n=7共14种拆分方法：

7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4 total=14 输入n。

按字典序输出具体的方案。

7 7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4

#include<iostream> #include<iomanip> #include<cstring> using namespace std; int a[10000]={1}; int n; void print(int); void search(int,int); int main() { cin>>n; search(n,1); return 0; } void search(int s,int t) { for(int i=a[t-1];i<=s;i++)//当前数要大于等于前一位数，所以每次从前一位数开始枚举，要小于等于当前未拆分的 { if(i<n)//i要小于n { a[t]=i; s-=i; if(s==0)print(t);//剩余未拆分的==0，说明一种方案完成 else search(s,t+1);//否则继续拆分 s+=i;//还原状态 } } } void print(int t) { cout<<n<<"="; for(int i=1;i<=t-1;i++) { cout<<a[i]<<"+"; } cout<<a[t]<<endl; }