计算机18讲题解

小技巧

• 在网页前面加上read有奇效
  例如：

  raed:https://www.reach-top.cn.com

  这个是阅读器模式，开启以后就能获取里面原先不让复制的内容了

  A题

• 题目描述
  每个整数都应输出一个各位数字和，并独占一行。

• 解题思路
  拿之前上课的程序自然是能解决的，直接一个循环算到底
  每一位的值是n%10，要取得下一位就n/=10再算就彳亍了
  但是注意到这节课的标题是函数，那么我们就编写一个递归程序来计算每一位的和
  边界条件：n<=10
  递推式子：n %10+solve(n/10)

• 参考代码

  ll solve(ll n){
    if(n<10) return n;
    return n%10+solve(n/10);
  }
  signed main(){
    ll T;
    while(cin>>T)
  	cout<<solve(T)<<endl;
    return 0;
  }//此处#define ll long long

  B题

• 题目描述
  给定若干个正整数，请你从这些整数中找到最小值和第二小的值，计算一下第二小的数值减去最小值的结果是不是素数，如果是则输出Yes，否则输出No”o。

• 解题思路
  直接写一个循环计算最小值和次小值，然后判断差是不是素数就行了
  计算最小值和次小值的思路，如果输入值x比最小值小，那么把次小值改成原先的最小值，再把最小值修改为输入值x，如果只是比次小值小，那么把次小值改成输入值x
• 参考代码

  void isprime(int n){
    if(n==1){
      cout<<"No\"o"<<endl;
      return;
    }
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        cout<<"No\"o"<<endl;
        return;
      }
    }
    cout<<"Yes"<<endl;
  }
  signed main()
    ll minn1=1e18,minn2=1e18,x;
    while(cin>>x){
      if(x<minn1){
        minn2=minn1;
        minn1=x;
      }
      else if(x<minn2)
        minn2=x;
    }
    isprime(minn2-minn1);
    return 0;
  }

C题

• 题目描述
  哥德巴赫猜想大家都知道一点吧。我们现在不是想证明这个结论，而是想在程序语言内部能够表示的数集中，任意取出一个偶数，来寻找两个素数，使得其和等于该偶数。 做好了这件实事，就能说明这个猜想是成立的。由于可以有不同的素数对来表示同一个偶数，所以专门要求所寻找的素数对是两个值最相近的。
• 解题思路
  直接暴力求解从中间开始计算，设两个数分别是x，y，然后x—，y++，判断是否是合法的，如果合法那么输出，这样得到的第一组解必然是最小的一组解。
  判断是否是素数的代码可以用上一题的代码。
• 参考代码

  bool isprime(ll n){
    if(n==1) return false;
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0)
        return false;
    }
    return true;
  }
  signed main(){
    ll x;
    while(cin>>x&&x){
      ll a1=x/2,a2=x/2;
      while(1){
        if(isprime(a1)&&isprime(a2)){
          cout<<a1<<' '<<a2<<endl;
          break;
        }
        a1--; a2++;
      }
    }
    return 0;
  }

D题

• 题目描述
  求给定n个正整数的最大公约数
• 解题思路
  计算每个数和现在得到的最大公约数的最大公约数
  首先先默认最大公约数为第一个正数，然后计算即可。
  计算最大公约数其实有两种方式，要是你用万能头的话，可以使用自带函数直接计算。
  这里采用的是标准的辗转相除法。
• 参考代码

  ll gcd(ll n,ll m){
    if(n%m==0) return m;
    else return gcd(m,n%m);
  }
  signed main(){
    ll n,x; cin>>n;
    ll m=n,maxgcd;
    while(cin>>x&&n){
      if(x<=0) continue;
      if(n==m) maxgcd=x;
      n--;
      maxgcd=gcd(maxgcd,x);
      //maxgcd=__gcd(x,maxgcd);这个是自带的函数，也是可以的
    }
    cout<<maxgcd<<endl;
  }

E题

• 题目描述
  找比x大的第一个回文数
• 解题思路
  每次加1，直到找到回文数为止。
  判断回文数的话，直接先一位一位取出来，然后计算，一个正向遍历，一个反向遍历，结果一样就是回文。
• 参考代码

  bool hws(ll x){
    ll a[2000],id=1;
    while(x){
      a[id++]=x%10;
      x/=10;
    }
    for(int i=1;i<id;i++)
      if(a[i]!=a[id-i])
        return false;
    return true;
  }
  signed main(){
    ll x;
    while(cin>>x){
      x++;
      while(!hws(x++));
      cout<<x-1<<endl;
    }
  }

  这里因为要求要比x大，所以先x++，最后输出x-1的原因是循环里写的是x++最后会多1。

F题

• 题目描述
  如果一个数从左到右和从右到左读都一样，那么这个数就叫做“回文数”。如果一个数的十进制和二进制表示都是回文数，则把这个数叫做“双重回文数”。例如，十进制33是回文数，将其转化为二进制表示100001也是回文数，所以33是双重回文数。编写程序，查找1~1000的所有双重回文数。
• 解题思路
  和上一题一样，只不过要多出力一个二进制的而已。
• 参考代码

  bool hws(ll x){
    ll a[2000],id=1;
    ll y=x;
    while(x){
      a[id++]=x%10;
      x/=10;
    }
    for(int i=1;i<id;i++)
      if(a[i]!=a[id-i])
        return false;
    
    id=1;
    while(y){
      a[id++]=y%2;
      y/=2;
    }
    for(int i=1;i<id;i++)
      if(a[i]!=a[id-i])
        return false;
    return true;
  }
  signed main(){
    for(int i=1;i<=1000;i++)
      if(hws(i)) cout<<i<<"为双重回文数"<<endl;
  }