首页 › 题库 › 信息学奥赛 › 4 函数与结构体

信息学奥赛-入门级 题库

共 101 道题 ,第 4 / 6 页 · 按题型筛选,点「查看答案」核对解析
章节 4 函数与结构体 清除
61 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

(切割绳子)有n条绳子,每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割,但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段,求绳段的最大长度是多少。(第一、二空2.5分,其余3分)

输入:第一行是一个不超过100的正整数n,第二行是n个不超过106的正整数,表示每条绳子的长度,第三行是一个不超过108的正整数m。

输出:绳段的最大长度,若无法切割,输出Failed。


#include <iostream>

using namespace std;


int n, m, i, lbound, ubound, mid, count;

int len[100];   // 绳子长度

int main() {

cin >> n;

count = 0;

for (i = 0; i < n; i++) {

cin >> len[i];

                        (1)        ;

}

cin >> m;

if (    (2)    ) {

cout << "Failed" << endl;

return 0;

}

lbound = 1;

ubound = 1000000;

while (    (3)   ) {

mid =     (4)    ;

count = 0;

for (i = 0; i < n; i++)

                               (5)     ;

if (count < m)

ubound = mid - 1;

else

lbound = mid;

}

cout << lbound << endl;

return 0;

}

答案与解析
参考答案

(1)count=count+len[i] 或 count+=len[i]

(2)count<m 或 m>count

(3)lbound<ubound 或 ubound>lbound

(4)(lbound+ubound+1)/2 或 (lbound+ubound+1)>>1 或 (lbound+ubound)/2+1

(5)count=count+len[i]/mid 或 count+=len[i]/mid

题目详情
62 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

(读入整数)请完善下面的程序,使得程序能够读入两个int范围内的整数,并将这两个整数分别输出,每行一个。(第一、五空2.5分,其余 3 分)

输入的整数之间和前后只会出现空格或者回车。 输入数据保证合法。 例如:

输入:

123-789


输出:

123
-789



#include <iostream>

using namespace std;


int readint() {

int num = 0;   // 存储读取到的整数

int negative = 0;  // 负数标识

char c;// 存储当前读取到的字符

c = cin.get();

while ((c < '0' || c > '9') && c != '-')

c =    (1)    ;

if (c == '-')

negative = 1;

else

               (2)       ;

c = cin.get();

while (   (3)   ) {

          (4)    ;

c = cin.get();

}

if (negative == 1)

            (5)      ;

return num;

}


int main() {

int a, b;

a = readint();

b = readint();

cout << a << endl << b << endl;

return 0;

}

答案与解析
参考答案

(1)cin.get()

(2)num=c-'0' 或 num=c-48

(3)c>='0'&&c<='9' 或 c>=48&&c<=57

(4)num=num*10+c-'0' 或 num=num*10+c-48

(5)num=-num 或 return -num

题目详情
63 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

(郊游活动)有n名同学参加学校组织的郊游活动,已知学校给这n名同学 的郊游总经费为A元,与此同时第 i 位同学自己携带了Mi元。为了方便郊游, 活动地点提供B(≥n)辆自行车供人租用,租用第j 辆自行车的价格为Cj元, 每位同学可以使用自己携带的钱或者学校的郊游经费,为了方便账务管 理,每位同学只能为自己租用自行车, 且不会借钱给他人, 他们想知道最多 有多少位同学能够租用到自行车。(第四、五空2.5分,其余3分)

本题采用二分法。对于区间[l, r] ,我们取中间点mid并判断租用到自行车的人数能否达到mid。判断的过程是利用贪心算法实现的。


#include <iostream>

using namespace std;

#define MAXN 1000000


int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;


bool check(int nn) {

int count = 0, i, j;

i =     (1)     ;

j = 1;

while (i <= n) {

if (       (2)     )

count += C[j] - M[i];

i++;

j++;

}

return      (3)     ;

}


void sort(int a[], int l, int r) {

int i = l, j = r, x = a[(l + r) / 2], y;

while (i <= j) {

while (a[i] < x) i++;

while (a[j] > x) j--;

if (i <= j) {

y = a[i]; a[i] = a[j]; a[j] = y;

i++; j--;

}

}

if (i < r) sort(a, i, r);

if (l < j) sort(a, l, j);

}


