阅读程序

注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。

第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)该程序只输出一行

A. 正确 B. 错误

(2)如果输入的三个数都相同，程序会运行错误。

A. 正确 B. 错误

(3)如果输入3 1 2,输出2,3,1.

A. 正确 B. 错误

(4)如果输入3 2 1.程序会超时

A. 正确 B. 错误

●选择题

(5)输入9108,输出为()。

A. 9,10,8 B. 9,8,10 C. 10,8,9 D. 8,9,10

(6)令n代表输入变量a、b,c的次数，则n=3该程序的时间复杂度为( )。

A. O(n) B. O(logn) C. $O(\sqrt{logn})$ D. $O(log(n\sqrt{n}))$

第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)程序可能没有输出。

A. 正确 B. 错误

(2)程序可能会死循环。

A. 正确 B. 错误

(3)输入10 10 10程序会运行错误。

A. 正确 B. 错误

(4)输入258 114514 1919810程序会运行错误。

A. 正确 B. 错误

●选择题

(5)如果n=3代表输人变量个数n=3,那么该程序时间复杂度是( )。

A. O($2^n$) B. O(n!) C. O($n^2$) D. O($n^n$)

(6)如果输入132,则输出是()。

A. 132/213/231/321/312/ B. 132/213/231/312/321/ C. 213/132/231/321/312/ D. 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。

A. 正确 B. 错误

(2)输入0程序不会出现运行错误。

A. 正确 B. 错误

(3)该程序开启O2不会出现错误。

A. 正确 B. 错误

(4)输入6,输出7。

A. 正确 B. 错误

●选择题

(5)时间复杂度为( )

A. O($2^n$) B. O($n^n$) C. O($n^{logn}$) D. O(n)

(6)输人7时输出( )。

A. -11 B. 11 C. -10 D. 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,答案不会错误。

A. 正确 B. 错误

(2)程序开启O2优化不会返回错误。

A. 正确 B. 错误

(3)如果输入-1,程序会输出-1。

A. 正确 B. 错误

(4)该问题r(n)的值没有规律。

A. 正确 B. 错误

●选择题

(5)如果输入7,程序会输出( )。

A. -1 B. 5 C. 1 D. 3

(6)如果输入16,程序会输出()。

A. 16 B. -1 C. 4 D. 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行<改成<=程序会出现运行错误。

A. 正确 B. 错误

(2)本题使用C++98编译不会出现编译错误。

A. 正确 B. 错误

(3)本题输人0 0不会出现运行错误。

A. 正确 B. 错误

(4)本题不可能输出0。

A. 正确 B. 错误

●选择题

(5)如果输人7 4,输出()

A. 11 B. 20 C. 21 D. 12

(6)如果输入10 0,输出( )。

A. 0 B. 1 C. 2 D. 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行删除，程序不会出现编译错误。

A. 正确 B. 错误

(2)输入为10,输出为125。

A. 正确 B. 错误

(3)把07行的“x<n”改为“x<=n”,程序运行结果会出现改变。

A. 正确 B. 错误

(4)该程序的时间复杂度为O(n)。

A. 正确 B. 错误

●选择题

(5)输入为35时，输出为()。

A. 1 2 5 13 34 B. 1 2 5 13 C. 1 2 13 D. 2 5 13 (6)输出为1 2 5时，n的值可以为

A. 3 B. 5 C. 9 D. 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。

A. 正确 B. 错误

(2)当n为小于1000的正整数时，将第9行或第11行中其中一行去掉，程序输出n。()

A. 正确 B. 错误

(3)函数中的fromPos与toPos与答案无关。

A. 正确 B. 错误

(4)该程序的时间复杂度为O($2^n$)。

A. 正确 B. 错误

●选择题

5)fun(5,1,3)的值为()。

A. 31 B. 23 C. 66 D. 9

(6)fun(n,1,3)的通项公式为()

A. fun(n-1,1.3)*2+1 B. 2*n C. $2^n$-1 D. $((\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。

A. 正确 B. 错误

(2)将第4行的内容接在第2行的后面，程序输出与原样不同。

A. 正确 B. 错误

(3)把第5行去掉，程序会编译错误。

A. 正确 B. 错误

(4)此程序的动能是求将m个无序物品无序地分成n份的方案数

A. 正确 B. 错误

●选择题

(5)输入7 3,则输出( )。

A. 2 B. 4 C. 6 D. 8

(6)输人5 5,则输出()

A. 1 B. 3 C. 5 D. 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行一起去掉，程序会出现死循环。

A. 正确 B. 错误

(2)当输人的n,m的绝对值在1000以内时，程序一定会正常运行。

A. 正确 B. 错误

(3)若将该递归程序执行记忆化，则程序的时间复杂度为O(nm)。

A. 正确 B. 错误

(4)将第3行接在第9行后，则程序会编译错误。

A. 正确 B. 错误

●选择题

(5)输入5 6,则输出为()。

A. 5 B. 6 C. 7 D. 8

(6)输人2 4,则输出为()

A. 5 B. 6 C. 7 D. 8

(7)如果代码进行记忆化优化后，输入998 998，则输出（）

A. 998 B. 1569 C. 1000 D. 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行删掉，程序编译错误。

A. 正确 B. 错误

(2)当输入的n的绝对值在1000以内时，程序不一定能正常运行

A. 正确 B. 错误

(3)将第4行的内容接在第2行后，程序输出与原样不同

A. 正确 B. 错误

(4)将第4行的内容去掉，程序推会运行错误。

A. 正确 B. 错误

●选择题

(5)fun(2,1,6)的值为( )

A. 15 B. 10 C. 6 D. 3

(6)fun(3,1,6)的值为( )

A. 20 B. 10 C. 4 D. 1