NOIP 2018 普及组初赛试题阅读程序解析

2022/9/17 1:17:25

本文主要是介绍NOIP 2018 普及组初赛试题阅读程序解析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

第 18 题

阅读程序写结果:

#include<stdio.h>
char st[100];

int main() {
  scanf("%s", st);//输入一个字符串
  for (int i = 0; st[i]; ++i) {
      if (‘A’ <= st[i] && st[i] <= ‘Z’)//如果是大写字母,执行指令
      st[i] += 1;//往后退一位(如A变成B,B变成C)
  }//是小写字母就照常输出
  printf("%s\n", st);//输出结果
  return 0;
}

 

输入:QuanGuoLianSai

解析:这个程序其实并不难。就是输入一个字符串,大写字母就往后退一位,小写字母照常输出就可以了。具体见代码注释。

答案:RuanHuoMianTai

第 19 题

阅读程序写结果:

#include <stdio.h>
int main() {
   int x;
   scanf("%d", &x);
   int res = 0;//res是result的缩写
   for (int i = 0; i < x; ++i) {//循环x-1次
      if (i * i % x == 1) {
          ++res;//如果符合条件,结果++
      }
   }
   printf("%d", res);//输出结果
   return 0;
}

输入:15

解析:这个程序也不是很难。输入一个数字,枚举0到x-1有没有取余这个数字等于1,有的话就输出答案。枚举可得1、4、11、14满足条件,有四个答案。具体见代码注释。

答案:4

第 20 题

阅读程序写结果:

#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;
}

解析:这个很简单,画一个图表。通过枚举可得n=5,m=6时,答案为8。

答案:8

第 21 题

阅读程序写结果:

#include <stdio.h>
int n, d[100];
bool v[100];

int main() {
   scanf("%d", &n);
   for (int i = 0; i < n; ++i) {
      scanf("%d", d + i);//d是个数组,+0就是d[0],+1就是d[1]
      v[i] = false;
   }
   int cnt = 0;
   for (int i = 0; i < n; ++i) {
      if (!v[i]) {//如果v[i]是false
         for (int j = i; !v[j]; j = d[j]) {
            v[j] = true;
         }
         ++cnt;
      }
   }
   printf("%d\n", cnt);
return 0;
}

 

解析:可以模拟一下这个题。如果输入了十个数,0到9,。0的变化就是0>-7>-8>-9,1的变化就是1>-1(1是个自环),2的变化就是2>-4>-2(2、4循环),3的变化就是3>-3(3是个自环),4对应的是2(找过了),5的变化就是5>-5(5是个自环),6的变化就是6>-9>-6(6、9循环),7、8、9都提过了。程序想找的就是有几个环。

答案:6

第 22 题
完善程序

(最大公约数之和)下列程序想要求解整数 nn 的所有约数两两之间最大公约数的和对10007求余后的值,试补全程序。(第一空2分,其余3分)

举例来说,4的所有约数是1,2,4。1和2的最大公约数为1;2和4的最大公约数为2;1和4的最大公约数为1于是答案为1+2+1=4。

要求 getDivisor 函数的复杂度为O(sqrt(n)),gcd函数的复杂度为O(log max(a,b))。

#include <iostream>
using namespace std;

const int N = 110000, P = 10007;
int n;
int a[N], len;
int ans;

void getDivisor() {//得到n的所有因数,并存入a数组
   len = 0;//len代表有几个因数
   for (int i = 1; ① <= n; ++i)
      if (n % i == 0) {
         a[++len] = i;//如果len=1,就代表a[1]=1
         if ( ② != i) a[++len] = n / i;//有一个漏洞,当找到i后,有一种情况是n/i=i
      }
   }

int gcd(int a, int b) {
   if (b == 0) {
      ③ ;
   }
   return gcd(b, ④ );//按函数描述,gcd(a,b)需变成gcd(a,a%b)
}

int main() {
   cin >> n;
   getDivisor();
   ans = 0;
   for (int i = 1; i <= len; ++i) {//循环a数组中的所有因数,所以i对应的是a[i]
      for (int j = i + 1; j <= len; ++j) {//j从i+1出发,保证了不会重复
         ans = ( ⑤ ) % P;
      }
   }
   cout << ans << endl;
   return 0;
}

答案:1.i*i

2.n/i

3.return a

4.a%b

5.ans+gcd(a[i],a[j])

第 23 题
对于一个1到n的排列P(即1到n中每一个数在P中出现了恰好一次),令q[i]为第i个位置之后第一个比 P[i] 值更大的位置,如果不存在这样的位置,则 q[i]=n+1。举例来说,如果n=5 且 P 为 1 5 4 2 3 ,则q为 2 6 6 5 6。

下列程序读入了排列 PP ,使用双向链表求解了答案。试补全程序。

答案:

答案:1.a[x]=i
2.i+1
3.R[a[i]]
4.a[i]
5.R[i]

#include <iostream>
using namespace std;

const int N = 100010;
int n;
int L[N], R[N], a[N];

int main() {
   cin >> n;
   for (int i = 1; i <= n; ++i) {
      int x;
      cin >> x;
      ① ;//a[i]=x是通过下标来找值,但我们希望通过值来找下标,就是a[x]=i
   }

   for (int i = 1; i <= n; ++i) {
      R[i] = ② ;//右边是i+1
      L[i] = i - 1;//左边是i-1
   }

   for (int i = 1; i <= n; ++i) {
      L[ ③ ] = L[a[i]];//中间是a[i],右边是R[a[i]],左边是L[a[i]]
      R[L[a[i]]] = R[ ④ ];//让L[a[i]]的左边指向R[a[i]],让R[a[i]]的右边指向L[a[i]]
   }

   for (int i = 1; i <= n; ++i) {
      cout << ⑤ << " ";
   }

   cout << endl;
   return 0;
}



这篇关于NOIP 2018 普及组初赛试题阅读程序解析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程