int main() {

int i;

cin >> n >> B >> A;

for (i = 1; i <= n; i++)

cin >> M[i];

for (i = 1; i <= B; i++)

cin >> C[i];

sort(M, 1, n);

sort(C, 1, B);

l = 0;

r = n;

while (l <= r) {

mid = (l + r) / 2;

if (   (4)   ) {

ans = mid;

l = mid + 1;

} else

r =   (5)    ;

}

cout << ans << endl;

return 0;

}

答案与解析
参考答案

(1)n-nn+1

(2)M[i]<C[j] 或 M[i]<=C[j]

(3)count<=A

(4)check(mid)

(5)mid-1

题目详情
64 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用
#include <iostream>

using namespace std;

struct point
	{
		int x;
		int y;
	};

int main()
	{
		int a, b, c;
		struct EX
			{
				int a;
				int b;
				point c;
			}e;
	e.a = 1;
	e.b = 2;
	e.c.x = e.a + e.b;
	e.c.y = e.a * e.b;
	cout << e.c.x << ',' << e.c.y << endl;
	return 0;
}

输出:                       

答案与解析
参考答案

3,2 

题目详情
65 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用
#include <iostream>
#include <string>

using namespace std;

void fun(char *a, char *b)
	{
		a = b;
		(*a)++;
	}

int main()
	{
		char c1, c2, *p1, *p2;
		c1 = 'A';
		c2 = 'a';
		p1 = &c1;
		p2 = &c2;
		fun(p1, p2);
		cout << c1 << c2 << endl;
		return 0;
	}

输出:              

答案与解析
参考答案

Ab

题目详情
66 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

完善程序: (打印月历)输入月份 m(1≤m≤12),按一定格式打印 2015 年第 m 月的月历。 (第三、四空 2.5 分,其余 3 分)

例如,2015 年 1 月的月历打印效果如下(第一列为周日):


#include <iostream>

#include <string>


using namespace std;


