每日一题之屏蔽信号

问题描述

在与三体文明的对抗中，人类联邦探测到了两个重要的信号源，分别用非负整数 aa 和 bb 来表示。

为了抵御三体舰队的入侵，科学家们制定出一项关键策略——屏蔽信号，目标是要让 aa、bb 这两个信号源其中之一的数值归零。 在实施屏蔽操作时，有着一套既定规则：每次操作，科学家们需要先对比两个信号源的数值大小，然后用较大的那个数减去较小的数，得出差值之后，再把原本较大的那个数替换成这个差值。就这样反复操作，一轮一轮进行下去。

现在，请你来帮忙计算一下，按照这样的操作方式，要想实现将两个信号源之中任意一个变为零，所需要进行的最少操作次数是多少呢？

输入格式

第一行包含一个整数 tt （1≤t≤1031≤t≤103），表示测试数据的数量。

接下来的 tt 行，每行包含两个非负整数 aa 和 bb （0≤a,b≤1090≤a,b≤109），表示两个关键的信号源。

输出格式

对于每组测试数据，输出一个整数，表示将其中一个信号源变为零所需的最小操作次数，每个结果占一行。

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  int t,temp,k=1;
  cin>>t;
  int a[t][2],res[t];
  for(int i=0;i<t;i++){
    for(int j=0;j<2;j++){
      cin>>a[i][j];
    }
  }
  for(int i=0;i<t;i++){
    if(a[i][0]==0||a[i][1]==0){
      res[i]=0;
      continue;
    }
    while(a[i][0]!=a[i][1]&&a[i][0]!=0&&a[i][1]!=0){
      if(a[i][0]>a[i][1]){
        temp=a[i][0]-a[i][1];
        a[i][0]=temp;
      }else{
        temp=a[i][1]-a[i][0];
        a[i][1]=temp;
      }
      k++;      
    }
    res[i]=k;
    k=1;
  }
  for(int i=0;i<t;i++){
  	cout<<res[i]<<endl;
  } 
  return 0;
}

整道题就可以顺着题目的思路直接写出代码，但是代码十分冗长，然后我想到反正是一组一组处理数据那么可以在输入之后直接进行处理，所以不必引入储存输入数据的数组。

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    int res[t];  // 存储每组数据的结果

    for (int i = 0; i < t; i++) {
        int a, b;
        cin >> a >> b;
        int k = 0;

        // 当a和b都不为0且不相等时，继续相减
        while (a != 0 && b != 0 && a != b) {
            if (a > b) {
                a -= b;
            } else {
                b -= a;
            }
            k++;
        }

        // 如果a和b相等且不为0，则操作次数为k+1
        if (a == b && a != 0) {
            k++;
        }

        res[i] = k;
    }

    // 输出结果
    for (int i = 0; i < t; i++) {
        cout << res[i] << endl;
    }

    return 0;
}

继续优化思路，2 5最后变成1 1,3 6最后变成3 3，4 16最后变成4 4，因此可以得出规律，当每组数组最后相等时，这个数就是这两个数的最大公约数。

#include <bits/stdc++.h>
using namespace std;
void gcd(int a, int b, int& c)
{
  if(!a || !b){
  	return;
  } 
  if(a < b){
  	swap(a, b);
  } 
  c += a / b;
  return gcd(b, a % b, c);
}
int main()
{
  int t;
  cin >> t;
  while(t--)
  {
    int a, b;
    cin >> a >> b;
    int c = 0;
    gcd(a, b, c);
    cout << c << endl;
  }
}

其实用最大公约数的思路就是去找大的数里最多有几个小的数，比如2 5,5最多有2个2，那么5减去两个2变成1，然后变成2 1,2里面最多2个1，2减去2个1变成0，ending！！！