admin管理员组

文章数量:829186

计导 递归函数例题

练习1 求任意正整数的逆置数
方法一:

#include<bits/stdc++.h>
using namespace std;
int length(int n)//递归函数求任意正整数的位数
{if (n / 10 == 0)return 1;else return 1 + length(n / 10);
}
int reverse(int n,int len)//将除最高位之外的数先逆置
{int highBit, restNum;if (len == 1)return n;else{highBit = n / pow(10, len - 1);restNum = n % (int)pow(10, len - 1);return highBit + reverse(restNum, len - 1)*10;}
}
int reverse2(int n,int len)//将除最低位之外的数先逆置
{int lowBit, restNum;if (len == 1)return n;else{lowBit = n % 10;restNum = n/10;return lowBit*pow(10,len-1) + reverse(restNum, len - 1);}
}
int main()
{int n;cin >> n;int len = length(n);cout << reverse(n,len) << endl;return 0;
}

方法二:

#include<bits/stdc++.h>
using namespace std;
void printDigit(int n)
{cout << n % 10;if (n >= 10)printDigit(n / 10);
}
int main()
{int n;cin >> n;printDigit(n);return 0;
}

练习2 输入n个整数,求最大数

#include<bits/stdc++.h>
using namespace std;
int findMax(int n)
{int max,num;if (n == 1){cin >> num;return num;}else{max = findMax(n - 1);//记录前n-1个数中的最大值cin >> num;//读取第n个数numreturn num > max ? num : max;//计算并返回num和max之间的最大值}
}
int main()
{int n;cin >> n;cout << findMax(n);return 0;
}

练习3 输入任意个整数,以-1结束,求最大数
递推过程:

  1. 在函数中读入任意数curr_num
  2. 不断地递归调用函数,将本次读入的curr_num作为函数调用的参数
  3. 直到读入-1;即为递归的结束条件,此时函数返回当前的最大值,即为:curr_num

回归过程:
上一个数preNum与返回的最大值进行比较,确定当前的最大值max,并返回到上一层的函数调用。

#include<bits/stdc++.h>
using namespace std;
int findMax(int preNum)//参数为上一层读入的数
{int max;//当前的最大值int curr_num;cin >> curr_num;//当前层读入的任意数if (curr_num== -1){return preNum;}//结束标志else//递归调用,得到后续数列中的最大值{max = findMax(curr_num);return preNum > max ? preNum : max;//比较确定当前的最大值}
}
int main()
{int firstNum;cin >> firstNum;//输入第一个数cout << findMax(firstNum);return 0;
}

练习4 汉诺塔问题(经典递归问题)

#include<bits/stdc++.h>
using namespace std;
void move(char a, char b)//直接移动盘子函数
{static int i;//每次调用move函数后,该静态变量的值一直保持到其所在的函数下一次被调用。以此记录步骤数i++;cout << i<<": "<<a << "→" << b << endl;
}
void honio(int n,char a,char b,char c)
{if (n == 1)move(a, c);else{honio(n - 1, a, c, b);//将A柱上的n-1个盘子,借助C柱移到B柱move(a, c);//将最大的一个盘子直接由A柱移到C柱honio(n - 1,b, a, c);//再将B柱上的n-1个盘子借助A柱移到C柱}
}
int main()
{int n;cin >> n;//输入盘子数honio(n,'A','B','C');return 0;
}

C. 实验6_7_最大公约数
题目描述
问题描述:
设计递归函数int GCD(int a,int b);计算正整数a和b的最大公约数并返回。如GCD(32,48)为16。
GCD(a,b)递归定义为:
GCD(a,b)=GCD(b,a MOD b) | a MOD b≠0
GCD(a,b)=b | a MOD b=0
输入与输出要求:
输入两个正整数a和b,输出两数的最大公约数数,占一行。
程序运行效果:
Sample 1:
32 48↙
16↙
Sample 2:
8 12↙
4↙

#include<bits/stdc++.h>
using namespace std;
int GCD(int a, int b)
{if (a%b != 0)return GCD(b, a%b);else return b;
}
int main()
{int a, b;cin >> a >> b;cout << GCD(a, b);return 0;
}

D. 实验6_9_素数分解
题目描述
问题描述:
设计递归函数void recurPrintFactor(int n,…);打印出对n进行素数分解的结果。当执行recurPrintFactor(60)时,打印效果为:60=2235。在函数的参数中“…”代表你可以添加参数。并且也可使用全局变量。关于素数分解的描述,见实验五第14题。
设计程序,已知一段数据范围[a,b],且a<=b,要求对其中的每一个数进行素数分解。你也可以设计其它辅助函数,如判断素数的函数isPrime(n)。
输入与输出要求:
输入两个正整数a、b,代表所分解的区间,满足1<=a<=b<=100000,且b-a<=100。输出b-a+1行,即b-a+1个数的分解。
程序运行效果:
Sample 1:
100 105↙
100=2
255↙
101=101↙
102=2317↙
103=103↙
104=22213↙
105=3
57↙
Sample 2:
9999 10005↙
9999=3
311101↙
10000=22225555↙
10001=73
137↙
10002=231667↙
10003=71429↙
10004=2
24161↙
10005=3523*29↙
方法一(利用break退出递归):

#include<iostream>
#include<cmath>
using namespace std;
//bool finish = false;
int isPrime(int n)
{for (int i = 2; i <= sqrt(n); i++){if (n%i == 0)return 0;}return 1;
}
void recurPrintFactor(int n)
{if (isPrime(n)){cout << n << endl;//finish = true;return;//只能返回到上一次递归的地方,return后遇到break,一层层退出直到最外层}else{int i = 2;while (i <= n / 2){if (isPrime(i))//&&!finish{if (n%i == 0){cout << i << "*";recurPrintFactor(n / i);break;//退出while循环}else i++;}else i++;}}
}
int main()
{int a,b;cin >> a>>b;for (int i = a; i <= b; i++){//finish = false;cout << i << "=";recurPrintFactor(i);}return 0;
}

方法二(用全局变量退出递归)

#include<iostream>
#include<cmath>
using namespace std;
bool finish = true;//利用全局变量退出递归
int isPrime(int n)
{for (int i = 2; i <= sqrt(n); i++){if (n%i == 0)return 0;}return 1;
}
void recurPrintFactor(int n)
{if (isPrime(n)){cout << n << endl;finish = false;}else{int i = 2;while (i <= n / 2){if (isPrime(i) && finish){if (n%i == 0){cout << i << "*";recurPrintFactor(n / i);}else i++;}else i++;}}
}
int main()
{int a,b;cin >> a>>b;for (int i = a; i <= b; i++){finish = true;cout << i << "=";recurPrintFactor(i);}return 0;
}

int convert(int n)
{if (n == 0 || n == 1)return n;else return n % 10 + convert(n / 10) * 2;
}

本文标签: 计导 递归函数例题