const int dayNum[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int m, offset, i;


int main()

{

cin >> m;

cout << "S\tM\tT\tW\tT\tF\tS" << endl;  //'\t'为 TAB 制表符

                         ⑴        ;

for(i = 1; i < m; i++)

offset =      ⑵      ;

for(i = 0; i < offset; i++)

cout << '\t';

for(i = 1; i <=     ⑶     ; i++)

{

cout <<    ⑷    ;

if(i == dayNum[m] ||    ⑸   == 0)

cout << endl;

else

cout << '\t';

}

return 0;

}

答案与解析
参考答案

⑴offset = 4

⑵(offset + dayNum[i]) % 7

⑶dayNum[m]

⑷i

⑸(offset + i) % 7

题目详情
67 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

完善程序:(中位数 median)给定 n(n 为奇数且小于 1000)个整数, 整数的范围在 0~m(0<m<2^31)之间, 请使 用二分法求这 n 个整数的中位数。所谓中位数,是指将这 n 个数排序之后,排在正中间的数。 (第五空 2分,其余 3 分)

#include <iostream>


using namespace std;


const int MAXN = 1000;

int n, i, lbound, rbound, mid, m, count;

int x[MAXN];


int main()

{

cin >> n >> m;

for(i = 0; i < n; i++)

cin >> x[i];

lbound = 0;

rbound = m;

while(       ⑴          )

{

mid = (lbound + rbound) / 2;

                             ⑵       ;

for(i = 0; i < n; i++)

if(     ⑶       )

                                                 ⑷       ;

if(count > n / 2)

lbound = mid + 1;

else

                                       ⑸        ;

cout << mid << " " << lbound << " " << rbound << " " << count << endl;

}

cout << rbound << endl;

return 0;

}

答案与解析
参考答案

⑴lbound <= rbound

⑵count = 0

⑶x[i] >= mid

⑷count++

⑸rbound = mid - 1

题目详情
68 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

完善程序:(数字删除)下面程序的功能是将字符串中的数字字符删除后输出。请填空。(每空3分, 共12分)


#include <iostream>

using namespace std;


int delnum(char *s) {

int i, j;

j = 0;

for (i = 0; s[i] != '\0'; i++)

if (s[i] < '0'    (1)     s[i] > '9') {

s[j] = s[i];

                      (2)    ;

}

return     (3)    ;

}


const int SIZE = 30;


int main() {

char s[SIZE];

int len, i;

cin.getline(s, sizeof(s));

len = delnum(s);

for (i = 0; i < len; i++)

cout <<     (4)    ;

cout << endl;

return 0;

}

答案与解析
参考答案

(1)||

(2)j++ 或 j=j+1 或 ++j

(3)j

(4)s[i]

题目详情
69 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

完善程序:(最大子矩阵和)给出m行n列的整数矩阵,求最大的子矩阵和(子矩阵不能为空)。

输入第一行包含两个整数m和n,即矩阵的行数和列数。之后m行,每行n个整 数,描述整个矩阵。程序最终输出最大的子矩阵和。 (最后一空 4 分, 其余 3 分, 共 16 分)


#include <iostream>

using namespace std;


const int SIZE = 100;

int matrix[SIZE + 1][SIZE + 1];

int rowsum[SIZE + 1][SIZE + 1];   //rowsum[i][j]记录第 i 行前 j 个数的和 int m, n, i, j, first, last, area, ans;


int main() {

cin >> m >> n;

for (i = 1; i <= m; i++)

for (j = 1; j <= n; j++)

cin >> matrix[i][j];

ans = matrix     (1)     ;

for (i = 1; i <= m; i++)

        (2)    ;

for (i = 1; i <= m; i++)

for (j = 1; j <= n; j++)

rowsum[i][j] =     (3)     ;

for (first = 1; first <= n; first++)

for (last = first; last <= n; last++) {

                       (4)    ;

for (i = 1; i <= m; i++) {

area +=     (5)    ;

if (area > ans)

ans = area;

if (area < 0)

area = 0;

}

}

cout << ans << endl;

return 0;

}

答案与解析
参考答案

(1)[1][1]

(2)rowsum[i][0]=0

(3)rowsum[i][j-1]+matrix[i][j]

(4)area=0

(5)rowsum[i][last]-rowsum[i][first-1]

题目详情
70 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

完善程序:(序列重排)全局数组变量a定义如下:

const int SIZE = 100;

int a[SIZE], n;

它记录着一个长度为n的序列a[1],a[2], … , a[n]。

现在需要一个函数,以整数p(1≤p≤n)为参数,实现如下功能:将序列a的前p个数与后n–p个数对调,且不改变这p 个数(或n–p个数)之间的相对位置。例如,长度为5的序列1,2,3,4,5,当p=2 时重排结果为3,4,5,1,2。

有一种朴素的算法可以实现这一需求,其时间复杂度为O(n)、空间复杂度为O(n):


void swap1(int p)

{

int i, j, b[SIZE];


for (i = 1; i <= p; i++)

b[    (1)    ] = a[i];                           //(3 分)

for (i = p + 1; i <= n; i++)

b[i - p] =    (2)     ;                          //(3 分)

for (i = 1; i <=     (3)     ; i++)                //(2 分)

a[i] = b[i];

}


我们也可以用时间换空间,使用时间复杂度为O(n2)、空间复杂度为O(1)的算法:


void swap2(int p)

{


int i, j, temp;


for (i = p + 1; i <= n; i++) {

temp = a[i];

for (j = i; j >=     (4)     ; j--)                   //(3 分)

a[j] = a[j - 1];

     (5)    = temp;                                                    //(3 分)

}

}

答案与解析
参考答案

(1)n – p + i

(2)a[i]

(3)n

(4)i – p + 1

(5)a[i – p]

题目详情
71 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

完善程序:(二叉查找树)二叉查找树具有如下性质:每个节点的值都大于其左子树上所有节点的 值、小于其右子树上所有节点的值。 试判断一棵树是否为二叉查找树。

输入的第一行包含一个整数n,表示这棵树有n个顶点, 编号分别为1,2, … ,n,其 中编号为1的为根结点。之后的第i行有三个数value,left_child,right_child,分别表示 该节点关键字的值、左子节点的编号、右子节点的编号;如果不存在左子节点或右子节 点,则用0代替。输出1表示这棵树是二叉查找树,输出0则表示不是。


#include <iostream>

using namespace std;


const int SIZE = 100;

const int INFINITE = 1000000;


struct node {

int left_child, right_child, value;

};


node a[SIZE];


int is_bst(int root, int lower_bound, int upper_bound)

{

int cur;


if (root == 0)

return 1;

cur = a[root].value;

if ((cur > lower_bound) && (     (1)     ) &&             //(3 分)


(is_bst(a[root].left_child, lower_bound, cur) == 1) && 

(is_bst(    (2)     ,    (3)     ,     (4)     ) == 1))    //(3 分,3 分,3 分)

return 1;

return 0;

}


int main()

{

int i, n;

cin>>n;

for (i = 1; i <= n; i++)

cin>>a[i].value>>a[i].left_child>>a[i].right_child;

cout<<is_bst(    (5)    , -INFINITE, INFINITE)<<endl;    //(2 分) 

return 0;

}

答案与解析
参考答案

(1)cur < upper_bound

(2)a[root].right_child

(3)cur

(4)upper_bound

(5)1

题目详情
72 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

完善程序:坐标统计

输入 n 个整点在平面上的坐标。 对于每个点,可以控制所有位于它左下方的点(即 x 、y 坐标都比它小),它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力,最后输出战斗力最高的点的编号(如果两个点战斗力一样,    输出较大的编号)。


#include<iostream>

using namespace std;


const int SIZE = 100;


intx[SIZE], y[SIZE], f[SIZE];

int n, i,j, max_f, ans;


int main()

{

cin>>n;

for (i = 1; i <= n; i++)

cin>>x[i]>>y[i];

max_f = 0;

for (i = 1; i <= n; i++)

{

f[i] =          ①      ;

for (j = 1; j <= n; j++)


{

if (x[j] < x[i] &&           ②    )

③    

}

if (        ④     )

{

max_f = f[i];

      ⑤      ;

}

}

for (i = 1; i <= n; i++)

cout<<f[i]<<endl;

cout<<ans<<endl;

}

答案与解析
参考答案

①0

②y[j] < y[i](或 y[i] > y[j])

③f[i]++(或++f[i],或 f[i] = f[i] + 1)

④f[i] >= max_f(或 max_f <= f[i],两种答案均必须有等号)

⑤ans = i

题目详情
73 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

完善程序:(排列数)输入两个正整数n, m (1 ≤n ≤20, 1 ≤m ≤n),在 1~n  中任取 m 个数,按字典序从小到大输出所有这样的排列。例如

输入

3 2

输出:


1 2
1 3
2 1
2 3
3 1
3 2


#include<iostream>

#include<cstring>

using namespace std;


const int SIZE = 25;


bool used[SIZE];

int data[SIZE];

int n, m, i,j, k;

bool flag;


int main()

{

cin>>n>>m;

memset(used, false, sizeof(used));

for (i = 1; i <= m; i++)

{

data[i] = i;

used[i] = true;

}

flag = true;

while (flag)

{

for (i = 1; i <= m-1; i++) cout<<data[i]<<" ";

cout<<data[m]<<endl;

flag =             ①             ;

for (i = m; i >= 1; i--)

{

           ②          ;

for (j = data[i]+1; j <= n; j++) if (!used[j])

{

used[j] = true;

data[i] =            ③           ;

flag = true;

break;

}

if (flag)

{

for (k = i+1; k <= m; k++)

for (j = 1; j <=       ④      ; j++) if (!used[j])

{

data[k] = j;

used[j] = true;

break;

}

       ⑤      ;

}

}

}

}

答案与解析
参考答案

①false 0

②used[data[i]] = false

③j

④n

⑤break

题目详情
74 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

(子矩阵)给输入一个n1*m1的矩阵a,和n2*m2的矩阵b,问a中是否存在子矩阵和b相等。

若存在,输出所有子矩阵左上角的坐标:若不存在输出“There isno answer”。


#include<iostream>

using namespace std;


const int SIZE = 50;


int n1,m1,n2,m2,a[SIZE][SIZE],b[SIZE][SIZE];

int main()

{

int i,j,k1,k2;

bool good ,haveAns;


cin>>n1>>m1;

for(i=1;i<=n1;i++)

for(j=1;j<=m1;j++)

cin>>a[i][j];


cin>>n2>>m2;

for(i=1;i<=n2;i++)

for(j=1;j<=m2;j++)

             ①                  

haveAns=false;

for(i=1;i<=n1-n2+1;i++)

for(j=1;j<=                ②         ;j++){

                ③       ;

for(k1=1;k1<=n2;k1++)

for(k2=1;k2<=           ④          ;k2++){

if(a[i+k1-1][j+k2-1]!=b[k1][k2])

good=false;

}

if(good){

cout<<i<<''<<j<<endl;

            ⑤           ;

}

}

if(!haveAns)

cout<<"There is no answer"<<endl;

return 0;

}

答案与解析
参考答案

①  cin>>b[i][j]

②  m1-m2+1

③  good=true

④  m2

⑤  haveAns=true

题目详情
75 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

 (大整数开方) 输入一个正整数n(1≤n≤10100),试用二分法计算它的平方根的整数部分。


#include<iostream>

#include<string>

using namespace std;


const int SIZE=200;

struct hugeint{

int len,num[SIZE];

};

//   其中len表示大整数的位数;num[1]表示个位,num[2]表示十位,以此类推


hugeint times(hugeinta,hugeintb)

//     计算大整数a和b的乘积

{

inti,j;

hugeint ans;

memset(ans.num,0,sizeof(ans.num));

for(i=1;i<=a.len;i++)

for(j=1;j<=b.len;j++)

                                                  ①          +=a.num[i]*b.num[j];

for(i=1;i<=a.len+b.len;i++){

ans.num[i+1]+=ans.num[i]/10;

                                        ②          ;

}

if(ans.num[a.len+b.len]>0)

ans.len=a.len+b.len;

else

ans.len=a.len+b.len-1;

return ans;

}


hugeint add(hugeinta,hugeintb)

//   计算大整数a和b的和

{

inti;

hugeint ans;

memset(ans.num,0,sizeof(ans.num));

if(a.len>b.len)

ans.len=a.len;

else

ans.len=b.len;

for(i=1;i<=ans.len;i++){

ans.num[i]+=             ③          ;

ans.num[i+1]+= ans.num[i]/10;

ans.num[i]%=10;

}

if(ans.num[ans.len+1]>0)

ans.len++;

return ans;

}


hugeint average(hugeinta,hugeintb)

//   计算大整数a和b的平均数的整数部分

{

inti;

hugeint ans;

ans=add(a,b);

for(i=ans.len;i>=2;i--){

ans.num[i-1]+=(          ④          )*10;


ans.num[i]/=2;

}

ans.num[1]/=2;

if(ans.num[ans.len]==0)

ans.len--;

return ans;

}


hugeint plustwo(hugeinta)

//     计算大整数加2之后的结果

{

inti;

hugeint ans;

ans=a;

ans.num[1]+=2;

i=1;

while( (i<=ans.len)&&(ans.num[i]>=10) ){

ans.num[i+1]+=ans.num[i]/10;

ans.num[i]%=10;

i++;

}

if(ans.num[ans.len+1]>0)

                    ⑤          ;

return ans;

}



boolover(hugeinta,hugeintb)

//     若大整数a>b则返回true,否则返回false

{

inti;

if(          ⑥          )


return false;

if( a.len>b.len )

return true;

for(i=a.len;i>=1;i--){

if(a.num[i]<b.num[i])

return false;

if(a.num[i]>b.num[i])

return true;

}

return false;

}


int main()

{

string s;

inti;

hugeint target,left,middle,right;

cin>>s;

memset(target.num,0,sizeof(target.num));

target.len=s.length();

for(i=1;i<=target.len;i++)

target.num[i]=s[target.len-i]-             ⑦          

memset(left.num,0,sizeof(left.num));

left.len=1;

left.num[1]=1;

right=target;

do{

middle=average(left,right);

if(over(          ⑧          ))

right=middle;

else

left=middle;

}while(!over(plustwo(left),right) );

for(i=left.len;i>=1;i--)

cout<<left.num[i];

return 0;

}

答案与解析
参考答案

① ans.num[i+j-1] 

② ans.num[i]%=10 

③ a.num[i]+b.num[i] 

④ ans.num[i] % 2 

⑤ ans.len++ 

⑥ a.len<b.len 

⑦ '0'或 48 

⑧ times(middle,middle),target

题目详情
76 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

01 #include <iostream> 

02 

03 using namespace std; 

04 

05 int main() 

06 { 

07 unsigned short x, y;

08 cin >> x >> y;

09 x = (x | x << 2) & 0x33; 

10 x = (x | x << 1) & 0x55; 

11 y = (y | y << 2) & 0x33; 

12 y = (y | y << 1) & 0x55; 

13 unsigned short z = x | y << 1; 

14 cout << z << endl;

15 return 0;

16 }

假设输入的 x、y 均是不超过 15 的自然数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
77 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

01 #include <algorithm> 

02 #include <iostream> 

03 #include <limits> 

04 

05 using namespace std; 

06 

07 const int MAXN = 105;

08 const int MAXK = 105; 

09 

10 int h[MAXN][MAXK]; 

11 

12 int f(int n, int m) 

13 { 

14 if (m == 1) return n;

15 if (n == 0) return 0;

16 

17 int ret = numeric_limits<int>::max();

18 for (int i = 1; i <= n; i++) 

19 ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1); 

20 return ret;

21 } 

