例题讲解: P1028 数的计算
我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:
- 不作任何处理;
- 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
- 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
递归实现:(虽然会超时)
int append(int n)
{
int sum = 0;
if (n == 1)
return 1;
for ( int i = 1; i <= n/2; i++)
sum += append(i);
return sum + 1;
}递归的执行过程:
红色箭头 是递推阶段
绿色箭头 是回溯阶段.
如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。
尾递归:
int ans;
void append(int n)
{
ans++;
if (n == 1)
return 1;
for ( int i = 1; i <= n/2; i++)
append(i);
}
void append(int n, int *ans)
{
*ans++;
if (n == 1)
return;
for ( int i = 1; i <= n/2; i++)
append(i, ans);
}
示例代码:
#include <bits/stdc++.h>
using namespace std;
int append1(int n)
{
int sum = 0;
if (n == 1)
return 1;
for ( int i = 1; i <= n/2; i++)
sum += append1(i);
return sum + 1;
}
int ans;
void append2(int n)
{
ans++;
if(n==1)
return;
for(int i = 1; i <=n/2; i++)
append2(i);
}
void append3(int n, int *cnt)
{
(*cnt)++;
if (n == 1)
return;
for ( int i = 1; i <= n/2; i++)
append3(i, cnt);
}
int main()
{
printf("append1: %d\n", append1(6));
append2(6);
printf("append2: %d\n", ans);
int cnt = 0;
append3(6, &cnt);
printf("append3: %d\n", cnt);
}避免超时: 递归—> 递推
我的直接理解就是把append函数变成数组.
其他复杂的递归,就只能模拟栈的操作了.
改成递归的过程其实就是回溯的过程的实现.
#include <cstdio>
using namespace std;
//递推
int a[1005] = {0,};
int main()
{
int n;
scanf("%d", &n);
a[0] = 0;
a[1] = 1;
for (int i = 2; i<=n; i++) {
a[i] += 1;
for(int j = 0; j <= i/2; j++) {
a[i] += a[j];
}
}
printf("%d", a[n]);
return 0;
}
….
P1036 选数
已知n个整数以及1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。可得全部的组合与它们的和为. 现在，要求你计算出和为素数共有多少种。
- 因为是求组合, 不是排列. 所以依次选中就可以了. 依次就是每次都在当前的后面进行选取. 所以递归函数需要一个记录当前选择的位置的参数.
- 和sum可以作为参数放入递归函数中, 也可以作为函数中的变量. 范围变量时, 就需要回溯 – 恢复现场.
#include <cstdio>
#include <cmath>
using namespace std;
int n, k, x[22];
int cnt = 0;
int sum = 0;
int isPrime(int a)
{
int m = sqrt(a);
if(a == 1)
return 0;
if(a==2 || a==3)
return 1;
for (int i = 2; i <=m; i++) {
if(a%i == 0)
return 0;
}
return 1;
}
int find(int start, int m)
{
if(m == 0) {
if(isPrime(sum)) {
// printf("is prime\n");
cnt++;
}
return 0;
}
for(int i = start; i<=n-m+1; i++){
sum +=x[i];
//printf("sum=%d + x[%d]=%d\n", sum, i, x[i]);
find(i+1, m-1);
sum -=x[i];
//printf("sum=%d - x[%d]=%d\n", sum, i, x[i]);
}
return 1;
}
int main()
{
scanf("%d %d", &n, &k);
for(int i =1; i <=n; i++)
{
scanf("%d", &x[i]);
}
find(1, k);
printf("%d", cnt);
return 0;
}- 把sum放入参数中, 避免了回溯
#include <cstdio>
#include <cmath>
using namespace std;
int n, k, x[22];
int cnt = 0;
int isPrime(int a)
{
int m = sqrt(a);
if(a == 1)
return 0;
if(a==2 || a==3)
return 1;
for (int i = 2; i <=m; i++) {
if(a%i == 0)
return 0;
}
return 1;
}
int find(int start, int m, int sum)
{
if(m == 0) {
if(isPrime(sum)) {
// printf("is prime\n");
cnt++;
}
return 0;
}
for(int i = start; i<=n-m+1; i++){
//printf("sum=%d + x[%d]=%d\n", sum, i, x[i]);
find(i+1, m-1, sum + x[i]);
}
return 1;
}
int main()
{
scanf("%d %d", &n, &k);
for(int i =1; i <=n; i++)
{
scanf("%d", &x[i]);
}
find(1, k, 0);
printf("%d", cnt);
return 0;
}