阅读程序-递推与递归
阅读程序
注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。
第5节：递推与递归
第1题【NOIP】2008
#include<iostream>
using namespace std;
void foo(int a, int b, int c)
{
if(a > b)
foo(c, a, b);
else
cout<<a<<','<<b<<','<<c<<endl;
}
int main()
{
int a, b, c;
cin >> a >> b >> c;
foo(a, b, c);
return 0;
}
●判断题
(1)该程序只输出一行
{{ select(1-1) }}
- 正确
- 错误
(2)如果输入的三个数都相同，程序会运行错误。
{{ select(1-2) }}
- 正确
- 错误
(3)如果输入3 1 2,输出2,3,1.
{{ select(1-3) }}
- 正确
- 错误
(4)如果输入3 2 1.程序会超时
{{ select(1-4) }}
- 正确
- 错误
●选择题
(5)输入9108,输出为()。
{{ select(1-5) }}
- 9,10,8
- 9,8,10
- 10,8,9
- 8,9,10
(6)令n代表输入变量a、b,c的次数，则n=3该程序的时间复杂度为( )。
{{ select(1-6) }}
- O(n)
- O(logn)
第2题【NOIP】2008
#include<iostream>
using namespace std;
void f(int a, int b, int c)
{
cout << a << b << c << ‘/’;
if(a == 3 && b == 2 && c == 1)
return;
if(b < c)
f(a, c, b);
else if(a < b)
{
if(a < c)
f(c, a, b);
else
f(b, c, a);
}
}
int main()
{
int a, b, c;
cin >> a >> b >> c;
f(a, b, c);
cout << endl;
return 0;
}
●判断题 (1)程序可能没有输出。
{{ select(2-1) }}
- 正确
- 错误
(2)程序可能会死循环。
{{ select(2-2) }}
- 正确
- 错误
(3)输入10 10 10程序会运行错误。
{{ select(2-3) }}
- 正确
- 错误
(4)输入258 114514 1919810程序会运行错误。
{{ select(2-4) }}
- 正确
- 错误
●选择题
(5)如果n=3代表输人变量个数n=3,那么该程序时间复杂度是( )。
{{ select(2-5) }}
- O()
- O(n!)
- O()
- O()
(6)如果输入132,则输出是()。
{{ select(2-6) }}
- 132/213/231/321/312/
- 132/213/231/312/321/
- 213/132/231/321/312/
- 213/132/231/312/321/
第3题【NOIP】2014
#include <iostream>
using namespace std;
int fun(int n) {
if(n == 1)return 1;
if(n == 2)return 2;
return fun(n -2) - fun(n - 1);
}
int main() {
int n;
cin >> n;
cout << fun(n) << endl;
return 0;
}
●判断题
(1)输入114514时在普通计算机上程序运行时间不会超过1s。
{{ select(3-1) }}
- 正确
- 错误
(2)输入0程序不会出现运行错误。
{{ select(3-2) }}
- 正确
- 错误
(3)该程序开启O2不会出现错误。
{{ select(3-3) }}
- 正确
- 错误
(4)输入6,输出7。
{{ select(3-4) }}
- 正确
- 错误
●选择题
(5)时间复杂度为( )
{{ select(3-5) }}
- O()
- O()
- O()
- O(n)
(6)输人7时输出( )。
{{ select(3-6) }}
- -11
- 11
- -10
- 10
第4题【NOIP】2010
#include <iostream>
using namespace std;
const int NUM = 5;
int r(int n)
{
int i;
if (n <= NUM)
return n;
for (i = 1; i <= NUM; i++)
if (r(n - i) < 0)
return i;
return -1;
}
int main()
{
int n;
cin>>n;
cout<<r(n)<<endl;
return 0;
}
●判断题
(1)将第4行的int改为unsigned,答案不会错误。
{{ select(4-1) }}
- 正确
- 错误
(2)程序开启O2优化不会返回错误。
{{ select(4-2) }}
- 正确
- 错误
(3)如果输入-1,程序会输出-1。
{{ select(4-3) }}
- 正确
- 错误
(4)该问题r(n)的值没有规律。
{{ select(4-4) }}
- 正确
- 错误
●选择题
(5)如果输入7,程序会输出( )。
{{ select(4-5) }}
- -1
- 5
- 1
- 3
(6)如果输入16,程序会输出()。
{{ select(4-6) }}
- 16
- -1
- 4
- 1
第5题【NOIP】2011
#include<iostream>
using namespace std;
int solve(int n,int m){
int i,sum;
if(m==1) return 1;
sum=0;
for(i=1;i<n;i++)
sum+= solve(i,m-1);
return sum;
}
int main(){
int n,m;
cin>>n>>m;
cout<<solve(n,m)<<endl;
return 0;
}
●判断题
(1)将第7行<改成<=程序会出现运行错误。
{{ select(5-1) }}
- 正确
- 错误
(2)本题使用C++98编译不会出现编译错误。
{{ select(5-2) }}
- 正确
- 错误
(3)本题输人0 0不会出现运行错误。
{{ select(5-3) }}
- 正确
- 错误
(4)本题不可能输出0。
{{ select(5-4) }}
- 正确
- 错误
●选择题
(5)如果输人7 4,输出()
{{ select(5-5) }}
- 11
- 20
- 21
- 12
(6)如果输入10 0,输出( )。
{{ select(5-6) }}
- 0
- 1
- 2
- 3
第6题【NOIP】2011
#include<iostream>
using namespace std;
int n;
void f2(int x,int y);
void f1(int x,int y)
{
7 if(x<n)
f2(y,x+y);
}
void f2(int x,int y)
{
cout<<x<<' ';
f1(y,x+y);
}
int main()
{
cin>>n;
f1(0,1);
return 0;
}
●判断题
(1)把04行删除，程序不会出现编译错误。
{{ select(6-1) }}
- 正确
- 错误
(2)输入为10,输出为125。
{{ select(6-2) }}
- 正确
- 错误
(3)把07行的“x<n”改为“x<=n”,程序运行结果会出现改变。
{{ select(6-3) }}
- 正确
- 错误
(4)该程序的时间复杂度为O(n)。
{{ select(6-4) }}
- 正确
- 错误
●选择题
(5)输入为35时，输出为()。
{{ select(6-5) }}
- 1 2 5 13 34
- 1 2 5 13
- 1 2 13
- 2 5 13 (6)输出为1 2 5时，n的值可以为
{{ select(6-6) }}
- 3
- 5
- 9
- 11
第7题【NOIP】2015
#include <iostream>
using namespace std;
int fun(int n, int fromPos, int toPos) {
int t, tot;
if (n == 0)return 0;
for (t = 1; t <= 3; t++)
if (t != fromPos && t != toPos)break;
tot = 0;
09 tot += fun(n - 1, fromPos, t);
tot++;
11 tot += fun(n - 1, t, toPos);
return tot;
}
int main() {
int n;
cin >> n;
cout << fun(n, 1, 3) << endl;
return 0;
}
●判断题
(1)当n为小于1000的正整数时，将第9行和第11行一起去掉，程序输出结果为1。
{{ select(7-1) }}
- 正确
- 错误
(2)当n为小于1000的正整数时，将第9行或第11行中其中一行去掉，程序输出n。()
{{ select(7-2) }}
- 正确
- 错误
(3)函数中的fromPos与toPos与答案无关。
{{ select(7-3) }}
- 正确
- 错误
(4)该程序的时间复杂度为O()。
{{ select(7-4) }}
- 正确
- 错误
●选择题
5)fun(5,1,3)的值为()。
{{ select(7-5) }}
- 31
- 23
- 66
- 9
(6)fun(n,1,3)的通项公式为()
{{ select(7-6) }}
- fun(n-1,1.3)*2+1
- 2*n
- -1
- $((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)/\sqrt{5}$
第8题【NOIP】2017
#include<iostream>
using namespace std;
int g(int m, int n, int x){
4 int ans = 0;
5 int i;
6 if (n == 1)
return 1;
for (i = x; i <= m / n; i++)
ans += g(m - i, n - 1, i);
return ans;
}
int main(){
int t, m, n;
cin >> m >> n;
cout << g(m, n, 0) << endl;
return 0;
}
●判断题
(1)把第6行去掉，程序总会输出1。
{{ select(8-1) }}
- 正确
- 错误
(2)将第4行的内容接在第2行的后面，程序输出与原样不同。
{{ select(8-2) }}
- 正确
- 错误
(3)把第5行去掉，程序会编译错误。
{{ select(8-3) }}
- 正确
- 错误
(4)此程序的动能是求将m个无序物品无序地分成n份的方案数
{{ select(8-4) }}
- 正确
- 错误
●选择题
(5)输入7 3,则输出( )。
{{ select(8-5) }}
- 2
- 4
- 6
- 8
(6)输人5 5,则输出()
{{ select(8-6) }}
- 1
- 3
- 5
- 7
第9题【NOIP】2018
#include <iostream>
using namespace std;
int n, m;
int findans(int n, int m) {
if (n == 0) return m;
if (m == 0) return n % 3;
return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);
}
int main(){
cin >> n >> m;
cout << findans(n, m) << endl;
return 0;
}
●判断题
(1)将第5行和第6行一起去掉，程序会出现死循环。
{{ select(9-1) }}
- 正确
- 错误
(2)当输人的n,m的绝对值在1000以内时，程序一定会正常运行。
{{ select(9-2) }}
- 正确
- 错误
(3)若将该递归程序执行记忆化，则程序的时间复杂度为O(nm)。
{{ select(9-3) }}
- 正确
- 错误
(4)将第3行接在第9行后，则程序会编译错误。
{{ select(9-4) }}
- 正确
- 错误
●选择题
(5)输入5 6,则输出为()。
{{ select(9-5) }}
- 5
- 6
- 7
- 8
(6)输人2 4,则输出为()
{{ select(9-6) }}
- 5
- 6
- 7
- 8
(7)如果代码进行记忆化优化后，输入998 998，则输出（）
{{ select(9-7) }}
- 998
- 1569
- 1000
- 1325
第10题【NOIP】2014
#include <iostream>
using namespace std;
int fun( int n, int minNum, int maxNum ){
int tot, i;
if ( n == 0 )return 1;
tot = 0;
for ( i = minNum; i <= maxNum; i++ )
tot += fun( n - 1, i + 1, maxNum );
return(tot);
}
int main(){
int m;
scanf( "%d", &m );
printf( "%d\n", fun( m, 1, n ) );
return(0);
}
●判断题
(1)将第5行删掉，程序编译错误。
{{ select(10-1) }}
- 正确
- 错误
(2)当输入的n的绝对值在1000以内时，程序不一定能正常运行
{{ select(10-2) }}
- 正确
- 错误
(3)将第4行的内容接在第2行后，程序输出与原样不同
{{ select(10-3) }}
- 正确
- 错误
(4)将第4行的内容去掉，程序推会运行错误。
{{ select(10-4) }}
- 正确
- 错误
●选择题
(5)fun(2,1,6)的值为( )
{{ select(10-5) }}
- 15
- 10
- 6
- 3
(6)fun(3,1,6)的值为( )
{{ select(10-6) }}
- 20
- 10
- 4
- 1