22 

23 int g(int n, int m) 

24 { 

25 for (int i = 1; i <= n; i++) 

26 h[i][1] = i;

27 for (int j = 1; j <= m; j++) 

28 h[0][j] = 0; 

29 

30 for (int i = 1; i <= n; i++) { 

31 for (int j = 2; j <= m; j++) {

32 h[i][j] = numeric_limits<int>::max();

33 for (int k = 1; k <= i; k++)

34 h[i][j] = min(

35 h[i][j],

36 max(h[i - k][j], h[k - 1][j - 1]) + 1); 

37 }

38 }

39 

40 return h[n][m];

41 } 

42 

43 int main() 

44 { 

45 int n, m;

46 cin >> n >> m;

47 cout << f(n, m) << endl << g(n, m) << endl; 

48 return 0;

49 }

假设输入的 n、m 均是不超过 100 的正整数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
78 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

01 #include <iostream> 

02 

03 using namespace std; 

04 

05 int n, k; 

06 

07 int solve1() 

08 { 

09 int l = 0, r = n; 

10 while (l <= r) {

11 int mid = (l + r) / 2; 

12 if (mid * mid <= n) l = mid + 1; 

13 else r = mid - 1; 

14 }

15 return l - 1; 

16 } 

17 

18 double solve2(double x) 

