NOIP2018初赛复习(7)-阅读程序写结果

网友投稿 2018-08-25 13:54


这部分其实很容易,目的几乎是送分,而且占的分数很多,但得分率却不见得高。很容易不明不白的就把分(全)丢了!!!

这部分程序考3个方面:

1.  程序设计语言本身,如循环、递归、值型参和变量型参数、跟踪变量等;

2.  归纳和数学运算能力;

3.  是否掌握了一些常用算法(程序段)的框架;

4.  细心、耐心等心理品质;灵感+编程的量等;

一般做这类题目的核心是找程序目的:

即这个程序想干什么。迄今为止考过的题目还没有“乱写”的,总有一点“写作目的”的。抓住了它,不仅得出答案变得很容易了,而且对自己的结果也会比较有信心。

一般的解题步骤如下:

1.  从总体上通读程序,大致把握程序的目的和算法;

2.  猜测变量的作用,跟踪主要变量值的变化(列表),找出规律;

3.  将程序分段,理清每一小段的作用和目的(灵感+关键表达式和语句的领会);

4.  看清输入、按照输出格式,写出结果;

5.  带着得到的结果回到程序进行检查;

例题(NOIP2017提高组)

1.

#include

using namespacestd;

int g(int m, intn, int x){

            int ans = 0;

            int i;

            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;

}

输入: 8  4

输出: 15

解析:就是一个简单的递推题,大家只要自己认真的推算一遍即可,一定要找一张干净的草稿纸,然后有条理的写,这样就能很容易的算出来了。博主第一遍就因为很随便,算出的答案是14,后来写完后面的题,回头找老师又要了几张草稿纸,重算一遍,才算正确。

2.

#include

using namespacestd;

int main() {

int n, i, j, x, y, nx, ny;

int a[40][40];

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

     for (j = 0;j< 40; j++)

                 a[i][j]= 0;

cin >> n;

y = 0; x = n-1;

n = 2*n-1;

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

     a[y][x] =i;

     ny = (y-1+n)%n;

     nx = (x+1)%n;

if ((y == 0 && x == n-1) || a[ny][nx] !=0)

          y= y+1;

else {y = ny; x = nx;}

            }

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

                        cout << a[0][j]<< “”;

cout << endl;

return 0;

}

输入: 3

输出: 17 24 1 8 15

解析:就是一个幻方。 
一眼看透本质后就很简单了,只要自己把幻方填上就行。 
这里说一下幻方的定义,就是将1到n*n这些整数填入n*n的方格表,使得每一行、每一列、对角线上的数之和为同一值。 
填的方法也很简单,我在小学时就和我的(女)同学探讨过奇数规模的幻方的填写方法(嗯?奇怪的强调……),具体方法如下:

  • 首先将1写在第一行的中间。

  • 之后,按如下方式从小到大依次填写每个数K(K=2,3,…,N*N):

  • 1.若(K−1)在第一行但不在最后一列,则将K填在最后一行,(K−1)所在列的右一列;

  • 2.若(K−1)在最后一列但不在第一行,则将K填在第一列,(K−1)所在行的上一行;

  • 3.若(K−1)在第一行最后一列,则将K填在(K−1)的正下方;

  • 4.若(K−1)既不在第一行,也不在最后一列,如果(K−1)的右上方还未填数,则将K填在(K−1)的右上方,否则将K填在(K−1)的正下方。

这样就能写出一个幻方了,然后输出第一行即可。 
还有注意,输入虽然是3,但求的是5*5的幻方。

3.

#include

using namespacestd;

int n, s,a[100005], t[100005], i;

void mergesort(intl, int r){

            if (l == r)

                        return;

            int mid = (l + r) / 2;

            int p = l;

            int i = l;

            int j = mid + 1;

            mergesort (l, mid);

            mergesort (mid + 1, r);

            while (i <= mid && j<= r){

                        if (a[j] < a[i]){

                                    s += mid – i+1;

                                    t[p] = a[j];

p++;

j++;

                        }

                        else {

                                    t[p] = a[i];

                                    p++;

i++;

                        }

            }

            while (i <= mid){

                        t[p] = a[i];

                        p++;

                        i++;

            }

            while (j <= r){

                        t[p] = a[j];

                        p++;

                        j++;

            }

            for (i = l; i <= r; i++ )

                        a[i] = t[i];

}

int main() {

cin >> n;

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

     cin>> a[i];

mergesort (1, n);

cout << s << endl;

return 0;

}

输入:

6

2 6 3 4 5 1

输出: 8

解析:一眼看透本质:求逆序对。 
然后就很容易的数出来了。 
但是是怎么看出来本质的呢? 
本题和上一题这样一眼看透本质,有两种方法:1、看算法,是自己熟悉的某个算法,那么恭喜你,你看透了本质。 

4.

#include

using namespacestd;

int main() {

int n, m;

cin >> n >> m;

int x = 1;

int y = 1;

int dx = 1;

int dy = 1;

int cnt = 0;

while (cnt != 2) {

cnt = 0;

x = x + dx;

y = y + dy;

if (x == 1 || x == n) {

++cnt;

dx = -dx;

}

if (y == 1 || y == m) {

++cnt;

dy = -dy;

}

}

cout << x << " " << y<< endl;

return 0;

}

输入1: 4 3

输出1: 1 3  (2 分)

输入2: 2017 1014

输出2: 2017 1 (3 分)

输入3: 987 321

输出3: 1 321 (3分)

解析:很明显第一个空是给我们模拟找规律的,其实模拟一下就能发现规律了,规律就是:

  • 求出输入的两个数的最小公倍数

  • 然后用最小公倍数分别除以两个输入的数

  • 如果结果是单数,则输出的是输入的这个数本身

  • 如果结果是偶数,则输出的是1

  • 注意输出顺序 
    这样就能顺利地写出结果。

--end--

声明:本文章由网友投稿作为教育分享用途,如有侵权原作者可通过邮件及时和我们联系删除:freemanzk@qq.com