19 { 

20 if (x == 0) return x;

21 for (int i = 0; i < k; i++) 

22 x = (x + n / x) / 2;

23 return x; 

24 } 

25 

26 int main()

27 { 

28 cin >> n >> k;

29 double ans = solve2(solve1());

30 cout << ans << ' ' << (ans * ans == n) << endl; 

31 return 0;

32 }

假设 int 为 32 位有符号整数类型,输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
79 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

(枚举因数)从小到大打印正整数 n 的所有正因数。

试补全枚举程序。

01 #include <bits/stdc++.h> 

02 using namespace std; 

03 

04 int main() { 

05 int n;

06 cin >> n;

07 

08 vector<int> fac;

09 fac.reserve((int)ceil(sqrt(n)));

10 

11 int i;

12 for (i = 1; i * i < n; ++i) { 

13 if (①) { 

14 fac.push_back(i);

15 }

16 }

17 

18 for (int k = 0; k < fac.size(); ++k) { 

19 cout << ② << " "; 

20 }

21 if (③) { 

22 cout << ④ << " "; 

23 }

24 for (int k = fac.size() - 1; k >= 0; --k) { 

25 cout << ⑤ << " "; 

26 }

27 }

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
80 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

(洪水填充)现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下:给定起始像素的位置和待填充的颜色,将起始像素和所有可达的像素(可达的定义:经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同),替换为给定的颜色。

试补全程序。

01 #include <bits/stdc++.h>

02 using namespace std;

03

04 const int ROWS = 8;

05 const int COLS = 8;

06

07 struct Point {

08     int r, c;

09     Point(int r, int c) : r(r), c(c) {}

10 };

11

12 bool is_valid(char image[ROWS][COLS], Point pt,

13     int prev_color, int new_color) {

14     int r = pt.r;

15     int c = pt.c;

16     return (0 <= r && r < ROWS && 0 <= c && c < COLS &&

17     ① && image[r][c] != new_color);

18 }

19

20 void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {

21     queue<Point> queue;

22     queue.push(cur);

23

24     int prev_color = image[cur.r][cur.c];

25     ② ;

26

27     while (!queue.empty()) {

28         Point pt = queue.front();

29         queue.pop();

30

31         Point points[4] = { ③ , Point(pt.r - 1, pt.c),

32         Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};

33         for (auto p : points) {

34             if (is_valid(image, p, prev_color, new_color)) {

35                 ④ ;

36                 ⑤ ;

37             }

38         }

39     }

40 }

41

42 int main() { 

43 char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},

44 {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},

45 {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},

46 {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},

47 {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},

48 {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},

49 {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},

50 {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};

51 

52 Point cur(4, 4); 

53 char new_color = 'y';

54 

55 flood_fill(image, cur, new_color);

56 

57 for (int r = 0; r < ROWS; r++) { 

58 for (int c = 0; c < COLS; c++) { 

59 cout << image[r][c] << " ";

60 }

61 cout << endl;

62 }

63 // 输出:

64 // g g g g g g g g 

65 // g g g g g g r r 

66 // g r r g g r g g 

67 // g y y y y r g r 

68 // g g g y y r g r 

69 // g g g y y y y r 

70 // g g g g g y g g 

71 // g g g g g y y g 

72 

73 return 0;

74 }

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情